APP下载

求解0-1背包问题的混沌二进制乌鸦算法

2018-05-21刘雪静贺毅朝吴聪聪

计算机工程与应用 2018年10期
关键词:二进制背包复杂度

刘雪静,贺毅朝,吴聪聪,李 靓

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

2.中国邮政集团公司 河北省邮政信息技术局,石家庄 050011

1 引言

0-1背包问题(0-1 Knapsack Problem,0-1KP)[1-2]是经典的NP-hard问题,在项目选择、货物装载和投资决策等方面具有重要的理论与应用价值。0-1KP的一般描述为:假定有n个不同的物品,重量集合W={w1,w2,…,wn},价值集合P={p1,p2,…,pn},背包最大载重C。0-1KP为从n个不同物品中选择若干个装入背包,在不超过背包载重C的前提下使其价值之和最大。0-1KP的数学模型表示如下,当且仅当第i个物品被装入背包时xi=1。

乌鸦算法(Crow Search Algorithm,CSA)[3]是一种新近被提出的新颖演化算法,由于该算法中仅有感知概率(Awareness Probability,AP)和飞行长度(flight length,fl)两个可调节参数,是一个参数较少的简单的算法,故CSA在参数设置方面具有一定的优势。由于乌鸦算法提出时间较短,应用领域较少,并且还未见其在0-1KP问题中的应用研究,为此本文首先提出利用乌鸦算法求解0-1KP。

2 相关研究工作

目前,人们相继研究了基于不同演化算法求解0-1KP的方法,并取得了许多可以借鉴的研究成果。例如,贺毅朝等[4]提出第一个二进制差分演化算法求解0-1KP问题,并证明了其收敛性;武慧虹等[5]提出利用克隆选择免疫遗传算法求解0-1KP问题;吴聪聪等[6]利用贪心二进制蝙蝠算法求解0-1KP问题,能获得最优解;李宁等[7]基于二进制和声搜索算法求解K-可满足性问题和0-1KP问题,并验证了算法的可行性;宋潇潇等[8]将膜计算的思想引入人工蜂群算法,提出了改进的蜂膜群算法求解0-1KP问题;李若平等[9]在和声搜索算法中引入新的学习搜索机制,提出学习型和声搜索算法求解0-1KP问题;李栋等[10]基于双子群协同进化的思想,提出求解0-1KP的双子群果蝇优化算法;高芳等[11]在粒子群中引入生物病毒机制和宿主与病毒的思想,提出求解0-1KP的病毒协同进化粒子群算法;Zhou等[12]提出了一种基于贪婪算法的二进制猴子算法求解0-1KP问题,能得到较好的结果。由此可见,利用演化算法快速高效求解0-1KP是智能计算领域中的一个研究热点问题。

3 乌鸦算法

自然界中的乌鸦具有以下特性:乌鸦是群居生活的鸟类,它们非常聪明,会记住自己藏匿食物的最佳位置(Memory,M),能跟踪其他乌鸦偷窃对方的食物,而被跟踪的乌鸦能以一定的感知概率AP保护自己的食物防止被窃取。文献[3]在研究了乌鸦特性的基础上提出了模拟乌鸦行为的乌鸦算法,下面给出CSA的算法描述。

算法1 CSA

步骤1初始化。

在n维的可行域中随机生成NP只乌鸦,每只乌鸦X=[x0,x1,…,xn-1]表示一个可行解,初始化最大迭代次数iter_max、飞行长度 fl和感知概率AP。

步骤2初始化乌鸦的记忆值,评价乌鸦的适应度值。

步骤3更新乌鸦位置。

假定乌鸦i随机选择乌鸦 j跟踪,结果如下:

乌鸦 j不知道乌鸦i跟踪它,则乌鸦i将接近乌鸦 j藏匿食物的最佳位置M;乌鸦 j知道乌鸦i跟踪它,则其故意把乌鸦i带到一个随机位置。

乌鸦 i的新位置如公式(4)所示,其中,ri、rj是服从[0,1]均匀分布的随机数,mj,iter为乌鸦 j在iter次迭代时的记忆值,APj,iter为乌鸦 j的感知概率,fli,iter为飞行长度。

步骤4检查新位置的可行性。

如果乌鸦i的新位置是可行的,则更新;否则乌鸦i停留在当前位置。

步骤5评价乌鸦i的新位置的适应度值。

步骤6以式(5)的方式更新记忆值。

步骤7重复步骤3~步骤6,直至迭代终止。

算法运行结束后,所有乌鸦记忆值中的最好位置即为问题的最优解。

