求解0-1背包问题的混沌二进制乌鸦算法
2018-05-21刘雪静贺毅朝吴聪聪
刘雪静,贺毅朝,吴聪聪,李 靓
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.