진화 프로그래밍

진화계산 및 진화디자인 : 황희수, 내하출판사, 2002, Page 79~87

1960년대에 로랜스 포겔 (Lawrence J. Fogel) 에 의해 만들어졌고, 데이비드 포겔 (David B. Fogel) 에 의해 개선된 진화프로그래밍 (EP : Evolutionary Programming) 은 유전알고리즘과 유사한 확률적 최적화 방법이지만, 자연계에서 볼 수 있는 특정한 유전 연산을 모방하는 대신에 부모와 자식간의 관계를 강조하는 돌연변이만을 사용한다. 비록 서로 독립적으로 발전했지만, 진화프로그래밍은 진화전략과 매우 유사하다. 다른 진화알고리즘처럼 진화프로그래밍은 해석적 접근이 불가능하거나 최적화 평면의 굴곡이 심해 다수의 국부 최적 점을 갖는 최적화 문제에 적합하다.

진화프로그래밍에서는 유전 연산자로 교배 연산을 사용하지 않는다. 돌연변이의 강도는 최적한 해에 가까워질수록 감소하도록 할 수 있는데, 최적 해를 사전에 알지 못하면 해가 최적한 값에 접근하는지를 모르기 때문에 돌연변이 강도를 줄일 수 없다. 이를 해결하기 위해 가장 널리 사용되는 방법은 메타-진화프로그래밍이다. 이 방법은 해의 돌연변에 사용되는 표준편차 값을 돌연변이 시킨다. 즉, 해에 대한 돌연변이 강도를 조정하는 표준편차를 해와 함께 진화시켜서, 진화 과정에서 해에 대한 돌연변이 강도를 스스로 조정할 수 있도록 한다. 따라서 메타-진화프로그래밍은 진화전략의 자기-적응성과 유사한 특성을 갖는다.

1. 개체의 데이터 구조

n 차원 공간의 목적변수 (목적함수를 최대화하는 탐색 대상인 변수) 에 대해 정의된 목적함수 를 최대화하는 문제를 생각해 보자. 진화프로그래밍은 n 차원의 목적변수를 코딩하지 않고 실수 벡터 (x) 를 직접다룰 수 있다. 메타-진화프로그래밍은 n 차원의 실수벡터 (x) 와 표준편차 벡터 (σ) 을 갖는다. 따라서 진화프로그래밍에서 개체는 해에 해당하는 실수벡터로 식 (1) 과 같이 표현되고, 메타-진화프로그래밍에서는 실수벡터와 표준편차 벡터로 구성되어 식 (2) 와 같이 표현된다.

a = x                                                                                     (1)

a = (x, σ)                                                                               (2)

m 개의 개체로 이루어진 집단 P 는 식 (3) 과 같이 표시된다.

                                                                      (3)

여기서 는 i 번째 개체로 진화프로그래밍에서는 이고 메타-진화프로그래밍에서는 이다. 개체 a 의 적합도함수 는 식 (4) 에서와 같이 목적함수 값을 비율 조정하거나 임의의 변경을 통해 얻어진다.

                                                                       (4)

는 비율조정 함수이고 δ 는 임의의 변경을 표시한다.

2. 돌연변이

진화프로그래밍은 집단에서 서로 다른 개체의 유전정보를 교환하는 교배 연산자를 사용하지 않으며, 돌연변이가 유일한 연산자이다.

1) 자기-적응성이 없는 돌연변이

진화프로그래밍에서 돌연변이는 식 (6) 에서와 같이 표준 정규분포의 랜덤 값에 식 (5) 의 표준편차를 곱하여, 이를 목적변수에 더함으로써 이루어진다. 이때, 표준편차는 적합도 값을 선형 변환한 후 제곱근을 취한 값이다.

                                                                   (5)

                                                                   (6)

식 (6) 에서 은 표준 정규분포에 의한 i 번째 랜덤 값이고, 식 (5) 에서 비례상수 와 오프셋 는 적용 문제에 따라 조정되어야 할 파라메타이다. 종종, 와 를 각각 1 과 0 으로 설정해서 식 (6) 을 식 (7) 과 같이 사용하기도 한다.

                                                            (7)

2) 자기-적응성이 있는 돌연변이

식 (5) 에서 , 는 문제에 따라 적절하게 선택되어야 할 파라메타이다. 메타-진화프로그래밍에서는 이런 번거로움을 피하기 위해, 식 (8) 과 식 (9) 와 같이 표준편차를 돌연변이해서 스스로 문제에 맞게 적응하도록 한다. 식 (8) 은 표준 정규분포의 자기-적응성을 갖도록 돌연변이하는 경우이고, 식 (9) 는 로그 정규분포의 자기-적응성을 갖도록 돌연변이하는 경우이다.

                                                                   (8)

