一种求解KPC问题的带有编码复用离散混合差分进化算法

郝 翔，李香军

(河北地质大学 信息工程学院，河北 石家庄 050031)

0 引言

0-1背包问题（0-1 Knapsack problem, 0-1KP）[1-2]既是一个 NP-complete问题，也是一个典型的组合优化问题，在资源分配、项目组合和整数规划等[3]领域有广泛的应用。0-1KP衍化出了多种扩展形式，其中具有单连续变量的背包问题（knapsack problem with a single continuous variable, KPC）[4]是一个在物品生产、组织协调、分配管理以及其他经济问题中具有重要的应用价值的0-1KP问题扩展形式之一，由 Marchand和 Wolsey于 1999年提出。KPC问题带有一个连续变量S，S的连续变化会导致背包容量发生扩大或者缩小，从而导致问题求解难度增大。由于0-1KP是KPC的一个特例，因此KPC也是一个NP-complete问题，如何对其进行快速、高效求解是一个重要的问题。

2011年，Lin等人[5]给出了KPC问题的混合整型规划公式，并通过将KPC问题转化为0-1KP和 pseudo-KP的方法，分别利用动态规划算法COMBO和分支定界算法EXPKNAP进行求解，显然算法具有很高的时间复杂度。2012年，Buther和Briskorn[6]提出了等价构造法和启发式策略，将KPC转化为0-1KP问题，最后通过COMBO方法对转化后的KP问题进行求解，执行速度仍较慢。2018年，He等人[7]首先利用放缩法将KPC中的连续变量离散化，并基于动态规划法提出了求解KPC的精确算法DP-KPC。上述算法均采用了动态规划等精确算法，时间复杂度都较高，在求解大规模KPC实例时存在速度慢、在限定时间内不能获得精确解的缺点，不能满足实际应用中时效性要求。为此，He等人[8]于 2018年提出了基于演化算法求解KPC问题的新思路，在利用降维法消除连续变量的基础上，基于离散差分演化算法给出了求解KPC的算法S-HBDE和B-HBDE，求解效果有了很大的提高。He等人[9]将 KPC的单连续变量与物品的装填方案（0-1向量）一起作为个体编码，基于编码转换技术提出了求解KPC问题的一个具有混合编码的差分进化算法 ETDE，该算法不需要进行放缩或者等价变换等操作，较文献[8]中的算法更加容易实现。

为了满足现实生产中对计算结果与时效性的要求，本文提出了一个具有编码复用的离散混合差分进化算法（Discrete hybrid differential evolution algorithm with code reuse, DHDE）来求解KPC问题。在算法DHDE单个种群的一次进化中，通过自适应的选择编码维度为n的 S-HBDE算法或者选择编码维度为(n+1)的 ETDE来进化个体，并最终获得KPC实例的最优解。

1 KPC 问题

KPC的定义：给定n个物品的集合N={ 1 ,2,…,n}和一个基本载重为C的背包，其中物品j∈N具有价值pj和重量wj，背包的可变载重S是区间[l,u]的一个连续变量，pj、wj和C是正有理数，S，l和u为有理数，且l＜0＜u.给定一个惩罚系数c＞0,如何确定S的取值以及在S确定的情况下如何选择物品装入背包，使得物品的重量之和在不超过载重C+S的前提下价值之和减去cS最大。

KPC问题的基本数学模型KPCM1如下：

其中，X= ［x1,x2,… ,xn］∈{0,1}n，xj=1(1≤j≤n)表示物品j被装入了背包，xj= 0 (1 ≤j≤n)表示物品j没有被装入背包。从KPCM1中不难看出，KPC的背包载重不再固定不变，而是由连续变量S进行连续调整，当S＞0时背包载重增加，当S＜ 0 时背包载重减少; 同时，目标函数也不只是装入背包物品的价值之和，而是要加上了一个关于S的增量（–cS）。

为了方便离散演化算法求解KPC问题，He等人在文献[8]中基于降维法“消去”连续变量S，提出了KPC的一个新数学模型KPCM2，其描述如下：

