A Memetic Algorithm for the Optimal Communication Spanning Tree Problem

In: Bartz-Beielstein and Aguilera and Blum and Naujoks and Roli and Rudolph and Sampels ed., HM 2007 -- 4th International Workshop on Hybrid Metaheuristics. LNCS, Volume 4771, Springer, P. 170--184, 2007

Authors

• Thomas Fischer
• Peter Merz

Abstract

For the NP-hard Optimum Communication Spanning Tree (OCST) problem a cost minimizing spanning tree has to be found, where the cost depends on the communication volume between each pair of nodes routed over the tree. We present a memetic algorithm (MA) for this problem and focus our discussion on the evaluation of recombination operators for the OCST. The resulting algorithm outperforms existing solvers when running on problem instances with non-Euclidean distances.

BibTeX

 
@Proceedings{ Fischer2007OCST, 
   title = { A Memetic Algorithm for the Optimal Communication Spanning Tree Problem }, 
   author = { Thomas Fischer and Peter Merz },  
   editor = { Bartz-Beielstein and Aguilera and Blum and Naujoks and Roli and Rudolph and Sampels }, 
   booktitle = { HM 2007 -- 4th International Workshop on Hybrid Metaheuristics },  
   series = { LNCS }, 
   volume = { 4771 },     
   publisher = { Springer },   
   pages = { 170--184 },   
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.