Paper Info
Title
A novel pheromone-based evolutionary algorithm for solving degree-constrained minimum spanning tree problem
Abstract
The degree-constrained minimum spanning tree problem (dc-MSTP) is crucial in the design of networks and it is proved to be NP-hard. The recently developed evolutionary algorithm utilizing node-depth-degree representation (EANDD) has successfully enabled the dc-MSTP solvable by generating new spanning trees in average time complexity , which is the fastest in the literature. However, as the generic operation of EANDD is to change two edges that are randomly selected from the entire tree, the efficiency of EANDD still has potential to be further improved. In this paper, we propose a novel pheromone-based tree modification method (PTMM) to improve the efficiency of EANDD. For each edge, a pheromone value is defined based on the historical contribution of the edge to the fitness of the spanning tree. Then, PTMM considers the pheromone value on each edge as a desirability measure for selecting the edge to construct the spanning tree. In this way, the more promising edge is more likely to be selected and therefore the efficiency of the tree modification operation in EANDD can be improved. The effectiveness and effieciency of PTMM is demonstrated on a set of benchmark instances in comparison with the original EANDD.
Year
DOI
Venue
2013
10.1145/2464576.2464636
GECCO (Companion)
Keywords
Field
DocType
average time complexity,tree problem,novel pheromone-based tree modification,dc-mstp solvable,evolutionary algorithm,tree modification operation,promising edge,generic operation,pheromone value,degree-constrained minimum,original eandd,entire tree,network design,evolutionary algorithms
Mathematical optimization,Distributed minimum spanning tree,Prim's algorithm,Computer science,Artificial intelligence,Spanning tree,Fractal tree index,Machine learning,Kruskal's algorithm,Interval tree,Minimum spanning tree,Search tree
Conference
Citations 
PageRank 
References 
0
0.34
4
Authors
3
Name
Order
Citations
PageRank
Xiao-ma Huang100.34
Yue-jiao Gong269141.19
Jun Zhang332621.82