DBPIA-NURIMEDIA

Transcription

1 ε - 다중목적함수진화알고리즘을이용한 DNA 서열디자인 1217 ε - 다중목적함수진화알고리즘을이용한 DNA 서열디자인 (DNA Sequence Design using ε -Multiobjective Evolutionary Algorithm) 신수용 이인희 장병탁 (Soo-Yong Shin) (In-Hee Lee) (Byoung-Tak Zhang) 요약최근들어 DNA 컴퓨팅이활발하게연구되면서, DNA 컴퓨팅에서가장기본적이고도중요한 DNA 서열디자인문제가부각되고있다. 기존의연구에서 DNA 서열디자인문제를다중목적최적화문제로정의하고, elitist non-dominated sorting genetic algorithm(nsga-ii) 를이용하여성공적으로 DNA 서열을디자인하였다. 그런데, NSGA-II 는계산속도가느리다는단점이있어서, 이를극복하기위해본논문에서는 ε - 다중목적함수진화알고리즘 (ε -Multiobjective evolutionary algorithm, ε -MOEA) 을 DNA 서열디자인에이용하였다. 우선, 두알고리즘의성능을보다자세히비교하기위해서 DTLZ2 벤치마크문제에대해서적용한결과, 목적함수의개수가작은경우에는큰차이가없으나, 목적함수의개수가많을경우에는 ε -MOEA 가 NSGA-II 에대해서최적해를찾는정도 (convergence) 와다양한해를찾는정도 (diversity) 에있어서각각 70%, 73% 향상된성능을보여주었고, 또한최적해를찾는속도도비약적으로개선되었다. 이러한결과를바탕으로기존의 DNA 서열디자인방법론으로디자인된 DNA 서열들과 7- 순환외판원문제해결에필요한 DNA 서열을 NSGA-II 와 ε -MOEA 로재디자인하였다. 대부분의경우 ε -MOEA 가우수한결과를보였고, 특히 7- 순환외판원문제에대해서 NSGA-II 와비교하여 convergence 와 diversity 의측면에서유사한결과를 2 배이상빨리발견하였고, 동일한계산시간을이용해서는 22% 정도보다다양하게해를발견하였으며, 92% 우수한최적해를발견하는것을확인하였다. 키워드 :DNA 서열디자인, ε - 다중목적진화연산, NSGA-II, 다중목적진화연산 Abstract Recently, since DNA computing has been widely studied for various applications, DNA sequence design which is the most basic and important step for DNA computing has been highlighted. In previous works, DNA sequence design has been formulated as a multi-objective optimization task, and solved by elitist non-dominated sorting genetic algorithm (NSGA-II). However, NSGA-II needed lots of computational time. Therefore, we use an ε -multiobjective evolutionary algorithm (ε -MOEA) to overcome the drawbacks of NSGA-II in this paper. To compare the performance of two algorithms in detail, we apply both algorithms to the DTLZ2 benchmark function. ε -MOEA outperformed NSGA-II in both convergence and diversity, 70% and 73% respectively. Especially, ε -MOEA finds optimal solutions using small computational time. Based on these results, we redesign the DNA sequences generated by the previous DNA sequence design tools and the DNA sequences for the 7-travelling salesman problem (TSP). The experimental results show that ε -MOEA outperforms the most cases. Especially, for 7-TSP, ε -MOEA achieves the comparative results two times faster while finding 22% improved diversity and 92% improved convergence in final solutions using the same time. Key words :DNA sequence design, ε -MOEA, NSGA-II, MOEA 본연구는교육인적자원부 BK21-IT, 산업자원부차세대신기술개발사업의분자진화컴퓨팅 (MEC) 과제및과학기술부국가지정연구실 (NRL) 사업에의하여일부지원되었다. 또한이연구를위해장비를지원하고공간을제공한서울대학교컴퓨터연구소에도감사드린다. 학생회원 : 서울대학교컴퓨터공학부 syshin@bi.snu.ac.kr ihlee@bi.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학부 btzhang@bi.snu.ac.kr 논문접수 : 2004년 9월 16일심사완료 : 2005년 10월 14일 1. 서론최근 DNA 컴퓨팅이새로운컴퓨팅모델로부각을받으면서, 다양한 DNA 컴퓨팅연구결과들이나오고있다 [1,2]. DNA 컴퓨팅은 DNA 분자와같은생체분자를정보저장및연산의매체로사용하고, 생화학실험방법들을연산자로사용하여기존의컴퓨터로해결이불가능

