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

Parametrizing convection selection: conclusions from the analysis of performance in the NKq model

Published:13 July 2019Publication History

ABSTRACT

Convection selection in evolutionary algorithms is a method of splitting the population into subpopulations based on the fitness values of solutions. Convection selection was previously found to be superior to standard selection techniques in difficult tasks of evolutionary design. However, reaching its full potential requires tuning of parameters that affect the performance of the evolutionary search process. Performing experiments on benchmark fitness functions does not provide general knowledge required for such tuning. Therefore, in order to gain an insight into the link between the characteristics of the fitness landscape, the parameters of the selection technique, and the quality of the best found solutions, we perform an analysis based on the NKq model of rugged fitness landscapes with neutrality. As a result, we identify several rules that will help researchers and practitioners of evolutionary algorithms adjust the values of convection selection parameters based on the knowledge of the properties of a given optimization problem.

References

  1. Lionel Barnett. 1998. Ruggedness and neutrality --- the NKp family of fitness landscapes. In Proceedings of the 6th international conference on Artificial life. MIT Press, Cambridge, MA, USA, 18--27. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Kenneth Alan De Jong. 1975. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D. Dissertation. University of Michigan, Ann Arbor, MI, USA. AAI7609381.Google ScholarGoogle Scholar
  3. Marc Ebner, Patrick Langguth, Juergen Albert, Mark Shackleton, and Rob Shipman. 2001. On neutral networks and evolvability. In Proceedings of the Congress on Evolutionary Computation (CEC2001), Vol. 1. IEEE, 1--8.Google ScholarGoogle ScholarCross RefCross Ref
  4. Nicholas Geard, Janet Wiles, Jennifer Hallinan, Bradley Tonkes, and Ben Skellett. 2002. A comparison of neutral landscapes - NK, NKp and NKq. In Proceedings of the Congress on Evolutionary Computation (CEC2002), Vol. 1. IEEE, 205--210.Google ScholarGoogle Scholar
  5. David E. Goldberg, Jon Richardson, et al. 1987. Genetic algorithms with sharing for multimodal function optimization. In Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms. Hillsdale, NJ: Lawrence Erlbaum, L. Erlbaum Associates Inc., Hillsdale, NJ, USA, 41--49. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Georges R. Harik. 1995. Finding Multimodal Solutions Using Restricted Tournament Selection. In Proceedings of the 6th International Conference on Genetic Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 24--31. http://dl.acm.org/citation.cfm?id=645514.658086 Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. John Henry Holland. 1992. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, Cambridge, MA, USA. Google ScholarGoogle Scholar
  8. Marcus Hutter and Shane Legg. 2006. Fitness uniform optimization. IEEE Transactions on Evolutionary Computation 10, 5 (2006), 568--589. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Stuart A. Kauffman and Edward D. Weinberger. 1989. The NK model of rugged fitness landscapes and its application to maturation of the immune response. Journal of theoretical biology 141, 2 (1989), 211--245.Google ScholarGoogle ScholarCross RefCross Ref
  10. Hemanshu Kaul and Sheldon H. Jacobson. 2006. Global optima results for the Kauffman NK model. Mathematical Programming 106, 2 (2006), 319--338. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Maciej Komosinski and Konrad Miazga. 2018. Comparison of the tournament-based convection selection with the island model in evolutionary algorithms. Journal of Computational Science (2018).Google ScholarGoogle Scholar
  12. Maciej Komosinski and Konrad Miazga. 2018. Tournament-based convection selection in evolutionary algorithms. PPAM 2017 proceedings, Lecture Notes in Computer Science 10778 (2018), 466--475.Google ScholarGoogle ScholarCross RefCross Ref
  13. Maciej Komosinski and Adam Rotaru-Varga. 2001. Comparison of different genotype encodings for simulated 3D agents. Artificial Life Journal 7, 4 (Fall 2001), 395--418. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Maciej Komosinski and Szymon Ulatowski. 2017. Multithreaded computing in evolutionary design and in artificial life simulations. The Journal of Supercomputing 73, 5 (2017), 2214--2228. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Maciej Komosinski and Szymon Ulatowski. 2019. Framsticks Web Site. (2019). http://www.framsticks.comGoogle ScholarGoogle Scholar
  16. Shane Legg, Marcus Hutter, and Akshat Kumar. 2004. Tournament versus fitness uniform selection. In Proceedings of the Congress on Evolutionary Computation (CEC2004), Vol. 2. IEEE, 2144--2151.Google ScholarGoogle ScholarCross RefCross Ref
  17. Samir W. Mahfoud. 1995. Niching Methods for Genetic Algorithms. Ph.D. Dissertation. University of Illinois at Urbana-Champaign, Champaign, IL, USA. UMI Order No. GAX95-43663. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Martin Pelikan. 2008. Analysis of estimation of distribution algorithms and genetic algorithms on NK landscapes. In Proceedings of the 10th annual conference on genetic and evolutionary computation. ACM, New York, NY, USA, 1033--1040. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Ponnuthurai N. Suganthan, Nikolaus Hansen, Jing J. Liang, Kalyanmoy Deb, Ying-Ping Chen, Anne Auger, and Santosh Tiwari. 2005. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Technical Report. Nanyang Technological University.Google ScholarGoogle Scholar
  20. Sébastien Verel, Gabriela Ochoa, and Marco Tomassini. 2011. Local optima networks of NK landscapes with neutrality. IEEE Transactions on Evolutionary Computation 15, 6 (2011), 783--797.Google ScholarGoogle ScholarCross RefCross Ref
  21. K. Warwick and Erik D. Goodman. 2002. The hierarchical fair competition (HFC) model for parallel evolutionary algorithms. In Proceedings of the Congress on Evolutionary Computation (CEC2002). IEEE, 49--54.Google ScholarGoogle Scholar
  22. David H. Wolpert and William G. Macready. 1997. No free lunch theorems for optimization. IEEE transactions on evolutionary computation 1, 1 (1997), 67--82. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Alden H. Wright, Richard K. Thompson, and Jian Zhang. 2000. The computational complexity of NK fitness functions. IEEE Transactions on Evolutionary Computation 4, 4 (2000), 373--379. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Parametrizing convection selection: conclusions from the analysis of performance in the NKq model

    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 '19: Proceedings of the Genetic and Evolutionary Computation Conference
      July 2019
      1545 pages
      ISBN:9781450361118
      DOI:10.1145/3321707

      Copyright © 2019 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 the author(s) 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: 13 July 2019

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate1,669of4,410submissions,38%

      Upcoming Conference

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

      • Downloads (Last 12 months)2
      • Downloads (Last 6 weeks)0

      Other Metrics

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader