Coevolutionary Genetic Algorithms (CGAs) have been used as a useful optimization technique in a number of applications, and their results show that CGAs outperform traditional genetic algorithms under certain conditions. However, there was no systematic research that found those conditions and the reason why CGAs outperform the traditional genetic algorithm. Therefore this paper formulates the class of CGAs which shows better performance, and proves the reason. The definition of formulated CGA and problem cover the CGAs and the problems which showed good performance in the literature. Two theorems are provided to show the performance of the defined CGA, with respect to both the quality of the solution and the amount of computational time. The theorems are justified by an analysis carried on the experiments presented in literature. A supplementary experimental result on a reasonably difficult problem for the traditional genetic algorithms supports the theorems.
공진화적 유전 알고리즘은 최적화 기술로서 다양한 분야에 적용되었고, 연구 결과들을 통하여 특정한 조건하에서는 공진화적 유전 알고리즘이 전통적인 유전 알고리즘보다 뛰어난 성능을 보임이 실험적으로 밝혀졌다. 공진화의 작용 기작에 관한 지금까지의 몇몇 연구들은 탐색 과정에서 개척 효과를 나타내는 교배 연산자를 고려하지 않았기 때문에 공진화적 유전 알고리즘의 성능이 전통적인 유전 알고리즘의 성능을 앞서는 이유에 관한 연구는 미진하다 할 수 있다. 따라서 본 논문에서는 공진화적 유전 알고리즘을 공식화하고, 해법의 질과 그 해법을 얻게까지 걸리는 계산 시간의 두 가지 측면에서 볼 때, 전통적인 유전 알고리즘의 성능과 비교한 공진화적 유전 알고리즘의 성능에 관한 두개의 정리와 그것의 증명을 제시한다. 문헌상에 나타난 실험의 분석을 통해 본 논문에서 공식화한 공진화적 유전 알고리즘의 성능에 관한 정리가 기존의 실험 결과들을 설명할 수 있음을 보인다. 전통적인 유전 알고리즘이 낮은 성능을 보이는 문제에 대한 실험의 결과를 통해서 정리를 뒷받침한다.
