Abstract: The Multiple Knapsack Problem（MKP） is a classic NP-hard static combination optimization problem.The design of heuristic information is one of the key techniques to MKP for most meta-heuristics.This paper proposes a new design of heuristic information for MKP by measuring the vector distance between the capacity of the knapsack and resource of the object.Based on this heuristic information design,this paper re-implements ACS to tackle MKP benchmark.Among the 30 problem instances we are testing,our new approach finds 16 optima,which is overall superior over the current ACS implementation.This paper also compares the results to that of state-of-the-art results coming from GA approach.The testing results show that our new approach has better average quality than GA approach.

Key words: MKP, ACS, heuristic information

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

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