基于差分演化策略的混沌乌鸦算法求解折扣{0- 1}背包问题

刘雪静，贺毅朝，路凤佳，吴聪聪，才秀凤

(河北地质大学 信息工程学院，石家庄 050031)(*通信作者电子邮箱lxjpass@163.com)

0 引言

背包问题(Knapsack Problem, KP)[1]是一类经典的组合优化问题，在投资决策、货物装载、整数规划等领域有着非常重要的理论和应用价值。KP包含许多不同的形式，如0- 1背包问题(0- 1KP)[2]、多维背包问题(MultiDimensional Knapsack Problem, MDKP)[3-4]、多选择多维背包问题 (Multiple-Choice Multidimensional Knapsack Problem, MMKP)[5]、最大最小背包问题(Max-min Knapsack Problem, MmKP)[6]和折扣0- 1背包问题(Discounted {0- 1} Knapsack Problem, D{0- 1}KP)[7-8]等。

D{0- 1}KP是Guldan[7]于2007年提出的一个新颖KP，首先研究了利用动态规划法对其进行求解；Rong等[8]对D{0- 1}KP的核(Core)问题进行了研究，将其与动态规划法相结合求解D{0- 1}KP。贺毅朝等[9]利用杰出者保留策略遗传算法(Genetic Algorithm with Elitist reservation strategy, EGA)求解D{0- 1}KP，提出了基于两个不同数学模型的算法——FirEGA(First EGA)和SecEGA(Second EGA)，两种算法均能得到一个近似比接近于1的近似解；刘雪静等[10]利用细菌觅食(Bacterial Foraging Optimization, BFO)算法求解D{0- 1}KP，在两个不同数学模型下提出的算法FirBFO(First BFO)和SecBFO(Second BFO)，能够得到更好的近似解；吴聪聪等[11]利用变异蝙蝠算法(Mutated Double Binary Bat Algorithm, MDBBA)求解D{0- 1}KP，该算法在大部分实例上优于算法FirEGA。由于D{0- 1}KP的提出时间较晚，基于演化算法求解的相关研究成果相对较少，虽然利用EGA、BFO和MDBBA已经提出了求解D{0- 1}KP的不同方法，但是还存在许多有待改进的方面，例如如何提高初始解的多样性、如何提高算法的求解速度等问题，因此如何利用演化算法更好、更快地求解D{0- 1}KP是一个值得研究的问题。

为了利用新型演化算法——乌鸦算法(Crow Search Algorithm， CSA)[12]高效求解D{0- 1}KP，基于D{0- 1}KP的第一数学模型，本文基于多种有效策略与CSA相融合提出了求解D{0- 1}KP的一种新的高效方法。在新方法中，首先针对初始解随机产生时存在分布不均的缺陷，提出采用混沌映射优化初始解的方法；其次，利用混合编码方式得到D{0- 1}KP的潜在解，并通过GROS对潜在解进行修复和优化处理，以获得一个质量更优的可行解；第三，在算法中引入差分演化策略来提高算法的全局寻优能力和收敛速度。对4类大规模实例的计算结果表明：DECCSA能快速求得近似比接近1的满意解，优于FirEGA、FirBFO和MDBBA这3种算法。

1 D{0- 1}KP

定义[7]给定n个项集，且任一项集i(0≤i≤n-1)中均含3项，分别为3i、3i+1和3i+2，其对应的价值系数为p3i、p3i+1和p3i+2，重量系数为w3i、w3i+1和w3i+2，其中，p3i+2=p3i+p3i+1，w3i+2>w3i、w3i+2>w3i+1、w3i+2

(1)

(2)

x3i+x3i+1+x3i+2≤1;i=0,1,…,n-1

(3)

x3i,x3i+1,x3i+2∈{0,1};i=0,1,…,n-1

(4)

