Using Penalties instead of Rewards: Solving OCST Problems with Problem-Specic Guided Local Search

This paper considers the optimal communication spanning tree (OCST) problem. Previouswork analyzed features of high-quality solutions and found that edges in optimal solutions havelow weight and point towards the center of a tree. Consequently, integrating this problem-specific knowledge into a metaheuristic increases its performance for the OCST problem. Inthis paper, we present a guided local search (GLS) approach which dynamically changes theobjective function to guide the search process into promising areas. In contrast to traditionalapproaches which reward promising solution features by favoring edges with low weightspointing towards the tree's center, GLS penalizes low-quality edges with large weights thatdo not point towards the tree's center. Experiments show that GLS is a powerful optimizationmethod for OCST problems and outperforms state-of-the-art evolutionary algorithms usingedge-sets for larger problem instances. However, GLS performance does not increase if moreknowledge about low-quality solutions is considered but is about independent of whetheredges with low weight or wrong orientation are penalized. This is in contrast to the classicalassumption that considering more problem-specific knowledge about high-quality solutionsdoes increase search performance.[...]