Continuous-space embedding genetic algorithm applied to the Degree Constrained Minimum Spanning Tree Problem

This work presents an evolutionary approach for solving a difficult problem of combinatorial optimization, the DCMST (Degree-Constrained Minimum Spanning Tree Problem). Three genetic algorithms which embed candidate solutions in the continuous space [1] are proposed here for solving the DCMST. The results achieved by these three algorithms have been compared with four other existing algorithms according to three merit criteria: i) quality of the best solution found; ii) computational effort spent by the algorithm, and; iii) convergence tendency of the population. The three proposed algorithms have provided better results for both solution quality and population convergence, with reasonable computational cost, in tests performed for 25-node and 50-node test instances. The results suggest that the proposed algorithms are well suited for dealing with the problem under study.