📂최적화이론

유전 알고리즘에서 미분 진화란?

용어 ¹

유전 알고리즘에서 미분 진화^{differential evolution}이란 돌연변이를 일으킬 때 특정한 방향^direction을 주는 전략을 말한다.

설명

방향을 준다는 것에서 짐작할 수 있듯, 미분 진화는 그 자체로 경사하강법과 비슷한 아이디어에서 출발한다. 목적 함수가 미분 가능하다면 변이 자체를 도함수의 방향으로 일으킬 수 있고, 미분을 위한 비용이 너무 과하거나 미분을 할 수 없는 경우에는 문제에 따라 여러가지 전략을 시도해볼 수 있다².

미분은 할 수 없지만 함수의 평가^evaluation이 크게 부담되지 않는다면, 해집합이 벡터공간일 경우 다음과 같이 무작위로 선택한 해들 간의 차이를 이용해 변이 방향을 정할 수 있다:

1. 개체 중 $\mathbf{a}, \mathbf{b}, \mathbf{c}$ 를 무작위로 선택한다.
2. 하이퍼파라미터 $w \in \mathbb{R}$ 에 대해 임시 벡터 $\mathbf{z} = \mathbf{a} + w(\mathbf{b}-\mathbf{c})$ 를 계산한다.
3. $\mathbf{z}$ 와 $\mathbf{a}$ 를 비교해서 $\mathbf{z}$ 의 적합도^fitness가 더 높은 경우, $\mathbf{a}$ 를 $\mathbf{z}$ 로 대체한다.

여기서 $\mathbf{b}-\mathbf{c}$ 는 정확하게 미분의 의미가 된다기보다는, 매니폴드의 형태를 전혀 알 수 없는 목적함수를 공략함에 있어서 ‘말이 되는 방향’이라는 정도의 의미가 있다. 예를 들어, 모든 차원에서 1만큼 증가하는 벡터같은 건 아니고 유전 알고리즘의 순환 속에서 실제로 발견될 수 있다는 게 중요하다.