其中：变量xi(0≤i≤3n-1)表示项i是否被装入背包，xi=1即项i装入背包，xi=0即项i未装入背包。显然，任意的二进制向量X=[x0,x1,…,x3n-1]∈{0,1}3n仅是D{0- 1}KP的一个潜在解，只有同时满足约束条件式(2)、(3)和(4)的二进制向量X才是D{0- 1}KP的一个可行解。

2 乌鸦算法

乌鸦算法是一种新颖的元启发算法，在网络优化分配[13]、医学等领域有较少的研究成果。CSA模拟自然界中乌鸦的智能行为。乌鸦是群居生活的鸟类，它们非常聪明，能将自己多余的食物藏匿起来，藏匿位置称为记忆值(Memory，M)，并在需要时取出；当前能跟踪其他乌鸦，窃取其他乌鸦的食物，而被跟踪的乌鸦能以一定的感知概率(Awareness Probability， AP)保护自己的食物防止被窃。假定N只乌鸦分布在n维搜索空间中，Xi,iter表示第i只乌鸦在第iter次迭代时的位置，Xi,iter+1的结果如式(5)所示：

(5)

其中：ri、rj是[0,1]区间服从均匀分布的随机数；Mj,iter为乌鸦j、迭代次数iter时的记忆值；APj,iter为乌鸦j的感知概率；fli,iter为乌鸦i在第iter迭代时的飞行长度。

当乌鸦的位置发生了改变，式(6)给出了M的更新方式：

(6)

下面给出CSA的算法描述。

算法1 CSA。

初始化参数：最大迭代次数MITER，飞行长度fl，感知概率AP，种群大小N，问题维度n。

生成初始种群P(0)；

计算适应度值f(P(0))；

初始化乌鸦的记忆值M0=P(0)；

Whileiter

Fori=1toN

乌鸦i随机选择乌鸦j跟踪

Ifrj≥APj,iter

Xi,iter+1=Xi,iter+ri*fli,iter*(Mj,iter-Xi,iter)

Else

xi,iter+1←任意位置

Endif

检查新位置的可行性。如果乌鸦i的新位置是可行的，则更新；否则，乌鸦i停留在当前位置

评价乌鸦i的新位置的适应度值

以式(6)的方式更新记忆值

End for

End while

此时M中的最好位置即为问题的最优解。由于MITER、N是关于n的线性函数，故CSA的时间复杂度为O(n3)。

3 求解D{0- 1}KP的改进乌鸦算法

3.1 混沌序列初始化乌鸦位置

CSA采用随机方法初始化乌鸦的位置，极有可能造成乌鸦位置分布不均匀。而混沌映射[14]能按照自身的规律在一定范围内不重复遍历所有状态，因此利用混沌优化方法求解数值优化问题时，混沌轨迹能使搜索过程避免陷入局部最优，能更加有效地实现对搜索空间的搜索，从而获得全局最优解或较好的满意解。本文采用Circle映射初始化乌鸦位置，以增强初始解的多样性，为进一步有效地进行全局搜索打下良好的基础。Circle映射表达式如下：

xk+1=xk+b-(a/2π) sin(2πk) mod (1)

(7)

映射方式如下：

步骤1 随机产生一个n维向量X0={x0,x1,…,xn-1}，作为第一只乌鸦。

步骤2 将X0中的每一维按式(6)进行N-1迭代，生成其余N-1个乌鸦个体。

由此，初始化步骤完成。

3.2 混合编码方式

在CSA中，乌鸦个体X=[x0,x1,…,xn-1]为实型向量，fl、AP是实数，而0- 1KP是离散域的问题，因此本文利用sigmoid函数将一个实型向量转化为一个二进制向量[15]，实现对CSA的离散化。编码转换技术如式(8)所示：

(8)

其中，Y=[y0,y1,…,yn-1]，yj∈{0,1}，j=0,1,…,n-1。

由此，将种群中的每一个个体分别用n维实型向量X和n维二进制向量Y共同表示，记作(X,Y)，称(X,Y)为个体的混合编码表示[16]。b为一个给定的正数，则以[-b,b]n为辅助搜索空间，以{0,1}n为解空间，实现对离散化空间问题的求解。

