ABSTRACT
Mate selection is a key step in evolutionary algorithms which traditionally has been panmictic and based solely on fitness. Various mate selection techniques have been published which show improved performance due to the introduction of mate restrictions or the use of genotypic/phenotypic features. Those techniques typically suffer from two major shortcomings: (1) they are fixed for the entire evolutionary run, which is suboptimal because problem specific mate selection may be expected to outperform general purpose mate selection and because the best mate selection configuration may be dependent on the state of the evolutionary run, and (2) they require problem specific tuning in order to obtain good performance, which often is a time consuming manual process. This paper introduces two versions of Learning Individual Mating Preferences (LIMP), a novel mate selection technique in which characteristics of good mates are learned during the evolutionary process. Centralized LIMP (C-LIMP) learns at the population level, while Decentralized LIMP (D-LIMP) learns at the individual level. Results are presented showing D-LIMP to outperform a traditional genetic algorithm (TGA), the Variable Dissortative Mating Genetic Algorithm (VDMGA), and C-LIMP on the DTRAP and MAXSAT benchmark problems, while both LIMP techniques perform comparably to VDMGA on NK Landscapes.
- L. Booker. Improving the Performance of Genetic Algorithms in Classifier Systems. In Proceedings of the 1st International Conference on Genetic Algorithms, pages 80--92, 1985. Google ScholarDigital Library
- R. Craighurst and W. Martin. Enhancing GA Performance through Crossover Prohibitions Based on Ancestry. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 130--135, San Francisco, California, USA, 1995. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
- K. Deb and D. Goldberg. Analyzing Deception in Trap Functions. In Proceedings of FOGA II: the Second Workshop on Foundations of Genetic Algorithms, pages 93--108, 1992.Google Scholar
- C. Fernandes and A. C. Rosa. Self-adjusting the Intensity of Assortative Mating in Genetic Algorithms. Soft Comput., 12:955--979, May 2008. Google ScholarDigital Library
- C. Fernandes, R. Tavares, C. Munteanu, and A. Rosa. Using Assortative Mating in Genetic Algorithms for Vector Quantization Problems. In Proceedings of SAC 2001: the ACM Symposium on Applied Computing, pages 361--365, New York, NY, USA, 2001. ACM. Google ScholarDigital Library
- R. Fry, S. Smith, and A. Tyrrell. A Self-Adaptive Mate Selection Model for Genetic Programming. In Proceedings of CEC 2005: the IEEE Congress on Evolutionary Computation, volume 3, pages 2707 -- 2714, München, Germany, September 2005.Google ScholarCross Ref
- G. Harik. Finding Multimodal Solutions Using Restricted Tournament Selection. In Proceedings of the Sixth International Conference on Genetic Algorithms, pages 24--31. Morgan Kaufmann, 1995. Google ScholarDigital Library
- E. A. Holdener. The Art of Parameterless Evolutionary Algorithms. PhD thesis, Missouri University of Science and Technology, 2008.Google Scholar
- E. A. Holdener and D. R. Tauritz. Learning Offspring Optimizing Mate Selection. In Proceedings of GECCO 2008: Genetic and Evolutionary Computation Conference, pages 1109--1110, 2008. ACM. Google ScholarDigital Library
- R. Karp. Reducibility Among Combinatorial Problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, 1972.Google ScholarCross Ref
- S. A. Kauffman. Adaptation on Rugged Fitness Landscapes. Lectures in the Sciences of Complexity, 1:527--618, 1989.Google Scholar
- C.-Y. Lee and E. Antonsson. Reinforcement Learning in Steady-state Cellular Genetic Algorithms. In Proceedings of CEC 2002: the IEEE Congress on Evolutionary Computation, volume 2, pages 1793 -- 1797, May 2002. Google ScholarDigital Library
- G. Miller. Exploiting Mate Choice in Evolutionary Computation: Sexual Selection as a Process of Search, Optimization, And Diversification. In Selected Papers from AISB Workshop on Evolutionary Computing, pages 65--79, London, UK, 1994. Springer-Verlag. Google ScholarDigital Library
- M. Pelikan, D. Goldberg, and F. Lobo. A Survey of Optimization by Building and Using Probabilistic Models. Computational Optimization and Applications, 21(1):5--20, 2002. Google ScholarDigital Library
- W. R. M. U. K. Wickramasinghe, M. van Steen, and A. Eiben. Peer-to-peer Evolutionary Algorithms with Adaptive Autonomous Selection. In Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference, pages 1460--1467, 2007. ACM. Google ScholarDigital Library
Index Terms
- Learning individual mating preferences
Recommendations
Evolutionary multiobjective optimization with clustering-based self-adaptive mating restriction strategy
Mating restriction plays a key role in MOEAs, while clustering is an effective method to discover the similarities between individuals and therefore can assist the mating restriction. What is more, it is inappropriate to set the same mating restriction ...
Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computationPremature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue,...
Incremental learning-inspired mating restriction strategy for Evolutionary Multiobjective Optimization
AbstractThe prior knowledge from the problem property can boost the evolutionary multiobjective optimization (EMO). The existing machine learning model for knowledge mining in the EMO has led to enhanced performance on multiobjective optimization ...
Highlights- An incremental learning-inspired mating restriction strategy (ILMR) is proposed for boosting the evolutionary search with the knowledge of the problem property efficiently.
- In our proposed ILMR, the neighborhood of each solution for ...
Comments