An EDA-based with mutation approach for the degree-constraint minimum spanning tree problem

作者：Du Yeshuang; Wang Hua; Gao Chuangen; Kong Guohong; Yi Shanwen

来源：Journal of Computational Information Systems, 2015, 11(1): 37-48.

DOI：10.12733/jcis12705

• Estimation of distribution algorithm (EDA)
• Estimation of distribution algorithms
• Minimum Spanning Tree problem
• Minimum spanning trees
• Mutaiton
• Pre-mature convergences
• Random
• Telephone communication

The problem of finding the Degree-Constraint Minimum Spanning Tree (DCMST) in an edge weighted graph is well known NP-hard and widely applied to optimization in communications network design, telephone communication and other network-related work. To solve this problem, researchers have provided many classic solutions, most of which are based on the Prim's algorithm or Kruskal's algorithm to construct the DCMST. But it is easy to be misled on the test graphs of structured hard and misleading graph. This paper proposes a new method of solving DCMST by using estimation of distribution algorithm (EDA) with random mutation operation (EDA-RM). The basic idea is to initialize randomly a population of n individuals. A tree is kept in each individual, and each individual selects the mutation operation randomly which compensates the diversity of the population and changes the probability model. Some good individuals are selected for the aim of updating the probability. The algorithm constantly evolves trees to obtain a better solution tree which breaks the weak of local search capability and premature convergence in the EDA. This method leads to good performance, reduced time complexity, and optimized solution. Simulation results show that the algorithm has better performance in searching and converging speed.

• 出版日期2015