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

Authors:
  • HZHong Zhu
    Hong Zhu
  • YHYichao He
    Yichao He
  • XWXizhao Wang
    Xizhao Wang
  • ETEric C.C. Tsang
    Eric C.C. Tsang

Abstract
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.