MATLAB의 ga 함수로 최적화 문제 풀기(Genetic Algorithm)

1. Genetic Algorithm이란?

 GA(Genetic Algorithm)는 생물학적 진화 과정을 모방하여 최적화 문제를 푸는 알고리즘으로 Nature-inspired search method(자연에서 영감을 받은 최적점 찾는 방법이라는 뜻) 중에서 가장 유명한 방법이라고 할 수 있다. 특히 discrete variable(이산적인 변수)에 대해서도 최적화가 가능하고, 일반적으로 global minimum(전역 최솟점)에 수렴하는 것으로 알려져 있기 때문에 많은 최적화 관련 연구에서 널리 사용되고 있다.

 GA는 생물학적 진화 과정을 모사했기 때문에 생물학적 용어에 비유한 개념(population, generation, chromosome, gene 등)과 연산(reproduction, crossover, mutation 등)이 알고리즘 내에서 수행된다. 하지만 여기에서는 GA 자체에 대한 설명보다는 MATLAB 함수인 ga를 통해 최적화하는 방법을 간단히 소개하는 것이 목적이기 때문에 알고리즘 자체에 대한 구체적인 설명은 생략한다. 다만 GA에 대한 이해가 있으면 보다 정교한 함수 사용이 가능하기 때문에 보다 전문적으로 ga 함수를 사용하고자 한다면 GA에 대한 공부가 필수적이다. 다만 본 글에서는 단지 ga 함수를 통해 전역 최적화(global optimization)을 수행하고자 하는 분들을 위해 간단한 함수 사용 방법에 대해서 설명하겠다.

 위에서 언급했듯이 GA는 일반적으로 전역 최솟점에 수렴한다고 알려져 있다. 하지만 100% 보장되어 있는 것도 아니고, GA 특성 상 random process를 내포하고 있기 때문에 같은 최적화 문제여도 매 시행마다 최적화 결과가 달라질 수 있다는 점을 유념하자. 아무튼 전역 최솟점으로 수렴한다고 알려져 있기 때문에 ga 함수는 MATLAB에서도 Global Optimization Toolbox에 포함되어 있다. 즉, Global Optimization Toolbox를 설치해야 사용할 수 있는 함수이다.

2. ga 함수 기본적인 설명

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

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

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

1) 기본 문법(syntax)

x = ga(fun, nvars)

x = ga(fun, nvars, A, b)

x = ga(fun, nvars, A, b, Aeq, beq)

x = ga(fun, nvars, A, b, Aeq, beq, lb, ub)

x = ga(fun, nvars, A, b, Aeq, beq, lb, ub, nonlcon)

x = ga(fun, nvars, A, b, Aeq, beq, lb, ub, nonlcon, options)

[x, fval] = ga(___)

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

2) input 변수 설명

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

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

- A: 선형 부등식에서의 행렬을 의미한다.

- b: 선형 부등식에서의 벡터를 의미한다.

  -> 즉, A*x≤b

- Aeq: 선형 방정식에서의 행렬을 의미한다.

- beq: 선형 방정식에서의 벡터를 의미한다.

  -> 즉, Aeq*x=beq

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

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

- nonlcon: 비선형(nonlinear)인 constraint 함수를 의미한다.

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

※ linear constraint가 없으면 A, b, Aeq, beq는 [ ]로 처리한다.

3) output 변수 설명

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

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

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

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

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

1) 기본

목적 함수(Objective/Cost/Fitness function) 및 constraint 함수는 주로 m파일로 따로 정의해서 사용한다. 각각의 구성 예시는 fmincon 설명 글을 참고하기 바란다.

2) 예제 1 - linear constraint 문제

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

* ga 사용하기

fun = @ObjFunc;

A = [2, 3; 2, 1];

b= [12; 8];

Aeq = [];

beq = [];

lb = [0, 0];

ub = [inf, inf];

[x, fval] = ga(fun, 2, A, b, Aeq, beq, lb, ub)

3) 예제 2 - nonlinear constraint 문제

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

* ga 사용하기

Lb = []; Ub = [];

[x, Funval, ExitFlag, Output] = ga(@ObjFunc, 2, [ ], [ ], [ ], [ ], Lb, Ub, @ConstFunc)