| 最小赋权支配集的迭代禁忌搜索算法 |
| |
| 引用本文： | 林,耿.最小赋权支配集的迭代禁忌搜索算法[J].计算机工程与应用,2015,51(23):78-81. |
| |
| 作者姓名： | 林 耿 |
| |
| 作者单位： | 闽江学院 数学系，福州 350108 |
| |
| 摘 要： | 最小赋权支配集是一个NP困难的组合优化问题，有着广泛的应用背景。提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法。该算法采用随机贪心构造算法构造初始解，并利用快速的局部禁忌搜索算法寻找局部最优解，通过随机扰动和修复策略来搜索新的区域，以期跳出当前的局部最优解。用顶点数为800到1 000的大规模标准测试例子测试提出的算法。数值实验结果和与现存的启发式算法比较结果表明了算法是有效的。
|
| 关 键 词： | 支配集 禁忌搜索 组合优化 |
Iterated tabu search algorithm to minimum weighted dominating set |
| |
| LIN Geng.Iterated tabu search algorithm to minimum weighted dominating set[J].Computer Engineering and Applications,2015,51(23):78-81. |
| |
| Authors: | LIN Geng |
| |
| Affiliation: | Department of Mathematics, Minjiang University, Fuzhou 350108, China |
| |
| Abstract: | The minimum weighted dominating set problem is one of NP-hard combinatorial optimization problems, and has lots of applications. In this paper, an efficient iterated tabu search algorithm is proposed to solve the minimum weighted dominating set problem. It adopts a random greedy construction algorithm to generate initial solutions, and uses a fast tabu local search algorithm to find local minimizers. In order to escape from the current local minimizer, the proposed algorithm presents a random perturbation and a repair strategy to search new solution regions. The experiments are done on a number of large scale benchmarks with 800 to 1, 000 vertices from the literature. Numerical results and comparisons with several heuristic methods indicate that the proposed algorithm is efficient. |
| |
| Keywords: | dominating set tabu search combinatorial optimization |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
