劉雪靜，賀毅朝，路鳳佳，吳聰聰，才秀鳳

(河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊 050031)(*通信作者電子郵箱lxjpass@163.com)

0 引言

背包問(wèn)題(Knapsack Problem, KP)[1]是一類(lèi)經(jīng)典的組合優(yōu)化問(wèn)題，在投資決策、貨物裝載、整數(shù)規(guī)劃等領(lǐng)域有著非常重要的理論和應(yīng)用價(jià)值。KP包含許多不同的形式，如0- 1背包問(wèn)題(0- 1KP)[2]、多維背包問(wèn)題(MultiDimensional Knapsack Problem, MDKP)[3-4]、多選擇多維背包問(wèn)題 (Multiple-Choice Multidimensional Knapsack Problem, MMKP)[5]、最大最小背包問(wèn)題(Max-min Knapsack Problem, MmKP)[6]和折扣0- 1背包問(wèn)題(Discounted {0- 1} Knapsack Problem, D{0- 1}KP)[7-8]等。

D{0- 1}KP是Guldan[7]于2007年提出的一個(gè)新穎KP，首先研究了利用動(dòng)態(tài)規(guī)劃法對(duì)其進(jìn)行求解；Rong等[8]對(duì)D{0- 1}KP的核(Core)問(wèn)題進(jìn)行了研究，將其與動(dòng)態(tài)規(guī)劃法相結(jié)合求解D{0- 1}KP。賀毅朝等[9]利用杰出者保留策略遺傳算法(Genetic Algorithm with Elitist reservation strategy, EGA)求解D{0- 1}KP，提出了基于兩個(gè)不同數(shù)學(xué)模型的算法——FirEGA(First EGA)和SecEGA(Second EGA)，兩種算法均能得到一個(gè)近似比接近于1的近似解；劉雪靜等[10]利用細(xì)菌覓食(Bacterial Foraging Optimization, BFO)算法求解D{0- 1}KP，在兩個(gè)不同數(shù)學(xué)模型下提出的算法FirBFO(First BFO)和SecBFO(Second BFO)，能夠得到更好的近似解；吳聰聰?shù)萚11]利用變異蝙蝠算法(Mutated Double Binary Bat Algorithm, MDBBA)求解D{0- 1}KP，該算法在大部分實(shí)例上優(yōu)于算法FirEGA。由于D{0- 1}KP的提出時(shí)間較晚，基于演化算法求解的相關(guān)研究成果相對(duì)較少，雖然利用EGA、BFO和MDBBA已經(jīng)提出了求解D{0- 1}KP的不同方法，但是還存在許多有待改進(jìn)的方面，例如如何提高初始解的多樣性、如何提高算法的求解速度等問(wèn)題，因此如何利用演化算法更好、更快地求解D{0- 1}KP是一個(gè)值得研究的問(wèn)題。

為了利用新型演化算法——烏鴉算法(Crow Search Algorithm， CSA)[12]高效求解D{0- 1}KP，基于D{0- 1}KP的第一數(shù)學(xué)模型，本文基于多種有效策略與CSA相融合提出了求解D{0- 1}KP的一種新的高效方法。在新方法中，首先針對(duì)初始解隨機(jī)產(chǎn)生時(shí)存在分布不均的缺陷，提出采用混沌映射優(yōu)化初始解的方法；其次，利用混合編碼方式得到D{0- 1}KP的潛在解，并通過(guò)GROS對(duì)潛在解進(jìn)行修復(fù)和優(yōu)化處理，以獲得一個(gè)質(zhì)量更優(yōu)的可行解；第三，在算法中引入差分演化策略來(lái)提高算法的全局尋優(yōu)能力和收斂速度。對(duì)4類(lèi)大規(guī)模實(shí)例的計(jì)算結(jié)果表明：DECCSA能快速求得近似比接近1的滿意解，優(yōu)于FirEGA、FirBFO和MDBBA這3種算法。

1 D{0- 1}KP

