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

摘要：

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

关键词：多背包问题、蚁群优化算法、启发信息

所属期刊栏目：43

分类号：TP301.6(计算技术、计算机技术)

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

页数：共3页

页码：89-91