基于离散混合多宇宙算法求解折扣{0-1}背包问题

郝 翔，贺毅朝，朱晓斌，翟庆雷

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

2.石家庄文化传媒学校，石家庄050000

0-1背包问题（0-1 Knapsack Problem，0-1 KP）[1-2]既是一个典型的组合优化问题，也是一个NP-hard问题[3-4]，在资源分配、项目组合和整数规划等领域具有广泛的应用。折扣{0-1}背包问题（Discounted{0-1}Knapsack Problem，D{0-1}KP）[5]是由Guldan首次提出的一个0-1KP扩展形式，在商业领域有着重要的应用背景。2007年，Guldan[5]建立了D{0-1}KP的基本数学模型，并给出了求解它的动态规划算法；随后，Rong等人[6]基于D{0-1}KP的核问题和动态规划法研究了D{0-1}KP的求解算法。以上两算法均为精确算法，存在求解速度慢的缺点。贺毅朝等人[7]基于整数编码和集合编码分别给出了D{0-1}KP的第二数学模型和第三数学模型，首先提出了基于演化算法求解D{0-1}KP问题的新思路，并给出了利用遗传算法求解的新方法。随后，吴聪聪等人[8]利用变异蝙蝠算法（MDBBA）提出了求解D{0-1}KP的方法，刘雪静等人[9]利用自适应细菌觅食算法（ABFO）求解D{0-1}KP问题，冯艳红等人[10]利用差分进化帝王蝶优化算法（DEMBO）求解D{0-1}KP问题，Li等人[11]提出了利用离散鲸鱼优化算法（DWOA）求解D{0-1}KP问题。这四种算法的求解效果较遗传算法有了进一步提高。2017年，Zhu等人[12]基于离散差分进化算法HBDE提出了求解D{0-1}KP问题的新方法，并与基于整数编码的两种差分进化算法FDDE和SDDE进行比较，证明了HBDE算法的优越性。最近，He等人[13]提出了基于群论的优化算法（GTOA），并利用GTOA求解D{0-1}KP问题，随后He等人[14]又提出了基于环论的优化算法（RTEA）求解折扣背包问题的新方法，取得了更好的求解效果。2020年，Wu等人[15]针对D{0-1}KP问题提出了一类离散混合教学优化算法（HTLBO），并指出采用差分进化交叉策略的HTLBO2算法具有更好的求解性能。

不难发现，由于精确算法在求解大规模D{0-1}KP实例时存在时间复杂度高，执行速度慢，时效性差等缺点，人们往往采用非精确算法求解。演化算法是一类具有随机近似性的非精确算法，具有算法简单、通用性强和易于实现等优点，已被广泛用于求解具有较大难度的连续型与离散型优化问题（组合优化问题）[2，16-17]。多宇宙算法（Multi-verse Optimization Algorithm，MVO）是Mirjalili等人[18]于2016年提出的一个新颖演化算法，目前已被成功应用于工程优化和机器学习领域[19-23]。如Abasi等人[24]提出了一个基于链接的改进多宇宙算法LBMVO来求解文本文档聚类问题，通过与原始MVO算法以及其他经典的聚类算法在求解文档聚类标准数据集的结果对比，证明了LBMVO算法的高效性。Abdel-Basset等人[25]提出了一个带有重叠探测的改进多宙算法求解无线传感器网络部署问题。除此之外，多宇宙算法还被成功地用在石油消耗预测[26]，图像处理[27]等问题中。由于原始MVO算法只适用于求解连续型优化问题，不能直接求解组合优化问题，因此不能用于求解D{0-1}KP问题。为此，本文提出MVO的一个离散版本，使之能够用于组合优化问题的求解。

借鉴文献[13-14]中设计算法的思路，本文采用模运算直接离散化MVO算法，利用局部搜索策略和精英策略提高算法的局部搜索性能，提出一个离散混合多宇宙优化算法（Discrete Hybrid Multi-verse Optimization Algorithm，DHMVO）。为了利用DHMVO求解D{0-1}KP问题，基于D{0-1}KP的第二数学模型对个体采用整型向量编码，并利用文献[7]中提出的算法NROA处理不可行解，提出了求解D{0-1}KP问题的一个新方法。最后，将算法DHMVO与FirEGA[7]、SecEGA[7]、DEMBO[10]、DWOA[11]、HBDE[12]、GPSO[13]、GTOA[13]、RTEA[14]和HTLBO2[15]等已有求解D{0-1}KP算法的计算结果进行对比，验证了DHMVO的高效性与鲁棒性。

