生长森林的蚁群优化算法在Steiner树问题上的应用  

Ant Colony Optimization Algorithm Based on Forest Growth for Steiner Tree Problem

作　　者：许洪[1] 王华[1] 伊善文[1] 

机构地区：[1]山东大学计算机科学与技术学院,山东济南250101

出　　处：《小型微型计算机系统》2010年第4期752-755,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60773101)资助;中国下一代网络CNGI大规模路由和组播技术的研究与试验(CNGI-04-13-2T)资助

摘　　要：Steiner树问题是一个经典的优化问题.已被证明是NP-complete问题.对于此问题已经有了很多经典的求解方法,然而在这些方法中一些算法的时间复杂度太高,另一些算法则得不到较好的解.因此,本文提出一种生长森林的蚁群优化算法求解Steiner树问题.在此算法中,蚂蚁行动过程中形成的是森林,每只蚂蚁走出的每一步都只是使当前的森林进一步生长,蚂蚁行动的目标就是使森林中的所有的树连接成一棵树且这棵树包含了所有的目标节点.仿真实验结果表明,算法在寻优能力、收敛速度方面都有良好的表现.Steiner tree problem is a classical optimization problem which is proved as an NP-complete problem.Many classical algorithms have been proposed to solve this problem.However,these algorithms are either with high time complexity,or unable to obtain better solutions.Therefore,this article proposes an ant colony optimization algorithm based on forest growth for steiner tree problem.In this algorithm,A forest is formed during the ant movement progress,and for every ant,each step it takes is to make current forest grow.The objective of ant movement is to connect all the trees in the forest to form a single tree,which contains all target nodes.Simulation experiments indicate that this algorithm performs well both at solution optimizing and convergence speed.

关 键 词：Steiner树问题 NP-complete问题 蚁群优化算法 生长森林 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]