求解最小Steiner树的蚁群优化算法及其收敛性

• 作者: 杨文国 郭田德
• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 蚁群优化 最小Steiner树 算法 收敛性
• 年，卷（期）: 2006,（2）
• 页码范围: 352-361
• 页数: 10页
• 分类号: O221.7
• 字数: 6427字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-3079.2006.02.016

摘要

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用.蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法.本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架.把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨文国	中国科学院研究生院数学系	27	248	9.0	15.0
2	郭田德	中国科学院研究生院数学系	25	265	9.0	16.0