차분 진화 (Differential evolution, DE) 알고리즘은 최적해를 찾기 위한 metaheuristic 기법 중 하나입니다. Metaheuristic 알고리즘들은 global optimal solution으로의 수렴을 보장해주지는 않지만, 제한된 정보와 적은 복잡도를 가지고 상당히 좋은 솔루션을 찾을 수 있다는 장점이 있습니다.
Differential Evolution이란?
DE 알고리즘은 multi-dimensional real-valued 함수의 최적화를 위해 쓰이지만 gradient를 사용하지 않기 때문에 목적 함수가 미분 가능하지 않아도 된다는 특징이 있습니다.
DE 알고리즘은 기본적으로 유전 알고리즘 (Genetic algorithm, GA)와 유사한 구조를 가지고 있습니다. Population이라고 하는 초기 candidate solution 집합을 생성하고, mutation, crossover, selection의 과정을 통해 population이 최적해를 가지도록 candidate solution들을 진화시키는 방식을 사용합니다.
DE 알고리즘은 mutation, crossover 방식에 따라 여러 variant가 존재하지만 DE/rand/1/bin 알고리즘을 기준으로 설명하도록 하겠습니다.
1) Initialization
$NP$ 개의 agent를 가지는 임의의 초기 population을 생성합니다. 각각의 agent $x_i$는 n-dimensional real-valued 목적 함수 $f:\mathbb{R}^n\rightarrow \mathbb{R}$의 candidate solution입니다.
$$ x_i=[x_{1,i},x_{2,i},\dots,x_{n,i}] $$
DE 알고리즘은 아래의 세가지 파라미터를 가집니다.
- $NP\geq 4$ 는 population size입니다. (일반적으로 $10N$을 사용합니다.)
- $CR\in[0,1]$ 는 crossover probability입니다. (일반적으로 $CR=0.9$를 사용합니다.)
- $F\in[0,2]$ 는 differential weight입니다. (일반적으로 $F=0.8$를 사용합니다.)
2) Mutation
각 agent $x_i$마다, 세 개의 agent $x_{r1}$, $x_{r2}$, $x_{r3}$를 population에서 random하게 선택합니다. 이 때, agent $x_i$를 target vector라고 합니다.
$$ v_i=x_{r1}+F(x_{r2}-x_{r3}) $$
그리고 $x_{r1}$을 기준점으로 하여 $x_{r2}$와 $x_{r3}$의 차이를 가중치 $F$만큼 변화시켜준 $v_i$를 donor vector라고 합니다.
3) Crossover
Crossover는 기존 target vector $x_i$와 생성된 donor vector $v_i$의 일부를 교차시켜 trial vector $u_i$를 만들어주는 과정입니다.
$$ u_{j,i}=\begin{cases} v_{j,i} & \text{if $rand(0,1)<CR$} \\ x_{j,i} & \text{otherwise} \end{cases} $$
n-dimensional vector의 각각의 차원 $j$ 마다 [0,1]사이의 확률을 뽑아 CR보다 작으면 mutation된 값을 선택하고, CR보다 크면 mutation되지 않은 값을 선택합니다.
4) Selection
생성된 trial vector $u_i=[u_{1,i},u_{2,i},\dots,u_{n,i}]$을 기존 agent $x_i$를 대체하여 population에 새로 추가할지를 결정하는 단계입니다.
$$ x_i\leftarrow u_i ~~~\text{if $f(u_i)\leq f(x_i)$} $$
Trial vector $u_i$를 목적함수 $f$를 통해 평가하고 기존 agent $x_i$보다 좋다면 이를 대체합니다. (※ Minimization problem을 가정하면 $f(u_i)\leq f(x_i)$ 조건을 만족해야 합니다.)
위의 2~4 과정을 모든 agent $x_i$마다 수행하는 것이 하나의 루프이고, DE 알고리즘은 이를 종료 조건까지 반복수행하여 최적해를 찾아냅니다.
DE Algorithm (DE/rand/1/bin)
앞에서 설명한 DE/rand/1/bin 알고리즘의 pseudo-code는 아래와 같습니다.
DE 알고리즘은 mutation, crossover 방식에 따라 여러 variant가 존재한다고 하였습니다. 예를 들어, mutation을 생성할 시 기준점인 $x_{r1}$을 현재 population에서 가장 좋은 agent를 선택하면 'best' 이며, muation의 차를 구할 때 한 개가 아닌 두 개의 차를 이용하면 '2' , crossover 방법이 binomial이 아니라 exponential이면 'exp' 이라 DE/best/2/exp와 같이 표현할 수 있습니다. scipy 패키지에서는 다양한 variant를 제공하며 default는 DE/best/1/bin으로 설정되어 있습니다.
References
[1] https://en.wikipedia.org/wiki/Differential_evolution
[2] https://zapary.blogspot.com/2021/01/differential-evolution.html
오타나 잘못된 부분 있으면 댓글 부탁드립니다. 도움이 되셨다면 공감 눌러 주시면 감사하겠습니다 :)
댓글