定義[7]給定n個(gè)項(xiàng)集，且任一項(xiàng)集i(0≤i≤n-1)中均含3項(xiàng)，分別為3i、3i+1和3i+2，其對(duì)應(yīng)的價(jià)值系數(shù)為p3i、p3i+1和p3i+2，重量系數(shù)為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)表示項(xiàng)i是否被裝入背包，xi=1即項(xiàng)i裝入背包，xi=0即項(xiàng)i未裝入背包。顯然，任意的二進(jìn)制向量X=[x0,x1,…,x3n-1]∈{0,1}3n僅是D{0- 1}KP的一個(gè)潛在解，只有同時(shí)滿足約束條件式(2)、(3)和(4)的二進(jìn)制向量X才是D{0- 1}KP的一個(gè)可行解。

2 烏鴉算法

烏鴉算法是一種新穎的元啟發(fā)算法，在網(wǎng)絡(luò)優(yōu)化分配[13]、醫(yī)學(xué)等領(lǐng)域有較少的研究成果。CSA模擬自然界中烏鴉的智能行為。烏鴉是群居生活的鳥(niǎo)類(lèi)，它們非常聰明，能將自己多余的食物藏匿起來(lái)，藏匿位置稱(chēng)為記憶值(Memory，M)，并在需要時(shí)取出；當(dāng)前能跟蹤其他烏鴉，竊取其他烏鴉的食物，而被跟蹤的烏鴉能以一定的感知概率(Awareness Probability， AP)保護(hù)自己的食物防止被竊。假定N只烏鴉分布在n維搜索空間中，Xi,iter表示第i只烏鴉在第iter次迭代時(shí)的位置，Xi,iter+1的結(jié)果如式(5)所示：

(5)

其中：ri、rj是[0,1]區(qū)間服從均勻分布的隨機(jī)數(shù)；Mj,iter為烏鴉j、迭代次數(shù)iter時(shí)的記憶值；APj,iter為烏鴉j的感知概率；fli,iter為烏鴉i在第iter迭代時(shí)的飛行長(zhǎng)度。

當(dāng)烏鴉的位置發(fā)生了改變，式(6)給出了M的更新方式：

(6)

下面給出CSA的算法描述。

算法1 CSA。

初始化參數(shù)：最大迭代次數(shù)MITER，飛行長(zhǎng)度f(wàn)l，感知概率AP，種群大小N，問(wèn)題維度n。

生成初始種群P(0)；

計(jì)算適應(yīng)度值f(P(0))；

初始化烏鴉的記憶值M0=P(0)；

Whileiter

Fori=1toN

烏鴉i隨機(jī)選擇烏鴉j跟蹤

Ifrj≥APj,iter

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

Else

xi,iter+1←任意位置

Endif

檢查新位置的可行性。如果烏鴉i的新位置是可行的，則更新；否則，烏鴉i停留在當(dāng)前位置

評(píng)價(jià)烏鴉i的新位置的適應(yīng)度值

以式(6)的方式更新記憶值

End for

End while

此時(shí)M中的最好位置即為問(wèn)題的最優(yōu)解。由于MITER、N是關(guān)于n的線性函數(shù)，故CSA的時(shí)間復(fù)雜度為O(n3)。

3 求解D{0- 1}KP的改進(jìn)烏鴉算法

3.1 混沌序列初始化烏鴉位置

CSA采用隨機(jī)方法初始化烏鴉的位置，極有可能造成烏鴉位置分布不均勻。而混沌映射[14]能按照自身的規(guī)律在一定范圍內(nèi)不重復(fù)遍歷所有狀態(tài)，因此利用混沌優(yōu)化方法求解數(shù)值優(yōu)化問(wèn)題時(shí)，混沌軌跡能使搜索過(guò)程避免陷入局部最優(yōu)，能更加有效地實(shí)現(xiàn)對(duì)搜索空間的搜索，從而獲得全局最優(yōu)解或較好的滿意解。本文采用Circle映射初始化烏鴉位置，以增強(qiáng)初始解的多樣性，為進(jìn)一步有效地進(jìn)行全局搜索打下良好的基礎(chǔ)。Circle映射表達(dá)式如下：

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

(7)

映射方式如下：

步驟1 隨機(jī)產(chǎn)生一個(gè)n維向量X0={x0,x1,…,xn-1}，作為第一只烏鴉。

步驟2 將X0中的每一維按式(6)進(jìn)行N-1迭代，生成其余N-1個(gè)烏鴉個(gè)體。

