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

摘要：

折扣{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)

所属期刊栏目：16

分类号：TP18(自动化基础理论)

资助基金：河北省自然科学基金;河北省高等学校科学研究计划项目

在线出版日期：2022-02-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：468-479