2 S-HBDE和ETDE求解KPC

2.1 S-HBDE for KPC

从上述步骤中不难看出，S-HBDE算法的个体编码维度为n。由于篇幅缘故，S-HBDE算法的进化操作以及M2-GROA算法伪代码请见参考文献[8]，以下不再赘述。

2.2 ETDE for KPC

由于篇幅缘故，ETDE算法的进化操作以及KPC-GROA算法伪代码请见参考文献[9]，以下不再赘述。

3 DHDE求解KPC

为了高效的求解KPC问题，本文提出了一个具有编码复用的离散混合差分进化算法 DHDE。算法 DHDE仅有一个种群且个体编码维度为(n+1)，采用与ETDE算法相同方式进行初始化。在算法的每一次进化中，采用公式（7）自适应的随机选择S-HBDE或者ETDE算法进化个体。在利用算法 S-HBDE时仅仅利用前n个编码位置，第(n+1)个位置的数值通过计算获得。在利用算法 ETDE时则利用全部的(n+1)个编码位置，操作方式与原先算法相同。当满足终止条件时，此时f(Ybest,Sbest)即为利用算法DHDE求解KPC问题的最优解。

其中，bn表示利用前一次算法进化个体时适应度改进的数目，Pbn∈ [ 0,1]表示其对应的适应度改进概率，NP表示种群数目。Pbn越接近1表示前一次选取的算法的改进效果越好。所以，利用随机数rand∈ [ 0,1]是否小于Pbn来决定是否继续选择前一次所采用的进化算法，若小于，则仍采用前一次的进化算法；否则，采用另一个进化算法。

假设NP表示种群数目，n为 KPC实例中物品个数，MIT为迭代次数，A表示DHDE上一次进化种群选择的算法，可以选择 S-HBDE或者ETDE，bn表示前一次利用算法A进化个体时适应度改进的数目，Pbn∈ [ 0,1]表示其对应的适应度改进概率，rand是在[0,1]上的随机数。P(t)={(Xi(t),S(t) ) |1 ≤i≤N}表示 MOBTGA的第t代种 群 ， (Xt(t),St) = (xt1(t),xt2(t) , … ,xtn(t),St)表 示临时实数向量元组， (Yt(t),S(t) ) =(yt1(t),yt2(t),…,ytn(t),St)表示与(Xt(t),St)对应的个体向量元组。(Ybest,Sbest)表示由算法ETDE得到的最优解。则DHDE的伪代码如下:

算法1 DHDE

输入：一个KPC实例，S-HBDE和ETDE进化算子参数，NP，n和MIT。

输出：最优解 (Ybest,Sbest)以及目标函数值f(Ybest,Sbest)

Step.1按照价值密度pj/wj(1 ≤j≤n)由大到小的次序依次将物品对应下标存入的数组H[1 …n]中。

Step.2初始化种群P(t)，获得个体对应的元组向量(Yi(t) ,Si(t) ) ,1≤i≤NP,利用 KPC-GROA 对(Yi(t) ,Si(t))进行修复与优化操作并由f(Yi(t) ,Si(t))的大小获得 (Ybest,Sbest)。

Step.3t←0，bn←0和随机选择算法A

Step.4当t≤MIT，执行Step.5，否则执行Step.9

Step.5根据算法A的操作算子进化种群个体，并由与算法A对应的修复与优化操作修复个体向量

Step.6更新bn和Pbn值

Step.7由rand与Pbn的大小判定是否保持上一次的算法A，获得下一次进化个体的算法A

Step.8更新 (Ybest,Sbest)，t←t+1，转到Step.4

Step.9输出 ( (Ybest,Sbest),f(Ybest,Sbest))

