Article abstract << publications :: home  

Title: Maximally rugged NK landscapes contain the highest peaks

Authors: B. Skellett, B. Cairns, N. Geard, B. Tonkes and J. Wiles

Reference: In (Eds. H.-G. Breyer et al.), Proceedings of the 2005 Conference on Genetic and Evolutionary Computation (GECCO 2005), ACM Press, New York, pp. 579-584.

Full text: [Full text]


Abstract:

NK models provide a family of tunably rugged fitness landscapes used in a wide range of evolutionary computation studies. It is well known that the average height of local optima regresses to the mean of the landscape with increasing epistasis, k. This fact has been confirmed using both theoretical studies of landscape structure and empirical studies of evolutionary search. We show that the global optimum behaves quite differently: the expected value of the global maximum is highest in the maximally rugged case. Furthermore, we demonstrate that this expected value increases with K, despite the fact that the average fitness of the local optima decreases. That is, the highest peaks are found in the most rugged landscapes, scattered amongst masses of low-lying peaks. We find the asymptotic value of the global optimum as N approaches infinity for both the smooth and maximally rugged cases. In evolutionary search, the optima that are found reflect the local optima that exist in the landscape, the size of these optima -- which corresponds to the size of their basins of attraction, and the effort expended in the search process. Increasing the level of epistasis in an NK landscape stochastically introduces higher peaks, but renders them exponentially more difficult to find.

Keywords. NK landscapes, rugged landscapes, combinatorial landscapes, search, optimisation.

Acknowledgement. This study was supported by an Australian Postgraduate Award to NG and an Australian Research Council (ARC) grant to JW. The work of BC is supported by a PhD scholarship from the ARC Centre of Excellence for Mathematics and Statistics of Complex Systems. BT was hosted by the School of ITEE, UQ when this study was carried out.


Citations. Click here for citing articles via Google Scholar.

© 2002-2010 Benjamin J. Cairns: e-mail ; ph +44 1865 289673 ;
Cancer Epidemiology Unit, University of Oxford, Richard Doll Building, Roosevelt Drive, Oxford OX3 7LF, U.K.