由此，初始化步驟完成。

3.2 混合編碼方式

在CSA中，烏鴉個(gè)體X=[x0,x1,…,xn-1]為實(shí)型向量，fl、AP是實(shí)數(shù)，而0- 1KP是離散域的問(wèn)題，因此本文利用sigmoid函數(shù)將一個(gè)實(shí)型向量轉(zhuǎn)化為一個(gè)二進(jìn)制向量[15]，實(shí)現(xiàn)對(duì)CSA的離散化。編碼轉(zhuǎn)換技術(shù)如式(8)所示：

(8)

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

由此，將種群中的每一個(gè)個(gè)體分別用n維實(shí)型向量X和n維二進(jìn)制向量Y共同表示，記作(X,Y)，稱(chēng)(X,Y)為個(gè)體的混合編碼表示[16]。b為一個(gè)給定的正數(shù)，則以[-b,b]n為輔助搜索空間，以{0,1}n為解空間，實(shí)現(xiàn)對(duì)離散化空間問(wèn)題的求解。

3.3 差分演化策略

在CSA中，烏鴉i隨機(jī)選擇烏鴉j跟蹤，當(dāng)rj>AP時(shí)，烏鴉i以Xi,iter+1=Xi,iter+ri*fli,iter*(Mj,iter-Xi,iter)的方式向?yàn)貘fj的最佳位置移動(dòng)，但是烏鴉j的最佳位置不一定好，故收斂速度可能變慢，由此，引入差分演化策略對(duì)跟蹤方式進(jìn)行改進(jìn)。差分演化的變異算子的一般形式為DE/x/y/z[16]，其中：x是一個(gè)字符串，代表要被擾動(dòng)的基向量；y代表為擾動(dòng)x而使用的差分向量的個(gè)數(shù)；z代表交叉的類(lèi)型(指數(shù)交叉EXP或二項(xiàng)式交叉BIN)。本文采用DE/best/1/BIN的方式，跟蹤公式改進(jìn)如下：

(9)

其中，Bestiter為當(dāng)前迭代的最優(yōu)值。烏鴉i每次向著最優(yōu)的個(gè)體移動(dòng)，提高收斂速度。

3.4 貪心修復(fù)與優(yōu)化策略

由于二元向量Y=[y0,y1,…,yn-1]∈{0,1}3n可能是非正常編碼個(gè)體，因此引入貪心與優(yōu)化策略(Greedy Repair and Optimization Strategy， GROS)[9]把非正常編碼個(gè)體修正為正常編碼個(gè)體并進(jìn)行優(yōu)化。假定原二進(jìn)制個(gè)體為Y=[y0,y1,…,yn-1]∈{0,1}3n，修正后二進(jìn)制個(gè)體為Z=[z0,z1,…,zn-1]∈{0,1}3n，數(shù)組H[0,1,…,3n-1]中存放價(jià)值系數(shù)密度pj/wj(0≤j≤3n-1)的降序排列下標(biāo)序，各項(xiàng)集的狀態(tài)標(biāo)識(shí)F[0,1,…,n-1]∈{0,1}n，F(xiàn)[j]=0表示項(xiàng)集j中沒(méi)有項(xiàng)裝入背包，F(xiàn)[j]=1表示項(xiàng)集j中恰有一項(xiàng)裝入背包，?i/3」表示i/3向下取整。GROS算法描述如下。

算法2 GROS。

輸入：二進(jìn)制個(gè)體Y=[y0,y1,…,yn-1]和數(shù)組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)行的時(shí)間復(fù)雜度為O(n)；第4)～9)行將非正常編碼個(gè)體Y修復(fù)為正常編碼個(gè)體并存于Z中，時(shí)間復(fù)雜度為O(n)；第10)～15)行對(duì)Z作進(jìn)一步優(yōu)化，時(shí)間復(fù)雜度為O(n)。顯然，GROS的時(shí)間復(fù)雜度為O(n)。

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

