Evolutionary Algorithm

 

자연계의 진화는 주어진 환경에 잘 적응하는 유전자를 선택하여 교배하고 경우에 따라서 돌연변이도 하여 다음 세대에 우수한 진화 형질만 전달된다. 이런 방법으로 진화 과정을 반복하면 결국에는 환경에 가장 잘 적응한 우수한 형질만 남게 된다. 이러한 자연계의 진화 메커니즘을 모방하여 최적해를 구하는 방법이 진화 알고리즘(Evolutionary Algorithm)이다.

진화 알고리즘은 선택(Selection), 교배(Recombination), 돌연변이(Mutation)라는 연산자(Operator)를 이용하여 개체의 적합도를 개선한다.

 

l  진화 알고리즘의 특징

1.     진화 알고리즘은 결정론적인 규칙이 아닌 확률적인 방법이다.

2.     Gradient정보 없이 설계영역을 탐색하므로 목적함수의 형태에 제한이 없고, 연속적인 설계변수와 불연속적인 설계변수를 모두 다룰 수 있다.

3.     진화 알고리즘을 통해 얻은 최적해는 전역 최적해이다.

 

l  진화 알고리즘의 연산자

1.    선택(Selection)

환경 적응도의 척도가 되는 목적함수의 적합도를 이용하여 부모세대를 고르는 과정이다.

적합도가 높을수록 다음 세대에 우수한 형질이 진화될 가능성이 높으므로 적합도가 높을수록 부모로 선택될 확률이 높아진다.

 

그림 1 Rank based selection

 

2.    교배(Recombination)

부모 세대로 선택된 두 개체를 이용하여 자손세대를 만드는 과정으로 적합도가 우수한 부모 개체를 이용하므로 자손세대는 부모세대보다 더 우수한 적합도를 가질 것으로 기대 할 수 있다. 이러한 교배과정을 반복 수행하면 최종적으로 구해진 해는 적합도가 가장 우수한 최적해에 도달 할 수 있게 된다.

그림 2 Intermediate Tendency Recombination

 

3.    돌연변이(Mutation)

교배연산으로만 개체를 진화 시켜나갈 경우 무리 속 개체들이 가진 유전자의 근본적인 토대를 벗어날 수 없게 된다.

이러한 부분을 보완하기 위해 돌연변이 연산을 수행한다.

돌연변이 연산은 일정 확률로 교배연산 이후 얻은 자손세대의 유전 배열을 임의로 바꿔주는 과정이다.

 

그림 3 Random Mutation

 

 

l  진화알고리즘 Flowchart

진화 알고리즘의 전체 수행 과정은 다음과 같다.

그림 4 진화알고리즘의 flowchart