Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (2): 468-479.DOI: 10.3778/j.issn.1673-9418.2007047

• Theory and Algorithm • Previous Articles     Next Articles

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

ZHANG Fazhan, HE Yichao+(), LIU Xuejing, WANG Zekun   

  1. School of Information and Engineering, Hebei GEO University, Shijiazhuang 050031, China
  • Received:2020-07-17 Revised:2020-10-15 Online:2022-02-01 Published:2020-11-05
  • About author:ZHANG Fazhan, born in 1995, M.S. candidate. His research interests include evolutionary algorithm and its applications.
    HE Yichao, born in 1969, M.S., professor. His research interests include evolutionary algorithm and its applications, combinatorial optimization and reinforcement learning.
    LIU Xuejing, born in 1980, M.S., lecturer. Her research interests include swarm intelligence, evolutionary computation, approximation algorithm, etc.
    WANG Zekun, born in 1996, M.S. candidate. His research interests include evolutionary algorithm and its applications.
  • Supported by:
    Natural Science Foundation of Hebei Province(F2020403013);Scientific Research Program of Colleges and Universities in Hebei Province(ZD2021016)


张发展, 贺毅朝+(), 刘雪静, 王泽昆   

  1. 河北地质大学 信息工程学院,石家庄 050031
  • 通讯作者: + E-mail:
  • 作者简介:张发展(1995—),男,山东潍坊人,硕士研究生,主要研究方向为演化算法及其应用。
  • 基金资助:


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.

Key words: evolutionary algorithms, discrete differential evolution, discounted {0-1} knapsack problem (D{0-1}KP), novel V-shape transfer function (NV)



关键词: 演化算法, 离散差分演化, 折扣{0-1}背包问题(D{0-1}KP), 新V型转换函数(NV)

CLC Number: