📂최적화이론

유전 알고리즘에서 교차혼합이란?

정의

유전 알고리즘에서 교차혼합^crossover이란 여러 개체의 특징을 섞어 새로운 해를 만드는 연산을 말한다.

설명 ^{1 2}

유전 알고리즘에서 교차혼합, 혹은 더 짧게 교잡은 자연선택된 개체들의 형질을 섞어 새로운 자식 세대의 개체들을 만들어내는 방식이다. 이는 자연에서 일어나는 유성생식의 메커니즘에서 영감을 받은 것으로³, 해공간의 꼼꼼한 탐색은 포기하더라도 다양한 시도를 통해 더 나은 해를 찾으려는 목적을 가진다.

아무래도 도태되지 않은 부모들이니까 적합도가 높은 특징들을 물려줄 가능성이 큰 한 편, 너무 엘리트들만 싸고돌면 개체군의 다양성이 떨어져 쓸데없는 계산에 몰두하는 것을 방지한다.

지점 교잡

지점 교잡^{point crossover}은 크로모좀으로 표현되는 해의 특정 랜덤하게 잡아서 그 곳을 경게로 부모의 형질을 섞는다. 한 점만 선택하는 경우 구현이 훨씬 간단하지만 부모 중 한쪽으로 너무 치우친 자식이 나올 수 있고, 두 점을 고르면 구현 자체는 살짝 까다로워지지만 좀 더 고르게 섞인 자식이 나올 수 있다.

균등 교잡

균등 교잡^{uniform crossover}은 $p$ 의 확률로 부, $1-p$ 의 확률로 모의 형질을 골라 자식의 형질을 만든다. 보통 $p = 0.5$ 로 둘테고 자식은 부모의 형질을 고르게 물려받게 된다. 구현도 쉽고 치우치지도 않고 교잡의 의도 자체도 잘 살렸지만 ‘너무 말도 안되는 해’가 나올 가능성이 높다.

내삽 교잡

$$ \mathbf{x} \gets p \mathbf{x}_{a} + (1 - p) \mathbf{x}_{b} $$ 해공간 $X$ 가 벡터공간이라면, 부와 모의 해를 각각 $\mathbf{x}_{a} , \mathbf{x}_{b} \in X$ 라고 할 때 위와 같이 두 해의 중간지점 쯤에 자식을 만들 수도 있다. 이를 내삽 교잡^{intermediate crossover}이라 한다.