A PARTICLE SWARM OPTIMIZATION-LIKE ALGORITHM FOR CONSTRAINED MINIMAL SPANNING TREE PROBLEMS

作者：Yeh Chun Chao^*; Chien Ying Che

来源：Journal of Marine Science and Technology-Taiwan, 2014, 22(3): 341-351.

DOI：10.6119/JMST-013-1119-2

• evolutionary algorithm
• ant colony optimization
• genetic algorithm
• constrained minimal spanning tree

Previous studies have discussed various constrained minimal spanning tree (MST) problems. In this paper, we propose an efficient algorithm for solving a class of constrained MST problems. The proposed PSO (Particle Swarm Optimization)like strategy for solving constrained MST problems identifies optimal MSTs under degree and delay constraints. The solution quality and computation time of the proposed PLCMST (PSO-Like algorithm for Constrained MST problems) algorithm is compared with two other algorithms one based on ant colony optimization, and the other based on a genetic algorithm strategy. Our experimental results show that the PLCMST outperforms the other two approaches, particularly when using dense graphs.

• 出版日期2014-6