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

《基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题-刘雪静.pdf》由会员分享，可在线阅读，更多相关《基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题-刘雪静.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Journal of Computer Applications计算机应用，2018，38(1)：137145，181ISSN 1001908lCODEN JYIIDU2018-0110hup：wwwjocaca文章编号：1001-9081(2018)01013709 DOI：10I 1772jisan100190812017061445基于差分演化策略的混沌乌鸦算法求解折扣01背包问题刘雪静，贺毅朝，路凤佳，吴聪聪，才秀凤(河北地质大学信息工程学院，石家庄05003 1)(通信作者电子邮箱kips163conl)摘要：针对确定性算法难于求解的各项的重量系数和价值系数在大范围内取值的折扣0-1

2、背包问题(D0-1KP)，提出了基于差分演化策略的混沌乌鸦算法(DECCSA)。首先，采用混沌映射生成初始乌鸦种群；然后，采用混合编码方式和贪心修复与优化策略(Gnos)解决了D01KP的编码问题；最后，引入差分演化策略提高算法的收敛速度。对4类大规模D01KP实例的计算结果表明：DECCSA比遗传算法、细茵觅食算法和变异蝙蝠算法求得的最好值和平均值更优，能得到最优解或更好的近似解，非常适于求解D01KP。关键词：乌鸦算法；折扣0l背包问题；混沌；贪心修复与优化策略；差分演化策略中图分类号：TP3016；TPl8 文献标志码：AChaotic crow search algorithm bas

3、ed ondifferential evolution strategy for solving discountO-1)knapsack problemLIU Xuejing。，HE Yichao，LU Fengjia，WU Congcong，CAI Xiufeng(CoRe ofInformation凸曲咖ltebei GEO Unemty,鼬批zIl昭Hebei 050031，Chna)Abstract：In Discount0-1)Knapsack Problem(D0-1)KP)，the weight coefficients and the value coefficients i

4、n alarge range，are difficult to solve by deterministic algorithmsTo solve this problem，a Chaotic Crow Search Algorithm basedon Differential Evolution strategy(DECCSA)was proposedFirstly，the initial CrnW population Was generated by chaoticmappingSecondly，mixed coding and Greedy Repair and Optimizatio

5、n Strategy(GROS)were used to solve the cedingproblem of D01)KPFinally，Difference Evolution(DE)strategy was introduced to improve the convergence rate of thealgorithmThe experimental results on four largescale D0-1KP instances show that DECCSA is better than GeneticAlgorithm(GA)，bacterial foraging op

6、timization algorithm，and mutated bat algorithm， and it Can get the optimal solution orapproximate optimal solutionItS very suitable for solving D01 l KPKey words：crow search algorithm；Discount0-1】Knapsack Problem(D0-1 l KP)；chaotic；Greedy Repair andOptimization Strategy(GROS)；Difference Evolution(DE

7、)strategy0 引言背包问题(Knapsack Problem，KP)是一类经典的组合优化问题，在投资决策、货物装载、整数规划等领域有着非常重要的理论和应用价值。KP包含许多不同的形式，如0-1背包问题(01KP)旧J、多维背包问题(MultiDimensional KnapsackProblem，MDKP)”“1、多选择多维背包问题(Multiple-ChoiceMultidimensional Knapsack Problem，MMKP)L5、最大最小背包问题(Maxmin Knapsack Problem，MmKP)t6 J和折扣01背包问题(Discounted01Knapsac

8、k Problem，D0-1KP)“o等。D01KP是Guldan71于2007年提出的一个新颖KP，首先研究了利用动态规划法对其进行求解；Rong等o对D01KP的核(Core)问题进行了研究，将其与动态规划法相结合求解D01KP。贺毅朝等一1利用杰出者保留策略遗传算法(Genetic Algorithm with Elitist reservation strategy，EGA)求解D01KP，提出了基于两个不同数学模型的算法FirEGA(First EGA)和SecEGA(Second EGA)，两种算法均能得到一个近似比接近于1的近似解；刘雪静等驯利用细菌觅食(Bacterial Fo

9、raging Optimization，BFO)算法求解D0-lKP，在两个不同数学模型下提出的算法FirBFO(First BFO)和SecBFO(Second BFO)，能够得到更好的近似解；吴聪聪等利用变异蝙蝠算法(Mutated Double Binary Bat Algorithm，MDBBA)求解D0-1KP，该算法在大部分实例上优于算法FirEGA。由于D01KP的提出时间较晚，基于演化算法求解的相关研究成果相对较少，虽然利用EGA、BFO和MDBBA已经提出了求解D01KP的不同方法，但是还存在许多有待改进的方面，例如如何提高初始解的多样性、如何提高算法的求解速度等问题，因此如

