新颖的离散差分演化算法求解D0-1KP问题.docx

背包问题（knapsack problems,KP）

[1]

是一类经典的 NP 完全问题,也是重

要的组合优化问题。KP 在资源分配、投资决策、经济金融和信息安全等

[2]

诸多

领域都具有重要的理论意义和实用价值。KP 有许多不同的扩展形式,例如：集

合联盟背包问题（set-union knapsack problem,SUKP）

[3]

、多维背包问题（multi-

dimensional knapsack problem,MKP）

[4]

展形式。由于 D{0-1}KP 对项目（物品）的选择更加多样化,使得 D{0-1}KP 比

0-1 背包问题（0-1 knapsack problem,0-1KP）具有更大的挑战性。目前,许多

国内外学者对 D{0-1}KP 问题的求解算法进行了研究,例如 Guldan

[6]

讨论了如何

使用启发式和精确算法求解 D{0-1}KP,并给出了一种求解 D{0-1}KP 的动态规

划法;Rong 等人

[7]

于 2012 年通过核问题将 D{0-1}KP 划分为若干较容易的子问

题,并给出了一种动态规划与核相结合求解 D{0-1}KP 的精确算法;2016 年,He

等人

[8]

设计了一种新的 基于动态规划的精确算法,并在此基础上提出了三种近

D{0-1}KP 的 编 码 问 题 , 在 此 基 础 上 提 出 了 一 种 变 异 的 蝙 蝠 算 法 （ mutated

double binary bat algorithm,MDBBA）求解 D{0-1}KP;2018 年,刘雪静等人

对 D{0-1}KP 的两种数学模型,提出了自适应细菌觅食算法（adaptive bacterial

foraging algorithm,ABFO）求解 D{0-1}KP 的两种算法,并比较了两种算法的优

劣 ; 随 后 ,He 等 人 先 后 提 出 了 基 于 群 论 的 优 化 算 法 （ group theory-based

optimization algorithm,GTOA）

evolutionary algorithm,RTEA）

,并分别用于求解 D{0-1}KP,取得了较好的效

用于求解 D{0-1}KP 问题。显然,目前求解 D{0-1}KP 的算法主要分为两类：精

确算法和非精确算法。精确算法具有伪多项式时间复杂度,不适用于求解大规

模 D{0-1}KP 实例。非精确算法特别是演化算法不仅求解速度快,而且计算结果

能够满足实际应用的需求,因此探讨利用演化算法求解 D{0-1}KP 的高效方法是

一个值得研究与探讨的问题。

差分演化（differential evolution,DE）最初是由 Storn 和 Price

[16]

提出的一

种基于随机种群的元启发式算法,虽然在求解数值优化

和电力系统

等问题

时表现出优异的性能,但是由于差分演化是基于实数运算实现的,不能直接应用

于求解组合优化问题。为此,研究人员先后提出了不同版本的二进制差分演化

算法,例如 Engelbrecht 等人

[19]

差分演化算法（binary differential evolution,BinDE）。He 等人

基于混合编

码 机 制 提 出 了 一 个 二 进 制 差 分 演 化 算 法 （ binary differential evolution

个 0-1 向量,从而使 HBDE 适于求解以 0-1 向量为可行解的组合优化问题。但

是从相关文献中不难看出,BinDE 利用 S 型转换函数将 DE 中个体的实向量编

码转换为 0-1 向量编码的概率与一个随机数 rand 进行比较,容易造成可行解中

基础上提出了一种基于新 V 型转换函数的新离散差分演化算法（novel discrete

differential evolution algorithm,NDDE）,给出了求解 D{0-1}KP 的一个新的高

效方法。

上加入了“折扣”思想,当同时选择两个物品时就会得到折扣。这种思想来源于商

业领域,商场和企业通常会通过“折扣”的方式吸引更多的消费者。D{0-1}KP 问

题在项目决策、资源投资和资本预算等诸多领域具有重要的应用理论意义。

下面给出 D{0-1}KP 问题的定义和已有数学模型。

D{0-1}KP 的定 义一般 描述为 ：给定 n 个含 有 3 个物 品的物 品集, 物品集

i(0≤i≤n-1)中含有的 3 个物品分别表示为 3i, 3i+1 和 3i+2,其中前两个物品 3i

和 3i+1 的价值系数分别记为 p3i 和 p3i+1,重量系数分别记为 w3i 和 w3i+1;第

三个物品 3i+2 为前两个物品的合并,它的价值系数为 p3i+2=p3i+p3i+1,它的折

扣 重 量 系 数 为 w3i+2, 满 足 w3i+2<w3i+w3i+1, 并 且 、 w3i<w3i+2 、

使得装入背包的所有物品的重量系数之和在不超过背包载重 C 的前提下价值

系数之和达到最大。

根据上述定义,Guldan

（1）

其中, X=[x0,x1,⋯,x3n-1]∈{0,1}3n 为一个 3n 维二进制向量。 X 仅仅表示

D{0-1}KP 的一个潜在解,只有当它同时满足约束条件（2）和（3）时才是一个

可行解;二元变量 ）xj(0≤j≤3n-1）表示物品 j 是否装入背包, xj=0 表示物品 j 没

有被装入背包,反之 xj=1 表示物品 j 装入背包中。

He 等人根据 D{0-1}KP 的定义,建立了 D{0-1}KP 的两个新的数学模型：模

型二和模型三。本文仅研究如何基于 D{0-1}KP 的第一数学模型进行高效求解,

其他两个模型不再赘述,请参考有关文献[12]。

本章首先介绍了四种 S 型转换函数和四种 V 型转换函数,然后提出了一个

新 V 型 转 换 函 数 （ NV ） ,接 着 基 于 NV 提 出 了 一 个 新 的 离 散 差 分 演 化 算 法

（NDDE）,并给出其算法原理和伪代码描述。最后,给出了 利用 NDDE 求解

D{0-1}KP 的具体方法。

[21]

别命名为 S1~S4,V 型转换函数分别命名为 V1~V4。表 1 给出了 4 个 S 型转换

函数和 4 个 V 型转换函数。

表 1 S 型转换函数和 V 型转换函数

Table 1 S-shaped and V-shaped families of transfer functions

示,其函数曲线如图 1 所示。

NVA(x)=|x|A, A∈R+

（5）

图 1 NVA 的函数曲线

Fig.1 Function curve of NVA

从表 1、图 1 和式（5）可以看出：NV 型传递函数与 S 型传递函数相比,

两者之间差别巨大,它们明显具有不同的性质。且不难看出,由于 S 型函数中涉

及指数运算,NV 型传递函数的计算量远远小于 S 型传递函数。NV 型传递函数

与 V 型传递函数相比,虽然两者的函数图像相似,都是关于 y 轴对称的,但是两者