%0 Journal Article
%T 一种求解度约束最小生成树问题的优化算法
%A 王竹荣？
%A 张九龙？
%A 崔杜武？
%J 软件学报
%P 3068-3081
%D 2010
%X 为求解大规模结点度约束最小生成树问题,提出一种带有嫁接和剪接算子操作的优化算法.通过借鉴花草果树种植技术,建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系;嫁接以一种贪婪的思想加速搜索,按收益最大化原则进行剪接.对可能陷入局部极值引起冲突的现象及冲突检测的方法进行分析,并提出了冲突的若干解决方法.针对dcmst问题求解中的复杂性,提出了几种有效的嫁接和剪接的策略,并对算法的收敛性和计算复杂度进行了分析.通过该算法对结点数为50~500之间的euclidean问题和按均匀随机方式产生的non-euclidean度约束最小生成树问题进行求解.与现有文献的实验结果对比表明,该方法在求解最好解的精度和收敛速度上均有一定的优势.
%K 度约束最小生成树
%K 遗传算法
%K 嫁接
%K 剪接
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3713&flag=1