10、何利用演化算法更好、更快地求解D0-1KP是一个值得研究的问题。收稿日期：201706-13；修回日期：20170831。基金项目：河北省高等学校科学研究计划项目(ZD2016005)；河北省自然科学基金资助项目(F2016403055)。作者简介：刘雪静(1980一)，女，河北定州人，讲师，硕士，CCF会员，主要研究方向：演化计算、机器学习；贺毅朝(1969一)，男，河北晋州人，教授，硕士，CCF高级会员，主要研究方向：智能计算、计算复杂性理论；路风佳(1980一)，女，河北沧州人，讲师，硕士，主要研究方向：大数据、机器学习；吴聪聪(1975一)，女，河北唐山人，讲师，硕士，主要研究方向：智

11、能计算、信息检索、机器学习；才秀凤(1978一)，女，河北丰润人，讲师，硕士，主要研究方向：智能计算、机器学习。万方数据138 计算机应用 第38卷为了利用新型演化算法乌鸦算法(Crow SearchAlgorithm，CSA)12 J高效求解D0一ll(P，基于D0-1KP的第一数学模型，本文基于多种有效策略与CSA相融合提出了求解D0-lKP的一种新的高效方法。在新方法中，首先针对初始解随机产生时存在分布不均的缺陷，提出采用混沌映射优化初始解的方法；其次，利用混合编码方式得到D0一lKP的潜在解，并通过GROS对潜在解进行修复和优化处理，以获得一个质量更优的可行解；第三，在算法中引入差分演

12、化策略来提高算法的全局寻优能力和收敛速度。对4类大规模实例的计算结果表明：DECCSA能快速求得近似比接近l的满意解，优于FirEGA、FirBFO和MDBBA这3种算法。1 D01KP定义1 给定n个项集，且任一项集i(0i，l一1)中均含3项，分别为3i、3i+1和3i+2，其对应的价值系数为P，i、Pml和P3f+2，重量系数为W埘l和W3m，其中，P3i+2=P3I+p孔+l，埘孔+2lt)3f、埘3f+2W孔+1、埘孔+2c(oiB一1)。哟o(o3n一1)，背包载重为c(CO)。文献8中对D0-1KP的数学模型描述如下：n一1maxf(X)=max(xs护3i+X3i+IP3i+l

13、+X31+2P3i+2)(1)I oUnlstx3P3。+X3i+IP3+X3i+2P3m)C (2)l 20工瓢+茹孤+l+石孔+21；i=0，1，n一1 (3)茗孔，x孤+l，戈孔+20，1；i=0，1，挖一1 (4)其中：变量气(0i3n一1)表示项i是否被装入背包，黾=l即项i装入背包，蕾=0即项i未装入背包。显然，任意的二进制向量x=名o，茹1，“，茗扣。o，lP仅是D0-1KP的一个潜在解，只有同时满足约束条件式(2)、(3)和(4)的二进制向量x才是D01KP的一个可行解。2乌鸦算法乌鸦算法是一种新颖的元启发算法，在网络优化分配31、医学等领域有较少的研究成果。CSA模拟自然界中

14、乌鸦的智能行为。乌鸦是群居生活的鸟类，它们非常聪明，能将自己多余的食物藏匿起来，藏匿位置称为记忆值(Memory，M)，并在需要时取出；当前能跟踪其他乌鸦，窃取其他乌鸦的食物，而被跟踪的乌鸦能以一定的感知概率(AwarenessProbability，AP)保护自己的食物防止被窃。假定、r只乌鸦分布在t,维搜索空间中，r”7表示第i只乌鸦在第iter次迭代时的位置，r雕”1的结果如式(5)所示：叫，“r+l f掣”7+4。”(肝”一Xi”)，rjA】“L任意位置， 其他(5)其中：r。、rj是o，1区间服从均匀分布的随机数；胛”为乌鸦，、迭代次数iter时的记忆值；AP”为乌鸦，的感知概率；“

