다음 [그림 1]은 유전자 알고리즘의 일반적인 수행과정을 나타낸다.
|
|
[그림 1] 유전자 알고리즘 수행과정
유전자 표현(Gene Representation)은 유전자 알고리즘을 구축하는 첫단계로 문제의 잠재해를 유전적 표현 즉, 개체로 표현하여야 한다. 이 유전적 표현은 유전자 알고리즘의 다른 절차(적합도 평가와 유전연산자 등)에 영향을 주므로 문제의 특성을 잘 반영할 수 있도록 하고, 문제에 따라 표현은 다를 수 있다. 유전자 알고리즘은 개체들로 구성된 모집단을 바탕으로 해를 찾아 나가기 때문에 초기에 모집단이 생성되어야 한다. 생성 방법은 임의생성 방법이 흔히 사용된다.
적합도(Fitness)는 유전자 개체가 갖고 있는 피부색, 저항력 등과 같은 특성을 나타내는 값으로서 이것은 환경에서 생존할 수 있는 즉, 적응할 수 있는 정도를 나타내는 값이다. 개체가 주어진 어떤 환경에서 생존하기 위해서는 최적의 적합도를 가져야 하며, 이러한 최적값은 일반적인 최적화문제의 목적함수에서와 같이 목적함수인 적합도 함수를 설정하여 이것을 최적화함으로써 얻을 수 있다. 예를 들면, 임의의 염색체(스트링)의 유전자값이 주어질 때, 이 값들을 변수로 한 적합도 함수를 설정하여 최적화시킴으로써 최적의 적합도를 구한다. 그러나 주어진 특정한 값을 갖는 염색체가 원하는 수준의 적합도를 충족시키지 못하면 유전자 변형을 통하여 염색체를 변화시켜 원하는 최적 적합도가 생성될 때까지 반복한다.
선별(Selection)은 적자생존의 자연법칙에 기초하여 환경에 대한 적합도를 평가하여 현 세대의 모집단으로부터 다음 세대를 만들 개체를 선택하는 과정이다. 모집단의 다양성과 선별압력이 조화를 이룰 수 있어야 하고, 강한 선별압력(적합도가 높은 우수개체가 열성개체보다 생존확률이 아주 높은 것)은 모집단의 개체들을 조기에 수렴시키나 해의 다양성이 떨어지며, 약한 선별압력은 해의 다양성은 유지되나 효율적으로 해를 탐색하지 못한다.
유전 연산자(Operator)는 교차(crossover)와 돌연변이(mutation) 연산자로 나누어 진다. 교차는 두 부모(parent)가 갖는 유전자를 조합하여 자손(offspring)을 생성하는 과정이다. 교차시 부모의 좋은 형질(유전자)이 가능한 파괴되지 않고 자손에 상속될 수 있어야 한다. 돌연변이는 한 개체에서 아주 작은 수의 유전자를 임의로 변화시키는 과정이며 해를 다양하게 탐색할 수 있도록 한다.
세대(Generation)는 알고리즘에서 유전연산의 횟수이며, 유전 파라미터(Parameter)로는 모집단의 크기(pop-size), 교차율, 돌연변이율, 종료조건 등이 있다. 모집단의 크기는 모집단을 이루는 개체수를 의미하며, 교차율은 각 개체가 교차될 확률, 돌연변이율은 각 유전자가 돌연변이 될 확률을 나타낸다. 알고리즘 종료조건으로는 (1) 진행된 세대수 또는 생성된 개체수, (2) 해의 개선의 이루어지지 않고 진행된 세대수 또는 생성된 개체수, (3) 계산소요시간 등이 사용된다. 다음 <표 1>과 [그림 2]는 알고리즘의 세부 절차 및 흐름도를 나타낸다.
<표 1> 유전자 알고리즘의 절차
|
단 계 |
내 용 |
|
1 |
종료조건을 설정한다(진행할 세대수, 계산소요시간 등) |
|
2 |
최초의 유전자개체 모집단을 구성한다 |
|
3 |
최초 모집단의 유전자개체에 대하여 적응도를 평가한다 |
|
4 |
교차율에 의해 모집단에서 두 유전자개체를 선별한다. |
|
5 |
선별된 두 개체에 대하여 교차를 실시한다. |
|
6 |
돌연변이율에 의해 임의 개체를 변형시킨다. |
|
7 |
교차와 돌연변이된 유전자개체의 적응도를 평가한다. |
|
8 |
최초 정해진 종료조건을 만족하면 계산을 끝내며, 그렇지 않으면 단계 4로 다시 간다. |
|
procedure GA initialize Population; eval uate Population; while not (terminal condition satisfied) do select chromosomes for next population; Crossover and Mutation; eval uate Population; end while
end procedure |
[그림 2] 유전자 알고리즘 흐름도
[출처 : http://kr.blog.yahoo.com/g0jeon01/47]