Abstract
Mate selection plays a crucial role in both natural and artificial systems. While traditional Evolutionary Algorithms (EA) usually engage in random mating strategies, that is, mating chance is independent of genotypic or phenotypic distance between individuals, in natural systems non-random mating is common, which means that somehow this mechanism has been favored during the evolutionary process. In non-random mating, the individuals mate according to their parenthood or likeness. Previous studies indicate that negative assortative mating (AM)—also known as dissortative mating—, which is a specific type of non-random mating, may improve EAs performance by maintaining the genetic diversity of the population at a higher level during the search process. In this paper we present the Variable Dissortative Mating Genetic Algorithm (VDMGA). The algorithm holds a mechanism that varies the GA’s mating restrictions during the run by means of simple rule based on the number of chromosomes created in each generation and indirectly influenced by the genetic diversity of the population. We compare VDMGA not only with traditional Genetic Algorithms (GA) but also with two preceding non-random mating EAs: the CHC algorithm and the negative Assortative Mating Genetic Algorithm (nAMGA). We intend to study the effects of the different methods in the performance of GAs and verify the reliability of the proposed algorithm when facing an heterogeneous set of landscapes. In addition, we include the positive Assortative Mating Genetic Algorithm (pAMGA) in the experiments in order test both negative and positive AM mechanisms, and try to understand if and when negative AM (or DM) speeds up the search process or enables the GAs to escape local optima traps. For these purposes, an extensive set of optimization test problems was chosen to cover a variety of search landscapes with different characteristics. Our results confirm that negative AM is effective in leading EAs out of local optima traps, and show that the proposed VDMGA is at least as efficient as nAMGA when applied to the range of our problems, being more efficient in very hard functions were traditional GAs usually fail to escape local optima. Also, scalability tests have been made that show VDMGA ability to decrease optimal population size, thus reducing the amount of evaluations needed to attain global optima. We like to stress that only two parameters need to be hand-tuned in VDMGA, thus reducing the tuning effort present in traditional GAs and nAMGA.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Arabas J, Michalewicz Z, Mulawka J (1994) GAVaPS—a genetic algorithm with varying population Size. In: Proceedings of the first IEEE conference on evolutionary computation 1:73–78
Bäck T (1996). Evolutionary algorithms in theory and practice. Oxford University, New York
Bäck T, Eiben AE, van der Vaart NAL (2000) An empirical study on GAs without parameters. In: Proceedings of 5th international conference on parallel problem solving from Nature, LNCS 1917. Springer, Berlin, pp 315–324
Bian R, Chen Z, Yuan Z (2000) Improved crossover strategy of genetic algorithms and analysis of its performance. In: Proceedings of the third world congress on intelligent control and automation, pp 516–520
Craighurst R, Martin W (1995) Enhancing GA performance through crossover prohibitions based on ancestry. In: Proceedings of the sixth international conference on genetic algorithms, Morgan Kauffman, Los Altos
De S, Pal SK and Ghosh A (1998). Genotypic and phenotypic assortative mating in genetic algorithm. Inf Sci 105: 209–225
Eschelman LJ (1991). The CHC algorithm: how to have safe search when engaging in non-traditional genetic recombination. Proc Found Genet algorithms 1: 70–79
Eschelman LJ, Schaffer JD (1991) Preventing premature convergence in genetic algorithms by preventing incest. In: Proceedings of the fourth international conference on genetic algorithms, Morgan Kauffman, Los Altos
Fernandes C, Tavares R, Rosa AC (2000) NiGAVaPS—outbreeding in genetic algorithms. In: Proc of 2000 ACM symposium on applied computing, pp 477–482
Fernandes C, Rosa AC (2001) A study on non-random mating in evolutionary algorithms using a royal road function. In: Proceedings of the 2001 congress on evolutionary computation, pp 60–66
Fernandes C, Tavares T, Munteanu C, Rosa AC (2001) Using assortative mating in genetic algorithms for vector quantization problems. In: Proceedings of the 2001 ACM symposium on applied computing, pp 361–365
Fernandes C (2002) Algoritmos Genéticos e Acasalamento não-aleatório. MSc dissertation thesis, IST, Universidade Técnica de Lisboa, in Portuguese
Fernandes C, Rosa AC (2006) Self-regulated population size in evolutionary algorithms. In: Proceedings of 9th international conference on parallel problem solving from Nature, LNCS 4193, pp 920–929
García-Martínez C, Lozano M, Molina D (2006) A local genetic algorithm for binary-coded problems. In: Runarsson T et al. (eds) Proceedings of 9th international conference on parallel problem solving from Nature, LNCS 4193, pp 192–201
García-Martínez C, Lozano M, Herrera F, Molina D, Sánchez AM (2007) Global and local real-coded genetic algorithms based on parent-centric crossover operators. Eur J Oper Res (in press)
Glover F (1986). Future paths for integer programming and links to artificial intelligence. Comput Oper Res 5: 533–549
Hillis W (1991) Co-evolving parasites improve simulated evolution as an optimization procedure. In: Artificial Life II, SFI Studies in the Sciences of Complexity, vol X. Addison-Wesley, Reading
Jaffe K (1999). On the adaptive value of some mate selection techniques. Acta Biotheoretica 47: 29–40
Jones T (1995). A description of Holland’s royal road function. Evol Comput 2(3): 409–415
Lobo F, Lima C (2005) Revisiting evolutionary algorithm with on-the-fly population size adjustment. In: Proceedings of the 8th annual conference on genetic and evolutionary computation, pp 1241–1248
Lobo F, Lima C (2006) On the utility of the multimodal problem generator for assessing the performance of evolutionary algorithms, UAlg-ILab Report No. 200601. Also arXiv report No. cs.NE/0602051
Lozano M, Herrera F, Krasnogor N and Molina D (2004). Real coded memetic algorithms with crossover hill-climbing. Evol Comput J 12(3): 273–302
Matsui K (1999) New selection method to improve the population diversity in genetic algorithms. In: Proceedings of the 1999 IEEE international conference on systems, man, and cybernetics
Mauldin M (1984) Maintaining genetic diversity in genetic search. In: National conference on artificial intelligence, pp 247–250
Munteanu C and Rosa AC (2004). Adaptive reservoir evolutionary algorithm: an evolutionary on-line adaptation scheme for global function optimization. J Heuristics 10(6): 555–586
Mitchell M (1994). When will a GA outperform hillclimbing?. Adv Neural Inf Proc Syst 6: 51–58
Ochoa G, Madler-Kron C, Rodriguez R and Jaffe K (1999). On sex, selection and the Red Queen. J Theor Biol 199: 1–9
Ochoa G, Madler-Kron C, Rodriguez R, Jaffe K (2005) Assortative mating in genetic algorithms for dynamic problems. In: Rothlauf F et al (eds) Proceedings of the 2005 EvoWorkshops, LNCS 3449, pp 617–622
Ochoa G (2006). Error thresholds in genetic algorithms. Evol Comput 14(2): 157–182
Ochoa G, Jaffe K (2006) Assortative mating drastically alters the magnitude of error thresholds. In: Proceedings of 9th international conference on parallel problem solving from Nature, LNCS 4193, pp 890–899
Petrowski A (1997) A new selection operator dedicated to speciation. In: Proceedings of the 7th international conference on genetic algorithms, pp 144–151
Ronald E (1995) When selection meets seduction. In: Proceedings of the 6th international conference on genetic algorithms, Morgan Kauffman, Los Altos, pp 167–173
Roughgarden J (1979). Theory of population genetics and evolutionary ecology. Prentice-Hall, Englewood Cliffs
Russel PJ (1998). Genetics. Benjamin/Cummings, Reading
Shimodaira H (1997) DCGA: a diversity control oriented genetic algorithm, In: Proceedings of the IEEE international conference on tools with artificial intelligence, pp 367–374
Spears W (1998) The role of mutation and recombination in evolutionary algorithms. Ph.d. dissertation thesis, George Mason University
Ting C, Sheng-Tu L and Chungnan L (2003). On the harmounious mating strategy through tabu search. J Inf Sci 156(3–4): 189–214
Todd PM and Miller GF (1991). On the sympatric origin of species: mercurian mating in the quicksilver model. In: Belew, RK and Booker, LB (eds) Proceedings of the IV international conference on genetic algorithms, pp 547–554. Morgan Kaufmann, Los Altos
Wagner S, Affenzeller M (2005) SexualGA: gender-specific selection for genetic algorithms. In: Proceedings of the 9th world multiconference on systemics, cybernetics and informatics
Whitley D (1988) GENITOR: a different genetic algorithm. In: Proceedings of the Rocky mountain conference on artificial intelligence
Whitley D (1991). Fundamental principles of deception in genetic search. Found Genet algorithms 1: 221–241
Yang S and Yao X (2005). Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput 9(11): 815–834
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fernandes, C., Rosa, A.C. Self-adjusting the intensity of assortative mating in genetic algorithms. Soft Comput 12, 955–979 (2008). https://doi.org/10.1007/s00500-007-0265-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-007-0265-9