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

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