📂최적화이론

유전 알고리즘에서 자연선택이란?

정의

유전 알고리즘에서 자연선택^{natural selection}, 혹은 그냥 간단한게 선택이란 목적 함수의 값이 더 좋은 개체를 고르는 연산을 말한다.

설명 ¹

유전 알고리즘은 적자생존에서 영감을 받은 기법이니만큼, 자연선택은 진화 그 자체의 원동력이며 최적화의 성능에 직접적인 영향을 미친다. 여기서 선택이란 우리가 최대화하고 싶은 목적 함수 $f$ 그 자체가 ‘환경’이 되어 $f$ 에 적합한 개체가 생존되는 것으로 ‘선택’받는 것을 의미한다.

자연선택의 전형적인 구현은 룰렛 휠^{roulette wheel} 방식으로써, 각각의 개체 $\mathbf{x}_{k}$ 별로 적합도 $f \left( \mathbf{x}_{k} \right)$ 를 계산해서 적합도가 높을수록 선택될 확률이 높아지도록 하는 것이다. 개체별로 적합도를 기반으로 하는 기대값^{expected value} $E_{k}$ 라는 가중치를 주고 비복원추출을 통해 일부만 샘플링해서 다음 세대로 넘기고, 나머지는 도태시킨다.

볼츠만 선택

해집합의 기수가 $N$ 이라고 하자.

소프트맥스 함수의 정의: $\mathbf{x} := (x_{1} , \cdots , x_{n}) \in \mathbb{R}^{n}$ 이라고 하자. $\displaystyle \sigma_{j} ( \mathbf{x} ) = {{ e^{x_{j}} } \over {\sum_{i=1}^{n} e^{x_{i}} }}$ 에 대해 $\sigma ( \mathbf{x} ) := \left( \sigma_{1} (\mathbf{x}) , \cdots , \sigma_{n} (\mathbf{x} ) \right)$ 와 같이 정의된 $\sigma : \mathbb{R}^{n} \to (0,1)^{n}$ 을 소프트맥스^softmax라 한다.

$$ E_{k} = {\frac{ e^{ f ( \mathbf{x}_{k} ) / T } }{ \sum_{i=1}^{N} e^{ f ( \mathbf{x}_{i} ) / T } }} \qquad , k = 1, \cdots , N $$ 기본적으로 $f : X \to \mathbb{R}$ 은 음수가 될 수도 있으므로, 이들을 양수로 만드는 가장 간단한 아이디어는 소프트맥스를 취하는 것이다. 원래 소프트맥스와 달라진 것은 하이퍼파라미터 $T > 0$ 가 추가된 점인데, 이는 온도^temperature라 불리며 선택압^{selection pressure}을 조절하는 역할을 한다. 이는 2020년대 이후로 주목받는 LLM^{Large Language Model}의 ChatGPT에서도 볼 수 있는 아이디어인데, 온도 $T$ 가 높아질 수록 $\exp \left( f \left( x_{k} \right) / T \right) \to 1$ 이 되어 유니폼하게 샘플링이 일어나 적합도 그 자체보다는 하이퍼 파라미터에 영향을 많이 받는다. 반대로 온도 $T$ 가 낮아지면 적합도의 영향력이 커진다.

이렇게 소프트맥스와 온도를 도입한 선택 방식을 볼츠만 선택^{Boltzmann selection}이라 하고, 그 이름은 딱 봐도 알 수 있듯이 볼츠만 분포에서 따온 것이다. 선택의 방식으로 룰렛 휠을 사용하겠다면 가장 상식적이고 무난한 방법이다.

랭크 선택

랭크 선택^{rank selection}이란 적합도의 랭크, 즉 순위를 통해 기대값을 주는 방식이다. 이 방식은 직접적으로 적합도를 사용하지 않고 하이퍼파라미터도 따로 없으므로 $f$ 에 대해 잘 모르더라도 일관되게 적용가능한데, 예를 들자면 최적화해야할 $f$ 자체가 많을 때 유용할 수도 있고 해집단에서 적합도의 양극화를 어느정도 완화하는 효과가 있을 수도 있다.