Evolutionary strategy 1 - Simple Gaussian Evolution

최근 RL관련 논문이나 구루들의 토의 영상들을 보면 evolution strategy(혹은 evolution algorithm)이란 단어가 심심치 않게 등장한다. Evolution algorithm은 Black box optimization의 일종이다. Black box optimization은 우리가 최적화 하고자 하는 함수의 전체적인 형태는 알 수 없지만 입력에 대한 출력은 확인 할 수 있는 함수(evaluation만 가능한 black box)에 대해 우리가 원하는 최적 인풋을 찾는 기법을 말한다. 기존의 딥러닝 기법들은 경사도 기반 기법(gradient descent 등)들을 주로 사용하여 loss 함수를 최적화하는 것을 통해 학습을 진행해 왔다. Black box optimization이 이와 좀 다른 점은 함수의 gradient$\bigtriangledown f(x)$나 hessian${\bigtriangledown}^2 f(x)$을 직접적으로 구하지 않고도 원하는 최적화를 이뤄낸다는 점이다. Black box optimization에는 Evolutionary Algorithm, Heuristic algorithm, Global/Local modeling 등 다양한 접근들이 존재한다. 오늘은 Evolutionary algorithm의 가장 간단한 경우를 알아본다.

Black box optimization formulation

Evolutionary Algorithm

Evolutionary algorithm의 가장 기본적인 아이디어는 자연서택에 의한 최적화이다. 자연선택은 자연계에서 생물 종들이 생존이라는 objective 함수를 최대화 할 수 있는 개체는 살아남고 그 개체들이 자신의 특성을 보유한 자손들을 남기는 식으로 점점 환경에 어울리는 개체들이 종을 이루게 된다는 이론이다.

(자연선택)교과서에서 자주 보이는 그림

Evolutionary algorithm은 이런 이론에서 아이디어를 얻어 최적화 기법에 적용하는 전략이다. Evolutionary algorithm은 딱 정해진 하나의 알고리즘은 아니고 일반적인 프레임워크(Stochastic search)가 존재하고 각 스텝부분에 어떤 변화를 주냐에 따라 여러가지 알고리즘들로 나뉘어 진다. 그 유명한 Genetic Algorithm(유전 알고리즘)도 Evolutionary algorithm계열의 일종이다.

General recipe

Stochastic Search 프레임웍

 일반적인 프로세스를 단계별로 설명해보자면 

1. 알고리즘에 사용할 고정된 확률 분포 $p_{\theta}(x)$를 결정한다.

2. N개의 데이터 샘플을 $p_{\theta}(x)$에서 샘플링한다. $\left\{x_{i}\right\}_{i=1}^{n} \sim p_{\theta}(x)$

3. 샘플링 된 데이터 $x$에 대한 evaluation을 진행하고 대이터 셋을 구한다. $\left\{\left(x_{i}, f\left(x_{i}\right)\right)\right\}_{i=1}^{n}$

4. 고안한 휴리스틱 기법을 이용하여 파라미터를 업데이트한다. $\theta \leftarrow h(\theta, D)$

5. 위 과정들을 $\theta$가 수렴할 때 까지 반복

 

여기서 파라미터 $\theta$는 최적 솔루션에 대한 특성을 다음 세대로 전달하는 역할을 한다. 

 

Gaussian search distribution [$(\mu, \lambda)$-ES]

Evolutionary algorithm중 가장 간단한 버전을 알아본다. 

위 알고리즘은 탐색을 위한 확률 분포를 정규 분포로 고정하고(step1) 파라미터를 업데이트하는 휴리스틱을 objective에 대한 최고의 값 만을 정규분포의 평균값으로 가져가는(step 4) 알고리즘이다. 

 

Implementation

가장 간단한 경우에 대한 구현을 해보았다. 함수 $f(x)$는 2D target point에 대한 거리를 나타내는 함수로 정하고 이 것을 최소화하는 것을 목표로 하는 코드를 작성했다.

 

# Gaussian search distribution (mu lambda ES)
from matplotlib import pyplot as plt
import numpy as np

# Configuration
theta=[0.0, 0.0]    
mu_=100              # Mu (Parameter of "species")
lambda_= 5000        # Lambda (offspring)
target=[100.0, 100.0]
var=1.0
step=1

assert isinstance(theta, list) and len(theta)==2,"theta should be 2D list"
assert isinstance(target, list) and len(target)==2, "target point should be 2D list"

cov = [[var, 0], [0, var]]
theta = np.array(theta)
target = np.array(target)


while np.linalg.norm(theta-target, ord=2)>=0.01:
    # Plot
    if step%5==0:
        plt.plot(sampled_theta[:,0],sampled_theta[:,1],'x',label='theta')
        plt.plot(target[0], target[1], 'ro', label='target')
        plt.title('Step:'+str(step))
        plt.xlim([-5,105])
        plt.ylim([-5,105])
        plt.legend()
        plt.show()
        
    # Sample data from distribution model
    sampled_theta = np.random.multivariate_normal(theta, cov, lambda_) # x ~ p_t(x) = N(x|x_hat, sigma^2)

    # Evaluate Samples
    loss = np.linalg.norm(sampled_theta-target,ord=2,axis=1)

    # dataset D
    D = np.concatenate((sampled_theta,loss[:,None]),axis=1)
    
    
    # Update D' by select mu best from D
    D_prime = np.copy(D)
    best_idx = []
    loss_=D_prime[:,-1]
    for i in range(mu_):
        best_idx.append(loss_.argmin())
        loss=np.delete(loss_,loss_.argmin())
    D_prime = D_prime[np.array(best_idx)]
    
    # Update heuristic
    theta = D_prime[D_prime[:,-1].argmin()][:-1]
    
    step += 1
    
plt.plot(sampled_theta[:,0],sampled_theta[:,1],'x',label='theta')
plt.plot(target[0], target[1], 'ro', label='target')
plt.title('Step:'+str(step))
plt.xlim([-5,105])
plt.ylim([-5,105])
plt.legend()
plt.show()

Result

사용하는 샘플 데이터 갯수가 많을 수록 수렴속도는 더 빨랐다.

 

출처:

[1] https://lilianweng.github.io/lil-log/2019/09/05/evolution-strategies.html

[2] https://ipvs.informatik.uni-stuttgart.de/mlr/marc/teaching/13-Optimization/06-blackBoxOpt.pdf