[Zurück]

M. Ruthmair, G. Raidl:
"A Memetic Algorithm and a Solution Archive for the Rooted Delay-Constrained Minimum Spanning Tree Problem";
Vortrag: International Conference on Computer Aided Systems Theory (Eurocast), Gran Canaria, Spain; 06.02.2011 - 11.02.2011; in: "Proceedings of the 13th International Conference on Computer Aided Systems Theory: Part I", (2011), ISBN: 978-84-693-9560-8; S. 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