An efficient discrete particle swarm optimization algorithm for multi-criteria minimum spanning tree

作者：Guo Wen Zhong^*; Chen Guo Long

来源：Pattem Recognition and Aitificial Intelligence, 2009, 22(4): 597-604.

• Crossover operator
• Discrete particle swarm optimization
• Discrete particle swarm optimization algorithm
• Fitness functions
• Global convergence
• Length Estimation
• Local optima
• Markov Chain
• Minimum Spanning Tree (MST)
• Minimum spanning trees
• Multi-criteria
• Multi-Objective Optimization Problem (MOP)
• Objective space
• Pareto front
• PSO algorithms

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.

• 出版日期2009
• 单位福州大学