基于离散混合多宇宙算法求解折扣{0-1}背包问题

• 作者: 郝翔 贺毅朝 朱晓斌 翟庆雷
• 来源期刊: 计算机工程与应用
• 关键词: 离散混合多宇宙算法 折扣{0-1}背包问题 模运算 突变策略 局部搜索策略
• 年，卷（期）: 2021,（18）
• 所属期刊栏目: 理论与研发|Theory, Research and Development
• 页码范围: 103-113
• 页数: 11页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008-0454

摘要

为了利用多宇宙算法(MVO)求解折扣{0-1}背包问题(D{0-1}KP),基于模运算建立了离散型隧道模型和离散虫洞模型,引入具有反向搜索与突变特性的局部搜索策略,提出了第一个具有四进制编码的离散混合多宇宙算法DHMVO.在利用修复与优化算法消除不可行解的基础上,基于DHMVO提出了求解D{0-1}KP的一个新方法.为了检验DHMVO求解D{0-1}KP的性能,利用Kruskal-walli检验确定了其参数的最佳取值;将DHMVO求解四类大规模D{0-1}KP实例的计算结果与已有最好算法的计算结果进行比较,比较结果表明:DHMVO比其他算法的求解精度更高、稳定性更强,非常适合高效求解大规模D{0-1}KP实例.