An Efficient Differential Evolution Algorithm for Solving 0–1 Knapsack Problems

摘要

The traditional differential evolution algorithm was originally, and still is mainly, used to solve continuous optimization problems. As a result, it has not commonly been considered as applicable for several real-world problems in the permutation-based domain. In this paper, a novel differential evolution algorithm, which incorporates several effective components, is introduced. These components increase search effectiveness by providing a good balance between exploration (discovering new solutions) and exploitation (further exploring current solutions) processes. Moreover, a dual representation of solutions, which has the capability to allow normal continuous handling of variables by differential evolution operators, and at same time provide binary variables for fitness measurement, is employed. To judge the performance of the proposed algorithm, 14 instances of 0–1 knapsack problems have been solved and the results have been compared with those obtained from 11 state-of-the-art algorithms. Results show that the proposed algorithm was able to outperform other algorithms in solving small and medium sized knapsack problems and is competitive in large-sized problems.