An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-Criteria Minimum Spanning Tree
GUO Wen-Zhong1, CHEN Guo-Long1,2
1.College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou 350108 2.Key Laboratory of Discrete Mathematics with Applications of Ministry of Education, Fuzhou University, Fuzhou 350003
Abstract A discrete particle swarm optimization (DPSO) algorithm is developed. To obtain a better approximation of true Pareto front, the phenotype sharing function of the objective space is applied in the fitness function. Inspired by the physics of genetic algorithm (GA), the principles of mutation and crossover operator in GA are incorporated into the proposed PSO algorithm to achieve better diversity and break away from local optima. The global convergence of the proposed algorithm is proved by the theorem of Markov chain. The experimental results show that DPSO is efficient and has good performance to problems with increased size.
[1] Hong Xianlong, Yan Xiaolang, Qiao Changge. The Principles and Algorithms of VLSI Payout Design. Beijing, China: Sciences Press, 1998 (in Chinese) (洪先龙,严晓浪,乔长阁.超大规模集成电路布图理论与算法.北京:科学出版社, 1998) [2] Yan Weimin, Wu Weimin. Data Structure. 2nd Edition. Beijing, China: Tsinghua University Press, 1992: 168-174 (in Chinese) (严蔚敏,吴伟民.数据结构.第2版.北京:清华大学出版社, 1992: 168-174) [3] Zhou Gengui, Gen M. Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree Problem. European Journal of Operational Research, 1999, 114(1): 141-152 [4]Gottlieb J, Julstrom B A, Rothlauf F, et al. Prüfer Numbers: A Poor Representation of Spanning Trees for Evolutionary Search // Proc of the Genetic and Evolutionary Computation Conference. San Francisco, USA, 2001: 343-350 [5] Srinivas N, Deb K. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evolutionary Computation, 1995, 2(3): 221-248 [6] Knowles J D. Local-Search and Hybrid Evolutionary Algorithms for Pareto Optimization. Ph.D Dissertation. Reading, UK: University of Reading. Department of Computer Science, 2002 [7] Chen Guolong, Guo Wenzhong, Tu Xuezhu, et al. An Improved Algorithm to Solve the Multi-Criteria Minimum Spanning Tree Problem. Journal of Software, 2006, 17(3): 364-370 (in Chinese) (陈国龙,郭文忠,涂雪珠,等.求解多目标最小生成树问题的改进算法.软件学报, 2006, 17(3): 364-370) [8] Chen Guolong, Chen Shuili, Guo Wenzhong, et al. A Multi-Criteria Minimum Spanning Tree Problem Based Genetic Algorithm. Information Sciences, 2007, 177(22): 5050-5063 [9] Eberhart R C, Kennedy J. A New Optimizer Using Particles Swarm Theory // Proc of the 6th International Symposium on Micro Machine and Human Science. Nagoya, Japan, 1995: 39-43 [10] Kennedy J, Eberhart R C. Swarm Intelligence. San Mateo, USA: Morgan Kaufmann, 2001 [11] Kennedy J, Eberhart R C. A Discrete Binary Version of the Particle Swarm Optimization Algorithm // Proc of the IEEE International Conference on Systems, Man and Cybernetics. Orlando, USA, 1997, Ⅴ: 4104-4109 [12] Clerc M. Discrete Particle Swarm Optimization—Illustrated by the Traveling Salesman Problem [EB/OL]. [2000-02-29]. http://www.mauriceclerc.net [13] Pan Quanke, Tasgetiren M F, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for the Permutation Flowshop Sequencing Problem with Makespan Criteria // Proc of the 26th SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence. Cambridge, UK, 2006: 19-31 [14] Xie Tao, Chen Huowang, Kang Lishan. Evolutionary Algorithms of Multi-Objective Optimization Problems. Chinese Journal of Computers, 2003, 26(8): 997-1003 (in Chinese) (谢 涛,陈火旺,康立山.多目标优化的演化算法.计算机学报, 2003, 26(8): 997-1003) [15] Balling R. The Maximin Fitness Function, Multiobjective City and Regional Planning // Proc of the 2nd International Conference on Evolutionary Multi-Criterion Optimization. Faro, Portugal, 2003: 1-15 [16] Laumanns M, Thiele L, Deb K, et al. Combining Convergence and Diversity in Evolutionary Multi-Objective Optimization. Evolutionary Computation, 2002, 10(3): 263-282 [17] Qu Zhongshui, Liu Shulan. Convergence Analysis Means of Simple Genetic Algorithm. Journal of Harbin University of Science and Technology, 2003, 8(1): 42-45 (in Chinese) (曲中水,刘淑兰.基本遗传算法的收敛性分析方法. 哈尔滨理工大学学报, 2003, 8(1): 42-45)
2009, Vol. 22 
