求解0-1背包問題的混沌二進制烏鴉算法

劉雪靜，賀毅朝，吳聰聰，李 靚

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.