Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms

Terry Jones
Santa Fe Institute
1399 Hyde Park Road
Santa Fe, NM 87501, USA
terry@santafe.edu

and

Stephanie Forrest
Department of Computer Science
University of New Mexico
Albuquerque, NM 87131, USA
forrest@cs.unm.edu

Abstract

A measure of search difficulty, fitness distance correlation (FDC), is introduced and examined in relation to genetic algorithm (GA) performance. In many cases, this correlation can be used to predict the performance of a GA on problems with known global maxima. It correctly classifies easy deceptive problems as easy and difficult non-deceptive problems as difficult, indicates when Gray coding will prove better than binary coding, and is consistent with the surprises encountered when GAs were used on the Tanese and royal road functions. The FDC measure is a consequence of an investigation into the connection between GAs and heuristic search.

Questions may be asked about this and other papers through NetQ.

Terry Jones (terry <AT> jon.es)