An Investigation on Early Termination for Genetic Programming

Abstract

유전 프로그래밍(Genetic Programming)은 매우 집약적인 연산 비용을 지니는데, 특히 CPU 시간을 집중적으로 사용하는 특징이 있다. 유전 프로그래밍의 평가 비용(evaluation cost)을 줄이기 위해 적합도 근사(fitness approximation), 기계 코드 진화(machine code evolution), 병렬화(parallelization) 등 여러 가지 접근 방법들이 사용되어 왔다.

이 논문은 유전 프로그래밍의 평가 비용 절감을 위한 초기 종료 기법(early termination technique)을 제시한다. 논문에서 제시된 기법은 다른 접근 방법들과 함께 사용될 수 있는 것으로 기법 상에 정의된 조건이 충족되는 경우 개체(individual)의 적합도 평가(fitness evaluation)를 도중에 종료하여 가능한 경우 개체들의 적합도를 정확하게 끝까지 평가하는 것을 피하고자 하는 방법이다. 이 기법이 대상으로 하는 문제들은 단조(monotonic) 적합도 메트릭이 사용된 문제들로, 알고리즘 상에서는 단조성(monotonicity)을 이용하여 적합도 평가의 종료 시점을 결정한다.

이 논문은 초기 종료 기법이 유전 프로그래밍의 수행 시간과 해를 찾는 능력에 어떠한 영향을 미치는 지는 살펴본다. 실험은 초기 종료 기법의 효과를 측정하기 위해 고안되었는데, 먼저 초기 종료 기법이 적용된 경우와 그렇지 않은 경우 각각의 실험에서 수행 시간과 가장 좋은 개체(best individual) 적합도가 어떻게 다른지를 비교하였다. 또한 네 가지 기준을 사용하여 초기 종료 기법이 진화 과정 상에 어느 정도의 영향을 미쳤는지를 측정하였다. 실험에서 초기 종료 기법은 난이도가 서로 다른 미분 방정식 문제, 호수 문제 그리고 강 문제에 적용되었다.

실험 결과는 초기 종료 기법이 유전 프로그래밍의 해를 찾는 능력을 유지시키는 동시에 평가 비용을 줄일 수 있다는 점을 보여준다. 수행된 모든 실험에서 초기 종료 기법이 적용된 경우 전체 수행시간은 감소되었다. 속도 향상은 최대 1.9배였고, 최소 1.2배였다. 또한, 초기 종료 기법이 적용된 경우 가장 좋은 개체의 적합도는 호수와 강 문제의 경우에 거의 동일하게 유지되었고, 미분 방적식 문제의 경우에는 거의 두배 가량 개선되는 결과를 보였다.

Genetic programming is very computationally intensive, particularly in its use of CPU time. A number of approaches to evaluation cost reduction have been proposed, including algebraic simplification, caching, fitness approximation, training subset evaluation, and so on. Among them, this thesis suggests early termination of evaluation, which is applicable in problem domains where estimates of the final fitness value are available during evaluation.

In this method, predefined condition for early termination is checked at each step of fitness evaluation to see if an estimate of the ultimate fitness at that point is sufficiently reliable with respect to its impact on the trajectory of evolution, and if satisfied, fitness evaluation is terminated early, reducing evaluation cost. Like all cost reduction techniques, early termination balances overall computation cost against the risk of finding worse solutions.

We measure the costs and benefits of early termination in terms of mean best fitness and mean running time using original and early termination algorithms. Search performance, in general, does not deteriorate. Rather, early termination actually enhances search performance in the majority of cases. In terms of time performances, most problems see improvements ranging from substantial to negligible.

Then we evaluate the influence of various properties of the problem domain - problem class, reliability of fitness estimates, trajectory of fitness estimates, and evolutionary trajectory - to determine whether any is able to predict the effects of early termination. There is little correlation with any of these, with one exception: Boolean problems see little change in running time, and hence only small changes in performance, are distinguished by both problem class, and each of the other metrics.