Paper Info
Title
Solving the Delay-Constrained Capacitated Minimum Spanning Tree Problem Using a Dandelion-Encoded Evolutionary Algorithm
Abstract
The Delay-Constrained Capacitated Minimum Spanning Tree (DC-CMST) is a recently proposed problem which arises in the design of the topology of communications networks. The DC-CMST proposes the joint optimization of the network topology in terms of the traffic capacity and its mean time delay. In this paper, an evolutionary algorithm which uses Dandelion-encoding is proposed to solve the problem. The Dandelion code has been recently proposed as an effective way of encoding trees in evolutionary algorithms, due to its good properties of locality. We describe the main characteristics of the algorithm, and compare its results with that of an existing heuristic for the DC-CMST. We show that our Dandelion-encoded evolutionary algorithm is able to obtain better results in all the instances tackled.
Year
DOI
Venue
2008
10.1007/978-3-540-89694-4_16
simulated evolution and learning
Keywords
Field
DocType
encoding tree,Dandelion-encoded evolutionary algorithm,better result,Delay-Constrained Capacitated Minimum Spanning,network topology,communications network,evolutionary algorithm,Dandelion-Encoded Evolutionary Algorithm,Dandelion code,existing heuristic,Tree Problem,good property
Capacitated minimum spanning tree,Mathematical optimization,Distributed minimum spanning tree,Evolutionary algorithm,Computer science,Network topology,Spanning tree,Artificial intelligence,Machine learning,Reverse-delete algorithm,Kruskal's algorithm,Minimum spanning tree
Conference
Volume
ISSN
Citations 
5361
0302-9743
1
PageRank 
References 
Authors
0.36
12
5
Name
Order
Citations
PageRank
Ángel M. Pérez-Bellido113011.71
Sancho Salcedo-Sanz258071.21
Emilio G. Ortiz-García314010.54
Antonio Portilla-Figueras414719.07
Maurizio Naldi528547.98