ABSTRACT
Local optima networks are a recent model of fitness landscapes. They compress the landscape by representing local optima as nodes, and search transitions among them as edges. Previous local optima networks considered transitions based on mutation; this study looks instead at transitions based on deterministic recombination. We define and analyse networks based on the recently proposed partition crossover for k-bounded pseudo-Boolean functions, using NKq landscapes as a case study. Partition crossover was initially proposed for the travelling salesman problem, where it was found to ``tunnel" between local optima, i.e., jump from local optimum to local optimum. Our network analysis shows that this also happens for NK landscapes: local optima are densely connected via partition crossover. We found marked differences between the adjacent and random interaction NK models. Surprisingly, with the random model, instances have a lower number of local optima on average, but their networks are more sparse and decompose into several clusters. There is also large variability in the size and pattern of connectivity of instances coming from the same landscape parameter values. These network features offer new insight informing why some instances are harder to solve than others.
- E. Boros and P. L. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1--3):155 -- 225, 2002. Google ScholarDigital Library
- W. Chen, D. Whitley, D. Hains, and A. Howe. Second order partial derivatives for NK-landscapes. In Genetic and Evolutionary Computation Conference (GECCO), pages 503--510, New York, NY, USA, 2013. ACM. Google ScholarDigital Library
- F. Chicano, D. Whitley, and A. M. Sutton. Efficient identification of improving moves in a ball for pseudo-boolean problems. In Genetic and Evolutionary Computation Conference (GECCO), pages 437--444. ACM, 2014. Google ScholarDigital Library
- G. Csardi and T. Nepusz. The igraph software package for complex network research. InterJournal, Complex Systems:1695, 2006.Google Scholar
- F. Daolio, S. Verel, G. Ochoa, and M. Tomassini. Local optima networks of the quadratic assignment problem. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2010, pages 1--8. IEEE Press, 2010.Google ScholarCross Ref
- J. P. K. Doye. The network topology of a potential energy landscape: a static scale-free network. Physical Review Letter, 88:238701, 2002.Google ScholarCross Ref
- F. Glover. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13(5):533 -- 549, 1986. Google ScholarDigital Library
- S. Kauffman and S. Levin. Towards a general theory of adaptive walks on rugged landscapes. Journal of Theoretical Biology, 128:11--45, 1987.Google ScholarCross Ref
- M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.Google ScholarDigital Library
- M. E. J. Newman. Networks: An Introduction. Oxford University Press, Oxford, UK, 2010. Google ScholarCross Ref
- M. E. J. Newman and R. Engelhardt. Effect of neutral selection on the evolution of molecular species. Proc. R. Soc. London B, pages 1333--1338, 1998.Google Scholar
- G. Ochoa, M. Tomassini, S. Verel, and C. Darabos. A study of NK landscapes' basins and local optima networks. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2008, pages 555--562. ACM, 2008. Google ScholarDigital Library
- G. Ochoa, S. Verel, F. Daolio, and M. Tomassini. Local optima networks: A new model of combinatorial fitness landscapes. In H. Richter and A. Engelbrecht, editors, Recent Advances in the Theory and Application of Fitness Landscapes, volume 6 of Emergence, Complexity and Computation, pages 233--262. Springer Berlin Heidelberg, 2014.Google ScholarCross Ref
- P. Stadler. Fitness landscapes. Biological evolution and statistical physics, pages 183--204, 2002.Google Scholar
- R. Tinós, D. Whitley, and F. Chicano. Partition crossover for pseudo-boolean optimization. In Proceedings of FOGA, 2015. (to appear). Google ScholarDigital Library
- M. Tomassini, S. Verel, and G. Ochoa. Complex-network analysis of combinatorial spaces: The NK landscape case. Physical Revview E, 78(6):066114, 2008.Google ScholarCross Ref
- S. Verel, G. Ochoa, and M. Tomassini. Local optima networks of NK landscapes with neutrality. IEEE Transactions on Evolutionary Computation, 15(6):783--797, 2011.Google ScholarCross Ref
- D. Whitley and W. Chen. Constant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT. In Genetic and Evolutionary Computation Conference (GECCO), pages 1357--1364, 2012. Google ScholarDigital Library
- D. Whitley and A. Hains, D.and Howe. Tunneling between optima: partition crossover for the TSP. In Proc. of GECCO'09, pages 915--922, 2009. Google ScholarDigital Library
Index Terms
Tunnelling Crossover Networks
Recommendations
Partition Crossover for Pseudo-Boolean Optimization
FOGA '15: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIIIA partition crossover operator is introduced for use with NK landscapes, MAX-kSAT and for all k-bounded pseudo-Boolean functions. By definition, these problems use a bit representation. Under partition crossover, the evaluation of offspring can be ...
Hill-climbing strategies on various landscapes: an empirical comparison
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computationClimbers constitute a central component of modern heuristics, including metaheuristics, hybrid metaheuristics and hyperheuristics. Several important questions arise while designing a climber, and choices are often arbitrary, intuitive or experimentally ...
Heuristics for sampling repetitions in noisy landscapes with fitness caching
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computationFor many large-scale combinatorial search/optimization problems, meta-heuristic algorithms face noisy objective functions, coupled with computationally expensive evaluation times. In this work, we consider the interaction between the technique of "...
Comments