| 生长森林的蚁群优化算法在Steiner树问题上的应用 |
| |
| 引用本文： | 许洪,王华,伊善文. 生长森林的蚁群优化算法在Steiner树问题上的应用[J]. 小型微型计算机系统, 2010, 31(4) |
| |
| 作者姓名： | 许洪 王华 伊善文 |
| |
| 作者单位： | 山东大学,计算机科学与技术学院,山东,济南,250101 |
| |
| 基金项目： | 国家自然科学基金项目，中国下一代网络CNGI大规模路由和组播技术的研究与试验 |
| |
| 摘 要： | Steiner树问题是一个经典的优化问题.已被证明是NP-complete问题.对于此问题已经有了很多经典的求解方法,然而在这些方法中一些算法的时间复杂度太高,另一些算法则得不到较好的解.因此,本文提出一种生长森林的蚁群优化算法求解Steiner树问题.在此算法中,蚂蚁行动过程中形成的是森林,每只蚂蚁走出的每一步都只是使当前的森林进一步生长,蚂蚁行动的目标就是使森林中的所有的树连接成一棵树且这棵树包含了所有的目标节点.仿真实验结果表明,算法在寻优能力、收敛速度方面都有良好的表现.
|
| 关 键 词： | Steiner树问题 NP-complete问题 蚁群优化算法 生长森林 |
Ant Colony Optimization Algorithm Based on Forest Growth for Steiner Tree Problem |
| |
| XU Hong,WANG Hua,YI Shan-wen. Ant Colony Optimization Algorithm Based on Forest Growth for Steiner Tree Problem[J]. Mini-micro Systems, 2010, 31(4) |
| |
| Authors: | XU Hong WANG Hua YI Shan-wen |
| |
| Affiliation: | XU Hong,WANG Hua,YI Shan-wen(Department of Computer Science , Technology,Sh,ong University,Jinan 250101,China) |
| |
| Abstract: | 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 fore... |
| |
| Keywords: | steiner tree problem NP-complete problem ant colony optimization algorithm forest growth |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
