최적설계 | 자연 영감 탐색법(1): 유전 알고리즘 GA

1. 자연 영감 탐색법

   자연 영감 탐색법은 임의의 초기 설계점을 시작으로 확률적으로 최적점으로 접근하는 방법이다. 지금까지 다룬 방법론과는 다르게 국소 최소점이 아닌 전역 최소점으로 수렴하는 경향을 보이며, 탐색 과정에서 경사도를 필요로 하지 않기 때문에 연속변수, 이산변수, 미분 불가능 함수 등 모든 종류의 최적 문제에 적용할 수 있다. 하지만 수학적인 엄밀함 없이 확률적으로 탐색하기 때문에 동일한 조건에서 탐색을 시작하더라도 항상 동일한 결과를 도출하지 않으며, 도출된 결과가 전역적으로 최적해라는 보장은 없다. 물론 이러한 단점은 탐색을 여러 번 수행하는 것으로 보완할 수 있다.
 

2. 유전 알고리즘

유전 알고리즘

   유전 알고리즘(genetic algorithm, GA)은 각 설계변수에 허용된 값들을 무작위로 선택하여 여러 개의 설계대안을 생성하는 것으로 시작한다. 이때 설계변수의 값을 유전자(gene), 유전자의 집합인 설계대안을 염색체(chromosome), 염색체의 집합인 여러 개의 설계대안을 인구(population), 알고리즘의 반복 단계를 세대(generation)로 정의하여 취급한다. 

 

2.1. 설계 표시

 

설계 표시

   유전 알고리즘을 적용하기에 앞서 무작위로 생성된 설계대안을 이진법 문자열로 부호화한다. 이때 이진법 문자열은 각 설계변수에 허용하는 값의 개수보다 큰 값을 기준으로 나타낸다. 예를 들어, 한 설계변수가 10개의 값을 허용한다면 해당 설계변수를 부호화하기 위해 16가지 표현을 나타낼 수 있는 네 자리의 이진법 문자열을 사용한다. 이처럼 m자리의 이진법 문자열은 2^m가지의 이산값을 부호화하여 표시하는 데 적용할 수 있으며, 설계변수에 허용하는 값의 개수가 N_c라면 2^m > N_c여야 한다. j번째가 N_c보다 크다면 아래 식을 이용하여 j ≤ N_c가 되도록 조정한다.

 

$$ \begin{align} j = INT\left(\frac{N_c}{2^m-N_c}\right)\left(j-N_c\right) \end{align}$$

 

2.2. 적합성 함수 

   적합성 함수(fitness function)은 해당 설계대안이 최적점으로 얼마나 적합한지 정의한다. 비제약조건 문제에서는 목적함수를, 제약조건 문제에서는 벌칙함수를 사용하여 정의하며, 설계대안을 적합성 함수에 대입하였을 때 높은 적합성 값이 나올수록 더 좋은 설계를 의미한다. 적합성 함수는 여러 가지 다양한 방식으로 정의될 수 있는데, 목적함수 혹은 벌칙함수를 이용하여 정의하면 아래와 같다. f_i는 i번째 설계대안에 대한 목적함수 또는 벌칙함수 값이고, f_max는 현재까지 기록된 가장 큰 목적함수 또는 벌칙함수 값이다.

 

$$ \begin{align} F_i = \left(1+2\times10^{-7}\right)f_{max} - f_i \end{align}$$

 

   무작위로 생성되어 이진법 문자열로 표시된 초기 세대를 시작으로, 적합성 함수를 통해 각 설계대안을 검토하고 적합도가 높은 대안들을 지정한다. 선택한 대안들을 대상으로 ▲재생, ▲교차, ▲변이 과정을 거쳐 이전 세대보다 더 적합한 성향을 가진 새로운 세대를 생성한다. 해당 과정은 종료 기준이 만족되거나 사전에 명시한 반복 횟수를 초과하면 종료된다.

 

3. 재생

재생

   재생(reproduction)은 현재 인구에서 설계대안을 선택하여 다음 세대로 복사하는 과정이다. 해당 과정에서 설계대안은 확률적으로 선택되며, 그 확률 P_i는 적합성 함수의 값 F_i를 기반으로 아래와 같이 결정된다. 아래 식에서 N_p는 인구의 크기를 의미하며, 높은 적합성을 갖는 개체들이 다음 세대로 복사될 가능성이 더 크다.

 

$$ \begin{align} P_i = \frac{F_i}{\sum_{j=1}^{N_p}F_j} \end{align}$$

 

4. 교차

교차

   교차(crossover)는 재생 과정을 통해 선별된 설계대안을 대상으로 서로의 특성을 교환하기 위해 무작위로 혼합하는 과정이다. 해당 과정을 수행하기 위한 보편적인 방법으로 일절단점과 이절단점이 있다. 일절단점은 무작위로 선택된 두 설계대안을 대상으로 분리할 위치를 무작위로 선정한 뒤 자르고 교환하여 새로운 설계대안을 구성한다. 이절단점은 분리할 위치 두 지점을 무작위로 선정하여 자르고 교환한다.

 

5. 변이

변이

   변이(mutation)는 교차 과정을 마친 인구에서 소수의 설계대안을 무작위로 선택한 뒤, 설계대안을 표현한 이진법 문자열에서 무작위 위치에 있는 숫자를 반대로 바꾸는 과정이다. 이는 재생과 교차 과정을 거치면서 가치있는 설계대안이 너무 일찍 사라지는 경우를 방지하기 위한 안전 장치이다.

 

 

 

 

 

[함께 읽으면 좋은 페이지]

 

최적설계 | 파이썬 기반 유전 알고리즘 pygad.GA

 

 

 

 

 

참고문헌

- Arora, J. S. (2016). Introduction to optimum design. Elsevier.