摘要： 提出迭代禁忌算法求解0-1二次规划问题。在局部搜索过程中，使用禁忌搜索贪心跳坑策略，能够使算法有效跳出局部最优值的陷阱。采用国际上公认的30个算例作为算法测试实验集，与传统的禁忌搜索、模拟退火算法以及混合算法进行比较。实验结果表明，该算法在所有算例上都能够得到文献中报告的最优解，且计算效率明显优于其他算法。

关键词: 启发式算法, 0-1二次规划, 局部搜索, 禁忌搜索, 跳坑策略

Abstract: This paper presents an iterated Tabu Search(TS) algorithm for the Binary Quadratic Programming(BQP) problem. The TS as the Local Search(LS) and a new perturbation strategy makes the search jump into a more promising area when TS falling into the local optimum. Experimental results show that the proposed algorithm can reach the best known solution on all the 30 large OR-library instances and comparisons with TS. Simulated Annealing(SA) and Memetic Algorithm(MA) demonstrate the competitiveness of the proposed algorithm.

Key words: Heuristics Algorithm(HA), 0-1 Binary Quadratic Programming(BQP), Local Search(LS), Tabu Search(TS), perturbation strategy

中图分类号: 

• TP301.6