|
|
|
| Convergence Analysis of Genetic Algorithm Based on Space Mating |
| ZHENG Jin-Hua,L Hui,WU Jun,ZHOU Cong,LI Ke,LI Mi-Qing |
| Institute of Information Engineering,Xiangtan University,Xiangtan 411105 |
|
|
|
|
Abstract The genetic algorithm based on space mating (GASM) with space mating operator overcomes the premature convergence effectively, but it lacks theoretical analysis. In this paper, the convergent properties of the genetic algorithm based on space mating are analyzed by homogeneous finite Markov chain. It is proved that the GASM with the elitist mechanism can converge to the global optimum, and the GASM can converge to it with probability one on the condition of no mutation operator. By comparing the experimental results of four test problems, in which three of them are multi-peak complex issues, it is shown that the convergence of GASM is better than that of the genetic algorithm with the elitist mechanism, namely elitist genetic algorithm (EGA) in solving the multi-peak complex problems. The algorithm is compared with the algorithm of fast marriage in honey bees optimization as well.
|
|
Received: 12 January 2009
|
|
|
|
|
|
[1] Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor, USA: University of Michigan Press, 1975
[2] Michelewicz Z. Genetic Algorithms+Data Structure=Evolutionary Programs. 3rd Edition. New York, USA: Springer-Verlag, 1996
[3] Fogel D B. An Introduction to Simulated Evolutionary Optimization. IEEE Trans on Neural Networks, 1994, 5(1): 3-14
[4] Sharapov R R, Lapshin A V. Convergence of Genetic Algorithms. Pattern Recognition and Image Analysis, 2006, 16(3): 392-397
[5] Yao L, Sethares W A. Nonlinear Parameter Estimation via the Genetic Algorithm. IEEE Trans on Signal Processing, 1994, 42(4): 927-935
[6] Greenhalgh D, Marshall S. Convergence Criteria for Genetic Algorithms. SIAM Journal of Computing, 2000, 30(1): 269-282
[7] Belea R, Caraman S, Palade V. Genetic Algorithm Convergence Analysis Using a Unified Representation of Genes and the Hamming Distance. International Journal of Knowledge-Based and Intelligent Engineering Systems, 2006, 10(1): 29-40
[8] Gibbs M S, Maier H R, Dandy G C, et al. Minimum Number of Generations Required for Convergence of Genetic Algorithms // Proc of the IEEE Congress on Evolutionary Computation. Vancouver, Canada, 2006, Ⅱ: 565-572
[9] Rigal L, Truffet L. A New Genetic Algorithm Specifically Based on Mutation and Selection. Advances in Applied Probability, 2007, 39(1): 141-161
[10] Drezner Z, Marcoulides G A. Mapping the Convergence of Genetic
Algorithms. Journal of Applied Mathematics and Decision Sciences, 2006, 11(1): 1-16
[11] Balazs H, Janos B. Convergence Analysis of Genetic Algorithm Applied for Dynamic Optimization of Terminal to Base Station Assignment in Satellite Fed BFWA Systems // Proc of the IEEE International Workshop on Satellite and Space Communications. Toulouse, France, 2008: 273 - 277
[12] Guo Dongwei, Liu Dayou, Zhou Chunguang, et al. Dynamic Analysis of GAS Constringency and ITS Application. Journal of Computer Research and Development, 2002, 39(2): 225-230 (in Chinese)
(郭东伟,刘大有,周春光,等.遗传算法收敛性的动力学分析及其应用.计算机研究与发展, 2002, 39(2): 225-230)
[13] Liang Yanchun, Wang Zaishen, Zhou Guangchun. A Study of Convergence of Genetic Algorithms with Selection and Mutation Along. Journal of Computer Research and Development, 1998, 35(7): 655-660 (in Chinese)
(梁艳春,王在申,周光春.选择和变异操作下遗传算法的收敛性研究.计算机研究与发展, 1998, 35(7): 655-660)
[14] Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning. Milano, Italy: Addison-Wesley, 1989
[15] Rudolph G. Convergence Analysis of Canonical Genetic Algorithms. IEEE Trans on Neural Networks, 1994, 5(1): 96-101
[16] Xu Chuanyu. Hybrid Approach and Its Generalization for Solving Premature Convergence of a Class of Genetic Algorithms.Journal of Software, 1998, 9(3): 231-235 (in Chinese)
(徐川育.解决一类遗传算法早熟收敛的混合法及其推广.软件学报, 1998, 9(3): 231-235)
[17] Zheng Jinhua, Ye Zhenghua, Meng Zuqiang, et al. The Genetic Algorithm Based on Spacial Crossover. Pattern Recognition and Artificial Intelligence, 2003, 16(4): 482-485 (in Chinese)
(郑金华,叶正华,蒙祖强,等.基于空间交配的遗传算法.模式识别与人工智能, 2003, 16(4): 482-485)
[18] Xu Zongben, Nie Zankan, Zhang Wenxiu. Almost Sure Convergence of Genetic Algorithms: A Martingale Approach. Chinese Journal of Computers, 2002, 25(8): 785-793 (in Chinese)
(徐宗本,聂赞坎,张文修.遗传算法的几乎必然强收敛性——鞅方法.计算机学报, 2002, 25(8): 785-793)
[19] Guo Conghui, Tang Huanwen. Global Convergence Properties of Evolution Strategies. Mathematica Numerica Sinica, 2001, 23(1): 106-110 (in Chineset)
(郭崇慧,唐焕文.演化策略的全局收敛性.计算数学, 2001, 23(1): 106-110)
[20] Fogel D B. Evolving Artificial Intelligence. Ph.D Dissertation. San Diego, USA: University of California at San Diego. School of Engineering Sciences, 1992
[21] Yang Chenguang, Chen Jie, Tu Xuyan. Algorithm of Fast Marriage in Honey Bees Optimization and Convergence Analysis // Proc of the IEEE International Conference on Automation and Logistics. Shandong, China, 2007: 1794-1799 |
|
|
|
2010, Vol. 23 
