유전알고리즘

Genetic Algorithm; 유전 알고리즘, GA
생물의 진화 과정을 모방해, 여러 후보 해를 선택·교차·변이의 유전 연산으로 세대마다 개선하면서 최적해를 찾는 탐색·최적화 알고리즘

개요

유전알고리즘은 1970년대 존 홀랜드(John Holland)가 체계화한 방법이다. 문제의 해 하나를 염색체(보통 비트열이나 수열)로 표현하고, 여러 염색체로 이루어진 집단(population)을 만든 뒤, 좋은 해일수록 살아남아 자손을 남기게 하는 자연 선택의 원리를 흉내 낸다. 해를 평가할 함수만 있으면 미분할 수 없거나 탐색 공간이 매우 큰 문제에도 쓸 수 있어 최적화 및 검색 문제에 널리 쓰인다.

동작 순서

초기 집단 생성 — 후보 해를 무작위로 여러 개 만든다.
적합도 평가 — 적합도 함수(fitness function)로 각 해가 얼마나 좋은지 점수를 매긴다.
선택(Selection) — 적합도가 높은 해일수록 부모로 뽑힐 확률을 높인다. 룰렛 휠 선택, 토너먼트 선택 등이 있다.
교차(Crossover) — 두 부모 염색체의 일부를 서로 바꾸어 자손을 만든다. 일점 교차, 다점 교차, 균등 교차 등이 있다.
변이(Mutation) — 낮은 확률로 염색체 일부 값을 바꾼다. 집단의 다양성을 유지해 지역 최적해에 갇히는 것을 막는다.
새 세대로 2~5 를 반복하고, 정해진 세대 수에 이르거나 해가 더 나아지지 않으면 멈춘다.

유전 연산

연산	하는 일	역할
선택	좋은 해를 부모로 고른다	좋은 형질을 다음 세대로 넘긴다
교차	부모의 일부를 섞어 자손을 만든다	좋은 해의 조합으로 더 나은 해를 찾는다
변이	일부 값을 무작위로 바꾼다	새로운 영역을 탐색하고 다양성을 유지한다

특징

한 점이 아니라 여러 해를 동시에 탐색하므로 경사 하강법처럼 기울기를 따라가는 방법보다 지역 최적해에 덜 갇힌다.
확률적 방법이라 항상 전역 최적해를 보장하지는 않으며, 실행할 때마다 결과가 다를 수 있다.
집단 크기, 교차율, 변이율 같은 매개변수를 잘 정해야 한다.

같이 보기

[1] 참고