constraint adaptive differential evolution

Last Update: xxxx-xx-xx xx:xx
History
최초 작성: 2010-02-16 00:57

   글을 전부 작성하는데 어느 정도 시간이 걸릴 것 같아 우선 지금 상태에서 공개한다. 이 글에 앞으로 다음 내용들이 추가될 것이다(회색 부분이 아직 추가 안된 것).

ToDo:
1. 일반화된 정의/구현 코드(C++)
2. 예제 코드(GUI 포함)
2-1. global minima 찾는 것
2-2. canonical correlation analysis 와 같은 기능 구현
2-3. group separation (with cDNA)


   constraint adaptive differential evolution (CADE) 의 목적은 쉽게 말하면 global minima를 찾는 것이다. 즉, 주어진 목적 함수 (object function)에 대하여, 주어진 매개변수의 범위 내에서, 목적에 가장 부합하는 매개 변수(들)을 찾는 방법이다. CADE는 genetic algorithm의 한 부류인데, evolution 의 방법이 주어진 두 개체의 '차이'를 이용하기 때문에 differential 이란 단어를 사용한다. 또한 genetic algorithm과 같이 population-based algorithm^[각주:1]이며, 일반적으로 population의 크기는 parameter의 10 배 정도를 사용한다. 단점은 real-valued function에만 사용할 수 있다는 점이다.

  CADE가 사용될 수 있는 예를 들어 보면 이렇다. curve fitting이나 함수의 최대/최소값을 찾는 것. 이러한 것은 deterministic한 levenberg-marquardt (LM) 방법으로도 할 수 있는데 LM의 경우 local minimum 에 빠질 우려가 있고, 다루는 함수의 미분이나 2차 미분을 구해주어야 한다는 단점이 있다. CADE는 그렇지 않다. 또 다른 예로는, 변수 X1, ..., XN 으로 이루어진 벡터의 두 그룹의 평균을 가장 멀리 떨어뜨려 놓는 변수 1~N의 선형결합에 대한 상수를 찾는 일. 다시 말해, 유전자 10 개의 선형결합의 평균값이 질병군과 정상군에서 크게 차이가 나게 하기 위한 10개의 상수는 무엇일까? 현재의 내 지식으로는 이러한 목적에 맞는 deterministic algorithm 은 없다. 또 다른 예는, N 개의 변수와 M 개의 변수에 대하여, N 개 변수의 선형결합과 M 개 변수의 선형결합의 Pearson's correlation coefficient 를 최대로 해주는 M+N 개의 상수를 찾아 주는 일. 이것은 canonical correlation analysis (CCA)가 하려는 것과 정확히 같은 것인데, 제약조건이 들어가게 되면 CCA로 할 수 없지만 CADE는 여전히 매우 융통성있게 제약조건을 적용할 수 있다.


   최적화에 관련한 많은 문제는 적절히 다시 표현하면 목적함수의 global minimum 을 찾는 문제로 변형할 수 있다. 예를 들면, 함수의 형태와 몇 개의 실험 데이터가 주어졌을 경우, 주어진 실험 데이터를 모두 지나는 함수의 파라미터를 찾는 curve fitting 은 object function 을 RMSD^[각주:2]로 정의하면 global minimum 을 찾는 문제로 변경된다. CADE는 global minimum 이 여러 개 존재할 때 그와 같은 global minima 를 찾을 때 적합하다. 일반적으로 우리가 만나게 되는 문제는 정확히 'global minimum'이라기 보다는, 적정 선을 만족하는 parameter space의 subspace들이기 때문에 이런 경우 특히 CADE를 이용할 수 있다.


    CADE의 절차는 다음과 같다.

+ 초기화 : constraint C.
+ for each generation,
+- for each ith entity e in population,
+-- up to _NT times,
+--- select (k1,k2,k3) such that k_j != i and k_m != k_n for all m, n, j.
+--- make variant v with (k1,k2,k3).
+--- cross-over v with e.
+--- if v satisfies C then v replaces e and break.
+-- check age of e.
+--- If e > _NG then e is replaced with r from the current population but itself.
+--- if e <= _NG, then e is retained.
+- // for each entity.
+ // for each generation.
+ constraint C is updated.
+ check termination condition.



   일반적으로 constraint C 의 값은 populaton 내의 개체들 각각의 object function 값 중 제일 안 좋은 값을 사용한다. 현 세대의 개체는 object function 관점에서 보았을 때 전 세대의 개체 중 제일 적합하지 않은 개체보다 좀 더 적합하다면 진화를 계속 한다. 각 개체는 미리 정의된 횟수 _NT번 동안 진화를 시도하다가 실패하면 '나이'를 확인하여 주어진 나이 _NG 보다 작다면 계속 살아 남아 다음 세대로 넘어가게 된다. 만약 나이가 _NG보다 많다면 현 세대의 임의의 다른 개체로 대체된다. 이러한 식으로 현 세대의 모든 개체를 진화시킨 후, 새롭게 만들어진 개체군을 이용하여 constraint 를 재조정한다. 이 때, 진화된 개체들은 최소한 이전 세대의 개체 중 제일 적합하지 않은 개체와 동일한 object function 값을 갖으며, 일반적으로는 보다 '좋은' object function 값을 가능성^[각주:3]이 크다. 따라서 constraint C는 점점 최적화된다.

   임의의 3개체에 대하여 variant v는, 두 개체의 '차'에 다른 개체를 '더한 값'으로 만들어 진다. cross-over는 일반 genetic algorithm에서와 같다.

   위와 같은 방법은 중간에 적절하지 않은 parameter 인지 아닌지 확인하는 단계를 추가하여 원하지 않는 sub-space of parameters를 피해갈 수 있다. 또한 constraint C를 만족시키는 기준을 우리가 임의로 정할 수 있기 때문에 굳이 object function 의 최적화로만 한정할 필요가 없이 다른 조건들을 끼워 넣을 수 있다. 이와 같은 생각이 포함된, constraint adaptive differential evolution 의 단계를 도식화하면 다음과 같다.

