郝 翔，贺毅朝，朱晓斌，翟庆雷

1.河北地质大学 信息工程学院，石家庄050031

2.石家庄文化传媒学校，石家庄050000

0-1背包问题（0-1 Knapsack Problem，0-1 KP）[1-2]既是一个典型的组合优化问题，也是一个NP-hard问题[3-4]，在资源分配、项目组合和整数规划等领域具有广泛的应用。折扣{0-1}背包问题（Discounted{0-1}Knapsack Problem，D{0-1}KP）[5]是由Guldan首次提出的一个0-1KP扩展形式，在商业领域有着重要的应用背景。2007年，Guldan[5]建立了D{0-1}KP的基本数学模型，并给出了求解它的动态规划算法；随后，Rong等人[6]基于D{0-1}KP的核问题和动态规划法研究了D{0-1}KP的求解算法。以上两算法均为精确算法，存在求解速度慢的缺点。贺毅朝等人[7]基于整数编码和集合编码分别给出了D{0-1}KP的第二数学模型和第三数学模型，首先提出了基于演化算法求解D{0-1}KP问题的新思路，并给出了利用遗传算法求解的新方法。随后，吴聪聪等人[8]利用变异蝙蝠算法（MDBBA）提出了求解D{0-1}KP的方法，刘雪静等人[9]利用自适应细菌觅食算法（ABFO）求解D{0-1}KP问题，冯艳红等人[10]利用差分进化帝王蝶优化算法（DEMBO）求解D{0-1}KP问题，Li等人[11]提出了利用离散鲸鱼优化算法（DWOA）求解D{0-1}KP问题。这四种算法的求解效果较遗传算法有了进一步提高。2017年，Zhu等人[12]基于离散差分进化算法HBDE提出了求解D{0-1}KP问题的新方法，并与基于整数编码的两种差分进化算法FDDE和SDDE进行比较，证明了HBDE算法的优越性。最近，He等人[13]提出了基于群论的优化算法（GTOA），并利用GTOA求解D{0-1}KP问题，随后He等人[14]又提出了基于环论的优化算法（RTEA）求解折扣背包问题的新方法，取得了更好的求解效果。2020年，Wu等人[15]针对D{0-1}KP问题提出了一类离散混合教学优化算法（HTLBO），并指出采用差分进化交叉策略的HTLBO2算法具有更好的求解性能。……