A Gaussian Random Field Model of Smooth Fitness Landscapes

Authors

Abstract

The smoothness of a fitness landscape, to date still an elusive
notion, is considered to be a fundamental empirical requirement
to obtain good performance for many existing metaheuristics.
In this paper, we suggest that a theory of smooth
fitness landscapes is central to bridge the gap between theory
and practice in EC. As a first step towards this theory, we
formalize the notion of smooth fitness landscapes in a general
setting using a Gaussian random field model on metric
spaces. Then, for the specific case of the Hamming space,
we show experimentally that traditional search algorithms
with search operators based on this space reach better performance
on smoother fitness landscapes. This shows that
the formalized notion of smoothness captures the important
heuristic property of its informal counterpart.

Conference

Foundations of Genetic Algorithms (FOGA), January 2009