15、”为乌鸦i在第iter迭代时的飞行长度。当乌鸦的位置发生了改变，式(6)给出了肼的更新方式：肘；蛔“：J掣“”，八掣肚”1)以肘。“) (6)-；一SttMi， 其他下面给出CSA的算法描述。算法1 CSA。初始化参数：最大迭代次数MITER，飞行长度，感知概率AP，种群大小，问题维度n。生成初始种群P(O)：计算适应度值，(P(O)；初始化乌鸦的记忆值Mo=P(O)；While iterAP时，乌鸦i以膏”“=r向+ri*fl“(膨一一F”)的方式向乌鸦，的最佳位置移动，但是乌鸦，的最佳位置不一定好，故收敛速度可能变慢，由此，引入差分演化策略对跟踪方式进行改进。差分演化的变异算子的一般形式为

16、DExyzu“，其中：茹是一个字符串，代表要被扰动的基向量；y代表为扰动并而使用的差分向量的个数；z代表交叉的类型(指数交叉EXP或二项式交叉BIN)。本文采用DEbestlBIN的方式，跟踪公式改进如下：一，。一fBes“+“$(r“一刀”)，riAtr”7L任意位置， 其他(9)其中。Best。为当前迭代的最优值。乌鸦i每次向着最优的个体移动，提高收敛速度。34贪心修复与优化策略由于二元向量y=Yo，Yl，Y。0，1 P可能是非正常编码个体，因此引入贪心与优化策略(Greedy Repair andOptimization Strategy，GROS)一1把非正常编码个体修正为正常编码个体

17、并进行优化。假定原二进制个体为Y=Yo，Y。，Y川0，1P，修正后二进制个体为Z=ZO，zl一，稚。E0，1P，数组no，1，3n一1中存放价值系数密度pw_(0J3n一1)的降序排列下标序，各项集的状态标识F0，1，n一10，18，Fj=0表示项集，中没有项装入背包，Fj=1表示项集J中恰有一项装入背包，Li3j表示i3向下取整。GROS算法描述如下。算法2 GROS。输入：二进制个体Y=Y0，Y1，h1和数组H10，1，3n一1；输出：二元向量z=Z0，zl一，“一1和八z)。1) weight=0，value=02) Fori=0 to 3n一1 Do=03) Fori=0 to n一1

18、 DoFi=041 Fori=0 to 3n一1 Do5) If(Yzf=1)(weight+W珊c)(H LHi3J=0)6) weight=weight+WH，FLHi3J=1，7) value=value+Px，Zx2 18) Endif9) Endfor101 Fori=0 to 3n一1 Do11) If(weight+WItc)(FL日i3J=o)12) weight=weight+wHi1，zHi1=113) FL肌i3J=1，value=value+P小f14) Endif151 Endfor16) Return(Z，value)第2)和3)行的时间复杂度为0(凡)；第4)一9

19、)行将非正常编码个体y修复为正常编码个体并存于z中，时间复杂度为0(n)；第10)一15)行对z作进一步优化，时间复杂度为O(n)。显然，GROS的时间复杂度为O(，1)。35基于差分演化的混沌CSA求解D101KPDECCSA求解D01KP流程如图1所示。其中，QuickSort(piw；)为对价值系数密度P。wi(0i3n一1)按非递增进行快速排序，B(t)(0tMITER)为第i次迭代后种群。在图1中，虚线框A部分为采用Circle映射生成的优化初始乌鸦种群，虚线框B部分为采用差分演化策略按式(9)生成的乌鸦i在下一次迭代的位置。图1 DECCSA流程Fig1 Flow chart of

