计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (2): 468-479.DOI: 10.3778/j.issn.1673-9418.2007047

• 理论与算法 • 上一篇    下一篇

新颖的离散差分演化算法求解D{0-1}KP问题

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

  1. 河北地质大学 信息工程学院,石家庄 050031
  • 收稿日期:2020-07-17 修回日期:2020-10-15 出版日期:2022-02-01 发布日期:2020-11-05
  • 通讯作者: + E-mail: heyichao@hgu.edu.cn
  • 作者简介:张发展(1995—),男,山东潍坊人,硕士研究生,主要研究方向为演化算法及其应用。
    贺毅朝(1969—),男,河北晋州人,硕士,教授,主要研究方向为演化算法及其应用、组合优化、强化学习。
    刘雪静(1980—),女,河北定州人,硕士,讲师,主要研究方向为群智能、演化计算、近似计算等。
    王泽昆(1996—),男,河北石家庄人,硕士研究生,主要研究方向为演化算法及其应用。
  • 基金资助:
    河北省自然科学基金(F2020403013);河北省高等学校科学研究计划项目(ZD2021016)

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)

摘要:

折扣{0-1}背包问题(D{0-1}KP)是0-1背包问题(0-1KP)的一种更复杂的扩展形式。为了利用离散差分演化高效求解D{0-1}KP,首先提出了一个新V型转换函数(NV),通过NV将个体的实向量映射为一个二进制向量,与已有的S型和V型转换函数相比,NV计算复杂度更低,求解效率更高。然后,基于新V型转换函数给出了一种新的离散差分演化算法(NDDE),并利用NDDE提出了求解D{0-1}KP的一个新的高效方法。最后,为了验证NDDE求解D{0-1}KP的性能,利用它求解四类大规模D{0-1}KP实例,并与基于群论的优化算法(GTOA)、基于环理论的演化算法(RTEA)、混合教学优化算法(HTLBO)和鲸鱼优化算法(WOA)等已有算法的最好计算结果进行比较,比较结果表明,NDDE不仅求解精度更高,而且算法的稳定性佳,非常适于求解大规模D{0-1}KP实例。

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

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.

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

中图分类号: