Serial and parallel memetic algorithms for the bounded diameter minimum spanning tree problem

摘要

Given a connected, weighted, undirected graphG= (V,E) and an integerD = 2, the bounded diameter minimum spanning tree (BDMST) problem seeks a spanning tree of minimum cost, whose diameter is no greater thanD. The problem is known to be NP-hard, and finds application in various domains such as information retrieval, wireless sensor networks and distributed mutual exclusion. This article presents a two-phase memetic algorithm for the BDMST problem that combines a specialized recombination operator (proposed in this work) with good heuristics in order to more effectively direct the exploration of the search space into regions containing better solutions. A parallel meta-heuristic is also proposed and shown to obtain very good speedups - super-linear, in several cases - vis-a-vis the serial memetic algorithm. To the best of the authors' knowledge, this is the first parallel meta-heuristic proposed for the BDMST problem, and potentially paves the way for handling much larger problems than reported in the literature. Some observations and theorems are presented in order to provide the underlying framework for the proposed algorithms. Further, the proposed memetic algorithm and parallel meta-heuristic are shown, in the course of several computational experiments, to in general obtain superior solution quality with much lesser computational effort in comparison to the best known meta-heuristics in the literature over a wide range of benchmark instances.