DECCSA求解D{0- 1}KP流程如圖1所示。其中，QuickSort(pi/wi)為對(duì)價(jià)值系數(shù)密度pi/wi(0≤i≤3n-1)按非遞增進(jìn)行快速排序，B(t)(0≤t

在圖1中，虛線框A部分為采用Circle映射生成的優(yōu)化初始烏鴉種群，虛線框B部分為采用差分演化策略按式(9)生成的烏鴉i在下一次迭代的位置。

圖1 DECCSA流程

在DECCSA中，QuickSort的時(shí)間復(fù)雜度為O(nlogn)，生成初始種群的時(shí)間復(fù)雜度為O(nN)，GROS的時(shí)間復(fù)雜度為O(n)，由于N、MITER是關(guān)于n的線性函數(shù)，故DECCSA的時(shí)間復(fù)雜度為O(nlogn)+O(nN)+O(n)+MITER*(O(nN)+O(n))=O(n3)，因此DECCSA是一個(gè)復(fù)雜度為多項(xiàng)式時(shí)間的進(jìn)化算法。

4 仿真實(shí)驗(yàn)與分析

在本章中，不相關(guān)D{0- 1}KP實(shí)例(Uncorrelated instances of D{0- 1}KP， UDKP)、弱相關(guān)D{0- 1}KP實(shí)例(Weakly correlated instances of D{0- 1}KP， WDKP)、強(qiáng)相關(guān)D{0- 1}KP實(shí)例(Strongly correlated instances of D{0- 1}KP, SDKP)和逆向強(qiáng)相關(guān)D{0- 1}KP實(shí)例(Inversestrongly correlated instances of D{0- 1}KP， IDKP)的生成參照文獻(xiàn)[10]，每一類(lèi)實(shí)例包含10個(gè)不同規(guī)模的實(shí)例。首先利用若干實(shí)例的計(jì)算結(jié)果所對(duì)應(yīng)的箱線圖(Boxplot)分析并確定CSA和DECCSA中感知概率AP和飛行長(zhǎng)度f(wàn)l的合理取值；然后利用對(duì)4類(lèi)大規(guī)模D{0- 1}KP實(shí)例的計(jì)算結(jié)果比較CSA和DECCSA的求解性能。

本文所使用微型計(jì)算機(jī)硬件配置為Intel Core i3- 4005u CPU- 1.70 GHz，4 GB內(nèi)存(3.75 GB可用)，操作系統(tǒng)Microsoft Windows 7，編程語(yǔ)言C語(yǔ)言，編譯環(huán)境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，共構(gòu)成20種不同的組合形式(AP,fl)，表1列出所有組合的ID。下面分別利用4類(lèi)實(shí)例對(duì)AP和fl的每一種組合進(jìn)行計(jì)算，以確定AP和fl的合理取值。限于篇幅，針對(duì)每一種組合形式，僅給出CSA和DECCSA兩種算法在規(guī)模為3n=1 500的實(shí)例UDKP5、WDKP5、SDKP5和IDKP5的計(jì)算結(jié)果及其所對(duì)應(yīng)的箱線圖。

表1 參數(shù)組合形式(AP， fl)及其ID

圖2是在20種組合情況下獨(dú)立運(yùn)行CSA 30次求解UDKP5、WDKP5、SDKP5和IDKP5時(shí)所求最好值箱線圖。

圖2 20種組合下CSA求解4個(gè)實(shí)例的性能比較

從圖2(a)可以看出，求解UDKP5，當(dāng)AP=0.2時(shí)，所求的最優(yōu)值最好，當(dāng)AP=0.4、fl=2時(shí)，中位數(shù)最好。從圖2(b)可以看出，求解WDKP5，當(dāng)AP=0.4時(shí)，所求最好值較好，當(dāng)AP=0.3、fl=2時(shí)，中位數(shù)最好。從圖2(c)可以看出，求解SDKP5，當(dāng)AP=0.1，fl=3或5時(shí)，所求最優(yōu)值最好，當(dāng)AP=0.2，fl=3時(shí)，中位數(shù)最好。從圖2(d)可以看出，求解IDKP5，當(dāng)AP=0.3，fl=1,2,3時(shí)，所求最優(yōu)值最好，當(dāng)AP=0.3，fl=2時(shí)，中位數(shù)最好。由圖2可得，針對(duì)UDKP、WDKP和IDKP類(lèi)實(shí)例，當(dāng)AP取值稍大時(shí)平均求解性能較好，針對(duì)SDKP類(lèi)實(shí)例，當(dāng)AP=0.2時(shí)平均求解性能較好。本文采用的是求得中位數(shù)最好的組合。

圖3是20種組合情況下獨(dú)立運(yùn)行DECCSA 30次求解UDKP5、WDKP5、SDKP5和IDKP5時(shí)所求最好值的箱線圖。由圖3(a)可以看出，AP=0.1，fl=5.0時(shí)所求最好值最優(yōu)，AP=0.1，fl=2.0時(shí)中位數(shù)值最好。在圖3(b)中，30次所求中位數(shù)基本相同，AP=0.1，fl=2.0、0.4和AP=0.3，fl=1.0時(shí)最好值最好。在圖3(c)中，AP=0.1，fl=2.0時(shí)最好值和中位數(shù)值都最好。在圖3(d)中，除AP=0.1，fl=2.0外所有組合所求最好值相同，AP=0.1，fl=2.0時(shí)最優(yōu)。圖2與圖3對(duì)比可以看出，DECCSA所求的最好解相對(duì)較集中，針對(duì)4類(lèi)實(shí)例，AP值相對(duì)較小為好。綜上，DECCSA參數(shù)的最佳設(shè)置應(yīng)為AP=0.1,fl=2.0。

圖3 20種組合下DECCSA求解4個(gè)實(shí)例的性能比較

4.2 計(jì)算結(jié)果比較與分析

實(shí)驗(yàn)參數(shù)設(shè)置如下：CSA求解4類(lèi)D{0- 1}KP實(shí)例時(shí)，N=50，MITER=3 000，求解UDKP時(shí)，AP=0.4，fl=2；求解WDKP時(shí)，AP=0.3，fl=2；求解SDKP時(shí)，AP=0.2，fl=3；求解IDKP時(shí)，AP=0.3，fl=2。DECCSA求解4類(lèi)D{0- 1}KP實(shí)例時(shí)，設(shè)置AP=0.1，fl=2.0，N=50，MITER=3 000。不同算法求解各個(gè)實(shí)例的結(jié)果如表2～5所示，其中DPDKP為由動(dòng)態(tài)規(guī)劃法所求最優(yōu)解[7],FirEGA算法求解4類(lèi)實(shí)例的數(shù)據(jù)來(lái)自文獻(xiàn)[10]，F(xiàn)irBFO算法求解4類(lèi)實(shí)例的數(shù)據(jù)來(lái)自文獻(xiàn)[11]，MDBBA算法求解4類(lèi)實(shí)例的數(shù)據(jù)來(lái)自文獻(xiàn)[12]。

表2給出了UDKP類(lèi)實(shí)例的理論最優(yōu)值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五種算法所求的最好值、最差值和平均值。最優(yōu)值/最好值和最優(yōu)值/最差值分別代表最好值近似比和平均值近似比[17]。

表2 6種算法求解UDKP實(shí)例的結(jié)果比較

圖4對(duì)CSA和DECCSA求解UDKP類(lèi)實(shí)例時(shí)的最好值近似比和平均值近似比進(jìn)行了比較。

圖4 CSA與DECCSA求解UDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

從圖4(a)可以看出，DECCSA的最好值近似比的最大值與CSA的最小值大致相當(dāng)。圖4(b)與圖4(a)區(qū)別不大，但是平均值近似比值相對(duì)有所增大。由圖4可知，DECCSA比CSA更適合求解UDKP類(lèi)實(shí)例。

圖5給出了DECCSA與FirEGA、FirBFO和MDBBA求解UDKP類(lèi)實(shí)例時(shí)的最好值近似比和平均值近似比的比較。

圖5 DECCSA與另三種算法求解UDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

由圖5(a)可以看出DECCSA在求解UDKP1～UDKP4時(shí)比其他算法好，求解UDKP5～UDKP7時(shí)不如FirEGA和MDBBA，求解UDKP8～UDKP10時(shí)與FirEGA和MDBBA能力相當(dāng)。由圖5(b)可看出在求解UDKP1、UDKP2、UDKP4時(shí)，DECCSA明顯比其他算法好，求解UDKP5～UDKP7明顯不如FirEGA和MDBBA，其他實(shí)例DECCSA、FirEGA和MDBBA3種算法能力相當(dāng)。

表3給出了求解WDKP實(shí)例的理論最優(yōu)值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五種算法所求的最好值、最差值和平均值。

表3 6種算法求解WDKP實(shí)例的結(jié)果比較

圖6對(duì)CSA和DECCSA求解WDKP類(lèi)實(shí)例時(shí)的最好值近似比和平均值近似比進(jìn)行了比較。

圖6 CSA與DECCSA求解WDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

由圖6(a)可以看出，DECCSA在求解WDKP實(shí)例時(shí)最好值近似比遠(yuǎn)遠(yuǎn)小于CSA；圖6(b)中兩種算法的平均值近似比有所增大，曲線變化不大，仍然是DECCSA的平均值近似比小于CSA，故DECCSA比CSA更適合求解WDKP類(lèi)實(shí)例。由圖7(a)可以看出求解WDKP1～WDKP3三個(gè)實(shí)例時(shí)DECCSA性能最好，求解其他實(shí)例時(shí)FirBFO、MDBBA和DECCSA的求解能力相當(dāng)，F(xiàn)irEGA最好值近似比最大。

圖7 DECCSA與另三種算法求解WDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

圖7(b)中FirEGA的平均值近似比值當(dāng)實(shí)例規(guī)模增大時(shí)與圖7(a)差異明顯，變得更差，DECCSA的求解性能在WDKP1～WDKP3時(shí)最好，在其余實(shí)例上與FirBFO、MDBBA求解能力相當(dāng)。

表4給出了求解SDKP實(shí)例的理論最優(yōu)值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五種算法所求的最好值、最差值和平均值。

表4 6種算法求解SDKP實(shí)例的結(jié)果比較

圖8給出了CSA與DECCSA求解SDKP實(shí)例時(shí)的最好值近似比與平均值近似比的比較。

圖8 CSA與DECCSA求解SDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

由圖8可以看出DECCSA在求解SDKP類(lèi)實(shí)例時(shí)最好值近似比和平均值近似比都遠(yuǎn)遠(yuǎn)小于CSA，比CSA適合求解SDKP類(lèi)實(shí)例。由圖9(a)可以看出DECCSA在求解SDKP實(shí)例時(shí)比其他算法好，能得到較好的滿意解，且在求解SDKP1～SDKP3三個(gè)實(shí)例時(shí)優(yōu)勢(shì)明顯。從圖9(b)可以看出，平均值近似比也是DECCSA最小，取得的平均值最優(yōu)。

圖9 DECCSA與另三種算法求解SDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

表5給出了求解IDKP實(shí)例的理論最優(yōu)值及FirEGA、FirBFO、MDBBA、CSA和DECCSA五種算法所求的最好值、最差值和平均值。從表5可以看出，求解IDKP實(shí)例時(shí)，CSA的求解性能最差，DECCCSA在IDKP1、IDKP2和IDKP4實(shí)例上能取得理論最優(yōu)值。由圖10(a)和圖10(b)可以看出，DECCSA在求解IDKP類(lèi)實(shí)例時(shí)最好值近似比和平均值近似比基本都為1，優(yōu)于CSA，非常適合求解IDKP類(lèi)實(shí)例。由圖11(a)可以看出DECCSA和MDBBA、FirBFO的最優(yōu)近似比基本等于1，F(xiàn)irEGA稍差。圖11(b)與圖11(a)區(qū)別不大，平均值近似比DECCSA、FirBFO、MDBBA相差依然不大，基本等于1，F(xiàn)irEGA稍差。

表5 6種算法求解IDKP實(shí)例的結(jié)果比較

圖10 CSA與DECCSA求解IDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

綜上，對(duì)于UDKP類(lèi)問(wèn)題，DECCSA與其他算法在求解效果上不相上下；對(duì)于WDKP、SDKP和IDKP類(lèi)問(wèn)題，DECCSA求解效果明顯比其他算法的更優(yōu)。之所以產(chǎn)生這樣的結(jié)果，一方面是因?yàn)镃SA的求解速度快且易于擴(kuò)充，另一方面是它與DE的結(jié)合做到了優(yōu)勢(shì)互補(bǔ)，因此體現(xiàn)出了極佳的求解性能。

