Solving OCST Problems with Problem-Specific Guided Local Search

摘要

This paper considers the Euclidean variant of the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions and found that edges in optimal solutions have low weight and point towards the center of a tree. Consequently, integrating this problem-specific knowledge into a metaheuristic increases its performance. In this paper, we present an approach to dynamically change the objective function to guide the search process into promising areas. Our approach is based on guided local search. The resulting problem-specific guided local search method considering weight and orientation of edges outperforms standard variants considering only edge weights as well as state-of-the-art evolutionary algorithms using edge-sets for larger problems.