Clustering Based Pseudo-Parallel Genetic Algorithms
LI Jun-Hua1, 2, LI Ming1, YUAN Li-Hua1, 2
1.Key Laboratory of Nondestructive Test of Ministry of Education, Nanchang Hangkong University,Nanchang 330063 2.College of Automation Engineering, Nanjing University of Aeronautics and Astronautics,Nanjing 210016
Abstract：The traditional genetic algorithm (GA) for multi-modal function optimization is studied and the characteristics of Niche GA and multi-population GA are analyzed. A clustering based pseudo-parallel genetic algorithm is proposed. Cluster analysis is carried out on all the individuals. Local search algorithm is used to search the optimum in all clusters. A new subpopulation is created by the unclassified individuals and the representations of all clusters. To get better global search capacity, niche technology is applied in the subpopulation. The convergence of the algorithm is proved theoretically. Moreover, a new method is designed for automatically calculating clustering threshold. Finally, the presented algorithm is compared with EGA、DCGA and MPGA. Results show that the new algorithm is well in searching global optimum and maintaining population diversity.
[1] Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor, USA: The University of Michigan Press, 1975 [2] Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning. New York, USA: Addison-Wesley, 1989 [3] Ewens W J. Mathematical Population Genetics. Berlin, Germany: Springer-Verlag, 1979 [4] Smith R E, Forrest S, Perelson A S. Searching for Diverse, Cooperative Populations with Genetic Algorithms. Evolutionary Computation, 1992, 1(2): 127-149 [5] Mahfoud S W. Crowding and Preselection Revisited // Manner R, Manderick B, eds. Parallel Problem Solving from Nature. Amsterdam, The Netherlands: Elsevier Science, 1992: 27-36 [6] Mengshoel O J, Goldberg D E. Probabilistic Crowding: Deterministic Crowding with Probabilistic Replacement // Proc of Genetic and Evolution Computation Conference. Orlando, USA, 1999: 409-416 [7] Gao Jiaquan, He Guixia. A Review of Parallel Genetic Algorithms. Journal of Zhejiang University of Technology, 2007, 35(1): 56-59,72 (in Chinese) (高家全,何桂霞.并行遗传算法研究综述.浙江工业大学学报, 2007, 35(1): 56-59,72) [8] Guan Yu, Xu Baowen. Parallel Genetic Algorithms with Schema Migration. Chinese Journal of Computers, 2003, 26(3): 294-301 (in Chinese) (管 宇,徐宝文.基于模式迁移策略的并行遗传算法.计算机学报, 2003, 26(3): 294-301) [9] Maeda Y, Ishita M. Fuzzy Adaptive Search Method for Parallel Genetic Algorithm with Combined Subpopulations // Proc of the IEEE International Conference on Fuzzy System. Budapest, Hungary, 2004, Ⅰ: 433-436 [10] Lai Xinsheng, Zhang Mingyi. Parallel Genetic Algorithms with Migration Scheme Based on Penetration Theory. Chinese Journal of Computers, 2005, 28(7): 1146-1152 (in Chinese) (赖鑫生,张明义.基于渗透原理迁移策略的并行遗传算法.计算机学报, 2005, 28(7): 1146-1152) [11] Liang Xu, Huang Ming. Application Research of an Annealing Parallel Genetic Algorithm Based on Learning. Journal of Systems Engineering, 2006, 12(6): 663-667 (in Chinese) (梁 旭,黄 明.基于学习机制的退火并行遗传算法应用研究.系统工程学报, 2006, 12(6): 663-667) [12] Li Minqiang, Kou Jisong. Coordinate Multi-Population Genetic Algorithms for Multi-Modal Function Optimization. Acta Automatica Sinica, 2002, 28(4): 497-504 (in Chinese) (李敏强,寇纪淞.多模态函数优化的协同多群体遗传算法. 自动化学报, 2002, 28(4): 497-504) [13] Liu Jun, Wang Jiesheng. Solving Traveling Salesman Problem(TSP) with Pseudo-Parallel Genetic Algorithms. Control Theory & Applications, 2007, 24(2): 279-282 (in Chinese) (刘 军,王介生.旅行商问题(TSP)的伪并行遗传算法.控制理论与应用, 2007, 24(2): 279-282) [14] Sander J, Ester M, Kriegel H P, et al. Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications. Data Mining and Knowledge Discovery,1998, 2(2): 169-194 [15] Zhang Wenxiu, Liang Yi. Mathematical Foundation of Genetic Algorithms. Xi'an, China: Xi'an Jiaotong University Press, 2000 (in Chinese) (张文修,梁 怡.遗传算法的数学基础.西安:西安交通大学出版社, 2000) [16] de Jong K A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D Dissertation. Ann Arbor, USA: University of Michigan, 1975 [17] TSPLIB [DB/OL]. www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95 [18] Li Junhua, Li Ming, Yuan Lihua. Study on Population Diversity of TSP in Genetic Algorithms. Journal of Chinese Computer Systems, 2008, 29(3): 544-547 (in Chinese) (李军华,黎 明,袁丽华.遗传算法求解TSP的种群多样性研究.小型微型计算机系统, 2008, 29(3): 544-547)
2009, Vol. 22 
