유전 알고리즘 성능평가 - De Jong's Function

2009. 7. 7. 11:51ETC.


내가 유전 알고리즘을 처음 접하고 나서 관련 연구 결과를 발표하거나, 논문을 쓸 때 가장 어려움을 느꼈던 부분은 유전 알고리즘을 이용해 개발한 프로그램이나 알고리즘의 성능을 '가시적'으로 보여주기가 힘들다는 것이었다. 사람들에게 설명할 때 뿐만 아니라, 나 스스로도 어떠한 기준을 가지고 성능을 평가해야 할지, 객관적인 지표를 마련하기가 어려웠다.

물론, 유전 알고리즘에도 다른 최적화 문제와 마찬가지로 최적화 대상이 되는 최적화 대상함수(reference function)에 해당하는, 적합도 함수(fitness function)가 있기 때문에, fitness function에 의한 적합도 값(fitness value)이 좋을 수록 최적화가 잘 이루어 졌다고 말할 수 있다. 

그러나 연산자들의 확률적 속성상, 유전알고리즘의 성능은 탐색환경에 따라 달라질 수 밖에 없다. 따라서 탐색성능에 영향을 주는 몇가지 요소들을 잘 이해하고 이들의 적절한 선택을 통해서만 좋은 성능을 얻을 수 있다.

※ 다른 최적화 알고리즘들이 그렇듯이 유전 알고리즘도 탐색성능에 영향을 주는 몇 가지 요소들을 가지고 있는데, 이에 관해서는 다음에 정리하기로 한다.   - 코딩법/유전 연산자/ 탐색전략 /제어 파라미터(집단크기, 교배확률, 돌연변이확률) 등

그래서, '어떤 방식이 유전알고리즘의 성능 및 결과를 보여주기에 알맞은가', '어떤 방식으로 유전 알고리즘을 테스트할 수 있는 환경일까'를 고민하다가 De Jong의 5개의 테스트 함수에 대해 알게 되었다.



De Jong의 테스트 함수(De Jong's Test Functions)
  다음의 탐색특성이 내포되도록 사려 깊게 선택
1. 연속 / 불연속
2. 볼록 / 비볼록
3. 저차 / 고차
4. 이차형식 / 비이차형식
5. 단봉 / 다봉
6. 결정적 / 확률적 탐색 특성