Using penalties instead of rewards: Solving OCST problems with guided local search

摘要

This paper considers 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 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. Experiments show that GLS is a powerful optimization method for OCST problems and outperforms standard EA approaches with state-of-the-art search operators for larger problem instances. However, GLS performance does not increase if more knowledge about low-quality solutions is considered but is about independent of whether edges with low weight or wrong orientation are penalized. This is in contrast to the classical assumption that considering more problem-specific knowledge about high-quality solutions does increase search performance.