CSA与遗传算法、粒子群算法、和声算法一样,都是利用群体智能来探索最优化问题的解。除了种群数量和最大迭代次数以外,优化算法一般还需涉及其他参数。由于参数的调整是一项耗时的工作,所以过多的参数是优化算法的一个缺点。粒子群算法中可调参数为惯性权重、速度的最大值、学习因子等;和声算法要求考虑和声库记忆选择概率和记忆扰动概率等参数;遗传算法需考虑交叉方法、交叉概率、变异方法、变异概率等参数。而CSA仅有AP和 fl两个可调节参数,故算法相对简单、易于实现。

任何元启发式算法都应在多元化与集约化之间提供良好的平衡[13]。CSA的集约化和多元化主要受到参数AP的控制。降低AP的值,CSA倾向于局部搜索,因此,较小的AP值增加了集约化;相反,加大AP的值,CSA趋向全局搜索,故较大的AP值增加了多元化。

4 混沌二进制乌鸦算法

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

十多年来,混沌优化方法[14]作为一种新颖的优化技术,得到了广泛的关注和应用。由于混沌能按照自身的规律在一定范围内不重复遍历所有状态,因此利用混沌优化方法求解数值优化问题时,混沌轨迹能使搜索过程避免陷入局部最优,从而获得全局最优解或者较好的满意解。

CSA采用随机方法初始化乌鸦的位置,极有可能造成乌鸦的位置分布不均匀,混沌序列能更加有效地实现对搜索空间的搜索,故采用Chebyshev映射初始化乌鸦位置,增加初始解的多样性,为进一步有效地进行全局搜索打下良好的基础,Chebyshev映射表达式如下:

本文采用两种映射方式生成乌鸦个体,第一种方式如下:

(1)对n维空间中的NP只乌鸦,个体 Xi=[xi,0,xi,1,…,xi,n-1](i=1,2,…,NP)的xi,0值随机产生。

(2)利用公式(6)对 xi,0(i=1,2,…,NP)进行 n-1次迭代,生成乌鸦Xi的xi,1,xi,2,…,xi,n-1值。

第二种映射方式如下:

(1)对n维空间中的NP只乌鸦,随机产生n维向量X0=[x0,x1,…,xn-1],作为第一只乌鸦。

(2)将 X0按公式(6)进行 NP-1迭代,生成其余NP-1个个体。

至此,乌鸦的初始化步骤完成。

4.2 混合编码方式

在CSA中,乌鸦个体X=[x0,x1,…,xn-1]为实型向量,fl、AP为实数,而0-1KP是离散域的问题,因此需要将乌鸦个体X转换为0-1向量以实现CSA对离散问题的求解。转换方法如式(7)所示。

其中,Y=[y0,y1,…,yn-1],yj∈{0,1},j=0,1,…,n-1。种群中的个体用n维实型向量X和二进制向量Y共同表示即(X,Y),以[-a,a]n为辅助搜索空间(本文a=5),以{0,1}n为解空间,实现对离散问题的求解。

4.3 贪心修复与优化算法

任意二进制个体Y=[y0,y1,…,yn-1]∈{0,1}n仅是0-1KP的一个潜在解,本文利用贪心修复与优化算法[15](Greedy Repair and Optimization Algorithm,GROA)对潜在解进行修复使之成为可行解,同时进一步优化该个体。

假定 n、W、P、C 含义同前,H[0,1,…,n-1]中存放物品按照 pi/wi降序排序的下标序,Y=[y0,y1,…,yn-1]∈{0,1}n为输入个体编码,B=[b0,b1,…,bn-1]∈{0,1}n为修复后个体编码。GROA伪代码如下:

算法2 GROA

1.weight=0,val=0;

2.Fori=0ton-1Dobi=0

3.Endfor

4.Fori=0ton-1Do

5. If(yH[i]==1&&weight+wH[i]<=C)then

6.weight=weight+wH[i],bH[i]=1,val=val+pH[i];

7. Endif

8.Endfor

9.Fori=0ton-1Do

10. If(weight+wH[i]<=C&&yH[i]==0)then

11. weight=weight+wH[i],bH[i]=1,val=val+pH[i];

12. Endif

13.Endfor

14.Return(B,val)

在算法中,输入二元向量Y和数组H,输出修正优化后向量B及其适应度值。步2~步3首先对二元向量B赋值0,步4~步8实现对非正常编码个体的修复,并将结果存到B中,步9~步13对B做进一步优化,步14返回最终结果。显然,GROA的时间复杂度为O(n)。

4.4 混沌二进制乌鸦算法求解0-1KP

假定 n、W、P、C、H、iter_max、NP 的定义同前,将CSA与混合编码技术、混沌策略、GROA相结合生成求解0-1KP的混沌二进制乌鸦算法(CBCSA),CBCSA的伪代码描述如下。

算法3 CBCSA

1.初始化参数 AP、fl、iter_max、NP ;

2.H[0…n-1]←QuickSort(pi/wi|0≤i≤n-1);

