Title: An improved chemical reaction optimisation algorithm for the 0-1 knapsack problem

Authors: Hamza Onoruoiza Salami; Abubakar Bala

Addresses: College of Computer Science and Engineering, University of Hafr al Batin, Hafr al Batin 31991, Saudi Arabia ' Department of Electrical and Electronics Engineering, Universiti Teknologi PETRONAS, Malaysia, 32610 Bandar, Seri Iskandar, Perak, Malaysia

Abstract: Knapsack problems (KPs) are well studied NP-hard problems with numerous real-life applications like capital budgeting, cargo loading, load-shedding in microgrids, and resource allocation in cloud computing. Chemical reaction optimisation (CRO) is a recently developed metaheuristic algorithm that works based on the principles of chemical reactions. This paper proposes a CRO-based algorithm for solving the 0-1 knapsack problem (0-1 KP). The proposed algorithm (newCRO) utilises a novel, optimistic neighbourhood search operator and a greedy repair and optimisation operator to fix invalid solutions and improve feasible solutions. We test the newCRO on a wide range of large-scale 0-1 KP benchmark problems, and its results are compared with five other existing methods to show its superior optimisation capabilities.

Keywords: chemical reaction optimisation; CRO; knapsack problems; metaheuristic algorithms.

DOI: 10.1504/IJBIC.2022.124334

International Journal of Bio-Inspired Computation, 2022 Vol.19 No.4, pp.253 - 266

Accepted: 02 Jul 2021
Published online: 22 Jul 2022 *

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