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.
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarCross Ref
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- Marcus Hutter and Shane Legg. 2006. Fitness uniform optimization. IEEE Transactions on Evolutionary Computation 10, 5 (2006), 568--589. Google ScholarDigital Library
- 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 ScholarCross Ref
- Hemanshu Kaul and Sheldon H. Jacobson. 2006. Global optima results for the Kauffman NK model. Mathematical Programming 106, 2 (2006), 319--338. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Maciej Komosinski and Szymon Ulatowski. 2019. Framsticks Web Site. (2019). http://www.framsticks.comGoogle Scholar
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarCross Ref
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
Index Terms
Parametrizing convection selection: conclusions from the analysis of performance in the NKq model
Recommendations
Fitness diversification in the service of fitness optimization: a comparison study
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference CompanionBlindly chasing after fitness is not the best strategy for optimization of hard problems, as it usually leads to premature convergence and getting stuck in low-quality local optima. Several techniques such as niching or quality-diversity algorithms have ...
Revealing the Inner Dynamics of Evolutionary Algorithms with Convection Selection
GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary ComputationEvolutionary algorithms are stochastic algorithms so they tend to find different solutions when run repeatedly. However, it is not just the solutions that vary - the very dynamics of the search that led to finding these solutions are likely to differ ...
Evolvability metrics in adaptive operator selection
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary ComputationEvolvability metrics gauge the potential for fitness of an individual rather than fitness itself. They measure the local characteristics of the fitness landscape surrounding a solution. In adaptive operator selection the goal is to dynamically select ...
Comments