|
|
|
| A Hybrid Particle Swarm and Multi-Population Cellular Genetic Algorithm |
| LI Ming, JIE Li-Lin, LU Yu-Ming |
| School of Information Engineering,Nanchang Hangkong University,Nanchang 330063 |
|
|
|
|
Abstract Cellular genetic algorithm (CGA) enhances global convergence rate via constraining individual interaction in its neighbor. However, it results in of low search efficiency. An algorithm, called hybrid particle swarm and multi-population cellular genetic algorithm (HPCGA), is proposed. Firstly, the whole population is divided into some sub-populations,the individuals in different sub-populations do not interact each other. Nevertheless different sub-populations can communicate with each other via immigrant and share the evolutionary information. Division of the population appropriately reduces the selection pressure, and thus the individual diversity is maintained more effectively. The mutation of CGA is replaced by particle swarm optimization to improve the ability of local search. The above two improvements balance the trade-off between global exploration and local exploitation. Selection pressure and individual diversity of the proposed HPCGA are also studied. Optimization of six typical functions is carried out by using the proposed HPCGA and CGA. The experimental results show that the performance of the proposed HPCGA is obviously superior to that of CGA in global convergence rate, convergence speed and stability.
|
|
Received: 25 July 2011
|
|
|
|
|
|
[1] Zhang Yu,Li Ming,Lu Yuming.Study on Evolution Rules of Optimization Genetic Algorithm with Cellular Automata.Application Research of Computers,2009,26(10): 1-4 (in Chinese)
(张 俞,黎 明,鲁宇明.元胞遗传算法演化规则的研究.计算机应用研究,2009,26(10): 1-4)
[2] 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)
[3] Alba E,Dorronsoro B.Cellular Genetic Algorithms.New York,USA: Springer,2008
[4] Sarma J,de Jong K A.An Analysis of the Effect of the Neighborhood Size and Shape on Local Selection Algorithms // Proc of the International Conference on Evolutionary Computation.Berlin,Germany,1996: 236-244
[5] Hisao I,Noritaka T,Yusuke N.Examining the Effect of Elitism in Cellular Genetic Algorithms Using Two Neighborhood Structures // Proc of the 10th International Conference on Parallel Problem Solving from Nature.Dortmund,Germany,2008: 458-467
[6] Chen Bingrui,Feng Xiating.Self-Adapting Chaos-Genetic Hybrid Algorithm with Mixed Congruential Method // Proc of the 4th International Conference on Natural Computation.Jinan,China,2008,VII: 674-677
[7] Feng Yongjiu,Han Zhen.Impact of Neighbor Configurations on Spatially-Explicit Modeling Results.Geographical Research,2011,30(6): 1-11 (in Chinese)
(冯永玖,韩 震.元胞邻域对空间直观模拟结果的影响.地理研究,2011,30(6): 1-11)
[8] Kirley M.A Cellular Genetic Algorithm with Disturbance: Optimization Using Dynamic Spatial Interactions.Journal of Heuristics,2002,8(3): 321-342
[9] Lu Yuming,Li Ming,Li Ling,et al.Improved Genetic Algorithm Based on Migration Differential Individuals.Systems Engineering and Electronics,2011,33(3): 1-4 (in Chinese)
(鲁宇明,黎 明,李 凌,等.基于个体差异移民的改进元胞遗传算法.系统工程与电子技术,2011,33(3): 1-4)
[10] Jiradej V,Nasimul N,Hitoshi I.Polynomial Selection: A New Way to Tune Selective Pressure // Proc of the 2nd World Congress on Nature and Biologically Inspired Computing.Kitakyushu,Japan,2010: 597-602
[11] Kaveh A,Shahrouzi M.Dynamic Selective Pressure Using Hybrid Evolutionary and Ant System Strategies for Structural Optimization.International Journal for Numerical Methods in Engineering,2008,73(4): 544-563
[12] Camargo G,Camargo J,Naufal J,et al.Definition of Selective Pressure Control Methods for Optimization of Genetic Algorithms in Air Traffic Control // Proc of the 10th International Conference on Artificial Intelligence and Soft Computing.Zakopane,Poland,2006: 304-311
[13] Janson S,Alba E,Dorronsoro B,et al.Hierarchical Cellular Genetic Algorithm // Proc of the 6th European Conference on Evolutionary Computation in Combinatorial Optimization.Budapest,Hungary,2006: 111-122
[14] Sun Jianyong,Zhang Qingfu,Li Jin,et al.A Hybrid Estimation of Distribution Algorithm for CDMA Cellular System Design // Proc of the 6th International Conference on Simulated Evolution and Learning.Hefei,China,2006: 905-912
[15] Muhlenbein H,Paass G.From Recombination of Genes to the Estimation of Distributions // Proc of the Ada-Europe International Conference on Reliable Software Technologies.Uppsala,Sweden,1996: 178-187
[16] Jolai F,Assadipour G.A Hybrid Cellular Genetic Algorithm for Multi-Objective Crew Scheduling Problem // Proc of the 5th International Conference on Hybrid Artificial Intelligence Systems.San Sebastián,Spain,2010: 359-367
[17] Durillo J J,Nebro A J,Luna F,et al.Solving Three-Objective Optimization Problems Using a New Hybrid Cellular Genetic Algorithm // Proc of the 10th International Conference on Parallel Problem Solving from Nature.Dortmund,Germany,2008: 661-670
[18] Beastin C,Michel D.Cellular Automata Modeling of Physical Systems.Cambridge,UK: Cambridge University Press,1998
[19] Eiben A E,Hinterding R,Michalewicz Z.Parameter Control in Evolutionary Algorithm.IEEE Trans on Evolutionary Computation,1999,3(2): 124-141
[20] Yang Xiaoqin,Li Ming,Zhou Linxia.Entropy Based Genetic Algorithm with Dual Subpopulations.Pattern Recognition and Artificial Intelligence,2005,18(3): 286-290 (in Chinese)
(杨小芹,黎 明,周琳霞.基于熵的双群体遗传算法研究.模式识别与人工智能,2005,18(3): 286-290) |
|
|
|
2012, Vol. 25 
