Solving 0-1 Knapsack Problems by a Discrete Binary Version of Differential Evolution
Chen Peng, Jian Li, Zhiming Liu · 2008
The 0-1 knapsack problem (KP) is one of the classical NP-hard problems with binary decision variables. The traditional differential evolution (DE) is an effective stochastic parallel search evolutionary algorithm for global optimization based on real valued crossover and mutation operations in continuous space. To solve KPs, based on DE, a discrete binary version of differential evolution (DBDE) was introduced, where each component of a mutated vector component changes with the probability and will take on a zero or one value. The approach was implemented to 4 cases. By comparisons with the results of the discrete binary version of particle swarm optimization (DPSO), DBDE outperformed DPSO for all the cases with better solutions and more rapid convergence speed.