3.3 差分演化策略

在CSA中，乌鸦i随机选择乌鸦j跟踪，当rj>AP时，乌鸦i以Xi,iter+1=Xi,iter+ri*fli,iter*(Mj,iter-Xi,iter)的方式向乌鸦j的最佳位置移动，但是乌鸦j的最佳位置不一定好，故收敛速度可能变慢，由此，引入差分演化策略对跟踪方式进行改进。差分演化的变异算子的一般形式为DE/x/y/z[16]，其中：x是一个字符串，代表要被扰动的基向量；y代表为扰动x而使用的差分向量的个数；z代表交叉的类型(指数交叉EXP或二项式交叉BIN)。本文采用DE/best/1/BIN的方式，跟踪公式改进如下：

(9)

其中，Bestiter为当前迭代的最优值。乌鸦i每次向着最优的个体移动，提高收敛速度。

3.4 贪心修复与优化策略

由于二元向量Y=[y0,y1,…,yn-1]∈{0,1}3n可能是非正常编码个体，因此引入贪心与优化策略(Greedy Repair and Optimization Strategy， GROS)[9]把非正常编码个体修正为正常编码个体并进行优化。假定原二进制个体为Y=[y0,y1,…,yn-1]∈{0,1}3n，修正后二进制个体为Z=[z0,z1,…,zn-1]∈{0,1}3n，数组H[0,1,…,3n-1]中存放价值系数密度pj/wj(0≤j≤3n-1)的降序排列下标序，各项集的状态标识F[0,1,…,n-1]∈{0,1}n，F[j]=0表示项集j中没有项装入背包，F[j]=1表示项集j中恰有一项装入背包，⎣i/3」表示i/3向下取整。GROS算法描述如下。

算法2 GROS。

输入：二进制个体Y=[y0,y1,…,yn-1]和数组H[0,1,…,3n-1]；

输出：二元向量Z=[z0,z1,…,zn-1]和f(Z)。

1)

weight=0,value=0

2)

Fori=0 to 3n-1 Dozi=0

3)

Fori=0 ton-1 DoF[i]=0

4)

Fori=0 to 3n-1 Do

5)

If((yH[i]=1)&(weight+wH[i]≤C) &

(F[⎣H[i]/3」]=0))

6)

weight=weight+wH[i],F[⎣H[i]/3」]=1,

7)

value=value+pH[i],ZH[i]=1

8)

Endif

9)

Endfor

10)

Fori=0 to 3n-1 Do

11)

If((weight+wH[i]≤C) & (F[⎣H[i]/3」]=0))

12)

weight=weight+wH[i],zH[i]=1

13)

F[⎣H[i]/3」]=1,value=value+pH[i]

14)

Endif

15)

End for

16)

Return (Z,value)

第2)和3)行的时间复杂度为O(n)；第4)～9)行将非正常编码个体Y修复为正常编码个体并存于Z中，时间复杂度为O(n)；第10)～15)行对Z作进一步优化，时间复杂度为O(n)。显然，GROS的时间复杂度为O(n)。

3.5 基于差分演化的混沌CSA求解D{0- 1}KP

