A hybrid metaheuristic approach to solving the UBQP problem

作者：Lue Zhipeng; Glover Fred; Hao Jin Kao

来源：European Journal of Operational Research, 2010, 207(3): 1254-1262.

DOI：10.1016/j.ejor.2010.06.039

• UBQP
• Memetic algorithm
• Tabu search
• Pool updating

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.

• 出版日期2010-12-16