현재까지도 NP-complete는 최적의 경로를 탐색하는데 있어 합리적인 시간안에 해결하기 매우 어려우며, 파라미터의 수가 증가함에 따라 계산 복잡도의 기하급수적인 증가로 많은 시간이 요구된다. 하지만 DNA 컴퓨팅은 DNA 분자의 특징인 초 병렬성과 막대한 저장능력을 이용하여 NP-complete에 대한 새로운 해결 방법으로 부각되고 있다. 따라서 본 논문에서는 기존에 연구된 NP-complete에 DNA 컴퓨팅 방법을 도입했을 때 발생되는 문제점들을 해결하기 위해 실제 DNA의 특성을 반영할 수 있는 DNA ...
현재까지도 NP-complete는 최적의 경로를 탐색하는데 있어 합리적인 시간안에 해결하기 매우 어려우며, 파라미터의 수가 증가함에 따라 계산 복잡도의 기하급수적인 증가로 많은 시간이 요구된다. 하지만 DNA 컴퓨팅은 DNA 분자의 특징인 초 병렬성과 막대한 저장능력을 이용하여 NP-complete에 대한 새로운 해결 방법으로 부각되고 있다. 따라서 본 논문에서는 기존에 연구된 NP-complete에 DNA 컴퓨팅 방법을 도입했을 때 발생되는 문제점들을 해결하기 위해 실제 DNA의 특성을 반영할 수 있는 DNA 코딩 방법을 사용한 ACO로 문제점들을 해결하였다. ACO는 NP-complete의 문제 중 HPP, TSP, MCP에 각각 적용한 실험을 통해 문제점들을 해결함으로써, ACO의 효율성을 확인하였다. 다음은 실험에서 ACO의 향상된 표현방법으로 해결된 내용들이다. 첫째, 반복적인 합성과 분리 과정을 통해 불필요한 생물학적 실험 오류들을 미리 제거함으로써 ACO를 적용한 HPP에서의 적합한 해의 평균 탐색횟수는 50%가 향상되었고, TSP는 정점이 4개일 경우 38%, 정점이 7개인 경우에는 32%가 향상되었다. 이렇듯 NP-complete에 적용한 ACO의 전체 적합한 해의 탐색횟수의 평균은 41.7%로 향상되어 기존의 DNA 컴퓨팅보다 우수한 해를 탐색했다. 둘째, DNA의 막대한 병렬성과 상보성을 이용한 정점과 간선의 생성을 통해 그래프 문제의 표현에서 ACO를 적용한 HPP는 평균 적합도에서 90%정도 향상되었으며, TSP의 정점이 4개일 경우에는 38%, 정점이 7개인 경우는 30% 향상되었다. 그리고 MCP에서는 80%의 평균 적합도 향상을 보였다. 이렇듯 NP-complete에 적용한 ACO의 평균 적합도의 전체 평균은 75%이상의 적합한 해들을 효율적으로 탐색할 수 있었다. 셋째, 문제에 대한 염기 표현에서 3개의 염기를 하나의 아미노산으로 코드를 압축하여 표현함으로써, 해를 탐색하는데 필요한 세대수에서 기존의 DNA 컴퓨팅 보다 평균 50%의 효율을 보였다. 이처럼 ACO는 DNA 컴퓨팅의 문제점을 효율적으로 해결하면서 기존의 DNA 컴퓨팅 보다 효율적인 표현으로 빠른 결과를 얻을 수 있었다. 향후, ACO를 다른 NP-complete 문제에 적용하였을 때 우수한 결과를 얻을 수 있는지 계속적인 실험과 DNA가 갖는 특징을 보다 효과적으로 표현할 수 있는 알고리즘에 대한 연구가 필요하다.
현재까지도 NP-complete는 최적의 경로를 탐색하는데 있어 합리적인 시간안에 해결하기 매우 어려우며, 파라미터의 수가 증가함에 따라 계산 복잡도의 기하급수적인 증가로 많은 시간이 요구된다. 하지만 DNA 컴퓨팅은 DNA 분자의 특징인 초 병렬성과 막대한 저장능력을 이용하여 NP-complete에 대한 새로운 해결 방법으로 부각되고 있다. 따라서 본 논문에서는 기존에 연구된 NP-complete에 DNA 컴퓨팅 방법을 도입했을 때 발생되는 문제점들을 해결하기 위해 실제 DNA의 특성을 반영할 수 있는 DNA 코딩 방법을 사용한 ACO로 문제점들을 해결하였다. ACO는 NP-complete의 문제 중 HPP, TSP, MCP에 각각 적용한 실험을 통해 문제점들을 해결함으로써, ACO의 효율성을 확인하였다. 다음은 실험에서 ACO의 향상된 표현방법으로 해결된 내용들이다. 첫째, 반복적인 합성과 분리 과정을 통해 불필요한 생물학적 실험 오류들을 미리 제거함으로써 ACO를 적용한 HPP에서의 적합한 해의 평균 탐색횟수는 50%가 향상되었고, TSP는 정점이 4개일 경우 38%, 정점이 7개인 경우에는 32%가 향상되었다. 이렇듯 NP-complete에 적용한 ACO의 전체 적합한 해의 탐색횟수의 평균은 41.7%로 향상되어 기존의 DNA 컴퓨팅보다 우수한 해를 탐색했다. 둘째, DNA의 막대한 병렬성과 상보성을 이용한 정점과 간선의 생성을 통해 그래프 문제의 표현에서 ACO를 적용한 HPP는 평균 적합도에서 90%정도 향상되었으며, TSP의 정점이 4개일 경우에는 38%, 정점이 7개인 경우는 30% 향상되었다. 그리고 MCP에서는 80%의 평균 적합도 향상을 보였다. 이렇듯 NP-complete에 적용한 ACO의 평균 적합도의 전체 평균은 75%이상의 적합한 해들을 효율적으로 탐색할 수 있었다. 셋째, 문제에 대한 염기 표현에서 3개의 염기를 하나의 아미노산으로 코드를 압축하여 표현함으로써, 해를 탐색하는데 필요한 세대수에서 기존의 DNA 컴퓨팅 보다 평균 50%의 효율을 보였다. 이처럼 ACO는 DNA 컴퓨팅의 문제점을 효율적으로 해결하면서 기존의 DNA 컴퓨팅 보다 효율적인 표현으로 빠른 결과를 얻을 수 있었다. 향후, ACO를 다른 NP-complete 문제에 적용하였을 때 우수한 결과를 얻을 수 있는지 계속적인 실험과 DNA가 갖는 특징을 보다 효과적으로 표현할 수 있는 알고리즘에 대한 연구가 필요하다.
DNA computing is technology that applies immense parallel castle of living body molecules into information processing technology, and has used to solve NP-complete problems. However, there are problems which do not look for solutions and take much time when only DNA computing technology solves NP-co...
DNA computing is technology that applies immense parallel castle of living body molecules into information processing technology, and has used to solve NP-complete problems. However, there are problems which do not look for solutions and take much time when only DNA computing technology solves NP-complete problems. In this paper we proposed an algorithm called ACO(Algorithm for Code Optimization) that can efficiently express DNA sequence and create optimum codes through composition and separation processes as many as the numbers of reaction by DNA coding method. Also, we applied ACO to HPP and TSP, MCP of NP-complete problems. As a result, ACO could create ranks that have high fitness values in early problem expression in comparison with DNA computing, and search fast optimum results in spite of change of paths. ** A thesis submitted to the committee of Graduate School, Kong Ju National University in partial fulfillment of the requirements for the degree of Master of Art(Doctor of Philosophy) Conferred February 2003.
DNA computing is technology that applies immense parallel castle of living body molecules into information processing technology, and has used to solve NP-complete problems. However, there are problems which do not look for solutions and take much time when only DNA computing technology solves NP-complete problems. In this paper we proposed an algorithm called ACO(Algorithm for Code Optimization) that can efficiently express DNA sequence and create optimum codes through composition and separation processes as many as the numbers of reaction by DNA coding method. Also, we applied ACO to HPP and TSP, MCP of NP-complete problems. As a result, ACO could create ranks that have high fitness values in early problem expression in comparison with DNA computing, and search fast optimum results in spite of change of paths. ** A thesis submitted to the committee of Graduate School, Kong Ju National University in partial fulfillment of the requirements for the degree of Master of Art(Doctor of Philosophy) Conferred February 2003.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.