3.采用混沌序列生成初始种群P′(0)={X′i(0)|1≤i≤NP}及二进制种群P(0);

4.GROA处理P(0)得B(0),计算 f(B(0));

5.初始化记忆值;

6.Foriter=1to iter_max Do

7.Fori=1toNPDo

8. 随机选择乌鸦j

9. If rj≥APj,iter

10. Fork=0ton-1

11.

12. Endfor

13. Else

14. xi,iter+1=搜索空间任意位置

15. Endif

16.Endfor

17.GROA对 Xiter+1处理得B(iter+1),评估新位置,以公式(5)方式更新记忆值

18.Endfor

19.返回最优值及最优个体

在CBCSA中,NP和iter_max是关于n的线性函数。QuickSort的时间复杂度为O(nlbn),步3的时间复杂度为O(nNP),GROA的时间复杂度为O(n),步6~步18中,步7~步16的时间复杂度为O(nNP),步17的时间复杂度为O(n),故CBCSA的时间复杂度为O(nlbn)+O(nNP)+O(n)+iter_max×(O(nNP)+O(n))≈O(n3)。

5 仿真计算分析与比较

为了验证二进制乌鸦算法(Binary Crow Search Algorithm,BCSA)、CBCSA1(第一映射方式)和CBCSA2(第二种映射方式)求解0-1KP的性能,本文采用表1所示的7个经典0-1KP实例进行实验,表1中dim代表维数。首先,以实验方式确定参数AP和 fl的取值。假设 AP 取值0.1,0.2,0.3,0.4,fl取值1.0,2.0,3.0,4.0,5.0,表2列出(AP,fl)的所有组合及其id。限于篇幅,针对(AP,fl)的每一种组合,图1~图7仅给出CBCSA1对7个实例分别独立计算20次所得到的最好结果。

表1 7个0-1KP实例

表2 (AP,fl)及其id

图1 CBCSA1求解KP1的性能比较

图2 CBCSA1求解KP2的性能比较

图4 CBCSA1求解KP4的性能比较

图5 CBCSA1求解KP5的性能比较

图6 CBCSA1求解KP6的性能比较

图3 CBCSA1求解KP3的性能比较

图7 CBCSA1求解KP7的性能比较

由图1可以看出,求解KP1时,id取值为3,4,5,8,9,10,13,14,15,19,20时能100%取得最优解;由图2~图4可以看出,求解KP2、KP3、KP4时,当 (AP,fl)为任意组合时都能100%取得最优解;由图5~图7可以看出,求解KP5、KP6、KP7时(AP,fl)的不同组合形式,对所求得的最优值有影响,本文选取所求中位数最好的组合,故 AP=0.1、fl=3.0。

参数设置如下:NP=30,iter_max=200,AP=0.1,fl=3.0,算法独立运行20次,实验结果如表3所示。其中,best为独立运行算法20次的最好值,worst为最差值,mean为平均值,sd为标准差,s(%)为独立运行算法20次能得到已知最优解的百分比,weight为被装入背包的物品的总重量,time(s)为算法运行一次的平均时间。表4中给出CBCSA1与其他文献算法得到的最优解的对比,“N”表示文献未提供,数值为对应的运行时间。

从表3可以看出,BCSA求解0-1KP性能较差,不能得到7个0-1KP的最优解,因此不适合求解0-1KP。由表3和表4综合来看,求解KP1时,CBCSA1能100%获得已知最优解3 119,CBCSA2在20次运行中命中16次,成功率80%,且CBCSA1的运行时间比CBCSA2略短,学习型和声算法[8]不能求得已知最优解,双子群果蝇优化算法[9]能求得3 119,但是成功率为80%;求解KP2时,CBCSA1和CBCSA2能100%得到已知最优解3 103,且CBCSA1的运行时间短,双子群果蝇优化算法也能得3 103,但是成功率为90%;求解KP3时,CBCSA1和CBCSA2均能100%得到已知最优解1 563,克隆选择免疫遗传算法[4]和改进膜蜂群算法[7]也能100%得到最优解1 563,但是求解时间比CBCSA1和CBCSA2长,ABC算法[16]不能100%获得最优解,其SD值为1.196;求解KP4时,CBCSA1和CBCSA2均能100%得到已知最优解2 660,其他算法中仅改进膜蜂群算法能取得2 660,而ABC算法、克隆选择免疫遗传算法和改进膜蜂群算法的SD值分别为18.4、2.78和1.91,且求解时间较CBCSA1和CBCSA2都长;求解KP5时,CBCSA1成功率70%,SD值为3.80,CBCSA2成功率40%,SD值为3.93,ABC算法、克隆选择免疫遗传算法和改进膜蜂群算法的SD值分别为24.43、8.62和1.35,虽然改进膜蜂群算法的SD值较CBCSA1小,但是求解时间为3.77 s,比CBCSA1的0.951 s长;求解KP6时,CBCSA1和CBCSA2的成功率虽然不如文献[6]提出的BHSA,但BHSA是在2 s内得到的运行结果,运行时间较长;求解KP7时,CBCSA1在0.858 s内得最优解88 228,CBCSA2在1.406 s内得最优解88 227,而BHSA在2 s内得到的最优解为88 129,虽然CBCSA1的成功率不高,但是Mean值为88 218.3,比BHSA的best都好,CBCSA1得到最优解的对应编码为:0,1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,1,1,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,0。