2 1218 정보과학회논문지 : 소프트웨어및응용제 32 권제 12 호 ( ) 한 NP 문제를해결하거나, 생체분자를사용한다는특징을이용하여의료진단등의응용에적용되고있는새로운계산모델이다 [3]. 기존의컴퓨터가 0과 1의이진수에기반을둔것에반해서 DNA 컴퓨팅은 A(Adenine), T(Thymine), G(Guanine), C(Cytosine) 의네개의염기로정보를표현한다. 약 1 그램의 DNA는 개의 DNA 염기를가지며따라서 10억 terabits의정보저장능력을지닌다. 또한 1 mole의 DNA 수용액에는아보가드로수만큼의즉 개의분자를가지고있으며이들은용액상에서의화학반응에의해초병렬적정보처리가가능하다. DNA 컴퓨팅은이러한많은수의초미세구조의연산소자가초고집적도로모여서정보를저장하고초병렬적으로처리함으로써기존의실리콘기술로서불가능한정보처리능력을발휘할수있는잠재력을지니고있는것으로평가되고있다. 이런장점들을바탕으로다양한분야에 DNA 컴퓨팅이응용되면서연구가활발히진행되기시작하였고, 이로인해 DNA 컴퓨팅의가장기본적인단계인 DNA 서열디자인문제가부각되기시작하고있다. DNA 컴퓨팅의연산과정인 DNA 반응은생화학적반응이기때문에항상오류의가능성을내재하고있다. 따라서 DNA 서열디자인을통해서정보를효율적으로표현하면서, 연산과정에서발생할수있는오류의가능성들을최소화한 DNA 서열을만드는것이중요한이슈이다 [4]. 기존의연구를통해 DNA 서열디자인문제는다중목적최적화문제 (multi-objective optimization problem, MOP) 에속하는것으로밝혀졌고, 특히다양한목적함수를가지고있으며, 문제에따라사용되어야할목적함수가다르기때문에다수의목적함수를유연하게처리할수있는 MOEA가적용되기적합한문제라는것을발견할수있었다. 따라서 DNA 서열설계문제를 MOP로수식화하였고, elitist non-dominated sorting genetic algorithm(nsga-ii) 을이용해서성공적으로최적화된 DNA 서열을디자인할수있었다 [4]. 그러나, NSGA-II는우수한성능에도불구하고계산시간이많이걸린다는단점이있어서, 본논문에서는기존의연구결과를바탕으로보다최적화되고빠른시간에 DNA 서열을생성하기위해서 ε -multiobjective evolutionary algorithm(ε -MOEA) 를도입하였다 [5,6]. 우선, ε -MOEA의우수성을검증하기위해서대표적인벤치마크문제인 DTLZ2에대해, 기존에사용한 NSGA-II[7] 와비교분석해보았고, 기존의 DNA 서열디자인알고리즘으로설계된 DNA 서열들을재설계하여비교하여보았고, 7-순환외판원문제에대해서 DNA 서열을디자인하여성능을비교하였다. 본논문의구성은다음과같다. 2장에서는 DNA 컴퓨팅을위한 DNA 서열디자인에대해살펴보고, 3장에서 MOEA의기본적인내용과 ε -MOEA에대해서설명을한후, ε -MOEA를 DNA 서열디자인문제에특화시킨내용에대해소개한다. 4장에서는실험결과를보여주며, 마지막으로 5장에서본논문의결론을내리고자한다. 2. DNA 컴퓨팅을위한 DNA 서열디자인 DNA 컴퓨팅에서서열디자인의역할은크게 2가지로구분할수있다. 첫번째는주어진문제의정보를 DNA 서열로표현하는것이고, 두번째는오류의가능성이가장적은서열을생성하는것이다. 이두가지의역할이그림 1에설명되어있다. 그림 1(a) 는그래프문제에서 3개의정점을서로다른 DNA 서열로나타낸예제를보여주고있는데, 이경우주어진정보는정점이라고할수있고, 이정점을서로다른 DNA 서열로표시하는것이서열디자인의역할중하나이다. 두번째역할은그림 1(b) 와 (c) 에설명되어있다. 그림 1(b) 에설명된것처럼각서열들이서로 Watson-Crick 상보결합을형성하지않도록하여야하는데, 만약그림 1(c) 처럼잘설계되지않은 DNA 서열을사용할경우서로다른정보를표현하여야할 DNA 서열들이상보결합을형성하여의도하지않은결과를생성해내는문제점이있다. 따라서 DNA 컴퓨팅에서는이러한연산과정상의오류를최소화하여주어진문제의해답을효율적으로발견할수있도록 DNA 서열을설계하는것이중요한문제이다 [4,8]. 일반적으로첫번째역할인주어진정보그림 1 (a) 그래프문제에서정점을 DNA 서열로표시한예. DNA 서열이가지고있는방향성을표시하기위해 과 을나타내었다. (b) 정점 1 과정점 2의 DNA 서열의 Watson-Crick 상보결합여부를보여주는예. 상보결합이형성되지않는것을확인할수있다. (c) 임의의다른 DNA 서열 -CCTATCCT- 과정점 1의 DNA 서열을비교한예. 네모칸으로구분된영역에서상보결합이형성되는것을확인할수있고, 이경우정확한연산이수행되지않는다.

