Abstract：Cellular genetic algorithms (cGAs) are a class of evolutionary algorithms (EAs) with a decentralized population in which the tentative solutions evolve in overlapped neighborhoods. However, there are few theoretical researches for the convergence and the convergence speed of cGA. A Markov chain that models canonical cGA is constructed. Then, the convergence of canonical cGA is deduced based on the absorbing state Markov chain. Next, the convergence rate of canonical cGA is studied. The upper and lower bounds for the number of iterations that canonical cGA gets a globally optimal solution are estimated.
[1] Zhou Yuren,Yue Xishun,Zhou Jixiang.The Convergence Rate and Efficiency of Evolutionary Algorithms.Chinese Journal of Computers,2004,27(11): 1485-1491(in Chinese) (周育人,岳喜顺,周继香.演化算法的收敛速率与效率分析.计算机学报,2004,27(11): 1485-1491) [2] Luo Xiaoping,Wei Wei.The Analysis on Strong Convergence (a.s.) and Convergence Rate Estimate of Immune Genetic Algorithm.Acta Electronica Sinica,2005,33(10): 1803-1807(in Chinese) (罗小平,韦 巍.生物免疫遗传算法的几乎处处强收敛性分析及收敛速度估计.电子学报,2005,33(10): 1803-1807) [3] Li Junhua,Li Ming.An Analysis on Convergence and Convergence Rate Estimate of Genetic Algorithms in Noisy Environments.Acta Electronica Sinica,2011,39(8): 1898-1902(in Chinese) (李军华,黎 明.噪声环境下遗传算法的收敛性和收敛速度估计.电子学报,2011,39(8): 1898-1902) [4] Alba E.Parallel Metaheuristics: A New Class of Algorithms.New York,USA: Wiley,2005 [5] Dorronsoro B,Alba E.A Simple Cellular Genetic Algorithm for Continuous Optimization // Proc of the IEEE Congress on Evolutionary Computation.Vancouver,Canada,2006: 2838-2844 [6] Antonio J N,Juan J D,Luna F,et al.MOCell: A Cellular Genetic Algorithm for Multiobjective Optimization.International Journal of Intelligent Systems,2009,24(7): 726-746 [7] Kamkar I,Poostchi M T,Mohammad R A T.A Cellular Genetic Algorithm for Solving the Vehicle Routing Problem with Time Windows.Advances in Intelligent and Soft Computing,2010,75: 263-270 [8] Martínez G J,Gámez J A,García V I.Comparing Cellular and Panmictic Genetic Algorithms for Real-Time Object Detection // Chio C D,Cagnoni S,Cotta C,et al,eds.Lecture Notes in Computer Science.New York,USA: Spring,2010,6024: 261-271 [9] Alba E,Dorronsoro B.The Exploration/ Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms.IEEE Trans on Evolutionary Computation,2005,9(2): 126-142 [10] Lu Yuming,Li Ming,Li Ling.The Cellular Genetic Algorithm with Evolutionary Rule.Acta Electronica Sinica,2010,38(7): 1603-1607(in Chinese) (鲁宇明,黎 明,李 凌.一种具有演化规则的元胞遗传算法.电子学报,2010,38(7): 1603-1607) [11] Lu Yuming,Li Ming,Li Ling,et al.Improved Cellular Genetic Algorithm Based on Migration of Different Individuals.Systems Engineering and Electronics,2011,33(3): 690-693(in Chinese) (鲁宇明,黎 明,李 凌,等.基于个体差异移民的改进元胞遗传算法.系统工程与电子技术,2011,33(3): 690-693) [12] Rudolph G,Sprave J.A Cellular Genetic Algorithm with Self Adjusting Acceptance Threshold // Proc of the 1st International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications.Sheffield,UK,1995: 365-372 [13] Vatanutanon J,Noman N,Iba H.Polynomial Selection Scheme with Dynamic Parameter Estimation in Cellular Genetic Algorithm // Proc of the Genetic and Evolutionary Computation Conference.Dublin,Ireland,2011: 1171-1178 [14] Alba E,Troya J.Cellular Evolutionary Algorithms: Evaluating the Influence of Ratio // Proc of the 6th International Conference on Parallel Problem Solving from Nature.Berlin,Germany,2000: 29-38 [15] Huang Han,Hao Zhifeng,Wu Chunguo,et al.The Convergence Speed of Ant Colony Optimization.Chinese Journal of Computers,2007,30(8): 1344-1353(in Chinese) (黄 翰,郝志峰,吴春国,等.蚁群算法的收敛速度分析.计算机学报,2007,30(8): 1344-1353) [16] Zhang Wenxiu,Leung Yee.Mathematical Foundation of Genetic Algorithms.Xi’an,China: Xi’an Jiaotong University Press,2003(in Chinese) (张文修,梁 怡.遗传算法的数学基础.西安:西安交通大学出版社,2003)
2012, Vol. 25 