1 MVO算法

多宇宙算法（MVO）是由Mirjalili等人[18]于2016年提出的一个新颖演化算法，并且已经在数值优化、复杂工程问题和机器学习方面有了成功的应用[19-23]。MVO算法启发于宇宙学中的三个基本概念：白洞、黑洞和虫洞，通过建立白洞和黑洞间的隧道模型去提高算法的探索性能，然后通过虫洞模型去模拟开发性能，保持了算法在探索和开发方面的平衡。在多宇宙算法中，每一个个体被称为宇宙，个体的适应度被称为宇宙的膨胀率，膨胀率高的宇宙被称为白洞，膨胀率低的宇宙被称为黑洞。

为了便于阐述如何利用MVO求解连续型优化问题，不失一般性，设maxg(X),X=[x1,x2,…,xn]∈Ω是一个最大优化问题和ubj是个体X中的每一维分量的上界和下界。下面分别介绍MVO的隧道模型和虫洞模型。

（1）隧道模型

隧道模型建立在白洞和黑洞之间，膨胀率较高的白洞通过隧道发送自身宇宙的某一个维度的物品给膨胀率较低的黑洞个体，并由黑洞接收。隧道模型的基本步骤如下：首先基于宇宙的膨胀率对宇宙进行排序并执行标准化操作，然后根据宇宙标准膨胀率的大小对宇宙的每一个维度作如下操作：

（2）虫洞模型

虫洞模型建立在当前宇宙与到目前为止的最好宇宙之间，该模型是在不考虑宇宙的膨胀率的前提下改变当前宇宙的每一个维度的值，具体的公式如下：

其中，l是指当前迭代次数，L是最大的迭代次数，min和max是WEP的最小和最大值。p是探索系数，更大的p值，会有更快和更精确的开发和局部搜索性能。也可以看出，WEP随着迭代次数的增大而增大，TDR随着迭代次数的增大而减小。

原始MVO通过顺序的执行式（1）、（2）生成下一代N个体的每一个维度的值，然后通过记录到目前为止的最好的个体来获得目标函数的最优解和最优值。即由MVO进化算子产生的新个体Xi(t+1),(1≤i≤N)可能不一定比上一代的个体更好，这种策略虽然提高了算法的探索性能，但是有可能会导致算法的收敛性较差。同时原始MVO算法不能直接求解组合优化问题。

由文献[18]知，当种群规模N，迭代次数MIT以及g(X)的时间复杂度O(g(X))均是n的线性函数时，MVO的时间复杂度为O(n3)。因为篇幅限制，不再给出MVO的算法伪代码，具体请见文献[18]。

2离散混合MVO算法

为了利用MVO求解组合优化问题，下面基于文献[13-14]中利用模运算设计离散进化算子的方法，借鉴差分进化算法[28-29]的变异策略提出离散型隧道模型和虫洞模型，在引入局部搜索策略和精英策略[14]的基础上，提出一个离散型混合多宇宙算法（DHMVO）。

不失一般性，令maxh(X),X=[x1,x2,…,xn]∈{0,1,2,3}n是一个最大优化问题。下面依次给出DHMVO的算法原理与算法伪代码描述。

2.1 新隧道模型

在DHMVO中，采用差分进化算法的突变策略“DE/rand/1”和模运算来对原始MVO算法的隧道模型进行修改，具体如式（5）所示：

通过式（5）与式（1）的对比可以看出，新隧道模型不再需要通过轮盘赌机制获得第j个维度的值，而是利用差分进化算法的突变策略“DE/rand/1”来获得。在轮盘赌机制中，适应值更好个体通过自身占有的权重获得更多输出个体信息的机会，加速了收敛。而“DE/rand/1”策略则通过三个个体间的组合运算来获得维度值，尽可能地利用了种群中每个个体，增加了算法的探索性能。

2.2 新虫洞模型

在DHMVO中，则采用突变策略“DE/best/1”和模运算来对原始MVO算法的虫洞模型进行修改，具体如式（6）所示：

在本文中，WEP的取值范围由0.2线性增大为0.6，TDR的取值范围由0.5线性减小为0。

