📂최적화이론

유전 알고리즘에서 근친상간 방지 알고리즘이란?

용어 ¹

유전 알고리즘의 교차혼합에서 해와 해 사이의 거리 혹은 유사성을 측정해서, 너무 비슷한 해들끼리 교배하는 것을 막아 다양성을 제고하는 기법을 근친상간 방지^{incest prevention}라 한다.

설명

유전 알고리즘에서 비슷한 해끼리의 반복 교잡을 허용한다는 건 자연에서 유전병의 발생 확률을 높이는 정도가 아니라, 하나마나한 계산에 계속해서 자원을 낭비하는 죄악이나 다름없다.

하필 이름에 근친상간이라는 강한 표현이 쓰인 것은 실제로 유전 알고리즘을 써보면 이해하기 쉬운데, 개체군 전체를 압도하는 엘리트가 태어나고 그 독주를 막지 못할 경우 대부분이 첫번째 선조와 닮아진 채로 세대를 거듭하게 되는 현상을 어렵지 않게 볼 수 있기 때문이다. 경험적으로 봤을 때 단순히 돌연변이로 그렇게까지 비슷한 해들이 독점적인 지위을 가지는 것은 거의 불가능하고, 보통은 친족끼리 근친상간을 반복하다 한 점에 몰리기 때문에 일어난다.

방지 알고리즘의 대표적인 예는, 크로모좀이 비트^bit로 표현되는 해공간 $\left\{ 0, 1 \right\}^{n}$ 에서 해밍 거리를 통해 두 해가 일정 거리 이상 떨어진 경우에만 교잡을 허용하는 것이다. 예를 들어 세 개의 해 $\mathbf{x}_{1}$, $\mathbf{x}_{2}$, $\mathbf{x}_{3}$ 가 다음과 같이 주어졌다고 하자. $$ \begin{align*} \mathbf{x}_{1} =& (0, 1, 0, 1, 1, 0, 0, 1) \\ \mathbf{x}_{2} =& (0, 1, 1, 1, 0, 0, 0, 1) \\ \mathbf{x}_{3} =& (1, 0, 1, 0, 1, 0, 1, 1) \end{align*} $$ 여기서 임계치^threshold가 4라고 치면, $\mathbf{x}_{1}$ 과 $\mathbf{x}_{2}$ 의 해밍 거리는 3으로 교잡이 금지되지만, $\mathbf{x}_{1}$ 과 $\mathbf{x}_{3}$ 의 해밍 거리는 5로 교잡이 허용된다.