改进蚁群优化算法求解折扣{0-1}背包问题

• 作者: 张铭 邓文瀚 林娟 钟一文
• 来源期刊: 计算机工程与应用
• 关键词: 折扣{0-1}背包问题(DKP) 蚁群优化算法(ACO) 信息素 组内选择 混合优化
• 年，卷（期）: 2021,（13）
• 所属期刊栏目: 理论与研发|Theory, Research and Development
• 页码范围: 85-95
• 页数: 11页
• 分类号: TP18
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2006-0278

摘要

折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem,DKP)是一个NP-困难的组合优化问题,尽管已经存在一些求解DKP的智能优化算法,但目前尚没有用蚁群优化(Ant Colony Optimization,ACO)算法求解DKP的研究.提出了一个求解DKP的改进ACO(Modified ACO,MACO)算法.MACO算法使用整数编码以保证每组物品最多只有一个物品被选中,在MACO算法构造解的每一步,采用组内竞争选择来降低算法的时间复杂性,对计算选择概率的公式,放弃启发式信息以减少参数并简化算法参数设置,对蚂蚁构造出的解,经修复后使用基于价值密度和价值的混合贪婪优化算子来提高算法的寻优能力.在四类测试用例上对MACO算法进行了测试并与其他算法进行比较,实验结果表明MACO算法的性能明显优于其他算法.