| 求解度约束最小生成树的新的遗传算法 |
| |
| 引用本文： | 韩丽霞,王宇平.求解度约束最小生成树的新的遗传算法[J].计算机工程与应用,2006,42(31):13-15. |
| |
| 作者姓名： | 韩丽霞 王宇平 |
| |
| 作者单位： | 西安电子科技大学,理学院,西安,710071;西安电子科技大学,计算机学院,西安,710071 |
| |
| 摘 要： | 针对度约束最小生成树问题的特征,设计了一种新的编码方式,并在此基础上提出了一个新遗传算法来求解该问题。该算法采用新的启发式杂交算子、变异算子和局部搜索算子,以概率1收敛到全局最优解。数值实验表明该算法优于文中提出的其他4种算法。
|
| 关 键 词： | 遗传算法 最小生成树 全局收敛性 |
| 文章编号： | 1002-8331（2006）31-0013-03 |
| 收稿时间： | 2006-08 |
| 修稿时间： | 2006-08 |
Novel Genetic Algorithm for Degree-constrained Minimum Spanning Tree Problem |
| |
| Han Li-xia,Wang Yu-ping.Novel Genetic Algorithm for Degree-constrained Minimum Spanning Tree Problem[J].Computer Engineering and Applications,2006,42(31):13-15. |
| |
| Authors: | Han Li-xia Wang Yu-ping |
| |
| Abstract: | For the degree-constrained minimum spanning tree problem,a new encoding scheme was presented based on its characters.And then a genetic algorithm was proposed.Heuristics crossover operator,mutation operator and local search scheme were designed in the algorithm and its convergence to global optimal solution with probability one was proved.At last,the simulated results indicate that this method is effective than other four algorithms. |
| |
| Keywords: | genetic algorithm Minimum Spanning Tree(MST) global convergence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