이 식에서 가 음이면, 를 양의 작은 값 ε 으로 설정할 수 있지만, 지나치게 작으면 탐색공간의 축소를 초래할 수 있다.

                                               (9)

이 식에서 τ 와 τ' 값으로 흔히 와 가 사용된다. 목적변수의 돌연변이는 식 (10) 과 같이 이루어진다.

                                                                 (10)

식 (8) 또는 식 (9) 에 의해 표준편차를 돌연변이한 후, 식 (10) 과 같이 목적변수를 돌연변이하는 경우를 '표준편차 우선 자기-적응' 이라 부르고, 그 반대로 식 (10) 의 목적변수 돌연변이를 먼저 실행하고 식 (8) 또는 식 (9) 의 표준편차를 돌연변이 시키는 경우를 '표준편차 나중 자기-적응' 이라 부른다. '표준편차 우선 자기-적응' 방식이 '표준편차 나중 자기-적응' 방식 보다 더 우수함이 다양한 시험 사례에서 입증되었다.

2) 새로운 돌연변이

최근에 코시 (Cauchy) 돌연변이 연산자가 소개되었으며, 이 돌연변이 연산자가 다수의 파라메타 최적화 문제에서 표준 정규분포의 돌연변이 연산자 보다 우수함이 입증되었다. 코시 돌연변이 연산자를 사용하면 목적변수는 식 (11) 과 같이 돌연변이 된다.

                                                                   (11)

C(0, 1) 은 중심이 0 이고 비율 조정 파라메타 값이 1 인 코시 랜덤 변수를 나타낸다.

코시 돌연변이를 사용하는 진화프로그래밍은 다수의 극점을 갖는 문제에서 기존의 표준정규분포의 돌연변이를 사용하는 진화프로그래밍 보다 성능이 우수했으며, 극점이 하나 또는 소수인 문제에서는 비슷한 성능을 보였다. 코시 돌연변이 연산자로 인한 성능 개선은 돌연변이가 커질 확률이 높은데 그 원인이 있는 것처럼 보인다. 여기서는 이 두 돌연변이를 선형적으로 결합해서 만든 새로운 돌연변이로 평균 돌연변이와 자기-적응성이 있는 평균 돌연변이를 소개하고자 한다.

평균 돌연변이는 두 개의 랜덤 변수 N(0, 1) 과 C(0, 1) 을 사용한다. 이 두 랜덤 변수 샘플의 평균값을 자기-적응 파라메타인 에 의해 비율 조정하고, 이를 목적변수 돌연변이에 사용한다. 따라서 목적변수는 식 (12) 와 같이 돌연변이 된다.

                                               (12)

두 개의 랜덤 변수를 평균한 값은 식 (13) 에서와 같이 표준 정규분포의 확률밀도함수 (PDF) 와 코시 확률밀도함수의 콘볼루션에 의해 얻어진 확률밀도함수를 따른다. 평균 돌연변이는 표준 정규분포의 돌연변이에 비해 크기가 작은 (0 ~ 0.6) 돌연변이와 크기가 큰 (2 ~ 4.8) 돌연변이를 많이 발생하는 반면에, 코시 돌연변이에 비해서는 크기가 작은 (0 ~ 1) 돌연변이를 많이 발생한다. 따라서 평균 돌연변이는 표준 정규분포의 돌연변이에 비해서는 크기가 크지만 코시 돌연변이 보다는 크기가 작은 돌연변이를 발생한다.

                         (13)

* 는 콘볼루션 표시.

진화 과정에서 평균 돌연변이 확률밀도함수의 형태는 고정되어 있으며, 확률밀도함수의 파라메타만이 자기-적응된다. 확률밀도함수의 형태와 파라메타를 함께 자기-적응시키면, 다양한 최적화 문제에서 보다 강인한 적응 능력을 발휘할 수 있을 것이다. 이를 위해, 자기-적응성이 있는 평균 돌연변이를 도입하면, 목적변수는 식 (12) 대신 식 (14) 와 같이 돌연변이 된다.

                                                    (14)

 식 (14) 는 두개의 자기-적응 파라메타 와 를 갖는다. 자기-적응 파라메타 는 코시 분포의 표준편차 부분을 나타내고 는 표준 정규분포의 표준편차 부분을 나타낸다. 이 둘을 결합하면 식 (15) 와 같이 쓸 수 있는데, 는 전체적인 표준편차를 나타내고 는 확률밀도 함수의 형태를 결정한다. 의 크기가 작아지면 전체 확률밀도함수는 코시 확률밀도함수를 닮아가고, 크기가 커지면 표준 정규분포의 확률밀도함수와 비슷해진다. 따라서 와 파라메타를 자기-적응시킴으로써, 표준 정규분포 확률밀도함수와 코시 확률밀도함수 사이에서 임의의 형태를 발생시킬 수 있다.

                                              (15)

