求解度约束最小生成树的单亲遗传算法

A Partheno-Genetic Algorithm for Solving the Degree- Constrained Minimum Spanning Tree Problem

提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计了三种变异操作,其中两种变异操作均不会产生不可行解,只有一种变异操作可能会产生不可行解,需要作树的度的检查和修改;这样就大大的降低了不可行解产生的机会,从而提高了遗传算法的效率;而且只使用变异算子,有效的避免了早熟收敛现象的产生;通过大量的数值试验,表明该算法简单,高效,收敛率高;最后对此算法做了适当推广,并给出了用它求解TSP问题的具体步骤和实例.

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 operator 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, efficiency and converges quickly. Finally, a example of solving traveling salesman problems with this algorithm is given with concrete steps.