Novel Degree Constrained Minimum Spanning Tree Algorithm Based on an Improved Multicolony Ant Algorithm

Abstract EN

Degree constrained minimum spanning tree (DCMST) refers to constructing a spanning tree of minimum weight in a complete graph with weights on edges while the degree of each node in the spanning tree is no more than d (d ≥ 2).

The paper proposes an improved multicolony ant algorithm for degree constrained minimum spanning tree searching which enables independent search for optimal solutions among various colonies and achieving information exchanges between different colonies by information entropy.

Local optimal algorithm is introduced to improve constructed spanning tree.

Meanwhile, algorithm strategies in dynamic ant, random perturbations ant colony, and max-min ant system are adapted in this paper to optimize the proposed algorithm.

Finally, multiple groups of experimental data show the superiority of the improved algorithm in solving the problems of degree constrained minimum spanning tree.