Title: A novel quantum-inspired binary wolf pack algorithm for difficult knapsack problem

Authors: Yang-Jun Gao; Feng-Ming Zhang; Yu Zhao; Chao Li

Addresses: Equipment Management and Unmanned Aircraft Engineering College, Air Force Engineering University, Xi'an, Shaanxi Province, China ' Equipment Management and Unmanned Aircraft Engineering College, Air Force Engineering University, Xi'an, Shaanxi Province, China ' Equipment Management and Unmanned Aircraft Engineering College, Air Force Engineering University, Xi'an, Shaanxi Province, China ' Equipment Management and Unmanned Aircraft Engineering College, Air Force Engineering University, Xi'an, Shaanxi Province, China

Abstract: 0-1 knapsack problem is a classical combinatorial optimisation problem, which is often used to validate the search performance of intelligent algorithms. Although the Binary Wolf Pack Algorithm (BWPA) can provide an effective solution to the general knapsack problem, it cannot achieve satisfactory optimisation results for the difficult knapsack problems. In order to improve the BWPA's searching ability in a difficult knapsack problem which has not been well resolved, a novel Quantum-Inspired WPA (QWPA) based on quantum encoding to enhance the performance of BWPA is presented. In this paper, the detailed quantitative design with a modified form of quantum collapse for the three important behaviours in QWPA is proposed and a new diversity analysis mechanism to verify the diversity of the proposed algorithm is given. Numerical simulation is obtained to show that the QWPA has a comparative performance than other quantum-inspired algorithms in solving the difficult knapsack problems.

Keywords: BWPA; binary wolf pack algorithm; quantum encoding; combinatorial optimisation; diversity; difficult 0-1 knapsack problem.

DOI: 10.1504/IJWMC.2019.099861

International Journal of Wireless and Mobile Computing, 2019 Vol.16 No.3, pp.222 - 232

Received: 29 May 2018
Accepted: 18 Sep 2018
Published online: 24 May 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article