Discrete differential evolutions for the discounted {0-1} knapsack problem

摘要

This paper first proposes a discrete differential evolution algorithm for discounted {0-1} knapsack problems (D{0-1} KP) based on feasible solutions represented by the 0-1 vector. Subsequently, based on two encoding mechanisms of transforming a real vector into an integer vector, two new algorithms for solving D{0-1} KP are given through using integer vectors defined on {0, 1, 2, 3} n to represent feasible solutions of the problem. Finally, the paper conducts a comparative study on the performance between our proposed three discrete differential evolution algorithms and those developed by common genetic algorithms for solving several types of large scale D{0-1} KP problems. The paper confirms the feasibility and effectiveness of designing discrete differential evolution algorithms for D{0-1} KP by encoding conversion approaches.