张 小 萍

(广西大学计算机与电子信息学院， 广西 南宁 530004)

0-1背包问题是一个经典的NP-hard问题，也是一个组合优化问题。0-1背包问题在生产和生活中应用较广，如物件装箱、投资组合和金融决策等，因此，0-1背包问题受到很多学者的关注。0-1背包问题可描述为：有D件物品，每件物品不可分割，第j件物品(j=1，2，…，D)的重量是wj，价值是pj，现有一个承载重量限制为C的背包，如何选择物品放入背包使得背包中物品的总重量不超过C且物品的总价值达到最大。0-1背包的数学模型可以表示为：

xj∈{0，1}，j=1，2，…，D

(1)

求解0-1背包问题的算法包括动态规划法、递归算法和回溯法等确定性算法，这类算法能够求解出问题的全局最优解，但是算法的时间复杂度与问题的规模呈指数关系，只能用于求解维度比较小的0-1背包问题。而智能优化算法只能求解出0-1背包问题的最优解域，不一定能够求解出全局最优解，但智能优化算法的时间复杂度比较低，可以用于求解高维的0-1背包问题。随着智能优化算法的发展，涌现出多种用于求解0-1背包问题的算法，这些算法在基本算法的基础上加入了改进策略来加快算法的收敛速度。周洋等人[1]在基本粒子群算法中加入贪婪策略(GOPSO)求解0-1背包问题，提高了算法的收敛性能。任静敏等人[2]通过在基本萤火虫算法中加入惯性权重、变异算子和贪婪策略(WGFA)，提高了算法的全局搜索能力。刘雪静等人[3]改进了乌鸦算法(BCSA)，先利用Chebyshev映射产生混沌序列初始化种群，使种群的初始分布比较均匀，然后使用贪婪策略修复不可行解和对可行解进行优化。……