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

摘要

针对蚂蚁系统算法求解度约束最小生成树时收敛速度慢和早熟问题,提出一种改进的蚁群系统算法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.