表3 运行结果

表4 运行结果对比

图8为BCSA、CBCSA1和CBCSA2在求解高维背包问题KP4~KP7时的收敛速度。由图8(a)~图8(d)可以看出,CBCSA1和CBCSA2的收敛速度非常快,甚至初始解就是最优解,即通过混沌策略生成的初始解性能非常好,且两种算法的最优解相差不大,几乎重叠;BCSA收敛速度相对较缓慢,求解性能明显不如CSCSA1和CBCSA2。

综上所述,对于0-1KP,CBCSA1和CBCSA2的求解效果非常好,远远优于BCSA,也优于其他文献所提出的算法,因此,CBCSA是适合求解0-1KP的有效算法,且混沌策略中的第一种方式比第二种方式求解性能更佳。

图8 三种算法的收敛速度

6 结束语

乌鸦算法是一种新颖演化算法,本文研究了如何利用乌鸦算法求解0-1KP,并针对CSA的不足,提出了一种基于混沌理论的二进制乌鸦算法。首先将混沌序列引入乌鸦的初始化过程,保证个体的初始位置在整个搜索空间均匀分布,提高了算法的全局寻优能力;然后针对非正常编码个体,采用贪心策略进行处理。仿真实验表明,CBCSA具有良好的全局寻优能力,收敛速度快,运行时间短,优于其他的算法,是一种求解0-1背包问题的有效实用算法。

CSA提出的时间较短,应用还很少,如何把CSA应用到其他领域是下一步的研究问题。

[1]Singh A.Elements computation theory[M].London:Springer,2009.

[2]Du D Z,Ko K I.Theory of computational complexity[M].New York:Wiley-Interscience,2000.

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

[4]贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法[J].计算机研究与发展,2007,44(9):1476-1484.

[5]武慧虹,钱淑渠,徐志丹.克隆选择免疫遗传算法对高维0/1背包问题应用[J].计算机应用,2013,33(3):845-848.

[6] 吴聪聪,贺毅朝,陈嶷瑛,等. 求解0-1 背包问题的二进制蝙蝠算法[J]. 计算机工程与应用,2015,52(19):71-74.

[7] 李宁,刘建芹,贺毅朝. 基于和声搜索算法求解组合优化问题[J]. 计算机应用,2012,32(4):1041-1044.

[8] 宋潇潇,王军. 改进膜蜂群算法求解0-1 背包问题[J]. 计算机应用,2015,35(7):2088-2092.

[9] 李若平,欧阳海滨,高立群,等. 学习型和声搜索算法及其在0-1 背包问题中的应用[J]. 控制与决策,2013,28(2):205-210.

[10] 李栋,张文宇.求解0-1背包问题的双子群果蝇优化算法[J].计算机应用研究,2015(11):3273-3277.

[11] 高芳,崔刚,吴智博,等. 求解背包问题的病毒协同进化粒子群算法[J]. 哈尔滨工业大学学报,2009(6):103-107.

[12] Zhou Y,Chen X,Zhou G.An improved monkey algorithm for a 0-1 knapsack problem[J].Applied Soft Computing,2016,38:817-830.

[13] Yang X S.Metaheuristic optimization:algorithm analysis and open problems[C]//International Conference on Experimental Algorithms,2011:21-32.

[14] Wu S,Manber U,Myers G.A subquadratic algorithm for approximate limited expression matching[J].Algorithmica,1996,15(1):50-67.

[15] 贺毅朝,宋建民,张敬敏,等. 利用遗传算法求解静态与动态背包问题的研究[J]. 计算机应用研究,2015,32(4):1011-1015.

[16] Karaboga D.An idea based on honey bee swarm for numerical optimization,technical report TR06[R].Kayseri:Computer Engineering Department,Engineering Faculty,Erciyes University,2005.

猜你喜欢

二进制背包复杂度
用二进制解一道高中数学联赛数论题
有趣的进度
大山里的“背包书记”
二进制在竞赛题中的应用
一种低复杂度的惯性/GNSS矢量深组合方法
一包装天下 精嘉Alta锐达Sky51D背包体验
求图上广探树的时间复杂度
鼓鼓的背包
某雷达导51 头中心控制软件圈复杂度分析与改进
二进制宽带毫米波合成器设计与分析