MKP的一种向量启发信息的设计和实现

• 作者: 吕强 王介新 钱培德
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 多背包问题 蚁群优化算法 启发信息
• 年，卷（期）: 2007,（28）
• 所属期刊栏目: 学术探讨
• 页码范围: 89-91
• 页数: 3页
• 分类号: TP301.6
• 字数: 2662字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2007.28.029

摘要

多背包问题(MKP)是一个典型的NP-hard组合优化问题.启发信息的设计是众多启发搜索算法解决MKP的关键手段之一.提出了一种新的针对MKP的启发信息设计,利用了向量距离来度量背包容量和物体消耗之间的拟和程度.基于这种启发信息,通过蚁群优化算法ACS实现了对MKP标准测试库30个实例的计算,与ACS现有启发信息相比,该方法有16例找到最优解,并全面优于同类实现.同时与当前MKP最好解决方案GA比较了2例结果,该方法的平均性能都优于该解决方案.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钱培德	苏州大学计算机科学与技术学院	77	844	16.0	25.0
2	吕强	苏州大学计算机科学与技术学院	134	1011	15.0	26.0
3	王介新	苏州大学计算机科学与技术学院	1	0	0.0	0.0