A new genetic algorithm for the degree-constrained minimum spanning tree problem

A novel genetic algorithm for the degree-constrained minimum spanning tree (d-MST) is proposed in this paper. In the proposed algorithm, a candidate solution is directly represented by set of the edges contained in the corresponding spanning tree, and a specific initialization scheme, a heuristic crossover and a mutation operator are designed, respectively. Moreover, both the crossover operator and the mutation operator are very easy to execute, and the offspring generated by them always represent feasible spanning trees. Furthermore, the global convergence of the proposed algorithm to globally optimal solution with probability one is proved. At last, the simulated results show the effectiveness of the proposed algorithm.