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

Optimization Algorithm for Solving Degree-Constrained Minimum Spanning Tree Problem

作　　者：王竹荣[1] 张九龙[1] 崔杜武[1] 

机构地区：[1]西安理工大学计算机科学与工程学院,陕西西安710048

出　　处：《软件学报》2010年第12期3068-3081,共14页Journal of Software

基　　金：国家自然科学基金No.60873035~~

摘　　要：为求解大规模结点度约束最小生成树问题，提出一种带有嫁接和剪接算子操作的优化算法．通过借鉴花草果树种植技术，建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系；嫁接以一种贪婪的思想加速搜索，按收益最大化原则进行剪接．对可能陷入局部极值引起冲突的现象及冲突检测的方法进行分析，并提出了冲突的若干解决方法．针对DCMST问题求解中的复杂性，提出了几种有效的嫁接和剪接的策略，并对算法的收敛性和计算复杂度进行了分析．通过该算法对结点数为50-500之间的Euclidean问题和按均匀随机方式产生的non—Euclidean度约束最小生成树问题进行求解与现有文献的实验结果对比表明，该方法在求解最好解的精度和收敛速度上均有一定的优势．To solve the degree-constrained spanning minimum tree （DCMST） problems with a large scale of nodes, an optimization algorithm based on grafting and pruning operator is proposed. Learning from the flower planting techniques, this paper establishes, an evolutionary computation framework containing accelerating and adjusting operators based on conventional genetic operators. The grafting and pruning are performed by a greedy strategy and gain maximization respectively. The collision caused by possible local minima is analyzed and detected, and several methods dealing with the collision are discussed. To tackle the complexity of DCMST problems, some strategies of grafting and pruning are proposed. The convergence of the proposed algorithm and the computation complexity are analyzed. For DCMST problems of Euclidean and uniform random non-Euclidean instances from 50 to 500 nodes, the experiments show that the quality and convergence rate of the proposed method are the best compared with the known results.

关 键 词：度约束最小生成树 遗传算法 嫁接 剪接 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]