圖11 DECCSA與另三種算法求解IDKP類(lèi)實(shí)例時(shí)的近似比對(duì)比

圖12顯示了CSA和DECCSA求解UDKP3、WDKP3、SDKP3和IDKP3四個(gè)實(shí)例時(shí)的收斂速度，每個(gè)實(shí)例獨(dú)立運(yùn)行30次，明顯可以看出DECCSA比CSA求解性能更優(yōu)。從圖12(a)可以看出，求解UDKP3時(shí)，DECCSA在前100代收斂速度較快，后面收斂速度緩慢，CSA也是前100代收斂速度稍快，后面較慢，且迭代次數(shù)對(duì)最好值影響不大。從圖12(b)～(d)可以看出，DECCSA求解WDKP3、SDKP3和IDKP3三個(gè)實(shí)例時(shí)，混沌策略非常有效，能得到較好的初始解，收斂曲線平緩，而CSA依然是處于緩慢收斂的狀態(tài)。

圖12 CSA和DECCSA在4個(gè)實(shí)例上的收斂速度對(duì)比

基于上述計(jì)算、比較和分析得出以下結(jié)論：

對(duì)于項(xiàng)的價(jià)值系數(shù)和重量系數(shù)均在大范圍內(nèi)隨機(jī)取值的4類(lèi)大規(guī)模D{0- 1}KP實(shí)例，DECCSA能夠快速求得一個(gè)近似比接近于1的近似解，是適于求解大規(guī)模難D{0- 1}KP的有效且實(shí)用的進(jìn)化算法。另外，求解UDKP實(shí)例時(shí)，DECCSA和FirEGA、MDBBA的求解性能相當(dāng)，10個(gè)實(shí)例各有優(yōu)劣，F(xiàn)irBFO性能稍差。求解WDKP、SDKP、IDKP三類(lèi)實(shí)例時(shí)，DECCSA比FirEGA、FirBFO、MDBBA三算法的求解性能好，從而說(shuō)明混沌策略和差分演化策略能有效地改進(jìn)CSA，能夠求得D{0- 1}KP的較滿意解或最優(yōu)解。

