  Given a connected, undirected graph whose edges are labelled (or coloured),
the minimum labelling spanning tree (MLST) problem seeks 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 heuristics
have been proposed and analyzed. In this paper we present an intelligent
optimization algorithm to solve the problem. It is obtained by the basic
Variable Neighbourhood Search heuristic with the integration of other
complements from machine learning, statistics and experimental algorithmics, 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, showing the crucial
effects of the implementation, the robustness, and the empirical scalability of
our intelligent algorithm. Furthermore, the computational experiments show that
the proposed strategy outperforms the heuristics recommended in the literature
and is able to obtain optimal or near-optimal solutions in short computational
running time.