DECCSA求解D{0- 1}KP流程如图1所示。其中，QuickSort(pi/wi)为对价值系数密度pi/wi(0≤i≤3n-1)按非递增进行快速排序，B(t)(0≤t

在图1中，虚线框A部分为采用Circle映射生成的优化初始乌鸦种群，虚线框B部分为采用差分演化策略按式(9)生成的乌鸦i在下一次迭代的位置。

图1 DECCSA流程

在DECCSA中，QuickSort的时间复杂度为O(nlogn)，生成初始种群的时间复杂度为O(nN)，GROS的时间复杂度为O(n)，由于N、MITER是关于n的线性函数，故DECCSA的时间复杂度为O(nlogn)+O(nN)+O(n)+MITER*(O(nN)+O(n))=O(n3)，因此DECCSA是一个复杂度为多项式时间的进化算法。

4 仿真实验与分析

在本章中，不相关D{0- 1}KP实例(Uncorrelated instances of D{0- 1}KP， UDKP)、弱相关D{0- 1}KP实例(Weakly correlated instances of D{0- 1}KP， WDKP)、强相关D{0- 1}KP实例(Strongly correlated instances of D{0- 1}KP, SDKP)和逆向强相关D{0- 1}KP实例(Inversestrongly correlated instances of D{0- 1}KP， IDKP)的生成参照文献[10]，每一类实例包含10个不同规模的实例。首先利用若干实例的计算结果所对应的箱线图(Boxplot)分析并确定CSA和DECCSA中感知概率AP和飞行长度fl的合理取值；然后利用对4类大规模D{0- 1}KP实例的计算结果比较CSA和DECCSA的求解性能。

本文所使用微型计算机硬件配置为Intel Core i3- 4005u CPU- 1.70 GHz，4 GB内存(3.75 GB可用)，操作系统Microsoft Windows 7，编程语言C语言，编译环境CodeBlocks，并利用Matlab 7.14.0.739 (R2012a)绘图。

4.1 确定AP和fl的合理取值

AP分别取值0.1,0.2,0.3,0.4，fl分别取值1.0,2.0,3.0,4.0,5.0，共构成20种不同的组合形式(AP,fl)，表1列出所有组合的ID。下面分别利用4类实例对AP和fl的每一种组合进行计算，以确定AP和fl的合理取值。限于篇幅，针对每一种组合形式，仅给出CSA和DECCSA两种算法在规模为3n=1 500的实例UDKP5、WDKP5、SDKP5和IDKP5的计算结果及其所对应的箱线图。

表1 参数组合形式(AP， fl)及其ID

图2是在20种组合情况下独立运行CSA 30次求解UDKP5、WDKP5、SDKP5和IDKP5时所求最好值箱线图。

图2 20种组合下CSA求解4个实例的性能比较

从图2(a)可以看出，求解UDKP5，当AP=0.2时，所求的最优值最好，当AP=0.4、fl=2时，中位数最好。从图2(b)可以看出，求解WDKP5，当AP=0.4时，所求最好值较好，当AP=0.3、fl=2时，中位数最好。从图2(c)可以看出，求解SDKP5，当AP=0.1，fl=3或5时，所求最优值最好，当AP=0.2，fl=3时，中位数最好。从图2(d)可以看出，求解IDKP5，当AP=0.3，fl=1,2,3时，所求最优值最好，当AP=0.3，fl=2时，中位数最好。由图2可得，针对UDKP、WDKP和IDKP类实例，当AP取值稍大时平均求解性能较好，针对SDKP类实例，当AP=0.2时平均求解性能较好。本文采用的是求得中位数最好的组合。

图3是20种组合情况下独立运行DECCSA 30次求解UDKP5、WDKP5、SDKP5和IDKP5时所求最好值的箱线图。由图3(a)可以看出，AP=0.1，fl=5.0时所求最好值最优，AP=0.1，fl=2.0时中位数值最好。在图3(b)中，30次所求中位数基本相同，AP=0.1，fl=2.0、0.4和AP=0.3，fl=1.0时最好值最好。在图3(c)中，AP=0.1，fl=2.0时最好值和中位数值都最好。在图3(d)中，除AP=0.1，fl=2.0外所有组合所求最好值相同，AP=0.1，fl=2.0时最优。图2与图3对比可以看出，DECCSA所求的最好解相对较集中，针对4类实例，AP值相对较小为好。综上，DECCSA参数的最佳设置应为AP=0.1,fl=2.0。

图3 20种组合下DECCSA求解4个实例的性能比较

4.2 计算结果比较与分析

实验参数设置如下：CSA求解4类D{0- 1}KP实例时，N=50，MITER=3 000，求解UDKP时，AP=0.4，fl=2；求解WDKP时，AP=0.3，fl=2；求解SDKP时，AP=0.2，fl=3；求解IDKP时，AP=0.3，fl=2。DECCSA求解4类D{0- 1}KP实例时，设置AP=0.1，fl=2.0，N=50，MITER=3 000。不同算法求解各个实例的结果如表2～5所示，其中DPDKP为由动态规划法所求最优解[7],FirEGA算法求解4类实例的数据来自文献[10]，FirBFO算法求解4类实例的数据来自文献[11]，MDBBA算法求解4类实例的数据来自文献[12]。

表2给出了UDKP类实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。最优值/最好值和最优值/最差值分别代表最好值近似比和平均值近似比[17]。

表2 6种算法求解UDKP实例的结果比较

图4对CSA和DECCSA求解UDKP类实例时的最好值近似比和平均值近似比进行了比较。

图4 CSA与DECCSA求解UDKP类实例时的近似比对比

从图4(a)可以看出，DECCSA的最好值近似比的最大值与CSA的最小值大致相当。图4(b)与图4(a)区别不大，但是平均值近似比值相对有所增大。由图4可知，DECCSA比CSA更适合求解UDKP类实例。

图5给出了DECCSA与FirEGA、FirBFO和MDBBA求解UDKP类实例时的最好值近似比和平均值近似比的比较。

图5 DECCSA与另三种算法求解UDKP类实例时的近似比对比

由图5(a)可以看出DECCSA在求解UDKP1～UDKP4时比其他算法好，求解UDKP5～UDKP7时不如FirEGA和MDBBA，求解UDKP8～UDKP10时与FirEGA和MDBBA能力相当。由图5(b)可看出在求解UDKP1、UDKP2、UDKP4时，DECCSA明显比其他算法好，求解UDKP5～UDKP7明显不如FirEGA和MDBBA，其他实例DECCSA、FirEGA和MDBBA3种算法能力相当。

表3给出了求解WDKP实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。

表3 6种算法求解WDKP实例的结果比较

图6对CSA和DECCSA求解WDKP类实例时的最好值近似比和平均值近似比进行了比较。

图6 CSA与DECCSA求解WDKP类实例时的近似比对比

由图6(a)可以看出，DECCSA在求解WDKP实例时最好值近似比远远小于CSA；图6(b)中两种算法的平均值近似比有所增大，曲线变化不大，仍然是DECCSA的平均值近似比小于CSA，故DECCSA比CSA更适合求解WDKP类实例。由图7(a)可以看出求解WDKP1～WDKP3三个实例时DECCSA性能最好，求解其他实例时FirBFO、MDBBA和DECCSA的求解能力相当，FirEGA最好值近似比最大。

图7 DECCSA与另三种算法求解WDKP类实例时的近似比对比

图7(b)中FirEGA的平均值近似比值当实例规模增大时与图7(a)差异明显，变得更差，DECCSA的求解性能在WDKP1～WDKP3时最好，在其余实例上与FirBFO、MDBBA求解能力相当。

表4给出了求解SDKP实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。

表4 6种算法求解SDKP实例的结果比较

图8给出了CSA与DECCSA求解SDKP实例时的最好值近似比与平均值近似比的比较。

图8 CSA与DECCSA求解SDKP类实例时的近似比对比

由图8可以看出DECCSA在求解SDKP类实例时最好值近似比和平均值近似比都远远小于CSA，比CSA适合求解SDKP类实例。由图9(a)可以看出DECCSA在求解SDKP实例时比其他算法好，能得到较好的满意解，且在求解SDKP1～SDKP3三个实例时优势明显。从图9(b)可以看出，平均值近似比也是DECCSA最小，取得的平均值最优。

图9 DECCSA与另三种算法求解SDKP类实例时的近似比对比

表5给出了求解IDKP实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。从表5可以看出，求解IDKP实例时，CSA的求解性能最差，DECCCSA在IDKP1、IDKP2和IDKP4实例上能取得理论最优值。由图10(a)和图10(b)可以看出，DECCSA在求解IDKP类实例时最好值近似比和平均值近似比基本都为1，优于CSA，非常适合求解IDKP类实例。由图11(a)可以看出DECCSA和MDBBA、FirBFO的最优近似比基本等于1，FirEGA稍差。图11(b)与图11(a)区别不大，平均值近似比DECCSA、FirBFO、MDBBA相差依然不大，基本等于1，FirEGA稍差。

表5 6种算法求解IDKP实例的结果比较

图10 CSA与DECCSA求解IDKP类实例时的近似比对比

综上，对于UDKP类问题，DECCSA与其他算法在求解效果上不相上下；对于WDKP、SDKP和IDKP类问题，DECCSA求解效果明显比其他算法的更优。之所以产生这样的结果，一方面是因为CSA的求解速度快且易于扩充，另一方面是它与DE的结合做到了优势互补，因此体现出了极佳的求解性能。

图11 DECCSA与另三种算法求解IDKP类实例时的近似比对比

图12显示了CSA和DECCSA求解UDKP3、WDKP3、SDKP3和IDKP3四个实例时的收敛速度，每个实例独立运行30次，明显可以看出DECCSA比CSA求解性能更优。从图12(a)可以看出，求解UDKP3时，DECCSA在前100代收敛速度较快，后面收敛速度缓慢，CSA也是前100代收敛速度稍快，后面较慢，且迭代次数对最好值影响不大。从图12(b)～(d)可以看出，DECCSA求解WDKP3、SDKP3和IDKP3三个实例时，混沌策略非常有效，能得到较好的初始解，收敛曲线平缓，而CSA依然是处于缓慢收敛的状态。

图12 CSA和DECCSA在4个实例上的收敛速度对比

基于上述计算、比较和分析得出以下结论：

对于项的价值系数和重量系数均在大范围内随机取值的4类大规模D{0- 1}KP实例，DECCSA能够快速求得一个近似比接近于1的近似解，是适于求解大规模难D{0- 1}KP的有效且实用的进化算法。另外，求解UDKP实例时，DECCSA和FirEGA、MDBBA的求解性能相当，10个实例各有优劣，FirBFO性能稍差。求解WDKP、SDKP、IDKP三类实例时，DECCSA比FirEGA、FirBFO、MDBBA三算法的求解性能好，从而说明混沌策略和差分演化策略能有效地改进CSA，能够求得D{0- 1}KP的较满意解或最优解。

5 结语

本文研究了如何利用乌鸦算法求解D{0- 1}KP，提出了针对初始解随机产生的缺点采用混沌策略初始化个体和引入差分演化策略改进乌鸦跟踪方式的差分混沌乌鸦算法求解D{0- 1}KP。仿真实验表明：对于大规模的D{0- 1}KP实例，DECCSA不受实例中各项的价值系数、重量系数和背包载重的大小影响，能够快速求得一个近似比接近于1的近似解，因此它是一个求解大规模难实例的实用进化算法。

在利用DECCSA求解D{0- 1}KP时，UDKP类实例的计算结果较其他三类的略差，因此进一步分析DECCSA的特点，使之对于UDKP类实例也能获得更佳的结果是需要今后研究的问题。此外，能否基于D{0- 1}KP的第二、三数学模型[9]设计更加高效的进化算法也是一个值得今后探讨的问题。

References)

