유전 알고리즘은 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 최적화 방법이다. 유전 알고리즘은 이론적으로 전역 최적점을 찾을 수 있으며, 수학적으로 명확하게 정의되지 않은 문제에도 적용할 수 있기 때문에 다양한 응용에서 매우 활발히 이용되고 있다. 일반적으로 유전 알고리즘에 대해 알고리즘이라는 표현을 이용하지만, 유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 최적화 문제를 풀기 위한 일반적인 방법론에 가깝다. 즉, 모든 문제에 적용 가능한 하나의 알고리즘이나 소스 코드가 있는 것이 아니기 때문에 유전 알고리즘의 원리를 이해하고, 이를 자신이 원하는 문제에 적용할 수 있도록 설계하는 것이 중요하다. 유전 알고리즘에서는 아래와 같은 개념을 바탕으로 알고리즘이 전개된다.
- 염색체 (Chromosome): 생물학적으로는 유전 물질을 담고 있는 하나의 집합을 의미하며, 유전 알고리즘에는 하나의 해 (solution)를 표현한다. 어떠한 문제의 해를 염색체로 인코딩 (encoding)하는 것에 대한 예시는 항목 4에서 자세히 서술한다.
- 유전자 (Gene): 염색체를 구성하는 요소로써, 하나의 유전 정보를 나타낸다. 어떠한 염색체가 [A B C]로 정의된다면 이 염색체에는 각각 A, B, C로 3개 값을 갖는 유전자로 구성되는 것이다.
- 적합도 (Fitness): 어떠한 염색체가 갖고 있는 고유값으로써 해당 문제에 대해 염색체가 표현하는 해가 얼마나 적합한지를 나타낸다. 예를 들어, 어떠한 경로를 이동하는 비용을 최소화하기 위해 유전 알고리즘을 적용한다면, 염색체의 적합도는 비용의 역수가 될 것이다.
유전 알고리즘은 현재 시점에 존재하는 염색체들의 집합으로부터 적합도가 가장 좋은 염색체를 선택하고, solution space에서 선택된 염색체가 나타내는 방향으로 탐색을 반복하면서 최적해를 찾아간다. 유전 알고리즘의 동작을 단계별로 정의하면 아래와 같다.
- 초기 염색체 집합 생성
- 초기 염색체들에 대한 적합도 계산
- 현재 염색체들로부터 자손들을 생성
- 생성된 자손들의 적합도 계산
- 종료 조건 판별
- 종료 조건이 거짓인 경우, 생성된 자손을 새로운 염색체로 설정하고 C 단계로 이동하여 반복
- 종료 조건이 참인 경우, 가장 높은 적합도의 염색체를 반환하고 알고리즘을 종료
B 단계의 적합도 계산에서는 하나의 염색체에 대한 적합도를 계산한다. 적합도를 계산하는 함수는 정해져있는 것이 아니라 연구자가 풀고자 하는 문제에 맞게 설계해야한다. 만약 하나의 염색체가 예측 모델의 매개변수를 나타낸다면, 해당 매개변수를 갖는 모델의 예측 정확도를 기반으로 적합도 함수를 정의할 수 있을 것이다.
적절한 적합도 함수를 설정했다면 나머지 과정은 비교적 정형화되어있다. 그러나 유전 알고리즘이 계속 연구되면서 C 단계에서 더 효과적인 자손 생성 방법들이 개발되었는데, 다음 항목에서는 유전 알고리즘의 기본적인 연산과 함께 효과적인 자손 생성을 위한 몇가지 기법에 대해 설명한다.
유전 알고리즘을 컴퓨터에서 실행 가능한 형태로 구현하기 위해서는 아래와 같은 5개의 연산을 연구자가 정의해야한다.
- 초기 염색체 생성 연산
- 적합도 계산 함수
- 적합도 기반의 염색체 선택 연산
- 선택된 염색체에 대한 자손 생성 연산
- 돌연변이 (mutation) 생성 연산
유전 알고리즘의 각 연산에 대해서는 아래에서 자세히 설명한다. 그러나 아래의 설명은 유전 알고리즘에서 일반적으로 이용되는 하나의 예시들을 설명한 것이며, 필요에 따라서는 해결하고자 하는 문제에 적합한 구현으로 대체할 수 있다.
3.1. 초기 염색체 생성 연산
알고리즘의 시작에서는 어떠한 염색체도 존재하지 않는 상태이기 때문에 초기 염색체를 생성하는 연산을 별도로 정의해야 한다. 유전 알고리즘에서 가장 많이 이용되는 방법은 solution space 내에서 임의의 값으로 염색체를 생성하는 것이다. 예를 들어, 파이썬으로 작성된 아래의 코드와 같이 초기 염색체 생성 연산을 구현할 수 있다.
import numpy
init_chrm = numpy.random.randint(MAX_VAL_SOLUTION + 1, size=(N_CHRM, DIM_SOLUTION))위의 코드는 각 요소가 {0, 1, ..., `MAX_VAL_SOLUTION`} 내에서 무작위로 생성된 정수를 갖는 `N_CHRM`개의 염색체를 생성한다. 하나의 염색체는 무작위로 생성된 `DIM_SOLUTION`개의 정수를 갖는다. 해결하고자 하는 문제에 따라 이항분포, 정규분포 등을 이용하여 초기 염색체를 생성해도 되고, 사전에 수집된 데이터가 있다면 데이터를 기반으로 초기 염색체를 생성할 수도 있다.
3.2. 적합도 계산 함수
적합도 계산 함수는 입력된 염색체의 각 요소들을 바탕으로 염색체의 적합도를 계산하는 함수이다. 수학적으로는 $d$가 염색체 요소의 수 (= `DIM_SOLUTION`)이라고 할 때, 적합도 계산 함수는 $f: \mathbb{R}^d \rightarrow \mathbb{R}$로 정의된다. 적합도 계산 함수는 문제에 따라 정의되어야하기 때문에 4번 항목의 예제에서 자세히 설명한다.
3.3. 적합도 기반의 염색체 선택 연산
가장 기본적인 염색체 선택 연산은 현재 세대에서 적합도가 가장 높은 두 개의 염색체를 선택하는 것이다. 그러나 이러한 방법은 염색체의 다양성을 크게 훼손하고, 결과적으로는 알고리즘이 다양한 공간을 탐색할 수 있는 능력을 저하시키기 때문에 전역 최적해를 찾기에는 부적합하다. 이러한 문제점을 해결하기 위해 유전 알고리즘에서는 일반적으로 확률에 기반을 두는 룰렛 휠 선택 (roulette wheel selection) 방법을 이용한다. $i$번째 염색체를 $\textbf{x}_i$, 적합도 함수를 $f$라고 할 때 룰렛 휠 선택에서는 식 (1)의 확률로 $i$번째 염색체를 선택한다.
$$\begin{equation} p(\textbf{x}_i) = \frac{f(\textbf{x}_i)}{\sum_{j=1}^N f(\textbf{x}_j)} \tag{1} \end{equation}$$
위의 식에서 $N$은 한 세대에 존재하는 염색체의 수 (= `N_CHRM`)이다. 식 (1)로 정의되는 룰렛 휠 선택을 그림으로 표현하면 아래의 그림 1과 같다.
룰렛 휠 선택은 식 (1)을 이용하여 그림 1과 같은 룰렛을 만들고, 만들어진 룰렛을 이용하여 확률적으로 염색체를 선택하는 것이다. 이러한 방법을 이용하면 적합도가 높은 염색체가 더 높은 확률로 선택되도록 구현하면서 염색체의 다양성도 유지할 수 있다.
3.4. 선택된 염색체에 대한 자손 생성 연산
이 연산은 선택된 두개의 부모 염색체로부터 하나의 자손 염색체를 생성한다. 유전 알고리즘에서는 일반적으로 crossover를 바탕으로 자손을 생성 연산을 정의한다. Crossover 연산의 개념은 그림 2와 같다.
Crossover 연산에서 부모 염색체를 분할하는 지점인 division point는 $d/2$로 고정하여 구현할 수도 있고, 난수생성기에 의해 무작위로 선택되도록 구현할 수도 있다. Crossover 연산을 이용하면 실제 생명체의 자손 생성 방식과 유사하게 부모 염색체의 형질을 일정 부분씩 자손 염색체에 전달할 수 있다.
3.5. 돌연변이 생성 연산
비록 3.3의 룰렛 휠 선택을 이용하더라도, 알고리즘이 반복될수록 적합도가 높은 염색체만 남게되어서 유전 알고리즘은 결과적으로 지역 최적점에 빠지게 될 학률이 높을 것이다. 유전 알고리즘에서는 지역 최적점에 빠지더라도 새로운 지점을 탐색할 수 있도록 생성된 염색체에서 확률적으로 돌연변이가 발생하도록 한다. 일반적으로 0.1%, 0.05% 등의 아주 낮은 확률로 돌연변이가 발생하도록 설정하며, 염색체에서 돌연변이를 발생시키는 연산은 매우 다양하게 정의된다. 예를 들어, 그림 2에서 생성된 자손에 대해 돌연변이를 생성하기 위해 아래의 그림 3과 같은 두 개의 연산을 정의할 수 있다.
그림 3a는 유전자가 가질 수 있는 값이 0 또는 1일 때, 임의로 하나의 유전자를 선택하여 0이면 1로, 1이면 0으로 값을 바꾸는 돌연변이 연산이다. 그림 3b는 두 개의 유전자를 임의로 선택하여 두 유전자의 값을 교환하는 돌연변이 연산이다. 돌연변이 연산에는 이외에도 많은 종류가 있으며, 해결하고자 하는 문제에 효과적인 돌연변이 연산을 정의하면 된다.
이 항목에서는 유전 알고리즘을 이용하여 NP-hard에 속하는 대표적인 문제인 TSP (travelling salesman problem)의 최적해를 구해본다. TSP는 간단히 아래와 같이 정의된다.
노드가 15개만 있다고 해도 TSP의 완벽한 답을 찾기 위해서는 $15!$에 해당하는 약 1조 3000천억개의 경우를 계산해야 한다. 따라서 현실적으로 TSP의 정확한 답을 찾는 것은 불가능하다. 그러나 유전 알고리즘을 하면 정확한 답은 아니더라도 거리가 일정 수준 이하인 최적해를 효율적으로 찾을 수 있다. 이 예제에서는 유전 알고리즘을 이용하여 도시의 수가 5개인 TSP의 최적해를 구할 것이다. 2차원 평면에 존재하는 각 도시의 이름과 좌표는 아래와 같으며, 출발 도시는 A이다.
- 도시 A: (10, 10)
- 도시 B: (10, 5)
- 도시 C: (14, 5)
- 도시 D: (40, 50)
- 도시 E: (1, 3)
도시의 좌표 정보를 바탕으로 아래와 같은 거리 정보 테이블을 구성할 수 있다. 거리 정보 테이블은 염색체의 적합도를 계산할 때 이용할 것이므로, 메모리상에 보관하도록 구현하는 좋다.
도시의 좌표 정보를 바탕으로 아래의 [그림 4]와 같은 거리 정보 테이블을 구성할 수 있다. 거리 정보 테이블은 염색체의 적합도를 계산할 때 이용되므로, 메모리상에 보관하는 것이 좋다.
| A | B | C | D | E | |
| A | 0 | 5.00 | 64.00 | 50.00 | 11.40 |
| B | 5.00 | 0 | 4.00 | 54.08 | 9.22 |
| C | 6.40 | 4.00 | 0 | 51.97 | 13.15 |
| D | 50.00 | 54.08 | 51.97 | 0 | 61.07 |
| E | 11.40 | 9.22 | 13.15 | 61.07 | 0 |
예제의 TSP에 대한 염색체 $\textbf{x}_i$는 그림 4와 같이 크기가 4인 벡터로 정의할 수 있다. 그림 4의 염색체는 도시 A에서 시작하여 도시 E→ C →D →B를 거쳐 다시 A로 돌아오는 경로를 의미한다.
도시의 좌표를 $\textbf{c}$, 두 지점간의 거리를 $d$라고 할 때, 적합도 함수 $f(\textbf{x})$는 아래의 식 (2)와 같이 정의할 수 있다.
$$\begin{equation} f(\textbf{x}_i) = \left(\frac{1000}{d(\textbf{c}_A, \textbf{c}_{\textbf{x}_{1}}) + \sum_{j=1}^{d-1} d(\textbf{c}_{\textbf{x}_j}, \textbf{c}_{\textbf{x}_{j+1}}) + d(\textbf{c}_{\textbf{x}_d}, \textbf{c}_A)} \right)^2 \tag{1} \end{equation} $$
식 (2)는 도시 A에서 염색체에 나타난 첫 번째 도시로 이동할 때의 거리와 염색체에 나타난 순서대로 도시를 이동할 때의 거리, 그리고 염색체의 마지막에 나타난 도시에서 도시 A로 이동할 때의 거리를 합하여 역수를 취하고 있다. 예를 들어, 그림 4의 염색체에 대해서는 A→E, E→C, C→D, D→B, B→A, 총 5개의 이동에 대해 거리를 계산하여 합산한다. 식 (2)에서 거리합 역수의 분자에 1000을 설정하여 제곱을 하는 것은 어떠한 규칙에 따라 정해진 것이 아니라, 총 이동 거리가 작으면 적합도가 높도록 단순히 경험적으로 설정한 것이다. 따라서 실제 구현에서는 더 좋다고 생각하는 적합도 함수가 있으면 식 (2)와 다르게 $f\textbf{x}$를 정의해도 된다.
유전 알고리즘의 hyperparameter인 한 세대 당 염색체의 수는 4로, 돌연변이 확률은 0.1%, 최대 반복횟수는 1,000, 최적해의 최대 거리는 125로 설정했다고 가정한다. 이렇게 적합도 함수 및 hyperparameter에 대해 항목 3에서 서술한 대로 유전 알고리즘을 동작하면 다음과 같다.
4.1. 초기 염색체 집합 생성
난수생성기 기반의 초기 염색체 생성 연산에 의해 생성된 염색체들은 아래의 그림 5와 같다.
4.2. 초기 염색체들에 대한 적합도 계산
그림 5의 염색체들에 대해 식 (2)로 적합도를 계산하면 그림 6과 같다.
4.3. 현재 염색체들로부터 자손들을 생성
룰렛 휠 선택 방법을 기반으로 두 염색체 [B C E D]와 [D E C B]가 선택되었다고 가정하면, crossover 연산을 통해 그림 7과 같이 하나의 자손이 생성된다.
TSP에서는 도시를 한 번만 경유해야 하기 때문에 첫 번째 부모로부터 B C를 받은 경우, 두 번째 부모 염색체에서 C B를 그대로 가져오는 것이 아니라, 중복되지 않은 도시들을 순서대로 가져온다. 따라서, 자손은 [B C C B]가 아니라, [B C D E]가 된다.
Crossover 연산을 통해 성공적으로 자손을 생성하였다면, 확률적으로 새롭게 생성된 자손에 돌연변이를 일으킨다. 유전 알고리즘의 인자를 설정하는 단계에서 돌연변이 확률을 0.1%로 설정하였기 때문에 0.1%의 확률로 새롭게 생성된 자손에 돌연변이가 발생한다. 만약, 그림 7에서 생성된 자손에 0.1%의 확률로 돌연변이가 발생하였다고 가정하면, 그림 8과 같은 과정을 통해 새롭게 생성된 자손이 변형된다. 돌연변이 연산은 두 유전자를 임의로 선택하여 교환하는 exchange로 하였다. 따라서, 최종적으로 생성된 자손은 [B E D C]가 된다.
앞에서 한 세대 당 염색체의 수를 4로 설정하였기 때문에 그림 7과 8의 과정 (룰렛 휠 선택, crossover, 돌연변이)을 3번 더 반복하여 총 4개의 새로운 자손을 생성한다.
4.4. 생성된 자손들의 적합도 계산
앞의 과정을 통해 생성된 4개의 자손에 대해 적합도를 계산하면 아래의 그림 9와 같다.
4.5. 종료 조건 판별
알고리즘의 최대 반복 횟수를 1,000으로 설정하였고, 현재 시점에서 적합도가 가장 큰 [C B E D] 염색체의 이동 거리는 약 130으로 최적해가 가질 수 있는 최대 거리인 125보다 크기 때문에 종료 조건 판별에서는 거짓이 반환된다. 따라서 항목 4.3의 자손 생성으로 이동하여 알고리즘을 반복한다.
[1] Schmitt, L. M. (2001). Theory of genetic algorithms. Theoretical Computer Science, 259(1-2), 1-61.
[2] Mitchell, M. (1998). An introduction to genetic algorithms. MIT press.
[3] Sivanandam, S. N., Deepa, S. N., Sivanandam, S. N., & Deepa, S. N. (2008). Genetic algorithms (pp. 15-37). Springer Berlin Heidelberg.
[4] Wang, Z., & Sobey, A. (2020). A comparative review between Genetic Algorithm use in composite optimisation and the state-of-the-art in evolutionary computation. Composite Structures, 233, 111739.
'지능형시스템 > 최적화' 카테고리의 다른 글
| [최적화] 입자 군집 최적화 (Particle Swarm Optimization, PSO)의 개념과 구현 (6) | 2021.07.25 |
|---|---|
| [최적화/전역 최적화] Tabu Search (0) | 2016.09.28 |
| 라그랑주 승수법 (Lagrange Multiplier Method) (8) | 2016.09.01 |
