基于蚂蚁搜索度约束最小生成树的改进算法  

An Improved Ant Search Algorithm for Degree-Constrained Minimum Spanning Tree

作　　者：赵玲[1] 刘三阳[1] 

机构地区：[1]西安电子科技大学理学院,陕西西安710071

出　　处：《计算机仿真》2006年第10期164-166,198,共4页Computer Simulation

基　　金：陕西省自然科学项目(2004A02)

摘　　要：针对度约束最小生成树问题,对基本的蚁群算法进行改进。提出了度信息的概念来改进转移概率,保证算法获得可行解;同时采用基于度的禁忌表这种数据结构来表示度约束生成树,并与深度优先搜索的思想结合,保证得到树的连通性;将遗传算法中的变异特征引入蚁群算法,对生成树进行局部优化。不仅提高算法的效率,而且避免早熟收敛。通过数值试验验证新算法的可行性,并与其他算法进行比较,取得了良好的效果。For the degree constrained minimum spanning tree problem, the basic ant algorithm is improved The concept of degree information is presented to improve transition probability, which makes solutions feasible Degree - based tabu list in the algorithm based on depth first search is introduced to obtain connected trees Mutation as local search is to improve minimum trees. It can improve its efficiency and avoid stagnation Compared with the other algorithms, numerical examples are tested which give promising results.

关 键 词：度约束 最小生成树 遗传算法 蚁群算法 

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