改进蚁群优化算法求解折扣{0-1}背包问题

折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem,DKP)是一个NP-困难的组合优化问题,尽管已经存在一些求解DKP的智能优化算法,但目前尚没有用蚁群优化(Ant Colony Optimization,ACO)算法求解DKP的研究.提出了一个求解DKP的改进ACO(Modifie...

Modified Ant Colony Optimization Algorithm for Discounted{0-1}Knapsack Problem

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.