A novel genetic algorithm preventing premature convergence by chaos operator

Abstract

An improved genetic algorithm (GA) is proposed based on the analysis of population diversity within the framework of Markov chain. The chaos operator to combat premature convergence concerning two goals of maintaining diversity in the population and sustaining the convergence capacity of the GA is introduced. In the CHaos Genetic Algorithm (CHGA), the population is recycled dynamically whereas the most highly fit chromosome is intact so as to restore diversity and reserve the best schemata which may belong to the optimal solution. The characters of chaos as well as advanced operators and parameter settings can improve both exploration and exploitation capacities of the algorithm. The results of multimodal function optimization show that CHGA performs simple genetic algorithms and effectively alleviates the problem of premature convergence.

Keywords

chaos / genetic algorithm / premature convergence / population diversity

References

[1] HollandJ HAdaptation in natural and artificial systems[M], 1975, Ann Arbor, MI, University of Michigan Press

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

[3] SrinivasM, PatnaikL M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans on SMC, 1994, 24(4): 656-667

[4] WuZhi-yuan. A new adaptive genetic algorithm & its application in multimodal function optimization (in Chinese)[J]. Control Theory and Applications, 1999, 16(1): 127-129

[5] XuChuan-yu. A Hybrid method & its generalization in solving premature convergence of VCGA[J]. J of Software, 1998, 9(3): 231-235(in Chinese)

[6] MaJun-shui. The great mutation used to improve the searching quality of GA[J]. Control Theroy and Applications, 1998, 15(3): 404-407(in Chinese)

[7] YeeLeung, GaoYang, XuZong-ben. Degree of population diversity: a perspective on premature convergence in genetic algorithms and its markov chain analysis[J]. IEEE Trans on Neural Network, 1997, 8(5): 1165-1176

[8] Craig PottsJ, GiddensT D, YadavS B. The development and evaluation of an improved genetic algorithm based on migration and artificial selection[J]. IEEE Trans on SMC, 1994, 24(1): 73-86

[9] LiuJian-qinArtificial life: theories and applications (in Chinese)[M], 1997, Beijing, Metallurgy Industry Press: 178-197

[10] YuShou-yi. A dynamic GA based on number encoding[J]. J Central South University of Technology, 1998, 29(1): 85-87(in Chinese)

[11] LiangYan-chun. Convergence analysis of an equivalent GA based on extended strings[J]. J of Computers, 1997, 20(8): 689-694(in Chinese)