张 铭，邓文瀚，林 娟，钟一文

1.福建农林大学 计算机与信息学院，福州350002

2.智慧农林福建省高等学校重点实验室（福建农林大学），福州350002

背包问题（Knapsack Problem，KP）是经典的NP-困难问题，它包括多维背包问题、完全背包问题、分组背包问题和折扣{0-1}背包问题（Discounted {0-1} Knapsack Problem，DKP）等多种类型。DKP 在2007 年首先在文献[1]中提出，它是对商场促销行为的抽象，在商业、投资决策、资源分配和密码学等方面都有实际应用价值。由于DKP是NP-困难的，近几年许多学者对使用智能优化算法来求解DKP进行了深入的研究，如遗传算法（Genetic Algorithm，GA）[2-4]、差分进化算法（Differential Evolution，DE）[5-6]、二进制蝙蝠算法[7]、帝王蝶算法[8-9]、混沌乌鸦算法[10]、蛾类搜索算法[11]、基于群论优化算法（Group Theory-based Optimization Algorithm，GTOA）[12]、细菌觅食算法（Bacterial Foraging Algorithm，BFO）[13]和粒子群优化算法[14]等。由于DKP 提出的时间还不是很长，关于该问题的研究在解的精度等方面还存在极大改进空间。蚁群优化算法（Ant Colony Optimization algorithm，ACO）是求解组合优化问题的经典群智能优化算法，目前尚未发现ACO 在DKP 上的应用研究。同时，现有的算法大多使用价值密度来引导解的优化，单纯使用价值密度来引导解的优化会导致算法过早收敛，影响其寻优能力。针对在DKP 上的以上不足，本文提出了一个改进的蚁群优化（Modified ACO，MACO）算法，算法具备以下几个特征：

（1）根据DKP的构造特点，采用组内竞争方式计算物品的选择概率，从而降低算法的时间复杂度。

（2）在不降低算法精度的前提下舍去启发式信息，从而减少算法所使用的参数，简化参数设置。

（3）采用混合基于价值密度及价值的优化算子，提高算法的寻优能力。

（4）基于上述的改进模块设计出的算法，在DKP问题的求解中具有良好的性能表现。……