求解度约束最小生成树的改进ACS算法  

Improved ACS Algorithm for Solving Degree-Constrained Minimum Spanning Tree

作　　者：王志杰[1] 全惠云[1] 

机构地区：[1]湖南师范大学数学与计算机科学学院,长沙410081

出　　处：《计算机工程》2009年第21期195-196,199,共3页Computer Engineering

摘　　要：针对蚂蚁系统算法求解度约束最小生成树时收敛速度慢和早熟问题,提出一种改进的蚁群系统算法UDA-ACS。该算法在保留蚁群系统算法优点的基础上,通过增大能见度的影响力、采用动态负反馈机制和赋予不同初始信息素的方法解决上述问题。理论分析和实验结果证明,该算法的求解质量和速度比蚂蚁系统算法更优越。Aiming at the problems of slow converge-rate and precocity when using Ant System（AS） algorithm to solve Degree-Constrained Minimum Spanning Tree（DCMST） problem, this paper presents an improved algorithm named UDA-ACS（Unequal initial pheromone strategy, Dynamic negative feedback mechanism, Adequately augment the effect of visibility-Ant Colony System）. It retains the advantages of Ant Colony System（ACS） algorithm, and adopts the method of augmenting the effect of visibility, dynamic negative feedback mechanism and giving with unequal initial pheromone. Theory analysis and experimental result prove that it gains better solving quality and higher speed than AS algorithm.

关 键 词：蚂蚁系统算法 度约束最小生成树 蚁群系统算法 

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