20、 DECCSA在DECCSA中，QuickSort的时间复杂度为O(凡log n)，生成初始种群的时间复杂度为O(nN)，GROS的时间复杂度为O(n)，由于N、MITER是关于n的线性函数，故DECCSA的时间复杂度为0(n log n)+0(nN)+0(n)+MITER(D(nv)+D(忍)=D(n3)，因此DECCSA是一个复杂度为多项式时间的进化算法。4仿真实验与分析在本章中，不相关D0-lKP实例(Uncorrelated instances0f D0-1KP，UDKP)、弱相关D0-1KP实例(Weaklycorrelated instances of D01KP，WDKP)、强相

21、关D01KP实例(Strongly correlated instances of D0-1KP，SDKP)和逆向强相关D01KP实例(Inversestrongly correlated instancesD0-lKP，IDKP)的生成参照文献10，每一类实例包含10个不同规模的实例。首先利用若干实例的计算结果所对万方数据140 计算机应用 第38卷应的箱线图(Boxplot)分析并确定CSA和DECCSA中感知概率AP和飞行长度的合理取值；然后利用对4类大规模DOlKP实例的计算结果比较CSA和DECCSA的求解性能。本文所使用微型计算机硬件配置为Intel Core i34005uCPU

22、170 GHz，4 GB内存(375 GB可用)，操作系统MicroaoftWindows 7，编程语言C语言，编译环境CodeBlocks，并利用M“ab 7140739(R2012a)绘图。41确定AP和n的合理取值AP分别取值01，02，03，04，分别取值10，20，30，40，50，共构成20种不同的组合形式(A尸，)，表1列出所有组合的ID。下面分别利用4类实例对AP和月的每一种组合进行计算，以确定AP和的合理取值。限于篇幅，针对每一种组合形式，仅给出CSA和DECCSA两种算法在规模为3n=l 500的实例UDKP5、WDKP5、SDKP5和IDKP5的计算结果及其所对应的箱线图

23、。衰1 参数组合形式IAP。)及其IDTab1 Parameter combination form(AP-J and its IDID(AP，) ID(AP，月) ID (AP，) ID(AP，)1 (01，1) 6 (O2，1) 11 (O3，1) 16 (O4，1)2 (01，2) 7 (O2，2) 12 (O3，2) 17 (04，2)3 (01，3) 8 (02，3) 13 (03，3) 18 (04，3)4 (O1，4) 9 (02，4) 14 (03，4) 19 (04，4)5 (01，5) lO (O2。5) 15 (03，5) 20 (04，5)图2是在20种组合情况下独立运

24、行CSA 30次求解UDKP5、WDKIPl5、SDKP5和IDKP5时所求最好值箱线图。组合编号(a)求解实例UDKP5组合编号(b)求解实例WDKP5组合编号(C)求解实例SDKP5组合编号(d)求解实例IDKP5图2 20种组合下CSA求解4个实例的性能比较Fig2 Performance coinpalison 0f 4 exan驴les by CSA20 combinations从图2(a)可以看出，求解UDKP5，当AP=02时，所求的最优值最好，当J4P=04、，=2时，中位数最好。从图2(b)可以看出，求解WDKP5，当AP=04时，所求最好值较好，当AP=03、=2时，中位数

25、最好。从图2(c)可以看出，求解SDKI】5，当AP=01，=3或5时，所求最优值最好，当AP=02，=3时，中位数最好。从图2(d)可以看出，求解IDKP5，当AP=03，刀=1，2，3时，所求最优值最好，当AP=03，=2时，中位数最好。由图2可得，针对UDKP、WDKP和IDKP类实例，当AP取值稍大时平均求解性能较好，针对SDKP类实例，当AP=02时平均求解性能较好。本文采用的是求得中位数最好的组合。图3是20种组合情况下独立运行DECCSA 30次求解UDKIP5、WDKP5、SDKP5和IDKP：5时所求最好值的箱线图。由图3(a)可以看出，AP=01，=50时所求最好值最优，A

26、P=01，刀=20时中位数值最好。在图3(b)中，30次所求中位数基本相同，AP=01，=20、04和AP=03，=I0时最好值最好。在图3(c)中，AP=01，=20时最好值和中位数值都最好。在图3(d)中，除AP=01，算=20外所有组合所求最好值相同，AP=01，=20时最优。图2与图3对比可以看出，DECCSA所求的最好解相对较集中，针对4类实例，AP值相对较小为好。综上，DECCSA参数的最佳设置应为AP=01，z=20。390=385蝈380蛰磊组合编号弓叠虫嘣色=趔虫堪组合编号58458358258l580组合编号(c)求解实例SDKP5组合编号(d)求解实例IDKP5图3 20

27、种组合下DECCSA求解4个实例的性能比较Fig3 Performance COII删SOII of 4 examples by DECCSA Oil 20 combinations42计算结果比较与分析实验参数设置如下：CSA求解4类D01KP实例时，N=50，MITER=3000，求解UDKP时，AP=04，=2；求解WDKP时，AP=03，=2；求解SDKP时，AP=02，=3；求解IDKP时，AP=03，：2。DECCSA求解4类D0-1KP实例时，设置AP=01，=20，N=50，MITER=3000。不同算法求解各个实例的结果如表25所示，其中DPDKP为由动态规划法所求最优解o“

28、，FirEGA算法求解4类实例的三坦虫路万方数据第1期 刘雪静等：基于差分演化策略的混沌乌鸦算法求解折扣01背包问题 141数据来自文献10，FirBFO算法求解4类实例的数据来自文献11，MDBBA算法求解4类实例的数据来自文献12。表2给出了UDKP类实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。最优值最好值和最优值最差值分别代表最好值近似比和平均值近似“川。裹2 6种算法求解UDKP实例的结果比较Tab2 ResultsplIriof six algorithms for solving UDKP instances图

29、4对CSA和DECCSA求解UDKP类实例时的最好值近似比和平均值近似比进行了比较。丑荟鲻j玺虫堪丑荟蚓趔露斗实例名实例名(b)平均值近似比比较图4 CSA与DECCSA求解UDKP类实例时的近似比对比rig4 Al】p砌蛐mtio伽哪pari啪d CSA and DECCSA for UDKP ill嘲II_嘲从图4(a)可以看出，DECCSA的最好值近似比的最大值与CSA的最小值大致相当。图4(b)与图4(a)区别不大，但是平均值近似比值相对有所增大。由图4可知，DECCSA比CSA更适合求解UDKP类实例。图5给出了DECCSA与FirEGA、FirBFO和MDBBA求解UDKP类实例时

30、的最好值近似比和平均值近似比的比较。丑至蝈趔虫堪丑荟蚓j罾露斗120118116114112110108106104102实例名(b)平均值近似比比较图5 DECCSA与另三种算法求解UDKP类实例时的近似比对比Fig5 Appmxinmte ratio comlIisof DECCSA andother three algorithms for UDKP instances由图5(a)可以看出DI麟在求解UDKPlUDKP4时比万方数据142 计算机应用 第38卷其他算法好，求解UDKI丐UDKP7时不如FirEGA和MDBBA，求解UDKP8UDKPl0时与FkEGA和MDBBA能力相当。

31、由图5(b)可看出在求解UDKPl、UDKF2、UDKP4时，DECCSA明显比其他算法好，求解UDKP5一UDKP7明显不如FirEGA和MDBBA，其他实例DECCSA、FirEGA和MDBBA3种算法能力相当。表3给出了求解WDKP实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。表3 6种算法求解WDKP实例的结果比较Tab3 Results comparison of six algorithms for solving WDKP instances图6对CSA和DECCSA求解WDKP类实例时的最好值近似比和平均值近

32、似比进行了比较。丑荟蚓j型虫堪(b)平均值近似比比较图6 CSA与DECCSA求解WDKP类实例时的近似比对比Fig6 AI)pmimale ratio删啤li咖0f CSA and DECCSA for WDKP instances由图6(a)可以看出，DECCSA在求饵WDKP实例时最好值近似比远远小于CSA；图6(b)中两种算法的平均值近似比有所增大，曲线变化不大，仍然是DECCSA的平均值近似比小于CSA，故DECCSA比CSA更适合求解WDKP类实例。由图7(a)可以看出求解WDKPl一WDKP3三个实例时DECCSA性能最好，求解其他实例时FirBFO、MDBBA和DECCSA的求

