Genetic Algorithm

다윈의 진화론으로부터 창안된 해 탐색 알고리즘

즉, ‘적자생존'의 개념을 최적화 문제를 해결하는데 적용한 것

<Pseudo-code>

초기 후보해 집합 G₀을 생성한다.
G₀의 각 후보해를 평가한다.
t←0
repeat
	Gₜ로부터 Gₜ₊₁을 생성한다.
	Gₜ₊₁의 각 후보해를 평가한다.
	t←t+1
until(종료 조건이 만족될 때까지)
return Gₜ의 후보해 중에서 가장 우수한 해

즉, 여러 개의 해를 임의로 생성하여 이들을 초기 세대(generation) G₀

repeat-루프에서 현재 세대의 해로부터 다음 세대의 해를 생성

루프가 끝났을 때 마지막 세대에서 가장 우수한 해를 리턴

이 해들은 후보해(candidate solution)라고 부른다.

repeat-루프의 반복적인 수행을 통해서 최적해 또는 최적해에 근접한 해가 될 수 있기 때문

후보해(candidate soultion)

시작도시 A에서 출발해서 모든 다른 도시를 1번씩만 방문하고 다시 시작도시로 돌아온다.

후보해는 ABCDEA, ACDEBA, AECDBA 등이 있다.

시작 도시 제외 중복된 도시가 있거나 빠진 도시가 있으면 안된다.

이 문제의 후보해의 수는 시작도시를 제외한 4개의 도시를 일렬로 나열하는 방법의 수와 같으므로 4! = 24이다.

후보해를 평가한다는 것은 후보해의 값을 계산하는 것

후보해의 값은 도시 간의 거리를 더하여 계산한다.

또한 후보해의 값을 후보해의 적합도(fitness value)라고 한다.

후보해 중에서 최적해의 값에 근접한 적합도를 가진 후보해를 ‘우수한’ 해라고 부른다.

Genetic Algorithm에서 가장 핵심적인 부분은 현재 세대의 후보해에 대해서 다음 세대의 후보해를 생성하는 것

다음과 같은 세 개의 연산을 통해 생성한다.

1. 선택(selection) 연산

   현재 세대의 후보해 중에서 우수한 후보해를 선택하는 것

   n개의 후보해 중 우수한 후보해는 중복되어 선택될 수 있고, 적합도가 낮은 후보해들은 선택되지 않을 수도 있다.

   이렇게 선택된 후보해는 n개로 유지된다.

   선택 연산을 구현하는 방법은 룰렛 휠 방법

   각 후보해의 적합도에 비례하여 원반의 면적을 할당하고, 원반을 회전시켜서 원반이 멈추었을 때 핀이 가리키는 후보해를 선택

   따라서 면적이 넓은 후보해가 선택될 확률이 높다

2. 교차(crossover) 연산

   선택 연산을 수행한 후의 후보해 사이에 수행되는데, 이는 염색체가 교차하는 것을 그대로 모방한 것

   예를 들어, 2개의 후보해가 각각 2진수로 다음과 같이 표현된다면, 교차점 이후의 부분을 서로 교환하여 교차 연산이 수행되며, 그 결과 각각 새로운 후보해가 만들어짐

   이와 같은 교차연산을 1-점 교차 연산이라고 한다

   후보해가 길게 표현되면, 여러 개의 교차점을 임의로 정하여 교차 연산을 할 수도 있다.

   교차 연산의 목적은 선택 연산을 통해 얻은 보다 우수한 후보해를 생성하기 위함

3. 돌연변이(mutation) 연산

   교차 연산이 수행된 후 돌연변이 연산 수행

   돌연변이 연산은 아주 작은 확률로 후보해의 일부분을 임의로 변형시키는 것

   돌연변이가 수행된 후 후보해의 적합도가 나빠질 수도 있음

   그러나 돌연변이 목적은 다음 세대에 돌연변이가 이루어진 후보해와 다른 후보해를 교차 연산함으로써 보다 우수한 후보해를 생성하기 위한 것

   더 이상 우수한 해가 출현하지 않으면 알고리즘 종료