通过式（6）可以看出，DHMVO的下一代种群在算法迭代的早期趋向于临时个体Y(t)，在迭代中期趋向于在最好个体XB(t)的周围进行局部搜索后得到的个体，在迭代后期则趋向于最好个体XB(t)。

通过式（6）与式（2）的对比可以看出，新虫洞模型本质上是原虫洞模型的一种通过模运算直接离散化的版本。在原虫洞模型中，当r2

2.3 DHMVO的算法伪代码

为了提高算法的收敛速度与求解效率，在DHMVO中引入局部搜索策略（Ring-based Local Development Operator，R-LDO）[14]，该策略融合了反向搜索策略和突变策略，具体的操作算子如公式（8）所示：

其中，MX为一个固定常数，本文MX=4,r4和r5是[0，1]的随机数，rand({0,1,2,3})表示随机选取{0，1，2，3}中的一个整数，pl表示局部搜索概率。

顺序的执行新隧道模型、新虫洞模型以及R-LDO构成了离散的混合多宇宙算法DHMVO。设N为DHMVO的种群规模，MIT为最大迭代次数，P(t)={Xi(t)|1≤i≤N}表示DHMVO的第t代种群，pl为局部搜索概率。表示P(MIT)最好个体对应的解，Y(t)=(y1(t),y2(t),…,yn(t))为由式（5）、（6）和（8）产生的临时个体。则对于最大优化问题maxh(X)，在算法1和图1中分别给出算法DHMVO的伪代码和流程图。

图1算法DHMVO的流程图Fig.1 Flow chart of algorithm DHMVO

算法1 DHMVO

记O(h)为计算h(Xi(t))的时间复杂度，则DHMVO的时间复杂度为O(h)+O(MIT×N×(n+O(h)))。显然，当N、MIT和O(h)都是关于n的线性函数时，DHMVO的时间复杂度为O(n3)，与原MVO算法的时间复杂度相同，但是新算法DHMVO较原MVO算法有以下几处优点：一是新隧道模型利用差分进化算法的突变策略“DE/rand/1”提高了算法的探索性能，并使之可以直接求解组合优化问题；二是通过模运算和突变策略“DE/best/1”直接离散化原虫洞模型，获得与原模型相同含义的新模型；三是采用局部搜索策略R-LDO来提高算法的探索性能；四是算法采用精英策略，确保进化产生的下一代个体总是比原个体更好，使收敛速度进一步提高。

3 基于DHMVO求解D{0-1}KP问题

3.1 D{0-1}KP的第二数学模型

D{0-1}KP的定义[5，7]：给定n个项集，每一个项集i∈{0,1,…,n-1}均含3项3i、3i+1和3i+2；其中项3i的价值和重量分别为p3i和w3i，项3i+1的价值和重量分别为p3i+1和w3i+1，项3i+2的价值和重量分别为p3i+2和w3i+2，其中p3i+2是p3i和p3i+1的和，w3i+2分别大于w3i和w3i+1，但小于w3i和w3i+1的和；同时每一项集中至多有一项可以被装入背包。D{0-1}KP问题的目的是如何选择物品装入背包，使得装入背包的所有物品的重量之和在不超过背包载重C的前提下价值之和最大。

本文基于D{0-1}KP的第二数学模型[7]进行求解，其数学模型如下：其中，X=[x0,x1,…,xn-1]∈{0,1,2,3}n为一个n维整型向量，[x]为顶函数，整型变量xi(0≤i≤n-1)的取值表示项集i中是否存在项被装入背包，xi=0表示项集i中没有项被装入了背包，xi=1和xi=2分别表示项3i和项3i+1被装入了背包，xi=3表示项3i+2被装入了背包。需要注意的是整型向量X仅为D{0-1}KP的一个潜在解，只有当它满足约束条件（10）时才是一个可行解。

3.2 基于DHMVO求解D{0-1}KP的方法

在利用演化算法求解D{0-1}KP问题中不可避免地会产生不可行解，为了提高算法求解效率，本文采用文献[7]中提出的基于贪心策略的修复与优化算法NROA来处理不可行解，下面首先介绍NROA的基本原理，然后在算法2中给出基于DHMVO求解D{0-1}KP的算法伪代码。

