Fitness landscapes and graphs: multimodularity, ruggedness and neutrality

ABSTRACT

The performances of evolutionary algorithms (genetics algorithms, genetic programming, etc.) or local search algotihms (Simulated annealing, tabu search, etc.) depends on the properties of seach space structure. One concept to analyse the search space is the fitness landscapes in which the problem to optimize and the search algorithm are taken into account. The fitness landscape is a graph where the nodes are the potential solutions. The study of the fitness landscape consists in analysing this graph or a relevant partition of this graph according to the dynamic or search difficulty.

This tutorial will give an overview, after an historical review of concept of fitness landscape, of the different ways to define fitness landscape in the field of evolutionary computation. Following, the two mains geometries (multimodal and neutral landscapes) corresponding to two different partitions of the graph, meets in optimization problems and the dynamics of metaheuristics on these will be given. The relationship between problems difficulty and fitness landscapes measures (autocorrelation, FDC, neutral degree, etc.) or the properties of the local optima networks, studied in recent work, will be deeply analysed. Finally, the tutorial will conclude with a brief survey of open questions and the recent researchs on fitness landscapes.

References

1. ]]L. Barnett. Ruggedness and neutrality -- the NKp family of fitness landscapes. In C. Adami, R. K. Belew, H. Kitano, and C. Taylor, editors, ALIFE VI, Proceedings of the Sixth International Conference on Artificial Life, pages 18--27. ALIFE, The MIT Press, 1998.
2. ]]Lionel Barnett. Netcrawling -- optimal evolutionary search with neutral networks. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pages 30--37, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27--30 2001. IEEE Press.
3. ]]U. Bastolla, M. Porto, H. E. Roman, and M. Vendruscolo. Statiscal properties of neutral evolution. Journal Molecular Evolution, 57(S):103--119, August 2003.
4. ]]Meriema Belaidouni and Jin-Kao Hao. An analysis of the configuration space of the maximal constraint satisfaction problem. In PPSN VI: Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, pages 49--58, London, UK, 2000. Springer-Verlag.
5. ]]P. Collard, M. Clergue, and M. Defoin Platel. Synthetic neutrality for artificial evolution. In Artificial Evolution: Fourth European Conference AE'99, pages 254--265. Springer-Verlag, 2000. Selected papers in Lecture Notes in Computer Sciences 1829.
6. ]]J. C. Culberson. Mutation-crossover isomorphisms and the construction of discrimination function. Evolutionary Computation, 2:279--311, 1994.
7. ]]J. P. K. Doye. The network topology of a potential energy landscape: a static scale--free network. Phys. Rev. Lett., 88:238701, 2002.
8. ]]J. P. K. Doye and C. P. Massen. Characterizing the network topology of the energy landscapes of atomic clusters. J. Chem. Phys., 122:084105, 2005.
9. ]]Ricardo Garcia-Pelayo and Peter F. Stadler. Correlation length, isotropy, and meta-stable states. Physica D, 107:240--254, 1997. Santa Fe Institute Preprint 96-05-034.
10. ]]Josselin Garnier and Leila Kallel. Efficiency of local search with multiple local optima. SIAM Journal on Discrete Mathematics, 15(1):122--141, 2002.
11. ]]P. Gitchoff and G. Wagner. Recombination induced hypergraphs: A new approach to mutation-recombination isomorphism, 1996.
12. ]]David E. Goldberg and Philip Segrest. Finite markov chain analysis of genetic algorithms. In ICGA, pages 1--8, 1987.
13. ]]M. Huynen. Exploring phenotype space through neutral evolution. Journal Molecular Evolution, 43:165--169, 1996.
14. ]]E. Izquierdo-Torres. The role of nearly neutral mutations in the evolution of dynamical neural networks. In J. Pollack and al, editors, Ninth International Conference of the Simulation and Synthesis of Living Systems (Alife 9), pages 322--327. MIT Press, 2004.
15. ]]T. Jones. Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, University of New Mexico, Albuquerque, 1995.
16. ]]S. A. Kauffman. The Origins of Order. Oxford University Press, New York, 1993.
17. ]]M. Kimura. The Neutral Theory of Molecular Evolution. Cambridge University Press, Cambridge, UK, 1983.
18. ]]J. Lobo, J. H. Miller, and W. Fontana. Neutrality in technology landscape, 2004.
19. ]]M. Newman and R. Engelhardt. Effect of neutral selection on the evolution of molecular species. In Proc. R. Soc. London B., volume 256, pages 1333--1338, 1998.
20. ]]Erik Van Nimwegen, James P. Crutchfield, and Martijn Huynen. Metastable evolutionary dynamics: Crossing fitness barriers or escaping via neutral paths? Technical Report 99-07-041, SanteFe institute, 1999.
21. ]]Gabriela Ochoa, Marco Tomassini, Sébastien Verel, and Christian Darabos. A Study of NK Landscapes' Basins and Local Optima Networks. In Proceedings of the 10th annual conference on Genetic and evolutionary computation Genetic And Evolutionary Computation Conference, pages 555--562, Atlanta États-Unis d'Amérique, 07 2008. ACM New York, NY, USA. best paper nomination.
22. ]]M. Defoin Platel. Homologie en Programmation Génétique -- Application à la résolution d'un problème inverse. PhD thesis, Université de Nice Sophia Antipolis, France, 2004.
23. ]]Eduardo Rodriguez-Tello, Jin-Kao Hao, and Jose Torres-Jimenez. A new evaluation function for the minla problem. In Proceedings of the MIC 2005, pages 796--801, Vienna Austria, 2005.
24. ]]Helge Rosé, Werner Ebeling, and Torsten Asselmeyer. The density of states -- a measure of the difficulty of optimisation problems. In Parallel Problem Solving from Nature, pages 208--217, 1996.
25. ]]P. Schuster, W. Fontana, P. F. Stadler, and I. L. Hofacker. From sequences to shapes and back: a case study in RNA secondary structures. In Proc. R. Soc. London B., volume 255, pages 279--284, 1994.
26. ]]Peter F. Stadler. Landscapes and their correlation functions. J. Math. Chem., 20:1--45, 1996.
27. ]]Peter F. Stadler and W. Schnabl. The landscape of the traveling salesmen problem. Phys. Letters, A(161):337--344, 1992.
28. ]]Peter F. Stadler and Gunter P. Wagner. Algebraic theory of recombination spaces. Evolutionary Computation, 5(3):241--275, 1997.
29. ]]Terry Stewart. Extrema selection: Accelerated evolution on neutral networks. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pages 25--29, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27--30 May 2001. IEEE Press.
30. ]]Marco Tomassini, Sébastien Verel, and Gabriela Ochoa. Complex-network analysis of combinatorial spaces: The NK landscape case. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 78(6):066114, 12 2008. 89.75.Hc; 89.75.Fb; 75.10.Nr.
31. ]]Vesselin K. Vassilev and Julian F. Miller. The advantages of landscape neutrality in digital circuit evolution. In ICES, pages 252--263, 2000.
32. ]]Sebastien Verel, Philippe Collard, and Manuel Clergue. Measuring the evolvability landscape to study neutrality. In M. Keijzer and et al., editors, Poster at Genetic and Evolutionary Computation -- GECCO-2006, pages 613--614, Seatle, 8--12 July 2006. ACM Press.
33. ]]Sébastien Verel, Gabriela Ochoa, and Marco Tomassini. The Connectivity of NK Landscapes' Basins: A Network Analysis. In Proceedings of the Eleventh International Conference on the Simulation and Synthesis of Living Systems Artificial Life XI, pages 648--655, Winchester France, 08 2008. MIT Press, Cambridge, MA. tea team.
34. ]]E. D. Weinberger. Correlated and uncorrelatated fitness landscapes and how to tell the difference. In Biological Cybernetics, pages 63:325--336, 1990.
35. ]]S. Wright. The roles of mutation, inbreeding, crossbreeding, and selection in evolution. In Proceedings of the Sixth International Congress of Genetics 1, pages 356--366, 1932.

Index Terms

• Computing methodologies

  • Artificial intelligence