📂최적화이론

유전 알고리즘이란?

정의 ¹

$$ \argmax_{\mathbf{x} \in X} f \left( \mathbf{x} \right) $$ 목적 함수 $f : X \to \mathbb{R}$ 를 최대화하는 최적화 문제에서 다음의 세가지 연산^operation을 반복하는 방법을 유전 알고리즘^{genetic algorithm}이라 한다.

• 자연선택^selection: 현재 해집합에서 우수한 해를 선택해 다음 세대의 해집합을 구성한다.
• 교차혼합^crossover: 해집합에서 여러 개의 해를 골라 일부 정보를 교환해 새로운 해를 생성한다.
• 돌연변이^mutation: 해집합에서 일부 해의 정보를 무작위로 변경해 다양성을 확보한다.

설명

유전 알고리즘은 다윈의 진화론에서 적자생존^{survival of the fittest}에 영감을 받은 개체군 메서드로써, 각각의 개체는 염색체^chromosome이라 불리는 벡터 $\mathbf{x} \in X$ 로 표현되며 $f \left( \mathbf{x} \right)$ 와 같이 평가되어 그 함수값 자체를 적합도^fitness로 삼는다. 진화론의 비유에서 $f$ 는 환경^enviroment 그 자체를 의미하며, 우리가 원하는 것은 이 환경에서 가장 잘 살아남는, 즉 $f$ 가 최대가 되는 $\mathbf{x}$ 를 찾는 것이다.

자연선택

진화론에서 자연선택을 설명하는 것과 마찬가지로, 진화라는 것은 어떤 의도를 가지고 기관이나 생리를 발달시키는 것이 아니라 단지 적합도가 떨어지는 개체가 도태되고 적합도가 높은 개체가 살아남는 것이 반복되며 일어나는 현상이다.

유전 알고리즙에서 자연선택이란 단순히 해집합에서 적합도가 낮은 해가 제거되도록 하는 연산으로써 구현되며, 근본적으로 유전 알고리즘이 작동하게끔하는 원동력이기도 하다.

교차혼합

최적화의 관점에서 교차혼합이란 해공간 전체를 넓게 훑기 위한 전역 탐색법으로써, 점진적인 변화가 아닌 급격한 변화를 통해 국소 최적해에 빠지는 것을 방지하는 역할을 한다. 이는 실제 자연에서도 마찬가지로, 주로 기생에 저항하는 전략으로써 설명되는 유성생식이 폭발적인 다양성을 확보하는 데에 유리하다는 점과 맥락을 같이 한다.

돌연변이

돌연변이는 염색체에 작은 변화를 주는 식으로 구현되며, 교차혼합과는 반대로 국소 탐색법의 성격을 가진다. 변이 없이 자연선택만 반복된다면 사실상 세대를 거듭할 필요 없이 첫 세대에서 최종적인 해가 결정되는 것이나 마찬가지고, 실패를 무릅쓰고서라도 조금씩 변화를 주어 더 나은 해를 찾으려는 것이다.