Evolutionary Computation

생태계 모방 알고리즘 (Bio-Inspired Algorithm) 은 생태계에서 일어나는 생물체들의 행동 습성 등을 관찰하여 알고리즘화 한 것으로, 다양한 진화적 알고리즘 (Evolutionary Algorithm) 중 한 부분을 차지한다. 기본적으로 어느 주어진 생태계 안에서 각각 하나씩의 가능한 해 (Solution)를 갖는 개체들이 모인 개체군이 각 알고리즘 나름의 진화연산을 수행하면서 최적의 (Optimal) 해 집단을 형성해 가는 것을 주요 목적으로 한다. 이러한 생태계 모방 알고리즘이 갖는 주요 특성으로는 그 연산과정에 있어서 확률론적인 (Stochastic) 접근방법을 사용한다는 것과 각 개체들 간, 즉 해들 간의 상호 작용 (Interaction)을 통해 최적의 해를 찾아가는 방법을 사용한다는 것이 있다[1].

이러한 생태계 모방 알고리즘은 다양한 분야에서 활용되고 있으며, 특히 최적화 (Optimize) 문제에 있어 유용한 해결 방법 중 하나로 잘 알려져 있다. 대표적인 생태계 모방 알고리즘으로는 유전자 알고리즘 (Genetic Algorithm), 개미 군집 최적화 알고리즘 (Ant Colony Optimization), 파티클 집단 최적화 알고리즘 (Particle Swarm Optimization) 등이 있다.

1. 유전자 알고리즘

유전자 알고리즘 (Genetic Algorithm, GA)은 널리 알려진 생태계 모방 알고리즘의 하나로, 생명체의 유전과 진화의 과정을 인공적으로 모사 하여 최적의 해 (Solution)를 찾는 알고리즘이다[2][3]. 주로 염색체와 같은 자료구조를 사용하여 각 염색체가 하나의 임의의 가능한 해를 갖고 확률적으로 개체의 일부 혹은 전체가 선택 (Selection), 교배 (Crossover), 돌연변이 (Mutaion) 의 유전자 연산자 (Genetic Operator) 에 의해 다음 세대로 유전되면서 점점 해 집단이 최적의 해로 수렴해간다[3]. 선택, 교배, 돌연변이의 유전자 연산자에 대한 도식적인 설명을 [그림 1]에서 보이고 있다.

genetic_algo01.png

[그림 1] 유전자 알고리즘에서의 유전자 연산자들의 일반적인 연산과정


선택 단계에서는 적합도 순으로 정렬된 염색체 집합에서 높은 적합도를 보이는 상위의 염색체들을 확률적으로 선택하여 다음 세대에 사용하게 된다. 선택된 염색체들은 서로간의 교배를 통하여 새로운 구조를 가지는 염색체를 만들어 내게 되는데, 이 때의 교배점 (Crossover Point) 은 역시 확률적으로 정해지며 교배점을 기준으로 분리된 개체의 염색체 부분을 교환하게 된다. 위의 [그림 1] 에서는 한점교배 (One-point Crossover)의 예를 보이고 있다. 마지막으로 돌연변이 과정은 교배를 통한 재조합이 끝난 후 염색체의 일부를 바꾸어주는 과정으로서, 마치 자연계의 생명체의 유전자의 일부가 조금 바뀜으로써 돌연변이가 일어나는 것과 흡사하여 돌연변이 과정이라고 한다. 일반적으로 돌연변이 확률은 아주 작은 값을 주게 된다.

교배와 돌연변이 과정까지 완료된 염색체 집단은 다시 적합도 함수에 의해 적합도가 평가된 후 선택 과정을 거쳐 다음 세대로 넘어가 다시 교배와 돌연변이 과정을 반복하게 된다. 이를 반복하며 충분히 좋은 적합도를 보여주는 해가 도출되었을 때, 혹은 사전에 정한 횟수만큼의 세대의 반복이 종료되었을 때 알고리즘을 종료하게 되고 그 때의 가장 적합도가 높은 염색체의 해가 최적 해로서 도출된다.

위에서 설명한 과정을 다음 그림에 정리하였다.

genetic_algo02.png

[그림 2] 유전자 알고리즘의 순서도


2. PSO

파티클 집단 최적화 (Particle Swarm Optimization, PSO) 알고리즘은 GA와 함께 잘 알려진 또 하나의 생태계 모방 알고리즘 중 하나로서, 새, 물고기, 벌 등 군집 생활을 하는 동물들의 행동 습성을 모방하여 최적의 해를 찾는 알고리즘이다[4][5][6]. 이 방법은 여러 개의 파티클 들이 해 공간 (Solution Space) 안에서 흩어져 있어, 반복을 거듭하며 좀 더 나은 해에 가까운 위치로 자신들의 위치를 변화시켜 가며 점점 파티클 집단이 최적의 해를 찾아가는 방향으로 수렴하게 된다.

References

[1] Mitchell, M. (1996). An Introduction to Genetic Algorithms. MIT PRESS.
[2] Goldberg, D. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. ADDISON-WESLEY.
[3] Kennedy, J. & Eberhart, R. (2001). Swarm Intelligence. MORGAN KAUFMANN.
[4] Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of the Conference on Neural Networks. pp. 1942-1948.
[5] Engelbrecht, A. (2005). Fundamentals of Computational Swarm Intelligence. WILEY.
[6] Bautista, M. & Vila, M. (1999). A Survey of Genetic Feature Selection in Mining Issues. Proceedings of the Congress on Evolutionary Computation. Vol. 2, pp. 1314-1321.