Abstract:

Discounted {0-1} Knapsack Problem （DKP） is a NP-hard combinatorial optimization problem. Although several intelligent optimization algorithms have been proposed for the DKP, no study has been found to use Ant Colony Optimization （ACO） algorithm to solve this problem. This paper presents a Modified ACO（MACO） algorithm for the DKP. The MACO algorithm uses integer coding to ensure that at most one item in each group is selected. In each step of the solution construction, MACO adopts an intra-group competitive selection to decrease time complexity. In the selection probability calculation equation, the original heuristic information is discarded to decrease the number of parameters and simplify the implementation of parameters tuning. Furthermore, a greedy hybrid optimization strategy based on both value density and value of items is designed to enhance the repaired solutions constructed by ants. The overall performance of MACO is tested and compared with other methods on four kinds of test cases. The experimental results show that the MACO algorithm is significantly superior to other algorithms.

Key words: Discounted{0-1} Knapsack Problem（DKP）, Ant Colony Optimization（ACO） algorithm, pheromone, intra-group selection, hybrid optimization

摘要：

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

关键词: 折扣{0-1}背包问题（DKP）, 蚁群优化算法（ACO）, 信息素, 组内选择, 混合优化