A New Evolutionary Algorithm for Spanning-Tree Based Communication Network Design

Sang-Moon SOAK  David CORNE  Byung-Ha AHN  

IEICE TRANSACTIONS on Communications   Vol.E88-B   No.10   pp.4090-4093
Publication Date: 2005/10/01
Online ISSN: 
DOI: 10.1093/ietcom/e88-b.10.4090
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network
optimum communication spanning tree problem,  quadratic minimum spanning tree problem,  evolutionary algorithm,  genetic representation method,  

Full Text: PDF>>
Buy this Article

A novel evolutionary algorithm is described for designing the topology of spanning tree-based communication networks. Two specific performance objectives are dealt with: the optimum communication spanning tree problem (OCSTP), and the quadratic minimum spanning tree problem (q-MST). Improved network performance is reliably obtained when using the proposed algorithm on accepted benchmark instances, in comparison with the previous best-known approaches. The same methodology can be applied straightforwardly to the design of communication networks with other objectives.