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

In this paper, a partheno-genetic algorithm for solving the degree-constrained minimum spanning tree problem is proposed. First, the algorithm encodes the tree with Prufer array; second, a method of producing random initial population is designed, the initial population produced by this method will not include any unfeasible solution; third, the algorithm employs only selection and mutation operator to produce the offspring. There are three kinds of mutation operator, two of those mutation operators will not produce any unfeasible solution, but one may produce unfeasible solution and needs to inspect degree and modify; therefore the opportunity of producing unfeasible solution is minimized, and efficiency of genetic algorithm is improved. In addition, since the algorithm only employs mutation operator, it can avoid the problem of premature convergence. The numeric experiments show that the algorithm is simple, efficient and converges quickly. Finally, an example of solving traveling salesman problems with this algorithm is given with concrete steps.