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

被引:21
|
作者
Zhou, Ying [1 ]
Wang, Jiahai [2 ]
Wu, Ziyan [3 ]
Wu, Keke [1 ]
机构
[1] Shenzhen Inst Informat Technol, Sch Comp Sci, Shenzhen 518172, Peoples R China
[2] Sun Yat Sen Univ, Dept Comp Sci, Guangzhou 510006, Guangdong, Peoples R China
[3] China Secur Depository & Clearing Corp Ltd, Shenzhen Branch, 2012 Shennan Blvd, Shenzhen 518038, Peoples R China
基金
中国国家自然科学基金;
关键词
Multi-objective optimization; Decomposition; Tabu search; HOPFIELD NETWORK; LOCAL SEARCH; EVOLUTIONARY; MOEA/D;
D O I
10.1016/j.knosys.2017.11.009
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:18 / 30
页数:13
相关论文
共 50 条
  • [31] Multi-objective Optimization for Plant Design via Tabu Search
    Mandani, Faiz
    Camarda, Kyle
    28TH EUROPEAN SYMPOSIUM ON COMPUTER AIDED PROCESS ENGINEERING, 2018, 43 : 543 - 548
  • [32] A pareto-based hybrid whale optimization algorithm with tabu search for multi-objective optimization
    AbdelAziz A.M.
    Soliman T.H.A.
    Ghany K.K.A.
    Sewisy A.A.E.-M.
    Algorithms, 2019, 12 (02):
  • [33] A Pareto-Based Hybrid Whale Optimization Algorithm with Tabu Search for Multi-Objective Optimization
    AbdelAziz, Amr Mohamed
    Soliman, Taysir Hassan A.
    Ghany, Kareem Kamal A.
    Sewisy, Adel Abu El-Magd
    ALGORITHMS, 2019, 12 (12)
  • [34] Multi-objective Baby Search Algorithm
    Liu, Yi
    Li, Gengsong
    Qin, Wei
    Li, Xiang
    Liu, Kun
    Wang, Qiang
    Zheng, Qibin
    ADVANCES IN SWARM INTELLIGENCE, ICSI 2023, PT I, 2023, 13968 : 259 - 270
  • [35] The benefits of adaptive parametrization in multi-objective Tabu Search optimization
    Ghisu, Tiziano
    Parks, Geoffrey T.
    Jaeggi, Daniel M.
    Jarrett, Jerome P.
    Clarkson, P. John
    ENGINEERING OPTIMIZATION, 2010, 42 (10) : 959 - 981
  • [36] Solving Multi-Objective Resource Allocation Problem Using Multi-Objective Binary Artificial Bee Colony Algorithm
    Zuleyha Yilmaz Acar
    Fatih Başçiftçi
    Arabian Journal for Science and Engineering, 2021, 46 : 8535 - 8547
  • [37] Multiple Trajectory Search for Unconstrained/Constrained Multi-Objective Optimization
    Tseng, Lin-Yu
    Chen, Chun
    2009 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-5, 2009, : 1951 - +
  • [38] Solving Multi-Objective Resource Allocation Problem Using Multi-Objective Binary Artificial Bee Colony Algorithm
    Yilmaz Acar, Zuleyha
    Basciftci, Fatih
    ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING, 2021, 46 (09) : 8535 - 8547
  • [39] A Novel Multi-objective Evolutionary Algorithm based on a Further Decomposition Strategy
    Liu, Songbai
    Lin, Qiuzhen
    Chen, Jianyong
    2017 13TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND SECURITY (CIS), 2017, : 25 - 29
  • [40] Multi-objective group learning algorithm with a multi-objective real-world engineering problem
    Rahman, Chnoor M.
    Mohammed, Hardi M.
    Abdul, Zrar Khalid
    APPLIED SOFT COMPUTING, 2024, 166