Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
复制标题
DOI：
10.1016/s0377-2217(00)00242-3
复制
发表时间：
2001-10
期刊：
影响因子：
--
通讯作者：
K. Katayama;H. Narihisa
中科院分区：
文献类型：
--
作者：
K. Katayama;H. Narihisa
无约束二元二次规划问题（BQP）是一个NP-难问题，有许多实际应用。本文提出了一种模拟退火（SA）为基础的启发式BQP。BQP的新SA启发式是基于一个简单的（1-opt）局部搜索启发式和设计一个简单的冷却时间表，但采用多个退火过程。为了显示SA的实际性能，我们测试公开的基准实例的大尺寸范围从500到2500个变量，并将它们与其他算法，如多启动本地搜索，以前的SA，禁忌搜索，遗传算法，将1-选择本地搜索。计算结果表明，我们的SA导致高质量的解决方案，时间短，是更有效的比竞争对手，特别是最大的基准集。此外，还报告了SA为几个大型实例找到的新的最知名的解决方案的值。
The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.