Algorithm Design - Genetic Algorithm

---

GA

GA(Genetic Algorithm)는 이름 그대로 유전의 개념을 기본 개념으로 디자인된 알고리즘이다.
생물은 생존과 번식에 이로운 방향으로 진화하는데 이 컨셉을 알고리즘에 갖고 온 것이다. 따라서 GA도 시간이 흐를수록 정답에 접근한다. 실제 유전학에서 T,A,C,G, DNA, RNA등이 있듯이 유전알고리즘에서도 염색체, 적응도(fitness), 교차(crossover), 돌연변이(mutation)등의 개념이 존재한다.

 

과정을 한번 살펴보자.

1. 어떤 문제의 답이 될 수 있는 후보를 인코딩 (인코딩 결과는 일종의 디지털 염색체)
임의의 염색체들 집합을 생성(population)

2. 가장 적응도가 높은 것을 선택(selection)

3. 교배 시킴(crossover)
4. 돌연변이 (mutation)

 

유전 알고리즘은 해답을 찾지 못 할 수도 있다. 그러나 최고의 장점은 문제를 어떻게 풀어야 하는지를 몰라도 된다는 것이다.

좀더 구체적인 과정을 보면 아래와 같다.
1. 100개의 초기 염색체 집단(population)을 만든다.
2. 각 염색체가 문제를 푸는 얼마나 적당한가를 검사하고 그에 상응하는 적응도 (fitness)를 부여한다.
3. 현재 집단에서 두 개를 선택(selection). 선택되는 확률은 적응도에 비례한다.
4. 두 염색체의 비트들 중에서 임의의 비트를 선정하여 교차(crossover)시킨다.
5. 교차된 염색체를 돌연변이(mutation) 시킨다.
6. 새로운 100개의 염색체로 대체(substitution)될 때까지 반복한다.

 

각 루프를 세대(generation), 전체를 시대(epoch)라고 한다.

---

룰렛 선택

Roulette wheel selection
각 염색체의 적합도에 비례하는 만큼 roulette의 영역을 할당한 다음, roulette을 돌려 화살표가 가리키는 영역의 염색체를 선택한다. 적합도가 높은 것은 선택될 확률이 그만큼 많고 적합도가 낮은 것은 선택될 확률이 상대적으로 낮다.

이때 Elitism(엘리트주의)를 ON/OFF할 수 있는데 이는 적합도가 매우 높은 염색체는 무조건 포함시키는 것이다. 이는 정답으로 빠르게 수렴하도록 하는 경향이 있고 문제에 따라 잘 맞고 안 맞는 경우가 있어서 적절히 선택해야한다.

---

Crossover

선택된 두 염색체가 새로운 자식 염색체를 만들기 위해서 부모염색체의 비트를 서로 바꾸는 것이다. 교차율은 실험적으로 얻어낸 결과 0.7이 적당한 값으로 알려져 있다. 몇개의 비트를 확률적으로 수정할지는 아래와 같이 다양한 방법이 있다.

---

Mutation

유전자를 일정한 확률로 변화시키는 조작이다. 예를들어 "0.001의 확률로 특정 비트를 반전시킨다."와 같이 적절한 확률을 지정해줄 수 있다.

돌연변이가 없는 경우 초기유전자조합 이외의 공간을 탐색할 수 없어 초기조합에 적절한 해가 없을 경우 원하는 해를 구할 수 없다. 다시말해서 Local Optimum에 빠지는 문제를 방지하는 역할을 하는 것이다.

---

미로 찾기 문제를 유전알고리즘이 다음과 같이 해결해내는 것을 볼 수 있다.

유전 알고리즘은 장점도 많지만 단점도 존재한다.

게놈 집단이 너무 빠르게 동일한 형태로 수렴할 수 있다. 게놈 집단이 서로 비슷하다면 교차가 무의미 해져서 염색체의 다양성이 상실되어 해답을 찾기 힘들다. 돌연변이가 있지만 확률은 매우 낮고 다양성을 위한 과정인 룰렛 선택으로 적응도가 높은 게놈이 다음 세대로 이어지는 것도 보장할 수 없다.
따라서, 다양성을 유지하면서 가장 적응도가 높은 게놈을 잃어버리지 않는 여러 가지 방법이 필요하다.

---