33、解能力相当，FirEGA最好值近似比最大。丑荟蚓趔曩牛i 一。一FirEGAj力|一FirBF0一早-MDBBA一DECCSA彩一实例名(b)平均值近似比比较图7 DECCSA与另三种算法求解WDKP类实例时的近似比对比Fig7 Approximate ratio comparison of DECCSA andother three algorithms for WDKP instances图7(b)中FirEGA的平均值近似比值当实例规模增大时ill丑荟蝈趔虫略万方数据第1期 刘雪静等：基于差分演化策略的混沌乌鸦算法求解折扣01背包问题 143与图7(a)差异明显，变得更差，DECCSA的

34、求解性能在WDICPlWDKP3时最好，在其余实例上与FirBFO、MDBBA求解能力相当。表4给出了求解SDKP实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。裹4 6种算法求解SDKP实倒的结果比较Tab4 Comparison of six algorithms for solving SDKP instances图8给出了CSA与DECCSA求解SDKP实例时的最好值近似比与平均值近似比的比较。丑荟蚓j墅露*(b)平均值近似比比较图8 CSA与DECCSA求解SDKP类实例时的近似比对比F培8山pp砌蛐ratio啪p日

35、Iison0f CSA and DECCSA for SDKP instances由图8可以看出DECCSA在求解SDKP类实例时最好值近似比和平均值近似比都远远小于CSA，比CSA适合求解SDKP类实例。由图9(a)可以看出DECCSA在求解SDKP实例时比其他算法好，能得到较好的满意解，且在求鹪SDKPl一SDKIr3三个实例时优势明显。从图9(b)可以看出，平均值近似比也是DECCSA最小，取得的平均值最优。丑至蚓j型虫堪丑荟蚓趔曰斗实例名(a)最好值近似比比较图9 DECCSA与另三种算法求解SDKP类实例时的近似比对比Fig9 Approximate ratio comparison

