6533b85ffe1ef96bd12c23a5
RESEARCH PRODUCT
Guided local search for the optimal communication spanning tree problem
Wolfgang SteitzFranz Rothlaufsubject
Distributed minimum spanning treeTree (data structure)Tree traversalMathematical optimizationSpanning treeOptimal binary search treeGuided Local SearchMinimum spanning treeMetaheuristicMathematicsdescription
This paper considers the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions. Consequently, integrating this knowledge into a metaheuristic increases its performance for the OCST problem. In this paper, we present a guided local search (GLS) approach which dynamically changes the objective function to guide the search process into promising areas. In contrast to traditional approaches which reward promising solution features by favoring edges with low weights pointing towards the tree's center, GLS penalizes low-quality edges with large weights that do not point towards the tree's center.
year | journal | country | edition | language |
---|---|---|---|---|
2011-07-12 | Proceedings of the 13th annual conference companion on Genetic and evolutionary computation |