[1] KELLERER H, PFERSCHY U, PISINGER D. Knapsack Problems [M]. Berlin: Springer, 2004: 55-75.

[2] WILBAUT C, SALHI S, HANAFI S. An iterative variable-based fixation heuristic for the 0- 1 multidimensional knapsack problem [J]. European Journal of Operational Research, 2009, 199(2): 339-348.

[3] CHU P C, BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem [J]. Journal of Heuristics, 1998, 4(1): 63-86.

[4] DJANNATY F, DOOSTDAR S. A hybrid genetic algorithm for the multidimensional knapsack problem [J]. International Journal of Contemporary Mathematical Sciences, 2008, 3(9/10/11/12): 443-456.

[5] SBIHI A. A best first search exact algorithm for the multiple-choice multidimensional knapsack problem [J]. Journal of Combinatorial Optimization, 2006, 13(4): 337-351.

[6] FURINI F, LORI M, MARTELLO S, et al. Heuristic and exact algorithms for the interval min-max regret knapsack problem [J]. INFORMS Journal on Computing, 2015, 27(2): 392-405.

[7] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems [D]. Erlangen: University of Erlangen-Nürnberg, 2007: 1-78.

[8] RONG A Y, FIGUEIRA J R, KLAMROTH K. Dynamic programming based algorithms for the discounted {0- 1} knapsack problem [J]. Applied Mathematics and Computation, 2012, 218(12): 6921-6933.

