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

A measure of search difficulty, “fitness distance correlation” (FDC), is introduced and its power as a predictor of genetic algorithm (GA) performance is investigated. The sign and magnitude of this correlation can be used to predict the performance of a GA on many problems where the global maxima are already known. FDC can be used to correctly classify easy deceptive problems and easy and difficult non-deceptive problems as difficult, it can be used to indicate when Gray coding will prove better than binary coding, it produces the expected answers when applied to problems over a wide range of apparent difficulty, and it is also 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.