Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem

Abstract

The discounted {0-1} knapsack problem (D{0-1}KP) is a more complex variant of the classic 0-1 knap-sack problem (0-1KP). In order to efficiently solve the D{0-1}KP by using discrete differential evolution algorithm, firstly, a novel V-shape transfer function (NV) is proposed. The real vector of an individual is mapped into a binary vector by NV. Compared with the existing S-shaped and V-shaped transfer function, NV has lower computational complexity and higher efficiency. Then, a new discrete differential evolution algorithm (NDDE) is given based on the novel V-shape transfer function. A novel and efficient method for solving D{0-1}KP is proposed by NDDE. Finally, in order to verify the efficiency of NDDE in solving D{0-1}KP, it is used to solve four kinds of large-scale D{0-1}KP instances, and the results are compared with the existing algorithms such as group theory-based optimi-zation algorithm (GTOA), ring theory-based evolutionary algorithm (RTEA), hybrid teaching-learning-based optimi-zation algorithm (HTLBO) and whale optimization algorithm (WOA). The results show that NDDE not only has higher accuracy, but also has good stability, which is very suitable for solving large-scale D{0-1}KP instances.

Keywords

• |evolutionary algorithms|discrete differential evolution|discounted {0-1} knapsack problem (d{0-1}kp)|novel v-shape transfer function (nv)