New Heuristic and Hybrid Genetic Algorithm for Solving the Bounded Diameter Minimum Spanning Tree Problem

In this paper, we propose the new heuristic, called Center-Based Recursive Clustering – CBRC, for solving the bounded diameter minimum spanning tree (BDMST) problem. Our proposed hybrid genetic algorithm [12] is also extended to include the new heuristic and a multi-parent crossover operator. We experiment the new heuristic and genetic algorithm on two sets of benchmark problem instances for the Euclidean and Non-Euclidean cases. Experimental results show the effectiveness of the proposed heuristic and genetic algorithm. Keywords Bounded diameter minimum spanning tree, heuristic algorithm, hybrid genetic algorithm, multi-parent crossover. 1