skip to main content
10.1145/2739480.2754657acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Tunnelling Crossover Networks

Published:11 July 2015Publication History

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.

References

  1. E. Boros and P. L. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1--3):155 -- 225, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. G. Csardi and T. Nepusz. The igraph software package for complex network research. InterJournal, Complex Systems:1695, 2006.Google ScholarGoogle Scholar
  5. 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 ScholarGoogle ScholarCross RefCross Ref
  6. J. P. K. Doye. The network topology of a potential energy landscape: a static scale-free network. Physical Review Letter, 88:238701, 2002.Google ScholarGoogle ScholarCross RefCross Ref
  7. F. Glover. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13(5):533 -- 549, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. S. Kauffman and S. Levin. Towards a general theory of adaptive walks on rugged landscapes. Journal of Theoretical Biology, 128:11--45, 1987.Google ScholarGoogle ScholarCross RefCross Ref
  9. M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. M. E. J. Newman. Networks: An Introduction. Oxford University Press, Oxford, UK, 2010. Google ScholarGoogle ScholarCross RefCross Ref
  11. 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 ScholarGoogle Scholar
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. 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 ScholarGoogle ScholarCross RefCross Ref
  14. P. Stadler. Fitness landscapes. Biological evolution and statistical physics, pages 183--204, 2002.Google ScholarGoogle Scholar
  15. R. Tinós, D. Whitley, and F. Chicano. Partition crossover for pseudo-boolean optimization. In Proceedings of FOGA, 2015. (to appear). Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. 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 ScholarGoogle ScholarCross RefCross Ref
  17. 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 ScholarGoogle ScholarCross RefCross Ref
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Tunnelling Crossover Networks

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
          July 2015
          1496 pages
          ISBN:9781450334723
          DOI:10.1145/2739480

          Copyright © 2015 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 11 July 2015

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • research-article

          Acceptance Rates

          GECCO '15 Paper Acceptance Rate182of505submissions,36%Overall Acceptance Rate1,669of4,410submissions,38%

          Upcoming Conference

          GECCO '24
          Genetic and Evolutionary Computation Conference
          July 14 - 18, 2024
          Melbourne , VIC , Australia

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader