Leaf constrained minimal spanning trees solved by modified quantum-behaved particle swarm optimization

摘要

Given an undirected, connected, weighted graph, the leaf-constrained minimum spanning tree (LCMST) problem seeks a spanning tree of minimum weight among all the spanning trees of the graph with at least l leaves. In this paper, we have proposed an approach based on Quantum-Behaved Particle Swarm Optimization (QPSO) for the LCMST problem. Particle swarm optimization (PSO) is a well-known population-based swarm intelligence algorithm. Quantum-behaved particle swarm optimization (QPSO) is also proposed by combining the classical PSO philosophy and quantum mechanics to improve performance of PSO. In this paper QPSO has been modified by adding a leaping behavior. When the modified QPSO (MQPSO), falls in to the local optimum, MPSO runs a leaping behavior to leap out the local optimum. We have compared the performance of the proposed method with ML, SCGA, ACO-LCMST, TS-LCMST and ABC-LCMST, which are reported in the literature. Computational results demonstrate the superiority of the MQPSO approach over all the other approaches. The MQPSO approach obtained better quality solutions in shorter time.