3. 진화 과정

μ 개의 부모 개체 각각을 돌연변이 시켜서 μ 개의 자식 개체를 만든 후, 부모와 자식 개체의 합한 2μ 개체로부터 확률적인 q- 승자승 선택 (q ≥ 1) 을 통해 다음 세대를 위한 μ 개의 부모 개체를 선택한다. q-승자승 선택 원리는 다음과 같다. 첫째, 개체 에 대해 2μ 개의 개체로부터 q 개의 개체를 랜덤하게 선택한다. 둘째, 선택된 q 개의 개체와 의 적합도를 비교해서 q 개 가운데 몇 개의 개체가 의 적합도 보다 열등한지를 세어서 이를 점수 로 준다. 셋째, 앞의 두 과정을 모든 개체 에 대해 실행한다. 넷째 2μ 개의 개체를 값에 따라 내림차순으로 정렬한다. 가 높은 값을 갖는 μ 개의 개체를 다음 세대의 부모 개체로 선정한다. 점수 는 식 (16) 과 같이 계산된다.

              (16)

  는 q-승자승에 포함될 개체를 지정하기 위한 균일분포의 정수형 랜덤 변수이고, 는 랜덤변수에 의해 지정된 개체의 적합도이다. 승자승 크기인 q 가 증가함에 따라 선택 체계는 (μ + μ) 진화전략에서처럼 결정론적으로 변해간다. 가장 우수한 개체는 최대 적합도 점수인 q 를 받기 때문에 항상 생존하며, 이는 엘리트주의를 사용한 것과 같은 효과를 나타낸다. 진화프로그래밍의 진화 과정은 다음의 3 단계로 이루어지며, 종료 조건 (만족할 만한 해를 찾았거나 계획된 반복 횟수에 도달한 경우) 을 만족할 때까지 계속된다.

단계 1 : 초기 집단을 임의의 값으로 초기화한다. 집단에서 개체 (해) 의 숫자는 최적화 속도에 큰 영향을 주지만, 집단 크기를 얼마로 해야 적당하지에 대한 답은 없다.

단계 2 : 개체는 새로운 집단으로 복제되고, 이 개체가 돌연변이 된다. 돌연변이의 강도는 부모 개체에 할당된 변화 요구에 의존한다. 메타-진화프로그래밍에서는 목적변수의 돌연변이에 앞서 표준편차를 먼저 돌연변이 해야 한다. 돌연변이 연산자로는 표준 정규분포 돌연변이, 로그정규분포 돌연변이, 평균 돌연변이 및 자기-적응성을 갖는 평균 돌연변이 가운데 하나를 사용한다.

단계 3 : 자식 개체는 적합도 평가를 받고, 확률적인 승자승 선택을 사용하여 다음 세대 집단을 구성한다.

집단 크기가 일정해야 할 필요는 없으며, 부모 개체가 하나 이상의 자식 개체를 발생할 수도 있다. 그림 1 은 진화프로그래밍의 계산 과정을 가상코드 형태로 정리한 것이다.

그림 1  진화프로그래밍의 계산 과정

표 1 은 유전알고리즘, 진화전략과 진화프로그래밍을 비교한 것으로 이들의 차이점과 공통점을 알 수 있다.

표 1  유전알고리즘, 진화전략 및 진화프로그래밍의 특성 비교

4. 활용 분야

    ■ 패턴분류

시계열 데이터의 패턴 분류, 환자의 나이와 방사선 사진의 특징으로부터 유방암을 찾는 선형 식별 모델과 신경회로망을 학습시킴, 분류 시스템의 설계

    ■ 모델링 및 제어

수술중인 환자의 혈압 제어, 바다 음향의 모델링, 진화에 의한 시스템 동정, 카오스 모델 (카오스 방정식의 파라메타 추정) 을 만들고, 이를 활용하여 관측된 시계열 데이터에 카오스 신호의 존재 유무를 확인, 비선형 시스템의 퍼지 모델링 및 제어를 위해 퍼지 규칙베이스를 동정, 최적 제어

    ■ 최적화

VLSI 채널의 라우팅 설계, 여행 일정 최적화, 연료 분배 최적화

    ■ 의사결정

게임에서 지능적인 의사결정, 지진 발생 진원지 결정, 재고 문제

    ■ 기타

음성 신호의 특징 해석, 신경회로망의 진화, 모의 DNA 칩으로부터 DNA 순서 정보 구성, 유한 요소 문제에 응용, 다국적 언어로 된 정보를 복구할 수 있도록 질문을 번역