[Back]


Talks and Poster Presentations (with Proceedings-Entry):

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.



English abstract:
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.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_201172.pdf


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