一种求解度约束最小生成树问题的优化算法

• 作者: 崔杜武 张九龙 王竹荣
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 度约束最小生成树 遗传算法 嫁接 剪接
• 年，卷（期）: 2010,（12）
• 页码范围: 3068-3081
• 分类号: TP301
• 字数: 11379字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03713

摘要

为求解大规模结点度约束最小生成树问题,提出一种带有嫁接和剪接算子操作的优化算法.通过借鉴花草果树种植技术,建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系;嫁接以一种贪婪的思想加速搜索,按收益最大化原则进行剪接.对可能陷入局部极值引起冲突的现象及冲突检测的方法进行分析,并提出了冲突的若干解决方法.针对DCMST问题求解中的复杂性,提出了几种有效的嫁接和剪接的策略,并对算法的收敛性和计算复杂度进行了分析.通过该算法对结点数为50～500之间的Euclidean问题和按均匀随机方式产生的non-Euclidean度约束最小生成树问题进行求解.与现有文献的实验结果对比表明,该方法在求解最好解的精度和收敛速度上均有一定的优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔杜武	西安理工大学计算机科学与工程学院	136	1718	19.0	35.0
2	王竹荣	西安理工大学计算机科学与工程学院	20	135	7.0	10.0
3	张九龙	西安理工大学计算机科学与工程学院	24	145	7.0	11.0