An adaptive genetic algorithm with diversity-guided mutation and its global convergence property

Abstract

An adaptive genetic algorithm with diversity-guided mutation, which combines adaptive probabilities of crossover and mutation was proposed. By means of homogeneous finite Markov chains, it is proved that adaptive genetic algorithm with diversity-guided mutation and genetic algorithm with diversity-guided mutation converge to the global optimum if they maintain the best solutions, and the convergence of adaptive genetic algorithms with adaptive probabilities of crossover and mutation was studied. The performances of the above algorithms in optimizing several unimodal and multimodal functions were compared. The results show that for multimodal functions the average convergence generation of the adaptive genetic algorithm with diversity-guided mutation is about 900 less than that of adaptive genetic algorithm with adaptive probabilities and genetic algorithm with diversity-guided mutation, and the adaptive genetic algorithm with diversity-guided mutation does not lead to premature convergence. It is also shown that the better balance between overcoming premature convergence and quickening convergence speed can be gotten.

Keywords

diversity-guided mutation / adaptive genetic algorithm / Markov chain / global convergence

References

[1] SrinivasM, PatnaiL M. Adaptive probabilities of crossover and mutation in genetic algorithms [J]. IEEE Trans Syst, Man, and Cybern, 1994, 24(4): 656-666

[2] ZongJing-qun. A kind of mixture adaptive genetic algorithm and analysis of property [J]. Systems Engineering: Theory & Practice, 2001, 21(4): 14-18(in Chinese)

[3] ZhouMing, SunShu-dongGenetic Algorithms: Theory and Applications [M], 1999, Beijing, National Defence Industry Press(in Chinese)

[4] RudolphG. Self-adaptive mutations may lead to premature convergence [J]. IEEE Transactions on Evolutionary Computation, 1998, 5(4): 410-414

[5] Burke E, Gustafson S, Kendall G. A survey and analysis of diversity measures in genetic programming [A]. The Genetic and Evolutionary Computation Conference 2002 [C]. New York, 2001.

[6] Burke E, Gustafson S, Kendall G, et al. Advanced population diversity measures in genetic programming [A]. The Parallel Problem Solving from Nature Conference, 7th International Conference [C]. Granada, 2002.

[7] Shimodaira H. A diversity control oriented genetic algorithm (DCGA): development and experimental results [A]. The Genetic and Evolutionary Computation Conference [C]. Florida, 1999.

[8] BosmanP A N, ThierensD. The balance between proximity and diversity in multi-objective evolutionary algorithms [J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 174-188

[9] IosifescuMFinite Markov Processes and their Applications [M], 1980, Chichester, Wiley

[10] RudolphG. Convergence properties of canonical genetic algorithms [J]. IEEE Transactions on Neural Networks, 1994, 5(1): 96-101

[11] HeLin, WangKe-jun, LiGuo-bin, et al.. The discussion about the paper “the analysis of global convergence and computational efficiency for genetic algorithm” [J]. Control Theory and Applications, 2001, 18(1): 141-144(in Chinese)