Authors: Consoli, Sergio
Mladenović, Nenad 
Moreno Pérez, José Andrés
Title: Solving the minimum labelling spanning tree problem by intelligent optimization
Journal: Applied Soft Computing Journal
Volume: 28
First page: 440
Last page: 452
Issue Date: 1-Jan-2015
Rank: M21
ISSN: 1568-4946
DOI: 10.1016/j.asoc.2014.12.020
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.
Keywords: Combinatorial optimization | Graphs and networks | Hybrid methods | Intelligent optimization | Minimum labelling spanning trees | Variable neighbourhood search
Publisher: Elsevier

Show full item record


checked on Jun 12, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.