最小赋权支配集的迭代禁忌搜索算法

摘要：

最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景.提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法.该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解.用顶点数为800到1 000的大规模标准测试例子测试提出的算法.数值实验结果和与现存的启发式算法比较结果表明了算法是有效的.

关键词：支配集、禁忌搜索、组合优化

所属期刊栏目：51

分类号：TP18;O221.4(自动化基础理论)

资助基金：国家自然科学基金11301255;福建省中青年教师教育科研项目JA13246

在线出版日期：2015-12-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：78-81,148