求解带有利用率惩罚背包问题的参数自适应差分进化算法

刘静宜　韩海燕

【摘 要】本文研究一类新型的背包问题，特征主要体现在目标函数不仅要最大化装载物品的价值，同时还包含关于背包利用率的凸型罚函数。首先分析该问题的线性松弛最优解性质，以揭示整数最优解的结构特征。为了有效求解该问题，设计了一种参数自适应差分进化算法。该算法中提出变异和交叉参数的自适应选择方法，在进化的过程中可以动态评估每组被选参数的性能，并用于指导下一个迭代过程的参数配置，从而避免了基本差分进化算法中参数选择的困难。实验结果显示提出的参数自适应差分进化算法性能显著优于基本差分进化算法，说明新算法在求解惩罚背包及类似问题上的有效性和稳定性。

【关键词】背包问题；利用率惩罚；参数自适应；差分进化算法

0 引言

背包问题是运筹学和管理科学领域中一类重要的NP-难组合最优化问题，对其研究具有重要的理论意义。背包问题在工业生产管理与物流作业中有着广泛的应用，例如资源分配，货物装载等，因此对其研究也具有重要的应用价值。本文研究一类新型的背包问题，特征主要体现在目标函数不仅要最大化装载物品的价值，同时还包含关于背包利用率的凸型罚函数。该问题最早作为子问题出现在动态环境下物流配送网络的运输与库存集成问题中[1]。文献[1]将动态环境下物流配送网络的运输与库存集成问题建模为非线性的广义分配问题，并将原问题重新建模问集合划分模型，提出基于列生成的分支-定价算法求解，列生成算法的价格子问题就是带有利用率惩罚背包问题。

针对背包问题及相关扩展问题，已经有大量的研究。文献[2-4]提出改进的声搜索算法求解0-1背包问题， 改进点在于提出新的操作和引入学习和自适应机制等，文献[5-8]提出了求解多维背包问题的提出了遗传算法（GA）、二进制蚂蚁算法、分散搜索算法和分布估计算法。

本文分析带有利用率惩罚背包问题的线性松弛最优解性质，以揭示整数最优解的结构特征。针对带有利用率惩罚背包问题的特征，设计了一种基于参数自适应的差分进化算法。实验结果显示提出的算法性能显著优于常规的差分进化算法，说明该算法在求解惩罚背包及类似问题上的有效性和鲁棒性。

1 问题描述

其中n为物品的数量，pj和wj为物品j的价值和重量，W为背包的容量，G（u）表示背包利用率为u时的惩罚，并且G（·）是凸函数。物品j被装入背包时，决策变量zj取1，否则取0。PKP的目标是在满足背包容量约束的前提下，选取若干个物品装入背包，使得装入物品的总价值同背包利用率的惩罚值之差最大化。由于所有重量为0且价值不小于0的物品一定被装入背包，因此，不失一般性，假设pj≥0，wj>0。

2 性质分析

将PKP问题的决策变量z从二元变量松弛为[0，1]间的连续变量，即可得到PKP问题的线性松弛问题，记为R（PKP）。文献[1]指出R（PKP）问题的最优解同PKP的最优解具有相同的结构，下文将首先分析R（PKP）的最优解性质。

3 参数自适应差分进化算法

在最优求解松弛问题R（PKP）的同时可以得到原问题PKP的一个可行解，但该可行解不能保证最优性，因此，需要针对PKP问题设计有效的求解算法。基于PKP问题的特点，提出一种改进的参数自适应差分进化算法来求解PKP问题，分别就算法设计中问题解的表达、变异操作、变异率参数自适应设计、交叉操作、交叉率参数自适应设计、选择操作、非可行解修复方法进行阐述。

3.1 解的表达

种群中每一个体对应PKP的一个解，每一个体用一个长度为n的向量z表示，每个分量zi是区间[0， 1]上的实数。zi≥0.5表示选择物品i放入背包中，zi<0.5表示物品i没有被选择。

3.2 变异操作

3.7 非可行解修复方法

如果新产生的个体是非可行解，即不满足背包容量约束，则采用一种随机修复机制对此个体进行修复。根据背包装载的超出量，随机选择多被装载的物品，将其从背包中删除，最后判断是否满足背包容量约束，如果满足则停止修复，否则重新进行随机修复。

4 实验结果

针对文献[9]给出的0-1背包问题的算例，采用文献[1]定义的背包利用率的罚函数G（·），对提出的参数自适应差分进化算法进行性能测试。所有算法均利用Microsoft Visual studio编程实现， 在Intel（R） Core（TM） i5-4210M CPU @ 2.60GHz，4.00GB内存物理地址扩展， Microsoft Windows 8.1系统电脑上运行.

文献[9]中算例的产生方法如下： 假设任意物品的重量wj和价值pj独立均匀分布在区间[1， 100]内，背包容量W=σ∑wj。按照N=100， 200， 500和σ=0.3， 0.5， 0.7的组合，生成9组算例。求解的参数设置保持不变的条件下， 针对每组算例，分别使用标准差分进化算法和参数自适应差分进化算法独立运行50次，得到的优化结果如表1所示。

由表1可见，对于所有算例，参数自适应差分进化算法都能获得更好的最好解、均值和最差解，对于大部分算例，参数自适应差分进化算法能获得更好的标准差。这说明了参数自适应差分进化算法具有更好的有效性和稳定性，显示出良好的优化潜力。

5 结论

针对带有背包利用率的凸型罚函数的新型背包问题，建立了数学模型，分析了线性松弛最优解性质和揭示了整数最优解结构，并提出了一个求解该问题的参数自适应差分进化算法。该算法中提出变异和交叉参数的自适应选择方法，在进化的过程中可以动态评估每组被选参数的性能，并用于指导下一个迭代过程的参数配置，从而避免了基本差分进化算法中参数选择的困难。通过对不同规模算例的计算实验，表明所提出的改进差分进化算法在求解这类新型背包问题上具有良好的优化潜力和稳定性，将来可以扩展到求解其他类型的背包问题。

【参考文献】

[1]Freling R， Romeijn H E， Romero Morales D， Wagelmans A P M. A branch-and-price algorithm for the multiperiod single-sourcing problem [J]. Operations Research， 2003，51（6）：922-939.

[2]李若平，欧阳海滨，高立群，等.学习型和声搜索算法及其在0-1 背包问题中的应用[J].控制与决策，2013，28（2）：205-210.

[3]欧阳海滨，高立群，孔祥勇，等.一种求解0-1 背包问题的二进制修正和声搜索算法[J].控制与决策，2014，29（7）：1174-1180.

[4]Tung K T， Li K L， Xua Y M. Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem [J]. Applied Soft Computing， 2013，13（4）：1774-1780.

[5]Chu P C， Beasley J E. A genetic algorithm for the multidimensional knapsack problem[J]. Journal of Heuristics， 1998，4（1）：63-86.

[6]Kong M， Tian P， Kao Y C. A new ant colony optimization algorithm for the multidimensional knapsack problem [J]. Computers & Operations Research， 2008，35（8）：2672-2683.

[7]Hanafi S， Wilbaut C. Scatter search for the 0-1 multidimensional knapsack problem[J]. Journal of Mathematical Modelling and Algorithms， 2008， 7（2）：143-159.

[8]王凌，王圣尧，方晨.一种求解多维背包问题的混合分布估计算法控制与决策[J].2011，26（8）：1121-1125.

[9]Martello， S， Toth P. Knapsack Problems， Algorithms and Computer Implementations[M]. 1990 John Wiley and Sons， New York.

[责任编辑：汤静]