Evolutionary Algorithms with Dissortative Mating on Static and Dynamic Environments
Carlos M., Agostinho C. · InTech eBooks · 2008
This chapter presented a study on Genetic Algorithms (GA) with dissortative mating. A survey on non-random mating was given, in which the most prominent techniques in Evolutionary Computation literature were presented and described. In addition, a survey on Bio-inspired Computation applied to Dynamic Optimization Problems (DOPs) was also given, since DOPs was one of the main aims of the experimental study performed for this chapter. The experiments were performed with the aim of checking the ability of Variable Dissortative Mating GA (VDMGA) on tracking the extrema in dynamic problems. VDMGA, presented in a recent work (Fernandes & Rosa, 2008), inhibits crossover when the Hamming distance between the chromosomes is below a threshold value. The threshold is updated (incremented or decremented) by a simple rule which is indirectly influenced by the genetic diversity of the population: it tends to decrease when the amount of successful crossovers is superior to the number of failed attempts in a generation; when the ratio of successful recombination events rises, the threshold will have a tendency to increase. VDMGA holds this mechanism without the need for further parameters than traditional GAs. In fact, the parameters that need to be tuned are reduced to population size and mutation rate. In addition, no replacement strategy has to be chosen: VDMGA is a steady-state GA in which the number of new chromosomes entering the population in each generation is controlled by the threshold value, genetic diversity and population's stage of convergence. Scalability tests were performed in order to investigate how VDMGA reacts to growing problem size. Deceptive and non-deceptive trap functions were used for that purpose. The algorithm was tested and compared with traditional GAs. Results showed that VDMGA scales clearly better than other traditional GAs when the trap function is deceptive. DOPs experiments demonstrated that in most of the cases, VDMGA is able to perform equally or better than other GAs, except when the speed of change is high. In particular, VDMGA outperformed, in general, the Random Immigrants GA, which a typical algorithm used in DOPs studies to compare other methods performance. Statistical t-tests were performed, giving stronger reliability to the conclusions. A study on the genetic diversity was also performed. As expected, VDMGA maintains a higher diversity throughout the run. The speed of the algorithm may be reduced in a first stage of search (and that is one of the reasons VDMGA is not so able to solve fast DOPs), but the diversity of its population gives it the ability to converge more often to the global optimum. VDMGA is a simple yet effective algorithm to deal with static and dynamic environments. It holds no more parameters than a standard GA. When regarding DOPs, VDMGA may be classified in the category of methods that preserve diversity in order to tackle DOPs (see section 3). Thus, it avoids the complexity of methods that hold memory schemes (which in general need rules and parameters to determine how to deal with memory), and the lower range of problems in which algorithms that react to changes may be applied. Changes in DOPs are not always detectable and a reaction to changes assumes that it is possible to detect when the environment shifts.