A study of NK landscapes' basins and local optima networks

ABSTRACT

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces (Doye, 2002). We use the well-known family of $NK$ landscapes as an example. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We exhaustively extract such networks on representative small NK landscape instances, and show that they are 'small-worlds'. However, the maxima graphs are not random, since their clustering coefficients are much larger than those of corresponding random graphs. Furthermore, the degree distributions are close to exponential instead of Poissonian. We also describe the nature of the basins of attraction and their relationship with the local maxima network.

REFERENCES

• 1: A-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286 (1999), 509--512.
• 2: K. D. Boese, A. B. Kahng, and S. Muddu, A new adaptive multi-start technique for combinatorial global optimizations, Operations Research Letters 16 (1994), 101--113.
• 3: Carlos Cotta , Juan-Julián Merelo, Where is evolutionary computation going? A temporal analysis of the EC community, Genetic Programming and Evolvable Machines, v.8 n.3, p.239-253, September 2007 [doi>10.1007/s10710-007-9031-0]
• 4: S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Oxford University Press, Oxford, New York, 2003.
• 5: J. P. K. Doye, The network topology of a potential energy landscape: a static scale-free network, Phys. Rev. Lett. 88 (2002), 238701.
• 6: J. P. K. Doye and C. P. Massen, Characterizing the network topology of the energy landscapes of atomic clusters, J. Chem. Phys. 122 (2005), 084105.
• 7: W. Feller, An introduction to probability theory and its applications, Wiley, New York, 1968.
• 8: Josselin Garnier , Leila Kallel, Efficiency of Local Search with Multiple Local Optima, SIAM Journal on Discrete Mathematics, v.15 n.1, p.122-141, 2002 [doi>10.1137/S0895480199355225]
• 9: M. Giacobini, M. Preuss, and M. Tomassini, Effects of scale-free and small-world topologies on binary coded self-adaptive CEA, Evolutionary Computation in Combinatorial Optimization -- EvoCOP 2006 (Budapest), LNCS, vol. 3906, Springer Verlag, 2006, pp. 85--96.
• 10: Mario Giacobini , Marco Tomassini , Andrea Tettamanzi, Takeover time curves in random and small-world structured populations, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068224]
• 11: S. A. Kauffman, The origins of order, Oxford University Press, New York, 1993.
• 12: Leslie Luthi , Marco Tomassini , Mario Giacobini , William B. Langdon, The genetic programming collaboration network and its communities, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277284]
• 13: Peter Merz , Bernd Freisleben, Memetic Algorithms and the Fitness Landscape of the Graph Bi-Partitioning Problem, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.765-774, September 27-30, 1998
• 14: M. E. J. Newman, The structure and function of complex networks, SIAM Review \textbf45 (2003), 167--256.
• 15: Joshua L. Payne , Margaret J. Eppstein, Takeover times on scale-free topologies, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277018]
• 16: C. R. Reeves, Landscapes, operators and heuristic search, Annals of Operations Research 86 (1999), 473--490.
• 17: D. L. Stein, Disordered systems: mostly spin glasses, Lectures in the Sciences of Complexity (D. L. Stein, ed.), Addison-Wesley, 1989, pp. 301--353.
• 18: F.H. Stillinger, A topographic view of supercooled liquids and glass formation, Science 267 (1995), 1935--1939.
• 19: M. Tomassini, M. Giacobini, and C. Darabos, Evolution of small-world networks of automata for computation, Parallel Problem Solving from Nature -- PPSN VIII (Birmingham, UK), LNCS, vol. 3242, Springer-Verlag, 2004, pp. 672--681.
• 20: D. J. Watts, The "new" science of networks, Annual Review of Sociology 30 (2004), 243--270.
• 21: D. J. Watts and S. H. Strogatz, Collective dynamics of "small-world" networks, Nature 393 (1998), 440--442.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Measurement, Performance

Keywords:
complex networks, landscape analysis, local optima, network analysis, nk landscapes