A hybrid quantum particle swarm optimization for the Multidimensional Knapsack Problem

被引:65
作者
Haddar, Boukthir [1 ]
Khemakhem, Mahdi [2 ]
Hanafi, Said [3 ]
Wilbaut, Christophe [3 ]
机构
[1] Univ Sfax, LOGIQ ISGI, Sfax, Tunisia
[2] Prince Sattam Bin Abdulaziz Univ, Riyadh, Saudi Arabia
[3] Univ Valenciennes, LAMIH UMR CNRS 8201, Valenciennes, France
关键词
Combinatorial optimization; Hybrid heuristic; Multidimensional Knapsack Problem; Particle swarm optimization; GENETIC ALGORITHM; TABU SEARCH; SOLVE;
D O I
10.1016/j.engappai.2016.05.006
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper we propose a new hybrid heuristic approach that combines the Quantum Particle Swarm Optimization technique with a local search method to solve the Multidimensional Knapsack Problem. The approach also incorporates a heuristic repair operator that uses problem-specific knowledge instead of the penalty function technique commonly used for constrained problems. Experimental results obtained on a wide set of benchmark problems clearly demonstrate the competitiveness of the proposed method compared to the state-of-the-art heuristic methods. (C) 2016 Elsevier Ltd. All rights reserved.
引用
收藏
页码:1 / 13
页数:13
相关论文
共 68 条
[1]  
Abraham A., 2006, SWARM INTELLIGENT SY, P3
[2]   A hybrid of Nested Partition, Binary Ant System, and Linear Programming for the multidimensional knapsack problem [J].
Al-Shihabi, S. ;
Olafsson, S. .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (02) :247-255
[3]  
[Anonymous], 2014, P COMP PUBL ANN C GE
[4]  
[Anonymous], 2005, Fundamentals of Computational Swarm Intelligence
[5]  
[Anonymous], 1999, P C EV COMP
[6]   A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem [J].
Balev, Stefan ;
Yanev, Nicola ;
Freville, Arnaud ;
Andonov, Rumen .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 186 (01) :63-76
[7]   OR-LIBRARY - DISTRIBUTING TEST PROBLEMS BY ELECTRONIC MAIL [J].
BEASLEY, JE .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1990, 41 (11) :1069-1072
[8]   Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems [J].
Beheshti, Zahra ;
Shamsuddin, Siti Mariyam ;
Yuhaniz, Siti Sophiayati .
JOURNAL OF GLOBAL OPTIMIZATION, 2013, 57 (02) :549-573
[9]  
Berberler Murat Ersen, 2013, Mathematical and Computational Applications, V18, P486
[10]   An approximate dynamic programming approach to multidimensional knapsack problems [J].
Bertsimas, D ;
Demir, R .
MANAGEMENT SCIENCE, 2002, 48 (04) :550-565