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

摘要：

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

关键词：单亲遗传算法、度约束最小生成树、度、变异

所属期刊栏目：25

分类号：TP301(计算技术、计算机技术)

在线出版日期：2005-07-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：61-66