208 정보과학회논문지 : 소프트웨어및응용제 36 권제 3 호 (2009.3) 고차상관관계를표현하는랜덤하이퍼그래프모델진화를위한베이지안샘플링알고리즘 (A Bayesian Sampling Algorithm for Evolving Random Hypergraph Models Representing Higher-Order Correlations) 이시은 이인희 장병탁 (Si Eun Lee) (In-Hee Lee) (Byoung-Tak Zhang) 요약유전자알고리즘의교차나돌연변이연산을직접적으로사용하지않고개체군의확률분포를추정하여보다효율적인탐색을수행하려는분포추정알고리즘이여러방법으로제안되었다. 그러나실제로변수들간의고차상관관계를파악하는일은쉽지않은일이라대부분의경우낮은차수의상관관계를제한된가정하에추정하게된다. 본논문에서는데이타의고차상관관계를표현할수있고최적해를좀더효율적으로찾을수있는새로운분포추정알고리즘을제안한다. 제안된알고리즘에서는상관관계가있을것으로추정되는변수들의집합으로정의된하이퍼에지로구성된랜덤하이퍼그래프모델을구축하여변수들간의고차상관관계를표현하고, 베이지안샘플링알고리즘 (Bayesian Sampling Algorithm) 을통해다음세대의개체를생성한다. 기만하는빌딩블럭 (deceptive building blocks) 을가진분해가능 (decomposable) 함수에대하여실험한결과성공적으로최적해를구할수있었으며단순유전자알고리즘과 BOA (Bayesian Optimization Algorithm) 와비교하여좋은성능을얻을수있었다. 키워드 : 베이지안샘플링알고리즘, 베이지안진화연산, 분포추정알고리즘, 랜덤하이퍼그래프 Abstract A number of estimation of distribution algorithms have been proposed that do not use explicitly crossover and mutation of traditional genetic algorithms, but estimate the distribution of population for more efficient search. But because it is not easy to discover higher-order correlations of variables, lower-order correlations are estimated most cases under various constraints. In this paper, we propose a new estimation of distribution algorithm that represents higher-order correlations of the data and finds global optimum more efficiently. The proposed algorithm represents the higher-order correlations among variables by building random hypergraph model composed of hyperedges consisting of variables which are expected to be correlated, and generates the next population by Bayesian sampling algorithm. Experimental results show that the proposed algorithm can find global optimum and outperforms the simple genetic algorithm and BOA(Bayesian Optimization Algorithm) on decomposable functions with deceptive building blocks. Key words :Bayesian Sampling Algorithm, Bayesian evolutionary computation, EDA, random hypergraph 정회원 : 백석대학교정보통신학부교수 leese@bu.ac.kr 학생회원 : 서울대학교컴퓨터공학부 ihlee@bi.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학부교수 btzhang@bi.snu.ac.kr (Corresponding author 임 ) 논문접수 : 2008년 0월 28일심사완료 : 2009년 월 22일 CopyrightC2009 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 소프트웨어및응용제36권제3호 (2009.3)
고차상관관계를표현하는랜덤하이퍼그래프모델진화를위한베이지안샘플링알고리즘 209. 서론자연세계의진화현상에기반하여교차와돌연변이연산을이용하는유전자알고리즘은적응적탐색과최적화를통해실세계의문제해결에많이응용되어왔으나문제의복잡도가커짐에따라최적해에접근하지못하는결과를가져올수도있다. 이러한문제점을해결하기위하여기존유전자알고리즘의교차와변이연산자들을직접적으로사용하지않고개체군의확률분포를추정하여효율적인탐색을수행하려는시도들이있어왔다. 대표적으로분포추정알고리즘 (Estimation of Distribution Algorithms, EDA)[] 이있으며적합도가좋은후보해들의확률분포를학습하여확률모델을생성하고그확률모델로부터새로운후보해들을샘플링해나간다. 따라서앞단계로부터키워온빌딩블럭들을분해하지않고변수들간에상호작용이있는문제해결에있어좋은성능을나타내어왔다. 후보해들로이루어진개체군의확률분포를평가하는것은주어진문제에존재하는변수들사이의관계를파악하는것으로관계표현능력에따라여러분포추정알고리즘이있다 [2]. 먼저각변수들이독립이라고가정하는 PBIL(Population Based Incremental Learning), cga(compact Genetic Algorithm) 과 UMDA(Univariate Marginal Distribution Algorithm) 등의알고리즘이있다 [,3,4]. 그러나변수들간의연관성이있는경우, 즉변수들이서로독립이아닌경우에는역시올바른해를얻기에어려움이있다. 이에대한해결의하나로두변수들간의상호작용을고려한알고리즘인 BMDA (Bivariate Marginal Distribution Algorithm) 등이있다 [5]. 또한 BOA(Bayesian Optimization Algorithm) 를통해베이지안네트워크로개체군을모델링함으로써더높은차수의상호작용이있는데이타를표현할수있게되었다 [6]. 그러나변수들간에상호작용이있는문제의경우그들의결합확률을모델링하고빌딩블럭을깨지않으며관련있는빌딩블럭이무엇인지를알아내는일은사전지식이없으면일반적인알고리즘에서는좋은성능을나타내기어렵다. 따라서주어진문제에존재하는변수들간의관계를파악하기위해그들간의관계를확률그래프모델 (probabilistic graphical model) 로구축하는것이필요하다. 여러모델중그래프를이용하여변수들간의확률관계를표현하는것은자연스러운것으로각노드는변수를, 각에지는변수들간의관계를표현할수있어그래프구조를조사함으로써변수들간의연관성을알아낼수있다. 최근에 Zhang[7] 은하이퍼그래프모델을이용하여다 양한기계학습분야의문제를해결하는데좋은방법론을제시하였다. 또한하이퍼그래프는데이타집합을저장하는확률적메모리로사용되어얼굴, 디지털이미지패턴분류문제등거대한문제공간에대한텍스트분류및완성문제, DNA 마이크로어레이데이타분석문제등에서기존의방법들과견줄만한좋은결과를가져왔다 [8-]. 본논문에서는랜덤하이퍼그래프모델을사용한새로운분포추정알고리즘을제안하고자한다. 주어진문제의변수들간에존재하는임의의차수의상관성을파악하기위해랜덤하이퍼그래프모델을구축하고그로부터하이퍼에지의사후확률분포에비례하여다음세대의개체군을베이지안샘플링함으로써변수들간의상관관계를반영한진화된개체들을생성하게된다. 생성된개체군에서적합도가우수한개체들을선택하고그로부터다시하이퍼에지들을생성하여랜덤하이퍼그래프모델을진화시켜나가므로원하는최적해에도달하는방법을제안하고자한다. 본논문의구성은다음과같다. 2절에서는분포추정계열의대표적알고리즘중의하나인 BOA에대해살펴본다. 3절에서는랜덤하이퍼그래프모델을구축하는방법에대해기술하며 4절에서는구축된하이퍼그래프모델로부터베이지안진화연산에기반을둔베이지안샘플링알고리즘을통해다음세대의개체군을구성하는방법에대해제안한다. 5절에서는변수들간의상관관계파악이문제해결에핵심이되는기만적 (deceptive) 문제에대한제안된알고리즘의실험방법과결과를보여주며 6절에서는결론에관해언급한다. 2. 분포추정알고리즘기존의유전자알고리즘은복잡한문제에대해서는임의의교차와변이연산에의해만들어진새로운탐색점들을가지고부모세대로부터물려받은좋은부분해, 즉빌딩블럭을키워나가는데한계가있다. 분포추정알고리즘 (Estimation of Distribution Algorithms, EDA) 은이러한결점을극복하기위해개발되었으며기존의유전자알고리즘과는다르게교차와변이연산을직접적으로사용하지않고학습된확률분포로부터새로운세대의개체군을구성하게된다. 분포추정알고리즘의개략적인흐름도는그림 과같다. 그림 분포추정알고리즘의흐름도
20 정보과학회논문지 : 소프트웨어및응용제 36 권제 3 호 (2009.3) 그러므로선택된개체들의확률분포를잘추정하는것이주요한문제가된다. 후보해들로이루어진개체군의확률분포를추정하는것은주어진문제에존재하는변수들사이의관계를파악하는것으로관계표현능력에따라여러분포추정알고리즘이있으며다변수데이타의임의의상관관계를나타내는대표적인알고리즘으로 BOA(Bayesian Optimization Algorithm) 이있다 [6]. BOA에서는선택된개체들로부터베이지안네트워크를구축하고그로부터새로운개체군을생성하게된다. 비순환방향그래프 (acyclic directed graph) 인베이지안네트워크에서각노드는하나의변수에해당한다. X i 는변수또는변수에해당하는노드를나타낸다고하자. 변수들간의의존관계는방향이있는에지로서표현한다. 베이지안네트워크는각변수 X i 에대한지역확률분포의곱으로결합확률분포를효율적으로표현하는확률그래프모델이다. X =(X,...,X n) 를문제공간변수들의벡터라할때결합확률분포는다음과같다. n px ( ) = px ( Π ), 여기서각변수 X i 에대하여 는베이지안네트워크에서 X i 로들어오는방향의에지를가진변수들의집합을말하며 집합의각구성원을 X i 의부모노드라부르고 X i 를 집합의구성원의자식노드라부른다. p(x i ) 는 에대한 X i 의조건부확률이다. 선택된개체들로부터최적의베이지안네트워크를구축하는방법은 NP-complete한문제로한노드로들어오는에지의수를제한하는등의제약조건을두어네트워크의복잡도를단순화하는것이필요하다. 네트워크가데이타를얼마나잘표현하느냐에대한측정값인스코어링메트릭 (scoring metric) 을최대화하는네트워크를 greedy한방법으로구축해나가는데빈네트워크로부터출발하여현재네트워크의스코어를개선시키는에지추가 (edge addition) 와같은원시그래프연산 (graph primitive operation) 을적용해나간다. 매단계네트워크는사이클이아니도록하며더이상스코어가개선되지않을때종료한다. 새로운개체군이생성되는것은베이지안네트워크의확률적논리샘플링을통해이루어진다. 먼저 ancestral 순서를결정하는데이는부모노드들이자식노드보다앞서는순서를말하며그계산된순서에따라새후보해를구성하는변수들의값을결정하게된다. 한변수의값을결정하려고할때 ancestral 순서가앞선그변수의부모노드들의값은이미다결정되어있으므로해당변수값의분포는변수의부모값들이주어졌을때상응 i Xi 하는조건부확률분포로부터얻게된다. 본논문에서는베이지안네트워크와비교하여볼때변수들간의확률적의존성 (probabilistic dependence) 은표현하지않지만, 하이퍼에지로변수들간의고차상관관계를쉽게표현하며그를반영하는다음세대의개체를바로생성할수있는하이퍼그래프모델을사용하여새로운분포추정알고리즘을제안하고자한다. 다음 3절에서는랜덤하이퍼그래프모델에대해간략히요약하고이를이용하여어떻게개체군의변수들간의상관관계를표현하는하이퍼에지들을구성할지에대해살펴본다. 4절에서는랜덤하이퍼그래프모델로부터다음세대의개체군을생성하는베이지안샘플링방법에대해설명한다. 3. 하이퍼그래프를이용한분포추정 3. 랜덤하이퍼그래프모델그래프는확률모델의구조를시각화하는데적합한구조중하나로노드는변수를, 에지는변수들간의관계를나타내게된다. 따라서그래프구조를조사함으로써변수들간의상관성을알아낼수있다. 일반적인그래프의경우는보통 2개의노드를하나의에지로연결하게되는데 3개이상의노드를하나의에지로연결하여그들간에상관관계가있음을표시할필요가있다. 이러한구조로하이퍼그래프 [2] 가있으며노드들의부분집합을하이퍼에지로갖게된다. 하이퍼그래프 G는 n개의노드들의집합을 V, l 개의하이퍼에지들의집합을 E라할때 G=(V,E) 로표시되며 V={v,...,v n}, E =(E,...,E l) 이다. 하이퍼에지의차수 (order) 는하이퍼에지를구성하는노드들의개수를말하며차수 k의하이퍼에지 를 k-하이퍼에 지라고하고, 아래첨자 i {,...n} 이다. 즉차수 k의하이퍼에지는 k개변수들을나타내는노드들로구성된집합이라고볼수있다. E 내에서하이퍼에지는중복하여존재할수있으며 E i 의개수를 w(e i) 라고하자. 그림 2는하이퍼그래프 G =(V, E), E ={E,...,E 6}, V ={v,...,v 8}, E ={v 3,v 4,v 5}, E 2 ={v 5,v 8}, E 3 ={v 6,v 7,v 8}, E 4 ={v 2,v 3,v 7}, E 5 ={v,v 2}, E 6 ={v 7} 인경우의예를보인것이다. k-하이퍼에지의가능한수 E k 는 n개의노드들의집합에서 k개의노드들을선택하는경우의수가된다. E n! = C = k!( n k)! k n k 상호작용이있는변수들을같은하이퍼에지에있는노드들로나타냄으로써그들간의관계를표현할수있다. 그러나초기에는변수들간의상관성을알지못하므
고차상관관계를표현하는랜덤하이퍼그래프모델진화를위한베이지안샘플링알고리즘 2 그림 2 하이퍼그래프의표현 [2] 로모든가능한하이퍼에지들의조합에대해고려해야한다. 현실적으로모든경우의변수들의상관성을고려 L 2 하는것은불가능하므로전체 = k n Ek 개의하이 퍼에지중에서실제로우리가고려하는하이퍼에지들의집합은랜덤프로세스에의해선택한작은집합이라할수있다. 전체모든가능한하이퍼에지들중에서우리가고려하는랜덤하이퍼그래프모델을구성하는하이퍼에지들을랜덤프로세스에의해생성하는방법은다음과같다. 데이타 x =(x,...,x n) 가 n 개의변수들로이루어져있을때 k 개의변수들로이루어지는 k -하이퍼에지 E h 를그림 3과같이랜덤프로세스에의해구성한다. 그림 3 하이퍼에지를구성하는랜덤프로세스따라서변수들의부분집합으로구성된각하이퍼에지들에대하여데이타 ( 개체군의개체들 ) 와의가능도 (likelihood) 를계산하고, 사전확률분포 ( 전단계의사후확률분포 ) 를반영하여사후확률분포를계산한후그에따라하이퍼에지들을베이지안샘플링해나감으로써문제공간변수간의고차상관관계를표현하는진화된다음세대의개체들을생성하게된다. 베이지안네트워크가방향이있는에지로변수들간의확률적의존성을표현하는데반해하이퍼그래프는 k 연관성이있을것으로예측되는변수들로하이퍼에지를구성하여조건부확률의표현없이구성변수들의집합이빌딩블럭으로유지되어야함을표시한다. 이때각변수 ( 노드로표시됨 ) 들은그림 2와같이서로다른여러하이퍼에지에나타날수도있다. 또한하나의하이퍼에지를구성하는변수들은적합도가우수한선택된개체 ( 데이타 ) 들로부터결정되므로하이퍼에지를구성하는변수들의상관성이높을경우에는해당하이퍼에지가여러번중복하여생성될수있다. 두경우모두, 최적의모델을구성하는것은 NP-complete한문제라베이지안네트워크는데이타를잘표현하는스코어를개선시키는방향으로 greedy한방법으로구축해나가며, 하이퍼그래프모델은데이타로부터랜덤하게생성한하이퍼에지들로구축하게된다. 본논문에서고려하는랜덤하이퍼그래프모델은조건부확률은표현할수없지만, 베이지안네트워크의경우와같은차수의제한을두지않고별도의계산없이최대 n의고차상관관계를하이퍼에지로쉽게표현할수있다. 또한작은차수의하이퍼에지들을결합하여고차의하이퍼에지를구축할수있는장점이있다. 3.2 하이퍼그래프분포생성된랜덤하이퍼그래프모델을통한변수들의확률분포추정을위해 n 개의노드, {v,v 2,...,v n} 을가진하이퍼그래프의 n 개노드들간의결합확률분포를다음과같이나타내기로한다. n l pv (, v2,, vn ) = ( v ) ( ), i E pe = () 여기서하이퍼에지 E 는노드들의부분집합이며 l 은하이퍼그래프를구성하는하이퍼에지의총가지수이다. 먼저노드 v i 가 l 개의각하이퍼에지에포함되는지의여부, v i E, 를아래와계산한다. if vi E ( v ). i E = 0 otherwise 만약노드 v i 가 E 의원소가되는경우에는, 식 () 의 p(e ) 는현재하이퍼그래프를구성하는전체하이퍼에지들의개수중 E 가몇개나존재하는지의비율로다음과같이계산한다. l we ( ) pe ( ) =, l we ( ) = pe ( ) =, pe ( ) 0, 여기서 w(e ) 는하이퍼에지 E 의개수를말한다. 다음 4절에서는진화연산을베이지안추론 (Bayesian i
22 정보과학회논문지 : 소프트웨어및응용제 36 권제 3 호 (2009.3) inference) 에기반한확률과정으로모델링하는베이지안진화연산 (Bayesian evolutionary computation)[3,4] 에기초하여위와같이구성한랜덤하이퍼그래프모델로부터그를구성하는하이퍼에지들의사후확률분포를구하고그확률에비례하여다음세대의개체들을생성하는베이지안샘플링알고리즘에대해제안한다. 4. 랜덤하이퍼그래프모델의진화를위한베이지안샘플링알고리즘하이퍼그래프모델의진화과정을베이지안진화연산에기반하여다음과같이고려할수있다. k-하이퍼에지 E h ={ } 에대하여 p(e h) 를사전 (prior) 확률분포라하고훈련데이타의집합 D={d,d 2,...,d N} 를관찰한후이데이타에대한가능도를 p(d E h) 라할때사후 (posterior) 확률분포 p(e h D) 는다음과같다. pd ( Eh) pe ( h) pe ( h D) =, pd ( ) (2) 여기서 p(d) 는정규화상수 (normalizing constant) 로다음과같이정의된다. pd ( ) = pd ( E) pe ( ). E 따라서식 (2) 는다음과같이나타낼수있다. pe ( h D) pd ( Eh) pe ( h). (3) 식 (3) 의사전확률분포 p(e h) 는문제에대한사전지식을고려하여정의되며특별한사전지식이없는경우에는균등분포를가정한다. 식 (3) 의가능도 p(d E h) 는하이퍼에지 E h 를구성하는변수값들로이루어진빌딩블럭을갖는데이타가몇개나되는지에대한값으로빌딩블럭의유용성에대한증거가되며다음과같이계산된다. pd ( E) = δ ( d ), N h i = k (4) 든데이타에대하여반복하여하이퍼에지 E h 의최종가능도를얻게된다. 현재세대의개체군으로부터학습된랜덤하이퍼그래프의사후확률분포는다음세대를생성하기위한사전확률분포가되어알고리즘이반복되며매세대진화된개체들을생성하게된다. 그림 4는본논문에서새롭게제안하는분포추정알고리즘으로랜덤하이퍼그래프를확률모델로사용하여분포추정을수행하는베이지안샘플링알고리즘 (Bayesian Sampling Algorithm) 의개략적인흐름도를보인다. 그림 4 랜덤하이퍼그래프모델진화를이용한베이지안샘플링알고리즘의흐름도 4. 개체군으로부터랜덤하이퍼그래프모델구축개체군의집합을 X ={X,...,X N}, 여기서각개체를 X i ={x (i),..., x (i) n ) 라고하자. 즉개체군의크기는 N, 각개체는 n 개의변수값들로이루어져있다. 먼저주어진절단임계치 (truncation threshold) 가 0< <일때적합도가우수한 M = N 개체들이선택된다. 변수들의상관관계를나타내는하이퍼에지로개체군의분포를추정하기위하여선택된 M개의개체들로부터상관관계가있을것으로예측되는 k개변수들의조합으로구성되는총 L개의하이퍼에지들을생성하여그림 5와같이하이퍼그래프 G를구축하게된다. () i if xh = d h δ ( di) =, 0 otherwise 여기서 h ={,...n} 이며 는 i 번째데이타인 d i = (d (i),...,d (i) n ) 에대하여 E h 를구성하는각변수의값과데이타 d i 의같은인덱스를갖는변수의값이일치하는 δ ( d) 지의여부를결정한다. 식 (4) 의 의값이 이면 k 하이퍼에지의변수값들과 d i 의해당인덱스를갖는변수의값들이모두일치함을나타낸다. 따라서하이퍼에지를구성하는변수들의상관성이있다는증거가되므로초기값이 0인가능도를 증가시키게된다. 이런과정을훈련데이타의집합 ( 개체군 ) D ={d,d 2,...,d N} 의모 = 그림 5 랜덤하이퍼그래프모델을구축하는프로세스
고차상관관계를표현하는랜덤하이퍼그래프모델진화를위한베이지안샘플링알고리즘 23 4.2 베이지안샘플링을통한새로운개체군생성구축된랜덤하이퍼그래프모델로부터다음세대의개체군이되는 N개의개체들을생성하기위한베이지안샘플링방법은다음과같다. 사후확률분포가우수한하이퍼에지에대하여우리는해당하이퍼에지를구성하는변수들간에상관성이높다는것을알수있으므로그변수값들의조합을그대로유지하는개체를생성한다. 이때 E h 로부터베이지안샘플링되는개체의수 m 은 E h 의사후확률분포에비례한다. m= N PE ( D) l = h PE ( D) 3-하이퍼에지 E h ={x p,x q,x r} 로부터베이지안샘플링되는 m개의다음세대개체들은그림 6과같다. 그림 6 베이지안샘플링방법을통한개체생성 E h 를구성하는변수의값 x p,x q,x r 을그대로고정시켜샘플링하므로써학습된변수들의상관관계를나타내는빌딩블럭을그대로유지하게한다. 이때 E h 를구성하지않는나머지변수들의값은랜덤하게샘플링하여개체군의다양성을유지하도록한다. 각하이퍼에지 E h 에대하여 E h 의사후확률분포에비례하는개수의개체들을생성해나감으로써 N개의개체들을구성하여다음세대의개체군을이룬다. 하이퍼에지의사후확률분포에비례하여다음세대의개체들을샘플링하므로, 만약사전확률분포가같을경우가능도가큰영역에서많은수의개체들이얻어진다. 베이지안진화연산의관점에서보면현재세대에서구축된랜덤하이퍼그래프모델이다음세대의모델을구축할때시작점이되어사전확률분포를나타내는모델로서사용된다. 실제로우리가고려하는 D는 N개의개체들로이루어진개체군이되며세대가진행됨에따라주어진데이타 ( 개체군 ) 를구성하는변수들의상관관계를잘반영하는랜덤하이퍼그래프모델로진화해나간다. 따라서진화된모델로부터베이지안샘플링방법을통해변수들의상관관계를반영한다음세대를구성하는진화된개체들을생성하게되므로개체군은점차적. 으로개선되고다양성은점차적으로감소하여마침내최적해에수렴하게된다. 5. 실험및결과 5. 함수최적화본논문에서제안한알고리즘의성능을평가하기위하여함수최적화문제로잘알려진유니트함수 (unitation) 에대하여실험, 비교하였다. 유니트함수는이진입력스트링이갖고있는 의개수에의존하는함수값을갖게되며이러한유니트함수들이더해져서좀더복잡한함수가될수있다. 즉함수 f k 를길이가 k 인스트링에서정의된유니트함수라고할때이러한함수 l 개를결합하여다음과같은함수 f 를구성한다. l f ( X) = fk( Si), 0 여기서 X 는 n 개변수들의집합이며 S i 는 X 의 k 개변수들로이루어진부분집합이다. 또한복잡한함수를더작은차수의, 즉변수들의부분집합으로구성되는더간단한함수들의합으로표시할수있을때원래의함수를덧셈으로분해가능 (additively decomposable) 하다고하며이때복잡한문제를더작은부분문제들로분할하여풀수있게된다. 실험은단순유니트함수가아닌기만 (deceptive) 함수에대해수행하였다. 기만현상 (deception)[5] 은탐색에의한최적화알고리즘의성능에대한연구를통해잘알려진현상으로, 기만함수는최적해 (global optimum) 가아닌그릇된지역해 (local optimum) 로알고리즘을유도하게되는데그이유는최적해가비관심지역에위치한고립된최고점이기때문이다. 차수 3을갖는기만함수인 3-deceptive 는다음과같이정의된다. 여기서 u는입력스트링에서 의개수이다. f 3 deceptive 0.9 if u = 0 0.8 if u = ( u) =. 0 if u = 2 if u = 3 그림 7 3-deceptive 함수
24 정보과학회논문지 : 소프트웨어및응용제 36 권제 3 호 (2009.3) 3-deceptive 함수는한개체를구성하는 3비트의입력스트링에적용되며전체문제의크기만큼더해져전체적합도를계산하게된다. 따라서크기 n 의문제에대해 n 비트모두 로구성되는하나의최적해를갖게된다. 그러므로올바른해를얻기위하여각분할내에의위치들간의상관성을고려하여야하며그렇지않고비트를독립적으로고려할경우최적해가아닌지역해에잘못이르게된다. 차수가 k 3인트랩 (trap) 함수는완전기만적 (fullydeceptive) 으로차수 k 보다작은어떠한통계자료 (statistics) 도최적해에이르지못하게한다 [6]. 따라서각트랩함수에속하는변수들끼리는빌딩블럭을형성하게되고확률모델을구축할때함께처리되어야한다. 그러므로문제에대한정보가주어지지않았을때에는변수들이랜덤하게분포되어있거나가깝게밀집되어있거나똑같이어려운문제가된다. 차수가 5인트랩함수는앞의 3-deceptive과비교하여 5비트그룹을고려하게된다. 각그룹의비트들은함께처리되며그렇지않을경우잘못된결과를얻게된다. trap-5는다음과같이정의된다. f trap 5 4 u if u< 5 ( u) =. 5 if u = 5 안샘플링을위한랜덤하이퍼그래프모델을구축하였다. BOA(Bayesian Optimization Algorithm) 와의성능비교를위해 BOA와단순유전자알고리즘 (Simple Genetic Algorithm, 이하 SGA) 에대한실험결과는 [6] 으로부터인용하였다. deceptive-3 함수에대하여베이지안샘플링알고리즘 ( 이하 BSA) 의경우, 문제의크기, 즉개체를구성하는변수의개수가 n =5에서 n =80인경우개체군의크기를 N =00에서 N = 3000으로실험하였으며하이퍼에지의차수는랜덤하게지정하였다. 개체군이최적해에수렴할때까지의평균적합도평가회수에대한결과가표 과그림 9에있다. 표 2와그림 0은 trap-5 함수에대한결과이다. 적합도평가회수는세대수와개체수의곱이며이때 BSA는앞에서와같이변수의개수가 n =5부터 n = 80인경우개체군의크기를 N =00에서 N =3000으로실험하였고하이퍼에지의차수는랜덤하게지정하였다. 실험을통해문제의크기가커짐에따라빌딩블럭이기만적이므로일점교차와변이연산 ( 변이율 =%) 을사용한 SGA의복잡도가지수적으로증가하였으나 BSA는선형의완만한증가도를갖는다. 따라서문제와는독립되고일점교차와변이연산과같은고정된변형 (variation) 연산자를사용하는 SGA와비교하여우리가제안하는알고리즘은훨씬낮은복잡도를갖고기만적덧셈분할가능한 (deceptive additively decomposable) 표 deceptive-3 함수에대한 BSA 의결과 그림 8 trap-5 함수 5.2 실험결과모든문제에대해서개체군이수렴할때까지 0번의독립적인실행의평균값으로적합도평가회수를구하였다. 개체군은각비트위치에서어떤값이전체개체군크기의 95% 에이를때수렴한다고정하였다. 그리고모든실험에서절단임계치 =50% 로하여적합도가우수한순으로절반의개체들을절단선택 (truncation selection) 하였다 [7]. 이전세대의하이퍼에지들을갱신하기위하여사전확률분포가높은하이퍼에지순으로적합도가높은순서대로선택된각개체로부터임의의변수값의조합을추가하여하이퍼에지들을갱신, 베이지 변수의개수 (n) 개체군의크기 (N) 세대수 평균적합도평가회수 평균 ± 표준편차 5 00 3.6±.82 360 30 00 6.8±.92 680 45 000 22.6±2.07 22600 90 500 3±3.39 46500 20 2000 3.2±3.63 62400 50 2500 33.2±3.7 83000 80 3000 33.8±3.87 0400 변수의개수 (n) 표 2 trap-5 함수에대한 BSA 의결과 개체군의크기 (N) 세대수 평균적합도평가회수 평균 ± 표준편차 5 00 2.6±.52 260 30 00 8.0±.58 800 45 000 24.2±2.39 24200 90 500 3.2±3. 46800 20 2000 36.8±3.27 73600 50 2500 38.2±2.7 95500 80 3000 42.6±3.6 27800
고차상관관계를표현하는랜덤하이퍼그래프모델진화를위한베이지안샘플링알고리즘 25 그림 9 3-deceptive 함수에대한결과 진문제의변수들간에존재하는임의의차수의상관성을파악하기위한랜덤하이퍼그래프모델을구축하여베이지안샘플링방법을통해개체군을진화시켜나가며최적해를찾아가는새로운분포추정알고리즘을제안하였다. BOA 등과같은경우, 모델을구축하기위해 greedy 한방법을사용해도적지않은시간이소요되며한노드로들어오는에지의수를제한하는등의제약조건을두어네트워크의복잡도를단순화하게된다. 본논문에서제안한방법에서는하이퍼에지를구성하는변수들을랜덤하게선택함으로써임의의상관관계를학습할수있으며우리가고려할거대한전체문제공간과비교하여상당히작은집합인랜덤하이퍼그래프만을유지하면서도랜덤하게생성한하이퍼에지들을통해개체군내에어떠한변수들의상관관계가유력한지를평가하고그모델로부터베이지안샘플링을통해결합확률분포를반영한개체들을생성하게된다. 실험을통해단순유전자알고리즘이해결하기어려운기만함수문제에대하여올바른결과를얻을수있음을보였고 BOA보다좋은성능을나타내었다. 참고문헌 그림 0 trap-5 함수에대한결과문제를풀수있음을알수있다. 또한 BOA와비교하여문제의크기가작은경우에는비슷한성능을가지나문제의크기가커질수록 BOA보다적은적합도평가회수를얻을수있었다. 또한랜덤하이퍼그래프모델을구축할때하이퍼에지의차수를고정시켰을때보다랜덤하게결정하였을경우가더좋은성능을보임을알수있었는데이는좀더빠른시간안에더큰빌딩블럭을형성할수있기때문으로보인다. 이러한결과들로부터문제공간의임의의고차상관관계를랜덤하이퍼그래프모델을통해잘학습할수있으며이를통해올바른최적해에도달할수있음을확인할수있었다. 6. 결론본논문에서는선택과정을통해살아남은개체들을구성하는변수들의가능한경우의결합분포를평가할수있도록에지를구성하는노드의개수를 2개이하로만제한하지않는하이퍼그래프구조를사용하였다. 그리하여상관관계가있을것으로추정되는변수들을하이퍼에지를구성하는노드들로나타낼수있었고주어 [ ] Mühlenbein, H. & Paaβ, G.., "From recombination of genes to the estimation of distributions I. Binary parameters," Parallel Problem Solving from Nature, pp. 78-87, 996. [ 2 ] Larranaga, P., "A review on estimation of distribution algorithms," Estimation of Distribution Algoruthms: A New Tools for Evolutionary Computation, Kluwer Academic Publisher, pp. 57-00, 200. [3] Balua, S., "Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning," Tech. Rep. No.CMU_CS_94_63, Pittsburgh, PA: Carnegie Mellon University, 994. [4] Harik, G. R., Lobo, F. G., & Goldberg, D. E., "The compact genetic algorithm," IlliGAL Report No.97006, Urbana, IL: University Of Illinois at Urbana Champaign, 997. [5] Pelikan, M., & Mühlenbein, H., "The bivariate marginal distribution algorithm," Advances in Soft Computing-Engineering Design and Manufacturing, pp. 52-535, 999. [6] Pelikan, M., Goldberg, D. E., & Cantu-Paz, E., "BOA: The Bayesian optimization algorithm," Genetic and Evolutionary Computation Conference GECCO-99, Vol., pp. 525-532, 999. [7] B.-T. Zhang, "Random hypergraph models of learning and memory in biomolecular networks: shorter term adaptability vs longer-term persis-
26 정보과학회논문지 : 소프트웨어및응용제 36 권제 3 호 (2009.3) tency," IEEE Symposium on Foundations of Computational Intelligence, pp. 344-349, 2007. [8] B.-T. Zhang & J.-K. Kim, "DNA hypernetworks for information storage and retrieval," Lecture Notes in Computer Science, DNA2, 4287:298-307, 2006. [9] S. Kim, M.-O. Heo & B.-T. Zhang, "Text classifier evolved on a simulated DNA computer," IEEE Congress on Evolutionary Computation(CEC2006), pp. 996-9202, 2006. [0] C.-H. Park, S.-J. Kim, S. Kim, D.-Y. Cho & B.-T. Zhang, "Finding cancer related gene combinations using a molecular evolutionary algorithm," IEEE 7 th international conference on Bioinformations & Bioengineering (BIBE2007), pp. 58-63, 2007. [] B.-T. Zhang, "Hypernetworks: A molecular evolutionary architecture for cognitive learning and memory," IEEE Computational Intelligence Magazine, 3(3):49-63, 2008. [2] Berge, C., Hypergraphs, North-Holland. 989. [3] B.-T. Zhang, "A Bayesian framework for evolutionary computation," IEEE Congress on Evolutionary Computation(CEC999), pp. 722-728, 999. [4] B.-T. Zhang, "A unified Bayesian framework for evolutionary learning and optimization," Advances in Evolutionary Computing, Springer-Verlag, Chap5, pp. 393-42, 2003. [5] Goldberg, D. E., "Simple genetic algorithms and the minimal deceptive problem," Genetic Algorithms and Simulated Annealing, Pitman, pp. 74-88, 987. [6] Deb, K. & Goldberg, D. E. "Analyzing deception in trap functions," Proceedings of Foundations of Genetic Algorithms FOGA-II, pp. 93-08, 993. [7] Claudio F. Lima, Pelikan, M., Goldberg, D. E., & Fernando G. Lobo, Kumara Sastry, and Mark Hauschild, "Influence of selection and replacement strategies on linkage learning in BOA.," IEEE International Conference on Evolutionary Computation (CEC2007), pp. 083-090, 2007. 이인희 200년 2월서울대학교컴퓨터공학부학 사. 200년 3월~현재서울대학교컴퓨 터공학부석박사통합과정. 관심분야는 진화연산, 생물정보학, 기계학습, DNA 컴퓨팅 장병탁 986년서울대학교컴퓨터공학학사. 988 년서울대학교컴퓨터공학석사. 992년독일 Bonn대학교컴퓨터공학박사. 992 년~995 년독일국립정보기술연구소 (GMD) 연구원. 995년~997년건국대학교컴퓨터공학과조교수. 997년~현재서울대학교컴퓨터공학부교수, 인지과학, 뇌과학, 생물정보학협동과정겸임. 200년~현재서울대학교바이오정보기술연구센터센터장. 관심분야는 Biointelligence, Probabilistic Models of Learning and Evolution, Molecular/DNA Computation 이시은 99년서울대학교컴퓨터공학학사. 997 년서울대학교컴퓨터공학석사. 999 년~현재서울대학교컴퓨터공학부박사과정. 998년~2005년백석문화대학컴퓨터정보학부조교수. 2006년~현재백석대학교정보통신학부조교수. 관심분야는진화연산, 기계학습, 생물정보학, 데이타마이닝