Solving the minimum labelling spanning tree problem by intelligent optimization

Abstract

Research on intelligent optimization is concerned with developing algorithms in which the optimization process is guided by an "intelligent agent", whose role is to deal with algorithmic issues such as parameters tuning, adaptation, and combination of different existing optimization techniques, with the aim of improving the efficiency and robustness of the optimization process. This paper proposes an intelligent optimization approach to solve the minimum labelling spanning tree (MLST) problem. The MLST problem is a combinatorial optimization problem where, given a connected, undirected graph whose edges are labelled (or coloured), the aim is to find a spanning tree whose edges have the smallest number of distinct labels (or colours). In recent work, the MLST problem has been shown to be NP-hard and some effective metaheuristics have been proposed and analysed. The intelligent optimization algorithm proposed here integrates the basic variable neighbourhood search heuristic with other complementary approaches from machine learning, statistics and experimental soft computing, in order to produce high-quality performance and to completely automate the resulting optimization strategy. We present experimental results on randomly generated graphs with different statistical properties, and demonstrate the implementation, the robustness, and the empirical scalability of our intelligent local search. Our computational experiments show that the proposed strategy outperforms heuristics recommended in the literature and is able to obtain high quality solutions quickly.