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

?

?

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

?

?

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

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

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，wj0。

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放入背包中，zi0.5表示物品i没有被选择。

3.2变异操作

3.7非可行解修复方法

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

4实验结果

针对文献[9]给出的0-1背包问题的算例，采用文献[1]定义的背包利用率的罚函数G（·），对提出的参数自适应差分进化算法进行性能测试。

所有算法均利用MicrosoftVisualstudio编程实现，在Intel（R）Core（TM）i5-4210MCPU@2.60GHz，4.00GB内存物理地址扩展，MicrosoftWindows8.1系统电脑上运行.

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