M. Ruthmair, G. Raidl:

"A Memetic Algorithm and a Solution Archive for the Rooted Delay-Constrained Minimum Spanning Tree Problem";

Talk: International Conference on Computer Aided Systems Theory (Eurocast), Gran Canaria, Spain; 2011-02-06 - 2011-02-11; in: "Proceedings of the 13th International Conference on Computer Aided Systems Theory: Part I", (2011), ISBN: 978-84-693-9560-8; 351 - 358.

We present a memetic algorithm for a combinatorial optimization

problem called rooted delay-constrained minimum spanning

tree problem arising for example in centralized broadcasting networks

where quality of service constraints are of concern. The memetic algorithm

is based on a specialized solution representation and a simple and

effective decoding mechanism. Solutions are locally improved by a variable

neighborhood descent in two neighborhood structures. Furthermore,

to tackle the problem of repeated examination of already visited solutions

we investigate a simple hash-based method to only detect duplicates or,

alternatively, a trie-based complete solution archive to additionally derive

new unvisited solutions. Experimental results show that our memetic

algorithm outperforms existing heuristic approaches for this problem in

most cases. Including the hash-based duplicate detection mostly further

improves solution quality whereas the solution archive can only rarely

obtain better results due to its operational overhead.

http://publik.tuwien.ac.at/files/PubDat_201172.pdf

Created from the Publication Database of the Vienna University of Technology.