在NROA中，首先根据价值密度pj/wj(0≤j≤3n-1)由大到小将3n个项排序，并存储到数组H[0,1,…,3n-1]中；然后计算当前个体X中已装入背包的项的重量和，并判断其是否超过背包载重C。当不满足载重C（即约束条件式（10））时对个体X进行修复操作，即尝试从背包中依次取出价值密度最小的项，直到满足式（10）的约束条件为止；然后尝试对个体X进行优化处理，即当背包中还有剩余的容量时，尝试向背包中加入还未装入背包且价值密度最大的物品项，直到所有物品项均被尝试完毕为止。算法NROA的伪代码请参考文献[7]，不再赘述。

算法2 DHMVO for D{0-1}KP

由文献[7]知，NROA的时间复杂度为O(n)。在算法2中，步骤1由快速排序算法实现，时间复杂度为O(nlbn)；步骤2、3的时间复杂度分别为O(Nn)和O(n)；步骤7的时间复杂度为O(N)；步骤9~13的时间复杂度均为O(n)；步骤5~20的时间复杂度为O(MIT×N×n)。因此，当MIT和N都是n的一次多项式时，算法DHMVO的时间复杂度为O(n3)。

4 实验结果与分析

4.1 实验环境和D{0-1}KP实例

本文采用具有Intel®CoreTMi5-8300H CPU@2.3 GHz和8 GB的RAM的微型计算机，编程语言为C，编译环境为Codeblocks 17.12，使用Python在编译环境JetBrains PyCharm 2018.3上绘图。

D{0-1}KP实例来自于文献[14]中提供的公开数据集，其中四类实例分别是不相关D{0-1}KP实例（UDKP）、弱相关D{0-1}KP实例（WDKP）、强相关D{0-1}KP实例（SDKP）和逆强相关D{0-1}KP实例（IDKP），每一类实例都包含10个实例，实例规模3n∈{300,600,…,3 000},所有实例数据见网址https：//www.researchgate.net/project/Four-kinds-ofD0-1-KP-instances。

4.2 参数设置

为了与已有求解D{0-1}KP的算法DWOA[11]、HBDE[12]、GPSO[13]、GTOA[13]、RTEA[14]和HTLBO2[15]的计算结果进行公平比较（由于FirEGA[7]、SecEGA[7]和DEMBO[10]的求解性能太差，不再与之进行比较），在DHMVO算法中，设置DHMVO的种群大小为20，迭代次数为12×n，其中n为项集的个数。由算法2知，参数WEP和TDR均由迭代次数自适应计算得出，所以仅有局部搜索概率pl影响算法DHMVO的性能。因此本节将通过分析算法DHMVO求解n=500的四个D{0-1}KP实例的计算结果来确定参数pl的合理取值，其中每一个实例独立计算50次，pl分别取0.001、0.003、0.005、0.007、0.009。利用Kruskal-Wallis检验[30]比较数据的优劣。表1给出了算法DHMVO在不同参数下求解4个D{0-1}KP实例的秩和检验表，图2为DHMVO在不同pl值下求解4个D{0-1}KP实例的性能比较图。

从表1中可以看出，在利用DHMVO求解n=500的实例SDKP5和UDKP5时，p_value值远小于0.05，即参数pl的取值对求解性能有明显的影响，而在求解WDKP5和IDKP时则影响不大。通过图2也可以看出，在pl=0.005时，算法DHMVO求解n=500实例的平均性能最好，所以在求解其他规模的D{0-1}KP实例时均设置局部搜索概率为pl=0.005。

表1 DHMVO在不同pl值下求解n=500四个实例的秩和检验表Table 1 Rank and test table of DHMVO for four instances with n=500 under different pl

图2 DHMVO求解n=500的四个D{0-1}KP实例的性能比较Fig.2 Performance comparison of DHMVO for four instances with n=500

算法DHMVO和其他算法的参数设置在表2中给出。N为种群大小，MIT为最大迭代次数。其他各算法参数含义见文献[7-15]。

表2 参数设置Table 2 Parameter settings

4.3 DHMVO与已有算法的比较

本节将利用算法DHMVO求解四类大规模D{0-1}KP实例，每个实例独立计算50次，并与HBDE[12]、DWOA[11]、GPSO[13]、GTOA[13]、RTEA[14]和HTLBO2[15]等算法的计算结果进行比较，在表3~表6中分别给出上述算法求解UDKP类实例、WDKP类实例、SDKP类实例以及IDKP类实例的结果。其中OPT是该实例的最好值，Best、Mean、Worst、Std分别是上述算法在运行50次中得到的最优值、平均值、最差值以及标准差，Gap由OPT和Mean计算得到，其计算方法见式（12）：

