Solving 0-1 Knapsack Problems via a Hybrid Differential Evolution

The 0-1 knapsack problem (KP) is a classical NP-hard problem with binary decision variables. The traditional differential evolution (DE) is an effective stochastic parallel search evolutionary algorithm and customized to continuous function optimization. To solve KPs, based on DE, a discrete binary version of differential evolution (DBDE) was employed, where each component of a mutated vector component changes with the probability and will take on a zero or one value. Moreover, a heuristic operator was employed to handle the constraint and to enhance local search. The approach was implemented to 3 cases. By comparisons with the other evolutionary algorithms, DBDE have shown the feasibility and effectiveness.