由文献[8][9]知，KPC-GROA的时间复杂度为O(n)，M2-GROA的时间复杂度为O(n2)。在算法 DHDE中，step1由快速排序[10]实现，时间复杂度为O(nlogn)，Step.2的时间复杂度为O(NP*n)，Step.3-Step 8的时间复杂度为O(MIT*NP*n2)，因此DHDE的时间复杂度为O(nl ogn) +O(NP*n)+O(MIT*NP*n2) =O(MIT*NP*n2)。

4 实验结果与分析

4.1 KPC 实例

本文实验环境在配置为 Intel(R) CoreTM i5-8300H CPU@2.3 GHz和8 GB的RAM的微型计算机上进行，编程语言为 C，编译环境为Codeblocks 17.12，使用Python在编译环境JetBrains PyCharm2018上绘图。

KPC实例来自于文献[5]中提供的公开数据集，KPC的四类大规模实例分别是不相关实例ukpc、弱相关实例wkpc、强相关实例skpc和逆强相关实例ikpc，其中每一类都包含10个不同规模的实例，实例规模n∈ { 100,200,… ,1 000}。所有实例的具体数据可以在网址：https://www.researchgate.net/project/KPC-problem-and-Its-algorithms中获得。

4.2 DHDE 与其它算法的比较

在本节中，首先利用DHDE算法对四类KPC实例独立运行50次，然后将得到的计算结果与利用DP-KPC ETDE、S-HBDE和B-HBDE的已有结果进行比较，DHDE中使用的S-HBDE和ETDE算法的设置参数与文献[8][9]相同，具体参数见参考文献。在表 1-表 4中给出上述算法分别求解ukpc类实例、wkpc类实例、skpc类实例以及ikpc类实例的计算结果。其中，OPT是利用DP-KPC算法求解KPC实例获得的最好值，Best，Mean和Std分别表示上述算法独立计算实例50次的计算结果的最优值，平均值以及标准差 （由于上述算法求解 kpc实例的运行时间差别不大，在表 1-4中便不再列出）。

表1 ukpc 实例结果Tab.1 The result of ukpc instances

表2 w kpc实例结果Tab.2 The result of wkpc instances

在表1-4中，通过统计 4个演化算法求解四类 KPC实例获得的Best总数不难发现，算法DHDE的寻优性能最强，共31个实例可以找到实例最好值，而ETDE，S-HBDE和B-HBDE找到Best的实例个数分别为 12，30和 27。为了更加直观的比较算法的求解性能，在图 1-2中给出 4个演化算法求解四类KPC实例的AR=|OPT-Mean|的曲线图和Std直方图。

表3 skpc 实例结果Tab.3 The result of skpc instances

表4 ikpc 实例结果Tab.4 The result of ikpc instances

从图 1-2中不难看出，DHDE算法充分继承了S-HBDE和ETDE的优点，能自适应的选择性能良好的算法进化个体，AR和Std值均得到了很大的改善，在ukpc9,wkpc5,skpc8,ikpc7等实例中尤为明显。同时，DHDE算法的稳定性也有了进一步的增强，40个实例中，有11个实例Std值达到最小，有37个Std值排名第二。

图 1 AR 曲线图(a) ukpc1–ukpc10, (b) wkpc1–wkpc10, (c) skpc1–skpc10, (d) ikpc1–ikpc10

图 2 Std 曲线图(a) ukpc1–ukpc10, (b) wkpc1–wkpc10, (c) skpc1–skpc10, (d) ikpc1–ikpc10

综上所述，DHDE是一个求解性能良好，稳定性很强的，很适合求解KPC问题的高效算法。

5 结论

本文提出了求解KPC问题的一个具有编码复用的离散混合差分进化算法 DHDE。算法在单种群中通过编码复用的方式混合了算法S-HBDE和ETDE两种进化算子，同时通过记录算法 DHDE在前一次进化模式中种群个体改善数目，自适应的选择下一次的进化算子。最后，通过将 DHDE求解四类KPC实例的计算结果与ETDE、S-HBDE和B-HBDE的计算结果对比，证明了DHDE在求解 KPC问题中的有效性，是一个适合高效求解KPC实例的新方法。