Process of constraint adaptive differential evolution

   위의 각 단계를 살펴 보자. 우선 파라미터를 초기화 해준다. 그 후 constraint 를 설정해 준다. 이제 evolution 단계로 들어 간다. population 내의 각 개체 k에 대하여, k를 대체하게 될 variant v를 만든다. 이 v 를 k 와 cross-over를 시킨다. 즉, 어느 parameter 는 v 것을, 나머지는 k 의 것을 사용하는 것이다. 그 후 v 가 evolution 을 했는지를 판단한다. 만약  v 가 진화되지 않은 것이면 k 의 나이를 확인해서 설정된 것보다 작으면 k 는 이번 세대에도 살아 남아 다음 세대로 넘어 가게 된다. 만약 k 의 나이가 너무 많으면 현 population 중 k 이외의 개체로 k 를 대체시킨다. 만약 v 가 진화된 것이면 v 는 k 를 대체해서 다음 세대는 k 는 없어지고 대신 v 가 다음 세대로 넘어 간다. 현 세대의 모든 개체에 대하여 위와 같은 진화를 수행 후, 종료 조건을 만족시켰으면 진화를 중지하고, 종료 조건을 만족시키지 못했다면 진화를 수행한다.


   위의 방법을 조금 일반화하여 C++로 표현하고자 한다면 그 구조는 다음과 같을 것이다. 즉, 우리는 함수의 형태나 constraint의 충족 여부, 초기화, constraint 를 만드는 과정, 종료 조건 확인 과정, 의미있는 variant인지를 확인하는 과정을 일반화시켜서 pure virtual function 으로 뺀 후, 상속받은 클래스에서 context에 맞게 적절하게 overriding 해주면 되는 것이다. 우선 pure virtual function 들을 중심으로 보면 다음과 같다.

위의 코드를 실제로 구현하여 curve fitting 을 하는 동영상은 다음과 같다.



(위 예는 좀 복잡한 미분방정식을 풀어서 6개의 파라미터를 찾는 과정인데, 위의 테스트 코드가 재작성되어 상용 프로그램에 들어간 루틴이라 지금 설명하긴 좀 그렇고, 구체적인 설명은 논문과 특허가 공개되면 추가하겠음)

   이 방법을 적절히 응용하면 왠만한 '최적화' 문제에 사용할 수 있을 것이다. 문제는 시간이 매우 오래 걸린다는 것인데, 따라서 적절히 코드의 최적화를 수행해야 한다. 특히 진화를 하는 각 세대에서, 각 개체는 독립적으로 진화를 할 수 있기 때문에 이 부분의 for 문에 OpenMP 를 적용할 수 있다. 또한 evolution 부분 안쪽에서 돌아가는 부분이 여러 번 수행되므로 그 부분에 걸리는 함수들은 fastcall 로 설정하거나 SSE를 사용하는 편이 좋다. 또한 log 나 삼각함수 등은 look-up table 을 만들어 사용하거나, 여하튼 속도가 문제가 될 수 있으니 최적화가 조금 신경 쓰일 수 있다. >.<""



참고 논문
1. Differential Evolution - A simple and efficient adaptive scheme for global optimization over continuous spaces (pdf (115KB) 임) (링크가 깨졌을 경우에는 아래 파일 이용)

invalid-file

2. Self-adaptive Differential Evolution Algorithm for Constrained Real-Parameter Optimization, 2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada July 16-21, 2006.

3. System Design by Constraint Adaptation and Differential Evolution, Rainer Storn, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 3, NO. 1, APRIL 1999

1. 파라미터들을 요소로 갖는 벡터 여러 개가 곧 population. 이 population 을 진화시키면  population 내의 벡터들이 거의 한 곳으로 수렴하게 된다 [본문으로]
2. root-mean square deviation, 주어진 데이터 포인트에서의 함수값과 데이터 값과의 차이의 합 [본문으로]
3. 따라서 이 방법은 확률적으로 수렴하는 성질을 이용한다, 많은 다른 stochastic algorithm과 같이 [본문으로]