A multi-objective tabu search algorithm based on decomposition for multi-objective unconstrained binary quadratic programming problem

摘要

Unconstrained binary quadratic programming problem (UBQP) is a well-known NP-hard problem. In this problem, a quadratic 0-1 function is maximized. Numerous single-objective combinatorial optimization problems can be expressed as UBQP. To enhance the expressive ability of UBQP, a multi-objective extension of UBQP and a set of benchmark instances have been introduced recently. A decomposition-based multi-objective tabu search algorithm for multi-objective UBQP is proposed in this paper. In order to obtain a good Pareto set approximation, a novel weight vector generation method is first introduced. Then, the problem is decomposed into a number of subproblems by means of scalarizing approaches. The choice of different types of scalarizing approaches can greatly affect the performance of an algorithm. Therefore, to take advantages of different scalarizing approaches, both the weighted sum approach and the Tchebycheff approach are utilized adaptively in the proposed algorithm. Finally, in order to better utilize the problem-specific knowledge, a tabu search procedure is designed to further optimize these subproblems simultaneously. Experimental results on 50 benchmark instances indicate that the proposed algorithm performs better than current state-of-the-art algorithms. (C) 2017 Elsevier B.V. All rights reserved.