A particle swarm optimization for steiner tree problem

摘要

This paper presents a particle swarm optimization for solving Steiner tree problem. In the algorithm a tree structure representation is used to encode a particle. To realize the transmission of tree structure information a novel method of particles flying in search space is proposed. We also present the r-neighborhood ring topology of particles to enhance the ability of local and global search of PSO algorithm, and a particle mutation method to keep the diversity of particle population. Exhaustive simulation experiments are carried out on different problems and different network topologies. The results indicate that the proposed algorithm has good searching performance for finding optimal Steiner tree.