A gaussian random field model of smooth fitness landscapes

摘要

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 meta-heuristics. 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.