📂최적화이론

유전 알고리즘에서 돌연변이란?

용어 ¹

유전 알고리즘에서 돌연변이^mutation, 혹은 그냥 간단한게 변이란 개체의 염색체에 주로 무작위적으로 변화를 주는 연산을 말한다.

설명

만약 개체가 교차혼합만을 통해 태어난다면, 초기 무작위 집단에 존재하지 않았던 형질들은 결코 발생할 수 없다. 변이와 자연선택은 실제 진화에 있어서도 가장 중요한 두 축이며, 유전 알고리즘에서도 마찬가지로 변이는 해집단의 다양성을 유지하고 새로운 형질을 도입하는 역할을 한다.

비트 반전

$$ x_{k} ! = x_{k} $$ 해집합이 $\left\{ 0 , 1 \right\}^{n}$ 과 같이 비트로 표현이 되는 경우, 변이를 구현하는 가장 간단한 방법은 무작위로 일부 위치를 골라서 비트를 반전시키는 것이다.

균등 대체

$$ x_{k} = U [ a , b ] $$ 좌표로 표현되는 연속적인 값들로 표현되는 염색체의 특정 차원이 상한과 하한을 가져서 구간 $[a , b]$ 에 속한다고 하면, 돌연변이는 비트 반전처럼 몇번째 위치의 값을 바꿀지를 먼저 고른 후 균등분포 $U [ a, b ]$ 를 따르는 무작위 수를 뽑는 식으로도 일으킬 수 있다.

가우시안 변이

$$ \mathbf{x} += \mathcal{N} ( \mathbf{0} , \Sigma ) $$ 좌표에 별도의 바운드가 없는 경우, 브라운 모션처럼 다변량정규분포를 따르는 인크리먼트를 계속 추가하는 방식의 구현이 가장 상식적이다. 다만 이 방법은 좌표별로 변이의 강도가 다를 수 있기 때문에 이를 조정하는 하이퍼파라미터 $\Sigma$ 에 대해 파악하는 과정이 필요하다.

레비 점프

레비 비행을 통해 해집합이 움직이는 방식으로 변이를 일으키는 방법도 있다. 이러한 변이는 해공간을 넓게 탐색하고 싶을 때, 폭발적인 돌연변이를 일으키고 싶을 때 유용하다.

보통은 다변량 코시분포를 사용할텐데, 주의해야할 것은 정규분포를 따르는 확률변수의 벡터가 곧 다변량정규분포를 따르는 것과 달리 t-분포를 따르는 확률변수의 벡터는 다변량 t-분포를 따르지 않으므로 정확히 다변량 t-분포에서 자유도를 $1$ 로 주어 다변량 코시분포를 만들어야 한다는 점이다.

실제로 필자도 이 팩트를 몰라서 헤맸던 적이 있다.