表6 DHMVO和其他算法求解IDKP类实例的计算结果Table 6 Experimental results by DHMVO and other algorithms for IDKP instances

显然Gap≥0,Gap越接近0，表明算法的求解性能越好。此外，为了方便比较，将同一个统计量中最好的值用黑体加粗表示，将无数据的部分用“—”表示。

从表3~6中可以看出以下两点：

表3 DHMVO和其他算法求解UDKP类实例的计算结果Table 3 Experimental results by DHMVO and other algorithms for UDKP instances

（1）对UDKP类、WDKP类和SDKP类的30个实例，除了实例UDKP3、UDKP4、UDKP5、WDKP6、WDKP7、WDKP8和SDKP1外，DHMVO求解其他的23个D{0-1}KP实例时，5个统计量均是最好的。下面给出算法DHMVO求解上述7个实例的求解结果。在求解实例UDKP3、UDKP4、UDKP5时，DHMVO的Gap<0.04，与求解性能最好的GTOA的Gap差值最大不超过0.006，在7个算法中，对这三个实例的求解性能仅次于GTOA。在求解实例WDKP6、WDKP7、WDKP8和SDKP1时，DHMVO的Gap在7个算法中最小，只有最优值未到达最好值，但与实例最好值OPT的差值最大不超过10。

（2）在求解IDKP类实例时，HTLBO2的求解性能最好，除实例IDKP外，共有9个实例的Gap值取得最小。算法DHMVO和GPSO的求解性能相当，仅次于HTLBO2。在算法DHMVO中，除实例IDKP1的Gap值小于0.015外，DHMVO求解其他9个实例的Gap均不超过0.005，同时10个IDKP实例中除了实例IDKP7和IDKP8的最优值未到达最好值外，其余的均已达到。总体而言，DHMVO在7个算法中的求解精度最佳，稳定度最好，非常适合求解D{0-1}KP问题。

为了更直观地比较计算结果，通过Gap图和Std直方图比较DHMVO、HBDE、HTLBO2、GPSO、GTOA和RTEA的求解性能（由于DWOA的计算结果明显比其他算法的差，因此不再与其对比）。6个算法求解D{0-1}KP的Gap曲线图和Std直方图如图3和图4所示。

图3 Gap拟合曲线Fig.3 Fitting curves of Gap

图4 Std直方图Fig.4 Std histograms

表4 DHMVO和其他算法求解WDKP类实例的计算结果Table 4 Experimental results by DHMVO and other algorithms for WDKP instances

表5 DHMVO和其他算法求解SDKP类实例的计算结果Table 5 Experimental results by DHMVO and other algorithms for SDKP instances

从图3和图4中可以看出，在利用6个算法求解D{0-1}KP实例时，DHMVO的Gap值和Std值总体上看均是最好的。

（1）在求解UDKP、WDKP和SDKP时，GTOA和RTEA的求解性能相当，但GTOA略好，两者性能仅次于DHMVO，算法HTLBO2的性能居于第四名，GPSO和HBDE最差。

（2）在求解IDKP时，HTLBO2最好，其次为DHMVO，GPSO性能居于第三名，之后求解性能好的算法依次为GTOA、RTEA和HBDE。

综上所述，DHMVO是一个在10个算法中的求解性能最好，稳定度最强，非常适合求解D{0-1}KP问题的高效算法。

5 结束语

本文提出了求解D{0-1}KP问题的一个离散混合多宇宙算法DHMVO。首先，基于模运算提出了新的隧道模型和虫洞模型，并基于局部搜索策略和精英策略来平衡算法的探索与开发能力。然后，采用基于贪心策略的修复与优化算法NROA处理D{0-1}KP的不可行解，基于DHMVO提出了求解D{0-1}KP的一种新方法。最后，将DHMVO求解四类大规模D{0-1}KP实例的计算结果与已有的求解算法FirEGA、SecEGA、DEMBO、HBDE、DWOA、HTLBO2、GPSO、GTOA和RTEA等的计算结果进行对比，验证了DHMVO在求解D{0-1}KP问题时的高效性，并指出DHMVO不仅求解精度更高，而且稳定性更强，是比其他算法更适合求解大规模D{0-1}KP实例的一种新的高效方法。