[9] 贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0- 1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630.(HE Y C, WANG X Z, LI W B, et al. Research on genetic algorithms for the discounted {0- 1} knapsack problem [J]. Chinese Journal of Computers, 2016, 39(12): 2614-2630.)

[10] 刘雪静,贺毅朝,吴聪聪,等.基于细菌觅食算法求解折扣{0- 1}背包问题的研究[J/OL].计算机工程与应用,2017:1-11. (2017- 02- 16)[2017- 08- 18]. http://kns.cnki.net/kcms/detail/11.2127.TP.20170216.1044.038.html.(LIU X J, HE Y C, WU C C, et al. Research on bacterial foraging optimization algorithm for the Discounted {0- 1} knapsack problem [J/OL]. Computer Engineering and Applications, 2017: 1-11. (2017- 02- 16) [2017- 08- 18]. http://kns.cnki.net/kcms/detail/11.2127.TP.20170216.1044.038.html.)

[11] 吴聪聪,贺毅朝,陈嶷瑛,等.变异蝙蝠算法求解折扣{0- 1}背包问题[J].计算机应用,2017,37(5):1292-1299.(WU C C, HE Y C, CHEN Y Y, et al. Mutated bat algorithm for solving the discounted{0- 1}KP [J]. Journal of Computer Applications, 2017, 37(5): 1292-1299.)

