A Hybrid Algorithm Based on Tabu Search and Chemical Reaction Optimization for 0-1 Knapsack Problem

摘要

The 0-1 knapsack problem(01KP) is a well-known NP-complete problem in combinatorial optimization problems. There exist different approaches employed to solve the problem such as brute force, dynamic programming, branch and bound, etc. In this paper, a hybrid algorithm CROTS (Chemical Reaction Optimization combined with Tabu Search) is proposed to address the issue. One of the four elementary reaction of CRO is performed first, and after that tabu search is employed to search for the neighbors of the optimum solution in the population. The experimental results show that CROTS owns better performance in comparison with GA and the original CRO.