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

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.