Novel Degree Constrained Minimum Spanning Tree Algorithm Based on an Improved Multicolony Ant Algorithm. (16th September 2015)

• Record Type: Journal Article
• Authors: Sun, Xuemei; Chang, Cheng; Su, Hua; Rong, Chuitian
• Other Names: Liu Kun Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2015(2015)
• Publication Date: 2015-09-16
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2015/601782
• Languages: English
• ISSNs: 1024-123X

Abstract

Abstract : 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.