3 ε - 다중목적함수진화알고리즘을이용한 DNA 서열디자인 1219 를표현하는것은오류의가능성이배재된 DNA 서열들을다수생성한후, 각서열에정보를 1:1 매핑하는것으로가능하기때문에, 두번째역할인오류의가능성을최소화시키는 DNA 서열을만드는것이가장어렵고도중요한문제라고할수있다. 따라서, 본논문에서는오류의가능성을최소화시키는 DNA 서열을만드는것에초점을맞추었다. 오류의가능성이가장적은서열이라는것은 DNA 서열들이서로독립적이되도록, 즉자기자신및다른 DNA 서열들과상보결합을형성하지않으며, 2차구조도만들어내지않도록디자인된서열을의미한다 [8]. 이문제를해결하기위해서많은연구자들이다양한방법으로연구를수행했는데 [4,8], 우선가장간단한방법으로 exhaustive 탐색이사용되었고, 다양한 heuristic과알고리즘이사용되었다. 사용된 heuristic으로는미리정의된 template를사용한방법, 그래프탐색알고리즘을이용해 DNA 서열을디자인한방법등이있고, 그외에도 simulated annealing, dynamic programming 기법, 진화연산등다양한방법이적용되었다 ( 보다자세한내용은 [4,8] 의내용과참고문헌참조 ). 2.1 DNA 서열디자인기준서로독립적인 DNA 서열을생성하기위해서다양한기준들이사용될수있는데, 본논문에서는 H-measure, similarity, continuity, hairpin, melting temperature (Tm), GC 함량의 6가지기준을사용하였다. 그런데, 마지막두가지기준은최적화대상인목적함수 (objective) 가아니라제약조건 (constraint) 로해석하는것이훨씬문제를효율적으로해결한다는사실을발견하여최종적으로표 1에있는것처럼 4가지목적함수 ( 와 2가지제약조건 ( 을 DNA 서열생성기준으로결정하였다 [4]. H-measure는다른 DNA 서열들과의 Watson-Crick 상보성을고려하여결합여부를판단하는기준이고, similarity는다른서열과의유사도를측정하는기준이다. Continuity는특정염기가연속적으로나타나는정도를판단하며, hairpin은서열이스스로휘어상보결합을통해 hairpin 구조를형성하는지를계산한 다. 마지막으로 Tm은 DNA 가닥의녹는점 ( 상보결합된서열의 50% 가분리되는온도 ) 이고, GC 함량은 DNA 서열에서 G(Guanine) 와 C(Cytosine) 가차지하는비율이다. 보다자세한설명은 [4] 에기술되어있다. 이러한기준들을사용하여독립적인 DNA 서열을생성해내는것은 NP 문제중하나로증명되어있을만큼어려운문제이다 [8]. DNA 서열디자인문제를소개한기준들을이용하여다중목적최적화문제형태로표현하면아래와같다. 입력 DNA 서열집합에대해서 subject to Tm Low G Tm (x) Tm High, GC Low G GC (x) GC High 여기서, 와 는 Tm의최소, 최대제약범 위이고, 와 는 GC 함량의최소, 최대제약 범위이다. 3. DNA 서열디자인을위한 ε -Multiobjective Evolutionary Algorithm ε - multiobjective evolutionary algorithm(ε -MOEA) 에대해서자세히설명하기이전에 multi-objective evolutionary algorithm(moea) 에대해서우선간단히설명을하고, ε -MOEA에대해서기술하고자한다. 그이후 ε -MOEA를주어진문제인 DNA 서열디자인에적용하기위해수정한내용에대해서설명한다. 3.1 다중목적진화연산다중목적함수진화연산 (multiobjective evolutionary algorithm, MOEA) 은진화연산의유연성과다수의목적함수를처리할수있는능력, 복잡한탐색공간을비교적쉽게탐색할수있는능력에기반을두어, 다수의목적함수가서로 trade-off 관계를가지는다중목적최적화문제 (multiobjective optimization problem, MOP) 를풀기위한새로운대안으로부각되고있다. MOEA 는기존의방법과는달리목적함수를통합하지않고, 각 표 1 DNA 서열디자인기준 Objectives H-measure : 두서열간의의도하지않은 hybridization 정도 Similarity: 두서열간의유사도 Continuity: 특정염기가연속적으로나타나는정도 Hairpin: 2차구조를생성할가능성 Constraints Melting temperature: 선택된서열의녹는점 GC content: 선택된서열에서의 G와 C의함량

4 1220 정보과학회논문지 : 소프트웨어및응용제 32 권제 12 호 ( ) 각의해들사이의 dominance 관계를이용하여후보해들을비교하여진화시키는데, 해들사이의 dominance 관계를알아볼때해들이가지는목적함수값들을별도의변환없이바로이용하기때문에, 가중치합을사용할때와같이목적함수공간을왜곡해서특정한해를찾을수없게된다거나하는단점이없고, 실제적용에필요한파라미터수도줄일수있다는장점이있다 [9]. 두해사이의 dominance 관계는다음과같이정의된다 [9]. 개의목적함수 을최대화하는 MOP에서, 두해와사이에다음과같은식이만족될경우, 는를 dominate한다. 즉, 두해, 중에서가를 dominate하기위해서는가보다모든목적함수에대해서나쁘지않고, 최소한 1개이상의목적함수에대해서더좋은값을가져야한다. 따라서가를 dominate할경우, 가보다더좋은해라는의미가된다 ( 그림 2(a) 참고 ). 만약두해사이에 dominance 관계가성립하지않는다면, 두해사이의우열이정의되지않으므로두해는동등하게취급하게되고 non-dominated 해들이라고한다. 또한, 어떤해가주어진 population 내의해들뿐만아니라해공간내의가능한모든해에대해서 dominate되지않을경우, 이러한해들을 Pareto-최적해 라고정의한다 [9]. 그런데, MOP에서목적함수들사이에는 trade-off 관계가존재하므로모든목적함수를동시에최적화시키는 그림 2 과 는모두최대화함수이다. (a) dominance 관계. 과 를볼때, 에대해서는같은값을가지지만, 에대해서 이 보다좋기때문에 은 를 dominate한다. 그러나 과 에서는서로 dominate되는관계를결정할수없다. 그리고회색영역은 A에의해 dominate되는영역을의미한다. (b) ε -dominance. 회색으로된영역은 A에의해 ε -dominate되는영역을의미한다. (a) 와비교해보면, 과 에대해서 ε만큼 dominate되는영역이커진것을알수있다. 하나의 Pareto-최적해가존재하는것은불가능하다. 그대신서로 non-dominated되면서해공간의모든다른해들을 dominate하는 Pareto-최적해집합이존재한다. 그러므로 MOEA의실행결과는대개이러한 Pareto-최적해의집합에가까워지도록진화시킨 population 내에서의 non-dominated 해집합이되며, MOEA의목표는 Pareto-최적해집합에최대한근접하면서도 (convergence) 다양한해를포함한 (diversity) non-dominated 해집합을찾는것이다. 3.2 ε - 다중목적진화연산앞에서설명한것처럼 MOEA는 convergence와 diversity를통해최대한다양한 Pareto-최적해집합을찾고자노력을하지만, convergence와 diversity를동시에만족시키는알고리즘을만들기가힘들다는문제점이있어주로어느한쪽에특화된알고리즘이개발되어왔다 [9]. 이러한한계를극복하기위해최근 ε -MOEA가제안되었는데, ε -MOEA는고정된크기의 non- dominated 해들을보관하고있으면서 ε -dominance의개념을이용해진화를시켜나가는새로운 MOEA 기법으로 steady-state GA에기반을두어 convergence와 diversity 양쪽을모두만족시켜주는새로운알고리즘이다 [4,5]. ε -MOEA를설명하기전에가장중요한 ε -dominance의개념부터설명을하고자한다. ε -dominance 관계는비슷한해들을묶기위해도입된개념으로하나의해가다른해를 ε -dominate하기위해서는모든목적함수에대해 ε이상크거나같아야한다 ( 그림 2(b) 참고 ). 즉, 개의목적함수를최대화시키는경우, 가를 ε -dominate하기위해서는다음과같은관계식을만족시켜야한다. ε -MOEA는 ε -dominance 관계를이용하기때문에전체해공간을 ε의크기를가지는격자공간 (grid) 으로나누어탐색하게되는데, 이러한탐색방식으로인하여 diversity와 convergence의측면에서성능을동시에향상시킬수있게되었다. 우선, 해를탐색할때격자로나누어진탐색공간에서하나의격자안에서는하나의대표해만을보존하기때문에보존된해들사이의최소거리가항상유지되어 diversity가보장되게된다. 또한전체알고리즘을통하여격자단위의탐색을수행함과동시에하나의격자내부에서도더좋은대표해만을보존하는방식의세밀한탐색도이루어지기때문에 convergence 측면에서도우수한성능을보인다. 또한 population을 2개로구분하여 archive라는 elite 집단을별도로유지하는데, 이를통하여탐색도중생성된해들중에서의 non-dominated 해집합을유지할수있으므로,

5 ε - 다중목적함수진화알고리즘을이용한 DNA 서열디자인 1221 단순히한세대의 population 내에서의 non-dominated 해집합만을유지하는것보다더나은 convergence 성능을보일수있다. 그림 3에 ε -MOEA의흐름이 pseudo 코드형태로설명되어있다. 먼저일반 population에서 domination 관계를사용한토너먼트를이용하여하나의부모를선택하고, archive에서임의로또하나의부모를선택한다음, 교차및돌연변이연산을통하여새로운해를생성해낸다. 그후, archive 내의해중에서새로운해에의해 ε -dominate되는것이있거나, archive의어떤해도새로운해를 ε -dominate하지못하면새로운해에의해 ε -dominate되는해들을모두 archive에서제거하고, 새로운해를넣는다. 또한, population의해중에서새로운해에의해 dominate되는해가있으면, 이중에서하나를새로운해로바꾸고다음세대로넘어가게된다 [5]. 3.3 DNA 서열디자인을위한알고리즘수정앞에서설명한것처럼 ε -MOEA는기존의다른 1. 초기해를무작위로생성한후, 함수값을계산. 2. domination 관계에따라 sorting 하고다른 front 를모두 dominate 하는 front 를 archive 로삼는다. 3. 현재 population 과 archive 에서각각부모를선택하여자손 1 개를생성 3-1. population 에서 2 개의개체를선택 에서선택한개체사이에 domination 관계가성립하면 dominate 하는개체를선택, 성립하지않으면임의로하나를선택 3-3. archive 에서임의로하나를선택 와 3-3 에서선택된부모로부터유전연산자에따라새로운자손 1 개를생성한후함수값계산 4. archive 의각개체들과새로운자손을비교하여 archive 를갱신 새로운자손이 ε -dominate 하는 archive 개체가있으면, 그개체를제거하고, 새로운자손을 archive 에추가 4-2. 같은격자공간에속하는 archive 개체가있으면, 둘중에 dominate 하는쪽만 archive 에남김 4-3. 위의두가지경우에해당하지않고, 새로운자손을 dominate 하는 archive 개체도없다면, 새로운자손을 archive 에추가 5. population 의각개체들과새로운자손을비교하여 population 갱신 5-1. 새로운자손이 dominate 하는개체가있으면, 그개체를대신하여새로운자손을 population 에추가후 6 으로진행 5-2. 새로운자손을 dominate 하는 population 이있으면, 새로운자손을버림 5-3. 위의두가지경우에해당하지않으면, population 개체중에서임의로선택된개체대신에새로운자손을 population 에추가 6. 종료조건검사후만족하지않으면 3 으로되돌아감. 그림 3 ε -MOEA 의 pseudo 코드 MOEA에비해우수한특성을가지고있었고, ε - dominance 성질을이용하여계산속도가빠르다는장점이있다 [4,5]. 따라서기존에사용한 NSGA-II의느린계산시간을극복하고부가적으로 convergence와 diversity에서우수한해를찾을수있을것으로예상되어 ε -MOEA를 DNA 서열디자인에적용하였다. ε - MOEA를 DNA 서열디자인문제에이용하기위해몇가지수정을하였는데, 우선, DNA 서열을나타내는개체의표현을위해계층구조를사용하여 individual level과 sequence level의 2단계를사용하였다. Sequence level은각 DNA 서열을나타내고, individual level은 DNA 서열들의집합을의미한다. 따라서교차연산자와돌연변이연산자는 2단계를거쳐서진행이된다. 자세한과정은그림 4에설명되어있다. 또한, 선택연산자도일반적인방법이아닌 constrained tournament 선택연산자를사용하였다. 2.1절에서설명한바와같이 DNA 서열디자인문제를제약조건이있는다중목적최적화문제로정의하였기때문에, 제약조건을고려하기위해서선택연산자를수정하였다. Constrained tournament 선택연산자의과정은다음과같다. 그림 4 2단계교차연산자의예. 돌연변이연산자도동일한과정을거친다. (a) 교차연산자적용과정. (b) individual level crossover. (c) sequence level crossover Infeasible-feasible : feasible한개체가선택 Infeasible-infeasible : 페널티가적은개체가선택 Feasible-feasible : 하나의개체가다른개체를 dominate하면 dominate하는개체가선택되고, 그렇지않으면, 두개의개체중에서하나를임의로선택

6 1222 정보과학회논문지 : 소프트웨어및응용제 32 권제 12 호 ( ) 그리고, 토너먼트의사이즈는 2로하였고, 각제약조건페널티의합을개체의페널티로사용하였다. 4. 실험및결과 4.1 DTLZ2 함수에대한성능비교 ε -MOEA의우수성을검증하기위해서기존에사용하였던 NSGA-II와비교분석해보았다. DNA 서열디자인문제에대해서직접적으로비교하기이전에두알고리즘간의우열을보다명확히확인하기위해서널리사용되고있는 benchmark 문제인 DTLZ2[10] 에적용하여보았다. 지금까지 NSGA-II와 ε -MOEA를직접적으로비교분석하여그성능을검증한논문이발표된적이없기때문에두알고리즘의우열비교가필요하다고생각되어실험해보았다. DTLZ2 목적함수의개수를 3, 6, 12개로변화시켜문제복잡도를증가시키면서실험하였다. DTLZ2는목적함수의개수를변화시켜가면서실험을하기가쉽고, 다른 MOEA 비교실험논문에서도많이사용된 test 함수이기때문에본논문에서의비교분석에사용하였다. 실험에사용한 DTLZ2 함수는다음과같다. Minimize Minimize Minimize Minimize Minimize..., for,,, for 여기서, 위의식을보면, 임 을할수있다. 교차연산자와돌연변이연산자는실수함수문제에적합하게사용하기위해서 simulated binary crossover [11], polynomial mutation[12] 을사용하였다. Simulated binary crossover는실수벡터에대해서도이진 문자열 (binary string) 에대한 1점교차연산과같은효과를얻을수있도록고안된교차연산자이다 [11]. 또한, polynomial mutation은이연산으로변화되는정도의확률이 polynomial 분포를따르도록고안된돌연변이연산자로서부모와가까운자손일수록생성될확률이높다 [12]. 이두연산자에의한변화정도는각각의변수를통하여조절할수있다. ε -MOEA와 NSGA-II 모두 population의크기는 100이며, function evaluation의횟수를맞추기위해서 NSGA-II인경우 1,000 세대를사용하였으며, ε - MOEA는 100,000 세대동안진화시켰다. NSGA-II에서 convergence와 diversity를조절하는 controlled elitism의파라미터로 0에서 1사이의값을가지는 reduction rate가있는데, 이값이작을수록 elite를더중시하여선택하게된다. Reduction rate 값으로양극단값인 0, 1은제외하고 0.1과 0.9를최소 / 최대값으로사용하였고, 그중간값으로 Deb 논문에서추천했던 0.6으로결정하였다 [9]. ε -MOEA의경우도 ε값을 0.1, 0.5, 0.9의 3가지로변화시켜가며다양한조건에대해분석했는데, archive의크기를적당히유지할수있도록 0.1과 0.9를사용하였고, 중간값으로 0.5를사용하였다. 3장에서설명한것과같이기존의 MOEA와 ε -MOEA의가장큰차이점은 ε -MOEA는탐색공간을 ε크기의격자로구분한다는것이다. 따라서 ε의크기에따라알고리즘의성능에차이가나게되는데, 이영향을보다확실히분석하기위해서 NSGA-II의 reduction rate 변화에따른결과값과비교해보았다. NSGA-II의결과는 reduction rate에따라 front의크기와개수가결정되기때문에공정한비교가될것으로생각된다. 일반적으로사용되는파라미터값들에따라교차연산비율은 0.9이고, 돌연변이연산비율은 0.01로결정하였다. 이연산자들도각각하나씩의파라미터를포함하고있는데, 파라미터들의값도변화시켜가면서다양한경우에대해서결과를비교하였다. 교차연산자는 의값들을사용하였고, 돌연변이연산자는 의값들을이용하였다 [11,12]. 실험결과의 convergence와 diversity 정도를알아보기위해, 각각 generational distance(gd)[13] 와 maximum spread[14] 을사용하여비교하였다. Generational distance는알고리즘에서찾아낸 non-dominated 해집합 Q와실제 Pareto-최적해집합 사이의평균거리를이용하여 Q가 converge한정도를측정하는방법으 로, 로정의된다. 여기서 는 Q 의 i 번

7 ε - 다중목적함수진화알고리즘을이용한 DNA 서열디자인 1223 째해에서 의각해까지의탐색공간상에서의유클리드거리중제일작은값을의미한다. 따라서 generational distance는값이작을수록실제 Pareto-최적해집합에가깝게발견하였다는것을나타낸다. 그리고 maximum spread는알고리즘에서찾아낸 nondominated 해집합 Q를둘러쌀수있는가장작은 hyper box의대각선값을이용하여 Q의분포정도를 측정하는방법으로 로정의되고, 여기서 와 는각각 Q 에서 m번째목적함수의최대값과최소값을의미한다. 따라서 maximum spread는반대로값이클수록다양한해집합을발견했다고할수있다. 자세히수치적으로비교한결과가표 2에설명되어있다. 우선, maximum spread 값이사용된문제의목적함수의개수나목적함수의값의범위에따라달라지기때문에, 각각의경우에대한 spread의이론적인최대값으로나누어 (spread/ideal 값 ) 0과 1사이로표준화하였다. 따라서표 2에서 spread/ideal 값이 1에가까울수록이상적인값에가까운것이라고할수있다. 표 2에서볼때 NSGA-II는목적함수의개수가작을때는 1에가까운값을보이나목적함수의개수가많아지면 diversity가좋지않은것을알수있다. 그러나 ε - MOEA는목적함수의개수가많아지더라도 1에가까운값을유지하여전체적인해답의분포를일정하게유지하는것을발견할수있다. 보다정확한비교를위해서, NSGA-II와 ε -MOEA의 spread/ideal 값을각각 A, B 라고할때, 의값을계산하여 NSGA-II 보다 ε -MOEA이얼마나큰성능향상을보이는지보였다. 표 2에설명된것처럼얻어진최적해의분포를보면 ε -MOEA의결과가세경우에대해평균적으로 73% 정도우수한것을알수있다. 또한 Pareto-최적해집합에대한 converge 정도를 GD값으로비교한결과도표 2에설명되어있다. 보다정확한비교를위해서 NSGA-II에서의 GD값과 ε - MOEA에서의 GD값의차이를 NSGA-II에서의 GD값으로나누어 NSGA-II에서보다 ε -MOEA에서얼마만큼의성능향상이있는지를보였다. 역시문제가쉬운경 우에는 NSGA-II의결과가좋으나, 문제가조금만복잡해지더라도 ε -MOEA의결과가우수한것을재확인할수있다. 목적함수가 3개인경우 NSGA-II가 2배정도좋은성능을보였으나, 소수점이하넷째자리값비교이기때문에실제로큰차이를보이지는않았다. 목적함수가 6개, 12개인경우만볼때 ε -MOEA는각각 95% 와 83% 의성능향상을보였다, 목적함수개수의영향을보다명확히확인하기위해목적함수의개수를 18개로확장시켜본결과, ε -MOEA와 NSGA-II의성능차이는 33% 로줄어들었다. Purshouse와 Fleming[15] 에의하면목적함수의개수가증가함에따라현재의 population 내에서 dominate되지않는해의비율이급격하게증가하게되며, 또한 dominance resistance라불리는교차나돌연변이연산에의해부모를 dominate하는해를찾아내는일이점점어려워지는현상이발생하게된다고한다. 이러한문제점들로인하여 ε -MOEA의수렴정도가느려져 NSGA-II와의성능차이가줄어든것으로생각된다. 그러나 NSGA-II가목적함수 6개정도에서수렴정도가느려진것에반해서 ε -MOEA는보다많은수의목적함수에서도 NSGA-II처럼급격히수렴속도가느려지지는않았으므로 ε -MOEA가 NSGA-II보다확장성 (scalability) 이좋다고할수있겠다. 마지막으로 NSGA-II와 ε -MOEA의수렴속도를확인하기위해서두경우모두파라미터값들중에서 converge 정도가제일좋은경우를선택하여 function evaluation 횟수에따른 generational distance 값을그래프로그려보았다. 그림 5와 6이그결과를보여주고있는데, 목적함수의개수가적을때는 NSGA-II의수렴속도도 ε -MOEA와비슷하나 ( 그림 5), 목적함수의개수가늘어나자 ( 그림 6) ε -MOEA의수렴속도가월등히빠른것을알수있다. 4.2 ε - MOEA 를이용한 DNA 서열디자인 DTLZ2 함수에대해서비교해본결과, ε -MOEA가예상한대로 convergence와 diversity는물론수렴속도까지빠르다는것을확인할수있었고, ε -MOEA를주목적인 DNA 서열디자인문제에적용해보았다. 기존의연구에서 NSGA-II와기존여러 DNA 서열디자인에사용된방법론 ( 유전자알고리즘, simulated annealing 등 ) 을비교하여 NSGA-II가기존여러방법 표 2 DTLZ2 함수에대한 NSGA-II 와 ε -MOEA 의결과비교. 각각 5 번씩의실험을통해얻어진결과값들이다. DTLZ2 GD NSGA-II ε -MOEA Compare Maximum Spread Spread /ideal GD Maximum Spread Spread /ideal GD Spread /ideal 3 OBJ OBJ OBJ

8 1224 정보과학회논문지 : 소프트웨어및응용제 32 권제 12 호 ( ) 그림 5 목적함수개수가 3 개인경우의 function evaluation 횟수비교 그림 6 목적함수가 12 개인경우 들보다모두우수한결과를보여주는것을확인하였다 [4]. 본논문에서는그러한연구결과를바탕으로하여 NSGA-II와 ε -MOEA의결과를비교하여보았는데, [4] 의결과중에서일반적인유전자알고리즘을사용하여생성된 DNA 서열집합 [16] 과 simulated annealing 을이용하여생성된 DNA 서열집합 [18], 그리고순환외판원문제를해결하기위해디자인된 DNA 서열 [19] 을대상으로비교하였다. NSGA-II와 ε -MOEA에사용된파라미터값들은다음과같다. H-measure와 similarity의하한값은 6 base와 17% 로하였고, continuity 는 2를사용하였으며, hairpin은 6개의 base가각각스템과루프에필요하다고가정하였다. NSGA-II의 reduction rate는 0.65를사용하였으며, ε -MOEA의 ε 값은 1을사용하였다. [16] 의서열집합을위해서는개체군 크기는 3000, 최대세대수는 200으로하였고, [18] 의경우 5000과 300을사용하였으며, 교차연산확률은 0.9, 돌연변이연산확률은 0.01로결정하였다. [16] 에서 Deaton 등이다중목적진화연산이아닌일반적인유전자알고리즘 (simple GA) 를사용하여 7개의길이가 20인 DNA 서열을생성하였고, [4] 에서 NSGA-II 가보다우수한 DNA 서열을생성하는것을보여주었다. 그결과를기반으로 ε -MOEA와비교한실험결과가표 3과 4에나타나있다. 표 3에는생성된 DNA 서열의예가제시되어있고, 표 4에자세히수치적으로비교한결과가나타나있다. 표 4, 6, 8은모두 NSGA-II 와 ε -MOEA 모두 5번씩실행을하여총 10개의 nondominated 집합을모은후이중에서다시 nondominated 해집합을찾아서이들을가상의 Pareto-최 표 3 [16] 의 DNA 서열생성결과. Tm은 nearest neighbor 모델을사용해 oligomer 10nM, Na + 농도 1M에서계 산하였다. NSGA-II Continuity Hairpin H-measure Similarity Tm GC% CTCTTCATCCACCTCTTCTC CTCTCATCTCTCCGTTCTTC TATCCTGTGGTGTCCTTCCT ATTCTGTTCCGTTGCGTGTC TCTCTTACGTTGGTTGGCTG GTATTCCAAGCGTCCGTGTT AAACCTCCACCAACACACCA ε - MOEA AGAAGAAGACGAGGAGAGGA CGGCACCATAGGAACAAGAA AAGCGAATCGGAGACAACAC AGAGGTAGGTAGAGGTTGTG GGCCGGAACCTAACATAACT GGAAGCGTGAGAAGAGAAGA TTATTGATGCGGCGTATGGC

9 ε - 다중목적함수진화알고리즘을이용한 DNA 서열디자인 1225 표 4 [16] 의서열에대한 NSGA-II 와 ε -MOEA 의성능비교 Convergence (generational distance) Diversity (maximum spread) NSGA-II ε -MOEA NSGA-II ε -MOEA 평균 표 5 [18] 의 DNA 서열에대한비교결과. Tm은표 3과같이 nearest neighbor 모델을사용해 oligomer 10nM, Na + 농도 1M에서계산하였다. NSGA-II Continuity Hairpin H-measure Similarity Tm GC% GTGACTTGAGGTAGGTAGGA ATCATACTCCGGAGACTACC CACGTCCTACTACCTTCAAC ACACGCGTGCATATAGGCAA AAGTCTGCACGGATTCCTGA AGGCCGAAGTTGACGTAAGA CGACACTTGTAGCACACCTT TGGCGCTCTACCGTTGAATT CTAGAAGGATAGGCGATACG CTTGGTGCGTTCTGTGTACA TGCCAACGGTCTCAACATGA TTATCTCCATAGCTCCAGGC TGAACGAGCATCACCAACTC CTAGATTAGCGGCCATAACC ε - MOEA CAGGCATCGATTACAGAGTC ATGCGGCGCTCTGAATATGT ATCCGAGTCGTTCATACTGC GCGCAAGTACCACCAACAAT AACAACGATCGCCTTAACGC GTTAGCGCTTCTTGTGTCGT GAGGAACTTACCGCATTGTG AAGGCACATCACAAGGAACC GCTATGGACATAGTCGAACG AGCACAACGCTAATAGGAGG GGTTCCACACGAGCATATTG GTGGAACTAGCGACCAAGAT CTGAATTGGCAACTGCTTGC AAGCCACGCGTAACTCCATA 표 6 [18] 의서열에대한 NSGA-II와 ε -MOEA의성능비교 Convergence Diversity NSGA-II ε -MOEA NSGA-II ε -MOEA 평균 적해집합이라고생각하고 convergence를측정한결과이다. DNA 서열디자인문제에서는해공간이방대하여실제 Pareto-최적해집합을모르기때문에위와같은가정을하였다. 표 4에서볼때 convergence의측면은 ε -MOEA가훨씬좋지만, diversity 측면에서는 ε - MOEA가조금좋지않은것을발견할수있다. 이는 NSGA-II에서생성된 DNA 서열이너무하나의목적함수 ( 주로 h-measure) 에특화되어있어서 ε -MOEA가 최종적으로발견한해집합의 diversity가계산기준인 maximum spread의특성상 NSGA-II이발견한해집합보다나쁜것처럼보이는것을알수있다. 본논문에기술하지는않았지만 DTLZ2의경우에서도유사한경우가발견되어분석을해본결과, 이는 maximum spread 기준이가지고있는한계점인것으로판단되었고, 실제로는 ε -MOEA가훨씬좋은 diversity를보이는것을그래프로확인할수있었다 [17]. 역시이경우

10 1226 정보과학회논문지 : 소프트웨어및응용제 32 권제 12 호 ( ) 표 7 7-TSP를위한 DNA 서열생성결과. Tm은 nearest neighbor 모델을사용해 oligomer 10nM, Na+ 농도 1M에서계산 NSGA-II Continuity Hairpin H-measure Similarity Tm GC% AATAGGAGCAGGAGACAACG CTCTCATCTCTCCGTTCTTC TATCCTGTGGTGTCCTTCCT ATTCTGTTCCGTTGCGTGTC TCTCTTACGTTGGTTGGCTG TAGTTCCAAGCGTCCGTGTT TATCCACACCAACACACCAC ε - MOEA AGCAACAAGAATGCGGCAAG TACATGACCAAGGACGCCAA GTGGAAGCTTGTAAGGCGTT GAGAGAGAACGGAAGAACGA AATCACTGTTGGATCGGACG CTCCTTGTCATCATGCTCTG ACTAGAGTAGGCCGGAGATA 표 8 7-TSP에서 NSGA-II와 ε -MOEA의성능비교 Convergence Diversity NSGA-II ε -MOEA NSGA-II ε -MOEA 평균 에도표 3을볼때, 선택된최종 DNA 서열집합을볼때는 h-measure도우수하며다른나머지목적함수들에대해서도좋은결과를보이는것을알수있었다. 그리고, 계산시간을비교하기위해서그림 7에 function evaluation 횟수에따른 convergence 정도를그려보았다. DTLZ2의함수때와마찬가지로 ε -MOEA가 NSGA-II보다훨씬빨리좋은결과를보여주며지속적으로점점좋은결과를찾아내는것을재확인할수있었다. 표 5와표 6에는 [18] 의 DNA 서열에대한비교분석그림 7 [16] 의서열에서 function evaluation 횟수에따른수렴정도비교 결과가설명되어있다. Tanaka 등은 simulated annealing을이용하여 14개의길이 20인 DNA 서열을디자인하였다 [18]. 역시표 5에최종 DNA 서열이제시되어있고, 표 6에비교결과가나타나있다. [18] 의 DNA 서열을재디자인하는경우에도 Deaton 등의경우와유사하게 convergence는좋으나 diversity는조금떨어지는현상을재확인할수있었다. 역시그림으로보여주지는않았으나수렴속도도역시 ε -MOEA가빠른것을볼수있었다. 그리고, 마지막으로실제적인문제해결에사용될수있다는것을보이기위해서 [19] 에서해결한순환외판원문제 (TSP) 를위해설계된 DNA 서열을 ε -MOEA 를이용하여재설계해보았다. [19] 에서는단순한유전자알고리즘을사용하여서열을생성했었는데, 표 7에새로이생성한 DNA 서열이소개되어있다. 그림 8에 7-순환외판원문제를위한 DNA 서열을생성하는데필요한 function evaluation 횟수를그래프로표시하여보았는데, 그림 8에서알수있는것처럼 ε - MOEA가절반의시간만을사용하고도수렴하는것을알수있고, 계속세대가진행될수록더욱최적해에가까운값들을계속찾아나가는것을확인할수있다. 알고리즘속도뿐만아니라해의품질과다양한해를찾는정도도 ε -MOEA가우수한것을확인할수있었는데, 표 8에설명되어있다. Convergence에서는 ε -MOEA 가훨씬좋은결과를보여주고, diversity에서도 ε -

11 ε - 다중목적함수진화알고리즘을이용한 DNA 서열디자인 1227 그림 8 7-순환외판원문제 DNA 서열생성을위한 NSGA-II와 ε -MOEA의 function evaluation 횟수비교 MOEA가 NSGA-II보다우수한결과를보여주는것을확인할수있다. 7-순환외판원문제서열디자인에대해서표 2를분석한방법과동일하게측정해본결과, convergence 에서 ε -MOEA 는 NSGA-II 보다 0.921, 즉약 92.1 % 의성능향상을보였고, diversity에 서는 0.22, 즉 22% 의정도의성능향 상을보이는것을확인할수있었다. 5. 결론및토의 본논문에서는기존에 DNA 서열디자인에사용한 NSGA-II의단점을해결하기위해서 ε -MOEA를이용해 DNA 서열을디자인해보았다. ε -MOEA의우수성을보다자세히 NSGA-II와비교하기위해서우선 DTLZ2 벤치마크문제에적용하여보았다. 목적함수의개수가작은경우에는큰차이가없었으나, 목적함수의개수가많을경우 (6개이상 ) ε -MOEA가 NSGA-II에대해서 convergence와 diversity에대해서각각 70%, 73% 향상된성능을보여주었고, 계산시간도목적함수의개수가많을수록비약적으로단축시키는것을확인할수있었다, 즉, DNA 서열디자인문제에대해서 ε - MOEA는기존에사용한 NSGA-II의문제점인느린계산시간을극복할수있을뿐아니라, convergence와 diversity에서도성능향상을보여줄수있는것이확인되어, ε -MOEA를이용하여 DNA 서열을디자인하여보았다. 기존의연구에서 NSGA-II가다른여러가지 DNA 서열디자인방법론들 ( 단순한유전자알고리즘, simulated annealing) 보다우수한것을확인하였는데, ε -MOEA를사용한결과 NSGA-II를능가하는것을알수있었고, 특히실제 DNA 컴퓨팅으로해결한 7-순환외판원문제에사용한 DNA 서열에대해서 NSGA-II보다 convergence와 diversity 측면에서유사한결과를 2 배이상빨리발견하였고, 동일한계산시간을이용해서는 22% 정도보다다양하게해를발견하였으며, 92% 우수한최적해를발견하는것을확인하였다. 특히 DNA 서열디자인문제의경우디자인해야하는서열의종류가많거나, 서열이길어질경우 function evaluation 시간이커지므로적은세대를이용해수렴할수있다면그만큼계산시간을절약할수있는장점이있다. 또한같은 function evaluation 횟수를사용하더라도 ε - MOEA의경우 NSGA-II에서보다알고리즘내부에서의 dominance 관계계산횟수가적기때문에 population 의크기가큰경우에는실제계산시간에서큰이득을볼수있다. 이러한결과를바탕으로본연구팀에서개발중인 DNA 서열디자인프로그램인 NACST/Seq 의알고리즘을기존의 NSGA-II에서 ε -MOEA로변경하였는데, 특히 ε -MOEA의빠른 convergence 속도로인해 DNA 서열을디자인하는데소비되는시간을대폭단축시킬수있을것으로기대된다. 참고문헌 [1] Garzon, M. H. and Deaton, R. J., "Biomolecule Computing and Programming," IEEE Transactions on Evolutionary Computation, Vol.3, No.3, pp , [2] Reif, J. H., "The Emergence of the Discipline of Biomolecular Computation in the US," New Generation Computing, Vol.30, No.3, pp , [3] Maley, C. C., "DNA Computation: Theory, Practice, and Prospects," Evolutionary Computation, Vol.6, No.3, pp , [4] Shin, S.-Y., Lee, I.-H., Kim, D., and Zhang, B.-T., "Multi-Objective Evolutionary Optimization of DNA Sequences for Reliable DNA Computing," IEEE Transactions on Evolutionary Computation, Vol.9, No.2, pp , [ 5 ] Laumanns, M., Thiele, L., Deb, K., and Zitzler, E., "Combining Convergence and Diversity in Evolutionary Multi-Objective Optimization," Evolutionary Computation, Vol.10, No.3, pp , [6] Deb. K., Mohan, M., and Mishra, S., "A Fast Multi-Objective Evolutionary Algorithm for Finding Well-Spread Pareto-Optimal Solutions," Kan- GAL Report No , [7] Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., "A Fast and elitist multiobjective genetic

12 1228 정보과학회논문지 : 소프트웨어및응용제 32 권제 12 호 ( ) algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, Vol.6, pp , [8] Garzon, M. and Deaton, R., "Codeword design and information encoding in DNA ensembles," Natural Computing, Vol.3, No.3, pp , [9] Deb, K., Multi-Objective Optimization using Evolutionary Algorithms, John Wiley & Sons, Ltd., [10] Deb, K., Thiele, L., Laumanns, M., and Zitzler, E., "Scalable Test Problems for Evolutionary Multi- Objective Optimization," KanGAL Report No , [11] Deb, K. and Agrawal, R. B., "Simulated Binary Crossover for Continuous Search Space," Complex Systems, Vol.9, No.2, pp , [12] Deb. K. and Goyal, M., "A Combined Genetic Adaptive Search(GeneAS) for Engineering Design," Computer Science and Informatics, Vol.26, No.4, pp , [13] Veldhuizen, D. V., "Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations," Ph. D. Thesis, Dayton, OH:Air Force Institute of Technology, Technical Report No. AFIT/DS/ENG/99-01, [14] Zitzler, E., "Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications," Ph. D. Thesis, Zurich, Switzerland:Swiss Federal Institute of Technology(ETH)(Dissertation ETH No ), [15] Purshouse, R. C. and Fleming, P. J., "Evolutionary Many-Objective Optimisation: An Exploratory Analysis," Proceedings of the 2003 Congress on Evolutionary Computation, pp , [16] Deaton, R., Murphy, R. C., Garzon, M., Franceschetti, D. R., and Stevens Jr., S. E., "Good encoding for DNA-based solutions to combinatorial problems." Proceedings of the Second Annual Meeting on DNA Based Computers, pp , [17] S.-Y. Shin, "Multi-Objective Evolutionary Optimization of DNA Sequences for Molecular Computing," Ph. D. Thesis, Seoul National University, [18] Tanaka, F., Nakatsugawa, M., Yamamoto, M., Shiba, T., and Ohuchi, A., "Developing support system for sequence design in DNA computing," Proceddings of the 7th International Workshop on DNA Based Computers, pp , [19] Lee, J. Y., Shin, S.-Y., Park, T. H., and Zhang, B.-T., "Solving Traveling Salesman Problems with DNA Molecules Encoding Numerical Values," BioSystems, Vol.78, pp , 신수용 1998 년 2 월서울대학교컴퓨터공학과학사 년 2 월서울대학교컴퓨터공학부석사 년 8 월서울대학교전기, 컴퓨터공학부박사. 관심분야는진화연산, DNA 컴퓨팅, 생물정보학, 기계학습 이인희 2001 년 2 월서울대학교컴퓨터공학부학사 년 3 월 ~ 현재서울대학교전기, 컴퓨터공학부석박사통합과정. 관심분야는다중목적진화연산, DNA 컴퓨팅, Molecular theorem proving method 장병탁정보과학회논문지 : 소프트웨어및응용제 32 권제 11 호참조