Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem

The 0–1 knapsack problem (KP01) is a well-known combinatorial optimization problem. It is an NP-hard problem which plays important roles in computing theory and in many real life applications. Chemical reaction optimization (CRO) is a new optimization framework, inspired by the nature of chemical reactions. CRO has demonstrated excellent performance in solving many engineering problems such as the quadratic assignment problem, neural network training, multimodal continuous problems, etc. This paper proposes a new chemical reaction optimization with greedy strategy algorithm (CROG) to solve KP01. The paper also explains the operator design and parameter turning methods for CROG. A new repair function integrating a greedy strategy and random selection is used to repair the infeasible solutions. The experimental results have proven the superior performance of CROG compared to genetic algorithm (GA), ant colony optimization (ACO) and quantum-inspired evolutionary algorithm (QEA).

Figure optionsDownload as PowerPoint slideHighlights
► A new algorithm based on chemical reaction optimization and greedy strategy is proposed to solve 0–1 knapsack problem.
► Four problem-specific operators are designed to implement the local search and global search.
► A new repair operator which helps the algorithm to be fast convergence and avoids local optima is proposed.