36、 of DECCSA andother three algorithms for SDKP instances表5给出了求解IDKP实例的理论最优值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五种算法所求的最好值、最差值和平均值。从表5可以看出，求解IDKP实例时，CSA的万方数据144 计算机应用 第38卷求解性能最差，DECCCSA在IDKPl、IDKIY2和IDKP4实例上能取得理论最优值。由图lO(a)和图10(b)可以看出，DECCSA在求解IDKP类实例时最好值近似比和平均值近似比基本都为1，优于CSA，非常适合求解IDKP类实例。由图11(a)可以看出DECCS

37、A和MDBBA、FirBFO的最优近似比基本等于l，FirEGA稍差。图1l(b)与图11(a)区别不大，平均值近似比DECCSA、FirBFO、MDBBA相差依然不大，基本等于1，FirEGA稍差。衰5 6种算法求解IDKP实例的结果比较Tab5 Results comparison of 6 al酬tlIm for solving IDKP instances算法 结果 IDKPI IDKP2 IDKIr3 IDKP4 IDICI】5 IDKI粥 IDKP7 IDKP8 IDKP9 IDKPl0丑奋杖趔曩1实例名(b)平均值近似比比较图10 CSA与DECCSA求解IDKP类实例时的近似比

38、对比隧10 Approximate ratio呷ari咖0f CSA and DECCSA for IDKP instances综上，对于UDKP类问题，DECCSA与其他算法在求解效果上不相上下；对于WDKP、SDKP和IDKP类问题，DECCSA求解效果明显比其他算法的更优。之所以产生这样的结果，一方面是因为CSA的求解速度快且易于扩充，另一方面是它与DE的结合做到了优势互补，因此体现出了极佳的求解性能。丑釜蚓趔露*买例名【b)平均值近似比比较图11 DECCSA与另三种算法求解IDKP类实例时的近似比对比Fig1 1 Approximate ratio comparison of DEC

39、CSA andother three algo珧ns for IDKP instances图12显示了CSA和DECCSA求解UDKIX3、WDKP3、SDKP3和IDKP3四个实例时的收敛速度，每个实例独立运行30次，明显可以看出DECCSA比CSA求解性能更优。从图12(a)可以看出，求解UDKP3时，DECCSA在前100代收敛i；ill羞套蝴遥虫蝎万方数据第1期 刘雪静等：基于差分演化策略的混沌乌鸦算法求解折扣01背包问题 145速度较快，后面收敛速度缓慢，CSA也是前100代收敛速度稍快，后面较慢，且迭代次数对最好值影响不大。从图12(b)(d)可以看出，DECCSA求解WDKP3、