5 結(jié)語(yǔ)

本文研究了如何利用烏鴉算法求解D{0- 1}KP，提出了針對(duì)初始解隨機(jī)產(chǎn)生的缺點(diǎn)采用混沌策略初始化個(gè)體和引入差分演化策略改進(jìn)烏鴉跟蹤方式的差分混沌烏鴉算法求解D{0- 1}KP。仿真實(shí)驗(yàn)表明：對(duì)于大規(guī)模的D{0- 1}KP實(shí)例，DECCSA不受實(shí)例中各項(xiàng)的價(jià)值系數(shù)、重量系數(shù)和背包載重的大小影響，能夠快速求得一個(gè)近似比接近于1的近似解，因此它是一個(gè)求解大規(guī)模難實(shí)例的實(shí)用進(jìn)化算法。

在利用DECCSA求解D{0- 1}KP時(shí)，UDKP類(lèi)實(shí)例的計(jì)算結(jié)果較其他三類(lèi)的略差，因此進(jìn)一步分析DECCSA的特點(diǎn)，使之對(duì)于UDKP類(lèi)實(shí)例也能獲得更佳的結(jié)果是需要今后研究的問(wèn)題。此外，能否基于D{0- 1}KP的第二、三數(shù)學(xué)模型[9]設(shè)計(jì)更加高效的進(jìn)化算法也是一個(gè)值得今后探討的問(wèn)題。

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}背包問(wèn)題的研究[J].計(jì)算機(jī)學(xué)報(bào),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] 劉雪靜,賀毅朝,吳聰聰,等.基于細(xì)菌覓食算法求解折扣{0- 1}背包問(wèn)題的研究[J/OL].計(jì)算機(jī)工程與應(yīng)用,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}背包問(wèn)題[J].計(jì)算機(jī)應(yīng)用,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] 賀毅朝,王熙照,寇應(yīng)展.一種具有混合編碼的二進(jìn)制差分演化算法[J].計(jì)算機(jī)研究與發(fā)展,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.