유전 알고리즘

정의와 핵심 용어

유전 알고리즘은 자연선택을 모방해 해의 집단을 진화시키는 확률적 탐색 알고리즘이다.

해는 염색체로 부호화하고, 우수한 해끼리 섞어 다음 세대를 만든다.

각 해가 문제를 얼마나 잘 푸는지는 적합도 함수가 수치로 나타낸다.

절차 흐름

절차는 초기 집단을 만드는 것에서 시작한다. 해는 염색체로 부호화된다.

각 개체를 적합도로 평가한 뒤, 선택과 교차로 새 자손을 만든다.

이후 변이와 대체를 거쳐 종료 조건을 만족할 때까지 세대를 반복한다.

종료 조건은 최대 세대 수, 수렴, 목표 적합도 도달 중 하나다.

룰렛 휠 선택 계산

룰렛 휠 선택은 적합도에 비례한 면적을 주고, 그 면적으로 부모를 확률적으로 뽑는다.

개체의 선택 확률은 개체 적합도를 전체 적합도 합으로 나눈 값이다.

적합도가 1, 2, 3, 4인 해라면 합계는 10이다. 4번 해는 0.4, 1번 해는 0.1이다.

교차 예제

교차는 두 부모의 유전자 일부를 맞바꿔 자손을 만든다.

예로 부모 [10110]과 [01011]에서 앞 2비트는 첫째 부모, 나머지 3비트는 둘째 부모에서 가져온다.

그러면 자손은 [10011]이 된다. 자손은 두 부모의 유전자를 함께 가진다.

선택 방식 비교

선택 방식은 룰렛 휠, 순위, 토너먼트, 엘리트주의로 나뉜다. 시험에서 자주 비교된다.

룰렛 휠은 적합도 값에 비례하고, 순위 선택은 값 대신 순서를 쓴다.

토너먼트 선택은 무작위 그룹의 최고 개체만 고르며, 그룹 크기로 압력을 조절한다.

실무에서는 토너먼트 선택을 기본값으로 쓰는 경우가 많다.

헷갈리는 점

시험에서는 유전 알고리즘을 특정 문제의 해법으로만 서술하는 실수가 많다.

실제로는 문제를 염색체로 부호화하는 접근 방법이므로 메타휴리스틱으로 본다.

선택은 우수한 해를 골라 집단을 개선하고, 교차는 기존 유전자를 조합한다.

정리

유전 알고리즘은 해를 염색체로 부호화해 선택, 교차, 변이를 반복하는 탐색이다.

룰렛 휠은 적합도에 비례한 확률로 부모를 뽑는다. 교차율과 변이율은 문제마다 다르다.

최적해를 보장하지 않으므로 조기 수렴을 막는 것이 성능의 핵심이다.