New Multi-parent Recombination in Genetic Algorithm for Solving Bounded Diameter Minimum Spanning Tree Problem

Given a connected, weighted, undirected graph G=(V, E) and a bound D, bounded diameter minimum spanning tree problem (BDMST) seeks spanning tree on G with smallest weight in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 les D les |V| - 1. This paper proposes three new multi-parent recombination operators using different methods to choose parents in genetic algorithm for solving bounded diameter minimum spanning tree problem. Results of computational experiments are reported to show the efficiency of proposed algorithms.