유전 알고리즘(Genetic Algorithm)

유전 알고리즘은 실제 생물체의 진화과정을 컴퓨터로 시행하는 탐색 알고리즘에 적용한 것으로
염색체를 인코딩하고 다윈의 적자 생존설에 기반해 적합도가 높은 유전체(구하려는 답과 근접한)
를 선택하고 교배시에 교차되는 과정과 돌연변이가 발생하는 과정을 거치는 것을 한 세대(generation)으로 보고 원하는 답을 찾을 때 까지 진화를하며 세대를 거치는 알고리즘이다.

이러한 유전 알고리즘을 사용함으로서 TSP같은 NP-complete을 현실적인 시간 내로 풀 수 있다는
장점이 있다. 현재 GA를 이용하여 85000개의 도시가 존재하는 TSP문제도 풀렸다고 한다.
또한 여러가지 문제에 해결 하는 것에 대해 알고리즘 구현이 비슷해서 한가지 문제를 제대로 해결하면
다른 문제들을 비교적 적은 노력으로 해결 할 수 있다는 것도 장점이라 생각된다.
하지만 말그대로 진화의 과정을 통해 원하는 답으로 진화하길 바래야 하기 때문에 간혹 답을
찾지 못하고 원치 않는 방향으로 진화를 해서 답을 못 찾는 경우가 있다는 단점은 있다.

이런 단점을 극복하기 위해 다양한 개체 표현방법이나 선택법, 변이연산자 등이 제시되었다.
1.표현 방법
-이진수표현
01010100101011 처럼 이진수로 유전체를 나타낸다.
길이가 길어져서 교차시 다양성 제공에 도움이 된다.
이진표현을 십진표현으로 바꿔주는 작업들을 계속 수행해야는 단점은 있지만
전체 수행시간에 큰영향은 안끼치지 않을까 생각된다.
-N진수 표현
3218679식으로 표현하게 되면 이진수 표현보다는 다양성이 떨어질 가능성은 있지만
의미 있는 유전자를 보존하게 될 가능성이 높아진다.
-순열 표현
TSP문제 같은 경우에서는 같은 도시가 중복으로 나오지 않게해야하기 때문에
순열의 표현을 해야한다. 인코딩시에도 고려해야하고 나중에 교차나 돌연변이 시에도
순열표현을 유지할 수 있도록 고려해야한다.
-그 외 교차연산자를 사용하지 않는 실수표현 방법이나 인접한 수가 한비트씩 차이나게하는 Gray코딩,
알고리즘 수행중 표현방식을 바꿀 수 있는 가변 표현 방식이 있다.

2.선택 방법 
-룰렛 선택
룰렛에서 각자 비율을 달리하여 선택되는 확률이 달라지게 하는 것 처럼 염색체의 적합도를 구해
그 적합도가 높을 수록 선택 될 확률이 높아지도록 하는 방식이다.
엘리티즘(Elitism)을 이용해서 가장 적합도가 높은 염색체를 반드시 다음 과정에 포함시키는 등의 방법도
많이 사용된다.
-토너먼트 선택
임의 갯수의 개체를 선택하여 토너먼트를 수행하고 가장 높은 적합도의 개체를 선택한다.
-SUS(Stochastic Universal Sampling)
균등한 간격으로 선택할 개체수 만큼의 바늘이 있는 룰렛을 돌려서 개체를 선택하는 방식.
작은 집단에서의 균형있게 선택하지 못하는 문제점을 해결하기 위해 고안된 방식.

3.교배 방법
 -single point crossover, two or multi crossover 
한개 또는 몇개의 점을 선택하여 서로 바꾸는 방법
-순열 이용한 인코딩 표현인 경우 PMX(partially mapped), OBX(order based), PBX(positon based) 등
의 방법을 사용한다.
PMX를 살펴보면 임의의 두지점을 선택해서 치환규칙을 정하는 방법이다.
아래의 첫번째에서 3과 2지점을 정하여 3,4,2를 정하고 그것과 대응되는 두번째의 2,7,3을 선택하여
이것을 바탕으로 3과2를 치환, 4와 7을 치환, 2와 3을 치환하는 등의 규칙을 정하여 교차한다.
1,6,3,4,2,7,8
8,4,2,7,3,6,1 

4.변이 방법 
-SM(Scramble Mutation)
임의의 두지점을 선택한 후 그사이의 값들을 뒤섞는다.
0,1,2,3,4,5,6,7 -> 0,1,2,4,5,3,6,7
-DM(Displacement Mutation)
임의 두지점을 선택후 이동시킨다.
0,1,2,3,4,5,6,7 -> 0,4,5,6,1,2,3,7 
-IM(Insertion Mutation)
DM과 비슷하지만 하나의 유전자만 위치를 바꾼다.
-IVM(Inversion Mutation)
임의의 두지점 선택한후 순서를 반대로 한다.


5.적합도의 가공
상황에 맞게 적합도를 가공해서 더 좋은 결과를 얻을 수 있는데
sigma scaling, moltzmann scaling 등의 방법을 사용해서 새로운 적합도를 얻기도한다. 


유전 알고리즘은 이러한 방법들을 어떻게 사용하느냐와 교차율, 돌연변이율, 개체군의 크기 등을
잘 고려해서 선택해야 한다. 

유전알고리즘에 대한 시뮬레이션등을 볼 수 있는 사이트
http://obitko.com/tutorials/genetic-algorithms/ga-basic-description.php 

어딘지도 모르겠는 어떤 중국 사이트에서 구한
유전 알고리즘으로 shortest path구하는 프로그램 소스들입니다..

shortest2.zip

shortest1.zip