2007 | OriginalPaper | Buchkapitel
A Memetic Algorithm for the Optimum Communication Spanning Tree Problem
verfasst von : Thomas Fischer, Peter Merz
Erschienen in: Hybrid Metaheuristics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 proposed algorithm outperforms evolutionary algorithms (EA) for known benchmark instances and outperforms state-of-the-art solvers for non-Euclidean instances.