A hybrid metaheuristic approach to solving the UBQP problem
A hybrid metaheuristic approach to solving the UBQP problem
复制标题
DOI：
10.1016/j.ejor.2010.06.039
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
Zhipeng Lü;F. Glover;Jin-Kao Hao
中科院分区：
文献类型：
--
作者：
Zhipeng Lü;F. Glover;Jin-Kao Hao
提出了一种求解无约束二元二次规划（UBQP）问题的混合元启发式算法（HMA）。通过将禁忌搜索过程的进化算法的框架中，所提出的方法具有几个显着的特点，包括多样化的组合算子和基于距离和质量的更换标准池更新。该算法能够很容易地获得最佳已知的解决方案，为31个大的随机实例高达7000个变量（没有以前的算法已经做了），并找到新的最佳解决方案的9个实例中的3个来自集划分问题，证明了我们所提出的算法在解决方案的质量和计算效率方面的功效。此外，HMA算法的一些关键元素和性质进行了分析。
This paper presents a hybrid metaheuristic approach (HMA) for solving the unconstrained binary quadratic programming (UBQP) problem. By incorporating a tabu search procedure into the framework of evolutionary algorithms, the proposed approach exhibits several distinguishing features, including a diversification-based combination operator and a distance-and-quality based replacement criterion for pool updating. The proposed algorithm is able to easily obtain the best known solutions for 31 large random instances up to 7000 variables (which no previous algorithm has done) and find new best solutions for three of nine instances derived from the set-partitioning problem, demonstrating the efficacy of our proposed algorithm in terms of both solution quality and computational efficiency. Furthermore, some key elements and properties of the HMA algorithm are also analyzed.