유전 알고리즘의 효율적인 교차 연산자

유전 알고리즘은 조합 최적화의 다양한 분야에 있어서 강력한 힘을 발휘하고 있는 문제 해결 기법이다. 이러한 유전 알고리즘의 성능은 유전 연산자들의 성능에 의존한다. 따라서 유전 알고리즘의 성능 향상을 위해서는 효율적인 유전 연산자들의 개발이 요구된다. 우리는 특히 교차 연산자에 관심을 두고 있다.

본 연구에서는 조합 최적화의 대표적인 문제인 순회 판매원 문제를 대상으로 그 성능을 극대화시킨 교차 연산자를 개발하고 이를 다른 최적화 문제들에 대해서 확대 적용시키는 것을 목적으로 한다.

이미 보로노이 양자화를 응용한 보로노이 양자화 교차 (VQX)를 개발하고 이를 다양한 문제들에 적용하는 연구를 수행하고 있다.

유전 알고리즘의 상위 현상에 관한 연구

유전 알고리즘의 대상이 되는 문제들은 기존의 결정론적인 방법으로 풀기 어려운 NP-hard 군에 속하는 문제들이다. 이러한 문제들의 특징은, 이러한 문제들에 유전 알고리즘을 적용할 경우 유전자들 사이의 강한 상호작용이 일어난다는 것이다. 이러한 유전자들의 상호작용을 상위라고 한다.

본 연구에서는 이론적인 연구에서 주된 적용대상이 되는 작은 크기의 문제들에서 탈피해서 실제적인 큰 문제들에 적용할 수 있는 상위 이론을 정립하고 이를 다양한 분야의 문제들에 대한 유전 알고리즘의 설계에 적용하는 것을 주된 목적으로 한다.

복수 교차 연산자의 병용과 상승 효과 연구

유전알고리즘의 각 연산자는 연산자 고유의 문제 공간 탐색 스타일을 갖고 있다. 일반적으로 교차 연산자는 유전 알고리즘 수행 중에 얻어진 정보를 이용하여 보다 좋은 해를 향한 방향으로 문제 공간을 탐색해 나가며, 변이 연산자는 새로운 해를 생성함으로써 문제 공간의 다양성을 유지시키는 경향이 있다. 유전 알고리즘에서는 다양한 교차 연산자와 변이 연산자가 사용된다. 각 연산자는 교차 연산자는 교차 연산자 나름의, 변이 연산자는 변이 연산자 나름의 일반적인 성질 안에서 또한 고유한 탐색 스타일을 갖고 있다고 믿어지고 있다.

본 연구는 여러 개의 교차 연산자를 하나의 유전 알고리즘에서 혼용하여 사용함으로써 유전 알고리즘의 성능을 향상시키려는 연구이다. 이러한 시도가 처음은 아니나 여태까지 수행되었던 대부분의 연구는 사용된 여러 개의 교차 연산자 중 상대적으로 성능이 우수한 교차 연산자를 우대하여 적용하는 직관적인 접근 방식을 취하였으며, 이러한 접근 방식에서 성능 향상을 얻지는 못하였다. 우리 연구실에서는 각 연산자의 상이한 문제 공간 탐색 스타일을 활용한다는 측면에서 접근하였다. 순회 세일즈맨 문제를 대상으로 다점 교차 연산자, 균등 교차 연산자, 싸이클 교차 연산자를 혼용하여 사용한 실험과, 그래프 분할 문제를 대상으로 다점 교차 연산자, 균등 교차 연산자, 2차원 교차 연산자를 혼용하여 사용한 실험에서 성능이 우수한 연산자를 단독으로 사용한 경우보다 더 좋은 결과를 얻음으로써 복수 교차 연산자의 혼용으로 인한 상승 효과를 입증하였다.