A Local Optima Network View of Real Function Fitness Landscapes
Open Access
Abstract
The local optima network model has proved useful in the past in connection with combinatorial optimization problems. Here we examine its extension to the real continuous function domain. Through a sampling process, the model builds a weighted directed graph which captures the function’s minima basin structure and its interconnection and which can be easily manipulated with the help of complex networks metrics. We show that the model provides a complementary view of function spaces that is easier to analyze and visualize, especially at higher dimensions. In particular, we show that function hardness as represented by algorithm performance is strongly related to several graph properties of the corresponding local optima network, opening the way for a classification of problem difficulty according to the corresponding graph structure and with possible extensions in the design of better metaheuristic approaches.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Basin Hopping Graph: a computational framework to characterize RNA folding landscapesBioinformatics, 2014
- On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectivesEuropean Journal of Operational Research, 2013
- Communities of minima in local optima networks of combinatorial spacesPhysica A: Statistical Mechanics and its Applications, 2011
- Complex-network analysis of combinatorial spaces: Thelandscape casePhysical Review E, 2008
- On the Multilevel Structure of Global Optimization ProblemsComputational Optimization and Applications, 2005
- Combinatorial LandscapesSIAM Review, 2002
- Error and attack tolerance of complex networksNature, 2000
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Protein folding funnels: a kinetic approach to the sequence-structure relationship.Proceedings of the National Academy of Sciences, 1992
- Quasi-Newton methods and their application to function minimisationMathematics of Computation, 1967