MATLAB의 particleswarm 함수로 최적화 문제 풀기(Particle Swarm Optimization)

1. Particle Swarm Optimization(PSO)이란?

 Particle swarm optimization(PSO)은 새 무리와 물고기 떼와 같은 동물 무리들의 집단적인 행동 양상을 모방하여 최적화 문제를 푸는 알고리즘으로 Nature-inspired search method(자연에서 영감을 받은 최적점 찾는 방법이라는 뜻) 중 하나이다. 일반적으로 이런 nature-inspired search method는 함수 계산량이 많지만 global minimum(전역 최솟점)에 수렴하는 것으로 알려져 있다.

 PSO 알고리즘 내에서는 particle, particle position(design point), particle velocity(design change), swarm leader(a design point having the smallest value)와 같은 개념들이 있다. 알고리즘 자체는 Genetic Algorithm(GA)와 비슷한 면이 있지만, 사람이 직접 정해주어야 하는 parameter(hyperparameter라고 한다.)가 GA보다 더 적다는 장점이 있다. 여기에서는 PSO 자체에 대한 설명보다는 MATLAB 함수인 particleswarm을 통해 최적화하는 방법을 간단히 소개하는 것이 목적이기 때문에 알고리즘 자체에 대한 구체적인 설명은 생략한다. 다만 PSO에 대한 이해가 있으면 보다 정교한 함수 사용이 가능하기 때문에 보다 전문적으로 particleswarm 함수를 사용하고자 한다면 PSO에 대한 공부가 필수적이다. 다만 본 글에서는 단지 particleswarm 함수를 통해 전역 최적화(global optimization)을 수행하고자 하는 분들을 위해 간단한 함수 사용 방법에 대해서 설명하겠다.

 위에서 언급했듯이 PSO와 같은 nature-inspired search method는 일반적으로 전역 최솟점에 수렴한다고 알려져 있다. 하지만 100% 보장되어 있는 것도 아니라는 점을 유념하자. 아무튼 전역 최솟점으로 수렴한다고 알려져 있기 때문에 particleswarm 함수는 MATLAB에서도 Global Optimization Toolbox에 포함되어 있다. 즉, Global Optimization Toolbox를 설치해야 사용할 수 있는 함수이다.

2. particleswarm 함수 기본적인 설명

 해당 Toolbox를 설치한 후 명령 창에 'help particleswarm'를 입력하면 particleswarm에 대한 사용 방법에 대해서 설명이 나와있다. 아래 링크를 통해 그 설명을 확인할 수 있다.

https://kr.mathworks.com/help/gads/particleswarm.html

해당 링크에서 설명하는 기본적인 설명은 다음과 같다.

1) 기본 문법(syntax)

x = particleswarm(fun, nvars)

x = particleswarm(fun, nvars, lb, ub)

x = particleswarm(fun, nvars, lb, ub, options)

x = particleswarm(problem)

[x, fval, exitflag, output] = particleswarm(___)

2) input 변수 설명

- fun: 최적화할 함수 즉, 목적 함수(objective function, cost function)을 의미한다. 주로 m 파일로 함수를 정의한 후 함수 핸들('@함수이름') 형태로 입력한다.(하단 예제 참고)

- nvars: input variable(input 변수)의 갯수를 의미한다. 즉, input variable x의 차원(dimension)을 뜻한다.

- lb(lower bound): 벡터 x의 각 구성요소들의 최솟값을 의미한다.

- ub(upper bound): 벡터 x의 각 구성요소들의 최댓값을 의미한다.

- options: 최적화에 사용되는 다양한 설정들을 변경할 수 있도록 하는 변수이다. optimoptions로 정의된 struct 구조체 배열을 입력하면 된다.

3) output 변수 설명

- x: 최적의 x값 즉, optimum solution(최적해)을 의미한다.

- fval: optimum solution에서의 목적 함수(objective function, cost function)의 값을 의미한다.

- exitflag: 종료 상황을 설명하는 값이다. 양수면 특정 수렴 조건이 만족해 정상적으로 종료된 것을 의미하고 음수면 제대로된 최적해를 찾지 못하고 종료된 것을 의미한다. 또한 정해진 iteration이 돼서 종료된 경우 0의 값을 갖는다. 더 자세하고 다양한 exitflag 값의 의미들은 위 링크를 참고하길 바란다.

- output: iteration 수, 목적 함수 evaluation 수 등 최적화 과정에 대한 정보를 담은 struct 구조체 배열이다.

3. particleswarm 함수로 최적화 문제 풀기

1) 기본

 이전에 다뤘던 fmincon과 ga 함수와는 다르게 particlaswarm에서는 constraint를 입력으로 받지 않는다. 이 경우 이미 정의된 목적 함수와 constraint 함수를 이용해서 penalty function을 정의한 후 그 함수를 목적 함수로 입력해주면 된다. 우선 목적 함수(Objective/Cost function) 및 constratin 함수는 주로 m파일로 따로 정의해서 사용한다. 함수의 구성 예시는 fmincon 설명 글을 참고하기 바란다.

 penalty function를 어떻게 정의하는지는 조금씩 다르지만 여기에서는 아래와 같이 정의한다.

Φ(x) = f(x) + R*V(x)

 여기에서 f(x)는 목적 함수이고, R은 상수 값으로 보통 Lagrangian multiplier를 고려해서 입력하지만 그냥 매우 큰 수(대충 1000000)를 넣는다고 생각하면 된다. V(x)는 아래와 같이 정의된다.

V(x) = max(|h(x)|, g(x), 0)

 여기에서 h(x)와 g(x)는 각각 equality constraint 함수와 inequality constraint 함수를 의미한다. 식에서 볼 수 있듯이 constraint 함수가 부등식 조건의 경우 0보다 크고, 등식 조건의 경우 0이 아닌 경우 R값이 곱해지면서 penalty function의 값을 매우 크게 증가시키는 것을 확인할 수 있다. 그러므로 penalty function을 최소화 하기 위해서 constraint 함수를 만족시키도록 강제할 수 있다. 이는 constrained 문제를 unconstrained 문제로 변환해서 푸는 대표적인 방법 중 하나이다. penalty function을 어떻게 구현하는지는 아래 예제를 통해서 설명한다.

2) 예제

 해당 문제는 fmincon 설명 글의 예제 2와 동일하다. 그러므로 목적 함수 정의 및 constraint 함수 정의 부분은 생략한다.

* 이미 정의된 목적 함수(ObjFunc)와 constraint 함수(ConstFunc)을 통해서 Penalty function(PenaltyFunc) 정의하기

% PenaltyFunc.m file

function f = PenaltyFunc(x, R)

obj = ObjFunc(x); % 목적 함수

[const_ineq, const_eq] = ConstFunc(x); % constraint 함수

V = max([const_ineq, const_eq, 0]);

f = obj + R*V;

end

* particleswarm 함수를 사용해 최적화하기

% Set bounds and parameter

 Lb = []; Ub = [];

 R = 10000000;

% PSO

 [x_PSO, Funval_PSO, ExitFlag, Output] = particleswarm(@(x) PenaltyFunc(x, R), 2, Lb, Ub)

최적화 결과를 보면 fmincon을 사용해 최적화한 결과와 동일한 것을 확인할 수 있다.