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

• 作者: 张发展 贺毅朝 刘雪静 王泽昆
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 演化算法 离散差分演化 折扣{0-1}背包问题(D{0-1}KP) 新V型转换函数(NV)
• 年，卷（期）: 2022,（2）
• 所属期刊栏目: 理论与算法|Theory and Algorithm
• 页码范围: 468-479
• 页数: 12页
• 分类号: TP18
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2007047

摘要

折扣{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实例.