40、SDKP3和IDKP3三个实例时，混沌策略非常有效，能得到较好的初始解，收敛曲线平缓，而CSA依然是处于缓慢收敛的状态二毛痼虫堪皂趔虫堪迭代次数，102(a)实例UDKP3的收敛曲线。笔235疽230虫225堪2 20乞j粤虫略迭代次数，102(b)实例WDKP3的收敛曲线迭代次数，102(c)实例SDKP3的收敛曲线迭代次tel0(d)实例IDKP3的收敛曲线图12 CSA和DECCSA在4个实例上的收敛速度对比Fig12 Conv郫speedmF抵0f CSA and DECCSA妇4 examples基于上述计算、比较和分析得出以下结论：对于项的价值系数和重量系数均在大范围内随机取值的4

41、类大规模D01KP实例，DECCSA能够快速求得一个近似比接近于l的近似解，是适于求解大规模难D0-lKP的有效且实用的进化算法。另外，求解UDKP实例时，DECCSA和FirEGA、MDBBA的求解性能相当，10个实例各有优劣，FirBFO性能稍差。求解WDKP、SDKP、IDKP三类实例时，DECCSA比FirEGA、FirBFO、MDBBA三算法的求解性能好，从而说明混沌策略和差分演化策略能有效地改进CSA，能够求得D01KP的较满意解或最优解。5 结语本文研究了如何利用乌鸦算法求解D01KP，提出了针对初始解随机产生的缺点采用混沌策略初始化个体和引入差分演化策略改进乌鸦跟踪方式的差分混

42、沌乌鸦算法求解D01KP。仿真实验表明：对于大规模的D0一lKP实例，DECCSA不受实例中各项的价值系数、重量系数和背包载重的大小影响，能够快速求得一个近似比接近于1的近似解，因此它是一个求解大规模难实例的实用进化算法。在利用DECCSA求解DO1KP时，UDKP类实例的计算结果较其他三类的略差，因此进一步分析DECCSA的特点，使之对于UDKP类实例也能获得更佳的结果是需要今后研究的问题。此外，能否基于D01KP的第二、三数学模型一1设计更加高效的进化算法也是一个值得今后探讨的问题。参考文献(References)【1】 KELLERER H，PFERSCHY U，PISINGER DKn

43、apsack Problems【M】Berlin：Springer，2004：5575【2】WILBAUT C，SALHI S，HANAFI SAn iterative variablebasedfixation heuristic for the 0-1 multidimensional knapsack problem【J】European Journal of Operational Research，2009，199(2)：339348【3】 CHU P C，BEASLEY J EA genetic algorithm for the multidimensional knapsack

44、 problem【J】Journal of Heuristics，1998，4(1)：6386【4】DJANNATY F，D(蜘AR SA hybrid genetic algorithm for the multidimemional knapsack problem【J】International Journal of Contempo-rary Mathematical Sciences2008，3(9101112)：443456【5】 SBIHI AA best first search exact algorithm for the multiplechoicemultidimens

45、ional knapsack problem【J】Journal of CombinatorialOptimization，2006，13(4)：337351【6】FURINI F，L0m M，MARTEUJ0 S，et a1Heuristic and exact al-gnrithms for the interval winmax regret knapsack problem【J1NFORMS Journal on Computing，2015，27(2)：392405【7】 GULDAN BHeuristic and exact algorithms for discounted kn

46、apsackproblems【D】Erlangen：University of ErlangenNfimberg，2007：l一78【8】 RONG A Y，FIGUEIRA J R，KLAMROTH KDynamic program-IIling based algorithms for the discounted f 01 1 knapsack problem【J1Applied Mathematics and Computation，2012，218(12)：69216933【9】 贺毅朝，王熙照，李文斌，等基于遗传算法求解折扣01)背包问题的研究【J】计算机学报，2016，39(12

47、)：26142630(HE YC，WANG X Z，U W B，et a1Research on genetic algorithms forthe discounted f 0一lknapsack problem【J】Chinese Journal ofComputers，2016，39(12)：26142630)【lO】 刘雪静，贺毅朝，吴聪聪，等基于细菌觅食算法求解折扣0一l背包问题的研究【JOL】计算机工程与应用，2017：111(20170216)【201708-18】http：knscnkinetkcmJdetail112127TP201702161044038htlIll(UUX J，HE Y C，WUC C，et a1Research on bacterial foraging optimization algorithmfor the Discounted【01 l knapsack problem【JOLlComputerEngineering and Applications，2017：1一11(20170216)【201708-18】http：knscnkinetkcmsdetail112127ri