 |
    |
A Memetic Algorithm for Multi Layer Hierarchical Ring Network Design*
Christian Schauer and Günther R. Raidl
Institute of Computer Graphics and Algorithms, Vienna University of Technology, Vienna, Austriaschauer@ads.tuwien.ac.at
raidl@ads.tuwien.ac.at
Abstract. We address the Multi Layer Hierarchical Ring Network Design Problem. This problem arises in the design of large telecommunication backbones, when high reliability is emphasized. The aim is to connect nodes that are assigned to different layers using a hierarchy of rings of bounded length. We present a memetic algorithm that focuses on clustering the nodes of each layer into disjoint subsets. A decoding procedure is then applied to each genotype for determining a ring connecting all nodes of each cluster. For local improvement we incorporate a previous variable neighborhood search. We experimentally evaluate our memetic algorithm on various graphs and show that it outperforms the sole variable neighborhood search approach in 13 out of 30 instances, while in eight instances they perform on par.
*This work has been funded by the Vienna Science and Technology Fund (WWTF) through project ICT10-027.
LNCS 8672, p. 832 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014