[12] ASKARZADEH A. A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm [J]. Computers & Structures, 2016, 169: 1-12.

[13] ABDELAZIZ A Y, FATHY A. A novel approach based on crow search algorithm for optimal selection of conductor size in radial distribution networks [J]. Engineering Science & Technology: An International Journal, 2017, 20(2): 391-402.

[14] SHEN L, XU L, WEI R, et al. Multi-swarm optimization with chaotic mapping for dynamic optimization problems [C]// Proceedings of the 2016 International Symposium on Computational Intelligence and Design. Piscataway, NJ: IEEE, 2016: 132-137.

[15] 贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法[J].计算机研究与发展,2007,44(9):1476-1484.(HE Y C, WANG X Z, KOU Y Z. A binary differential evolution algorithm with hybrid encoding [J]. Journal of Computer Research and Development, 2007, 44(9): 1467-1484.)

[16] NOMAN N, IBA H. Enhancing differential evolution performance with local search for high dimensional function optimization [C]// GECCO 2005: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation. New York: ACM, 2005: 967-974.

[17] MICHALEWICZ Z, JANIKOW C Z, KRAWCZYK J B. A modified genetic algorithm for optimal control problems [J]. Computers & Mathematics with Applications, 1992, 23(12): 83-94.

This work is partially supported by Scientific Research Project Program of Colleges and Universities in Hebei Province (ZD2016005), the Natural Science Foundation of Hebei Province (F2016403055).

LIUXuejing, born in 1980, M. S., lecturer. Her research interests include evolutionary computing, machine learning.

HEYichao, born in 1969, M. S., professor. His research interests include intelligent computing, computational complexity theory.

LUFengjia, born in 1980, M. S., lecturer. Her research interests include big data, machine learning.

WUCongcong, born in 1975, M. S., lecturer. Her research interests include intelligent computing, information retrieval, machine learning.

CAIXiufeng, born in 1978, M. S., lecturer. Her research interests include intelligent computing, machine learning.