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

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

0　引言

0-1背包問題(0-1 Knapsack Problem, 0-1 KP)[1]是計算機科學(xué)中典型的優(yōu)化難題，已應(yīng)用于很多領(lǐng)域，如資源分配、項目組合、整數(shù)規(guī)劃等。多維背包問題(MultiDimensional Knapsack Problem, MDKP)[2]、二次背包問題(Quadratic Knapsack Problem， QKP)[3]、多重二次背包問題(Quadratic Multiple Knapsack Problem, QMKP)[4]、折扣0-1背包問題(Discount {0-1} Knapsack Problem, D{0-1}KP)[5]都是0-1 KP的擴展形式。其中，D{0-1}KP源于商業(yè)領(lǐng)域的打折思想，是新型的0-1KP，目前D{0-1}KP的研究成果相對較少。

2007年,Guldan[5]首先提出了D{0-1}KP，并利用動態(tài)規(guī)劃法求解；Rong等[6]將D{0-1}KP的核(Core)問題與動態(tài)規(guī)劃法相結(jié)合求解D{0-1}KP；賀毅朝等[7]利用精英遺傳算法求解D{0-1}KP，首先利用演化算法求解D{0-1}KP，得到近似比接近1的近似解；He等[8]提出利用精確和近似算法求解D{0-1}KP，提出了求解該問題的精確算法、近似算法和利用二進制粒子群算法求解的有效方法；劉雪靜等[9]提出利用細菌覓食算法求解D{0-1}KP，并給出了兩種D{0-1}KP數(shù)學(xué)模型的求解算法；吳聰聰?shù)萚10]提出利用變異蝙蝠算法求解D{0-1}KP，能得到較好的最優(yōu)解；Zhu等[11]利用差分演化求解D{0-1}KP，給出了求解該問題的三個高效離散演化算法。目前，D{0-1}KP是{0-1}KP的一個熱點問題，如何利用啟發(fā)式算法快速求解D{0-1}KP是一個非常值得研究的問題。

針對D{0-1}KP的第二數(shù)學(xué)模型的編碼和優(yōu)化問題，本文利用改進的烏鴉算法(Crow Search Algorithm，CSA)[12]進行求解。首先介紹D{0-1}KP的第二數(shù)學(xué)模型，并利用混合編碼方式解決其整數(shù)編碼問題；其次采用新的貪心修復(fù)與優(yōu)化算法(New greedy Repair and Optimization Algorithm, NROA)處理潛在解；然后，對CSA進行改進，分別引入差分策略和Lévy飛行策略，進一步提高算法的收斂速度和求解精度。實驗表明：改進的烏鴉算法非常適于求解D{0-1}KP，其效果優(yōu)于文獻[7]中的Second Genetic Algorithm with Elitist reservation strategy(SecEGA)算法和文獻[9]中的Second Bacterial Foraging Optimization(SecBFO)算法。

1　D{0-1}KP問題

定義1[5]給定n個項集，且每一個項集中均含3項，項集i(0≤i≤n-1)中的3項為3i、3i+1和3i+2；項3i的價值系數(shù)為p3i，重量系數(shù)為w3i；項3i+1的價值系數(shù)為p3i+1，重量系數(shù)為w3i+1；項3i+2的價值系數(shù)為p3i+2，且p3i+2為p3i和p3i+1的和，重量系數(shù)為w3i+2，且w3i+2分別大于w3i和w3i+1，并小于w3i和w3i+1的和；每一項集中至多有一項可以被裝入背包中。D{0-1}KP為如何選擇裝入背包的項，使得裝入背包的所有項的價值系數(shù)之和達到最大且其重量系數(shù)之和不超過背包載重C。

文獻[5]給出了D{0-1}KP的第一數(shù)學(xué)模型，本文研究如何基于D{0-1}KP的第二數(shù)學(xué)模型[7]進行有效求解。首先給出該模型的描述如下：

(1)

(2)

xi∈{0,1,2,3};i=0,1,…,n-1

(3)

其中:「x?表示向上取整；xi(0≤i≤n-1)的值表示項集i裝入背包的項，xi=0表示沒有項裝入背包，xi=1表示項3i被裝入背包，xi=2表示項3i+1被裝入背包，xi=3表示項3i+2被裝入背包。任意向量X=[x0,x1,…,xn-1]∈{0,1,2,3}n僅表示D{0-1}KP的一個潛在解，滿足約束條件(2)和(3)的X才是D{0-1}KP的一個可行解。

2　烏鴉算法

烏鴉算法[12]是模擬烏鴉搜索食物的行為的新型演化算法。自然界中的烏鴉有如下行為：烏鴉以群居的形式生活,烏鴉能記住它們藏匿食物的最佳位置,烏鴉能跟蹤其他烏鴉以竊取對方的食物,烏鴉能以一定的概率保護自己的食物以防被竊取。

Xi,iter+1=

(4)

其中:ri、rj是 [0,1]內(nèi)服從均勻分布的隨機數(shù)。

當(dāng)烏鴉i的位置發(fā)生改變，則以式(5)的方式更新記憶值。

(5)

CSA的算法描述如下：

算法1CSA。

輸入?yún)?shù)N,n,itermax,AP，fl；

輸出最優(yōu)解Mbest及其目標(biāo)函數(shù)值f(Mbest)。

1)

InitializeNcrows in thendimension search space randomly

2)

Calculate the fitness(Xi) (i=1,2,…,N)

3)

InitializeMof each crow

4)

whileiter

5)

fori←1 toN

6)

Choose a crow randomly(for examplej)

7)

ifrj≥APj,iter

8)

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

9)

else

10)

Xi,iter+1←a random position

11)

endif

12)

Evaluate the new position of the crows

13)

UpdateMi

14)

endfor

15)

endwhile

16)

return(Mbest，f(Mbest))

當(dāng)達到最大迭代次數(shù)itermax時，所有烏鴉的Mi(i=1,2,…,N)中的最好位置即為最優(yōu)化問題的解。步驟1)～3)的時間復(fù)雜度為O(Nn)，步驟4)～15)的時間復(fù)雜度為itermax*O(Nn)，由于itermax、N是關(guān)于n的線性函數(shù)，故CSA的時間復(fù)雜度為O(n3)。

在CSA中，僅有AP和fl兩個可調(diào)節(jié)參數(shù)，是一個參數(shù)較少的簡單的算法，在參數(shù)設(shè)置方面具有一定的優(yōu)勢。在CSA中，集約化和多元化主要受到參數(shù)AP的控制。降低AP的值，CSA傾向于局部搜索，因此，較小的AP值增強了集約化。相反，增加AP的值，CSA趨向全局搜索，故較大的AP值增強了多元化。

3　改進的CSA求解D{0-1}KP

本章主要介紹求解D{0-1}KP時CSA用到的幾種策略及其對應(yīng)的算法。

3.1　混合編碼方式

基本CSA用來求解連續(xù)空間的優(yōu)化問題，而D{0-1}KP是離散域的問題，本文利用混合編碼方式[13]實現(xiàn)CSA對離散空間問題的求解。所用的編碼轉(zhuǎn)換方法如式(6)所示：

(6)

其中:k∈{1,2,3};xi∈(-4,4)，yi∈{0,1,2,3}，i=0,1,…,n-1。

由此，烏鴉個體用混合編碼(X,Y)表示，其中，X為n維實型向量，Y為n維整型向量，由此以(-4,4)n為輔助搜索空間，以{0,1,2,3}n為解空間，解決了D{0-1}KP的編碼問題。

3.2　新的貪心修復(fù)與優(yōu)化算法

由于任意整數(shù)向量X=[x0,x1,…,xn-1]∈{0,1,2,3}n僅僅是D{0-1}KP的潛在解，可能是非正常編碼個體，因此利用文獻[7]中提出的處理非正常編碼的算法NROA對X進行修復(fù)并優(yōu)化。假定原始編碼個體X=[x0,x1,…,xn-1]∈{0,1,2,3}n，Y=[y0,y1,…,yn-1]∈{0,1,2,3}n為修正后個體，數(shù)組H[0,1,…,3n-1]中存放按價值系數(shù)密度pj/wj(0≤j≤3n-1)降序排序后各項所對應(yīng)的下標(biāo)，價值系數(shù)集P、重量系數(shù)集W和背包容量C定義同前，則NROA的偽代碼描述如下。

算法2NROA。

輸入個體X=[x0,x1,…,xn-1]和數(shù)組H[0,1,…,3n-1]；

輸出修復(fù)與優(yōu)化后的個體Y=[y0,y1,…,yn-1]及其適應(yīng)度f(Y)。

1)

w=0,v=0

2)

fori=0 to 3n-1

3)

k=?H[i]/3」,m=H[i]mod 3

4)

if((xk==m+1)&&(w+wH[i]≤C))

5)

w=w+wH[i],yk=m+1,v=v+pH[i]

6)

endif

7)

if((xk==m+1)&&(w+wH[i]>C))

8)

yk=0

9)

endif

10)

endfor

11)

fori=0 to 3n-1

12)

k=?H[i]/3」,m=H[i]mod 3

13)

if((xk==0)&&(w+wH[i]<=C))

14)

w=w+wH[i],yk=m+1,v=v+pH[i]

15)

endif

16)

endfor

17)

return(Y，f(Y))

算法2中步驟2)～ 10)將非正常編碼個體X修復(fù)為正常編碼個體并存于Y中，其時間復(fù)雜度為O(n)；步驟11)～16)對Y作進一步的優(yōu)化處理，其時間復(fù)雜度為O(n)，因此算法NROA的時間復(fù)雜度為O(n)。

3.3　基于Lévy飛行的CSA

為了避免CSA中的烏鴉個體過早地陷入局部極值，在算法中引入Lévy飛行[14-15]。Lévy 飛行是服從Lévy 分布的隨機搜索路徑，是一種短距離的搜索與偶爾較長距離的行走相間的行走方式。經(jīng)Reynolds[14]研究發(fā)現(xiàn)，對于個體相互獨立的種群，當(dāng)解在解空間中稀疏且隨機分布時，Lévy 飛行是一種非常理想的搜索策略，能增加種群多樣性、擴大搜索范圍，有助于跳出局部最優(yōu)。

在CSA中，執(zhí)行完跟蹤操作的烏鴉個體按照一定概率(本文為0.5)進行Lévy飛行。Lévy 飛行的位置更新公式如下：

(7)

由此，基于Lévy 飛行的CSA(Crow Search Algorithm based on Lévy flight, LCSA)求解D{0-1}KP的算法如下。

算法3LCSA。

輸入?yún)?shù)N,n,itermax,AP，fl,a；

輸出最優(yōu)解Mbest及其目標(biāo)函數(shù)值f(Mbest)。

1)

InitializeNcrows in thendimension search space randomly

2)

Calculate the fitness of crows

3)

InitializeMi(i=1,2,…,N)

4)

H[0,1,…,3n-1]←QuickSort(pi/wi)

5)

whileiter

6)

fori=1 toN

7)

Select cowjrandomly and track according to formula (4)

8)

ifrand()>0.5

9)

Crowido Lévy flight

10)

endif

11)

RepairXiusing NROA and calculatefitness(Xi)

12)

UpdateMi

13)

endfor

14)

endwhile

15)

return(Mbest，f(Mbest))

在算法3中，利用QuickSort(pi/wi)按價值系數(shù)密度對各項進行快排序，并把下標(biāo)放入數(shù)組H中。在LCSA中，Lévy飛行的時間復(fù)雜度為O(n)，算法QuickSort的時間復(fù)雜度為O(nlogn)，生成初始種群的時間復(fù)雜度為O(nN)，NROA的時間復(fù)雜度為O(n)。由于N和itermax是關(guān)于n的線性函數(shù)，因此算法3的時間復(fù)雜度為O(nlogn)+O(nN)+O(n)+itermax*(N*(O(n)+O(n)+O(n))=O(n3)。

3.4　基于差分的CSA求解D{0-1}KP

在CSA中，烏鴉i隨機選擇一只烏鴉j進行跟蹤，以式(4)的方式向烏鴉j的Mj,iter位置移動。但是烏鴉j的Mj,iter值不一定好，可能導(dǎo)致算法收斂較慢，因此，在算法中引入差分策略改進烏鴉的跟蹤方式。差分演化(Differential Evolution, DE)算法中變異算子的一般形式為DE/x/y/z[16]，其中：x代表被擾動的基向量；y代表使用的差分向量的個數(shù)；z代表交叉的類型，Bin代表二項式交叉，Exp代表指數(shù)交叉。由于在CSA的跟蹤過程中僅涉及烏鴉i和烏鴉j兩個個體，故本文僅對DE/best/1/Bin和DE/best/1/Exp這兩種變異算子形式進行實驗來決定采用哪種形式的跟蹤方式，實驗結(jié)果見4.2節(jié)?；诓罘值腃SA(Crow Search Algorithm based on Differential Evolution, DECSA)描述如下。

算法4DECSA。

輸入?yún)?shù)N,n,itermax,AP，fl,Cr；

輸出最優(yōu)解Mbest及其目標(biāo)函數(shù)值f(Mbest)。

1)

Initialize crowsXi(i=1,2,…,N) randomly

2)

Calculate thefitness(Xi) (i=1,2,…,N)

3)

Initialize the Memory of each crow

4)

H[0,1,…,3n-1] ← QuickSort(pi/wi)

5)

whileiter

6)

fori=1 toN

7)

Select cowjrandomly

8)

ifrj≥APj,iter

9)

Apply difference strategy to calulateXi,iter+1

10)

else

11)

Xi,iter+1←a random position

12)

endif

13)

RepairXiusing NROA and calculatefitness(Xi)

14)

Update Memory of crowi

15)

endfor

16)

endwhile

17)

return(Mbest，f(Mbest))

算法4中，交叉概率Cr=0.5。易知，算法的時間復(fù)雜度O(nN)+O(nlogn)+O(n)+itermax*(N*(O(n)+O(n)+O(n))=O(n3)，即DECSA是一個復(fù)雜度為多項式時間的進化算法。

3.5　基于Lévy 飛行的DECSA求解D{0-1}KP

求解D{0-1}KP時，把Lévy飛行和差分策略都與CSA相結(jié)合，得到基于Lévy飛行的差分烏鴉搜索算法(Differential Crow Search Algorithm based on Lévy flight， LDECSA)，描述如下。

算法5LDECSA。

輸入?yún)?shù)N,n,itermax,AP，fl,a,Cr；

輸出最優(yōu)解Mbest及其目標(biāo)函數(shù)值f(Mbest)。

1)

Initialize crowsXi(i=1,2,…,N) randomly

2)

Calculate the fitness(Xi) (i=1,2,…,N)

3)

Initialize the Memory of each crow

4)

H[0,1,…,3n-1]←QuickSort(pi/wi)

5)

whileiter

6)

fori=1 toN

7)

Select a cowjrandomly

8)

ifrj≥APj,iter

9)

Apply difference strategy to calculateXi,iter+1

10)

else

11)

Xi,iter+1←a random position

12)

endif

13)

if rand()>0.5

14)

Crowido Lévy flight

15)

endif

16)

RepairXiusing NROA and calculatefitness(Xi)

17)

Update Memory of crowi

18)

endfor

19)

endwhile

20)

return(Mbest，f(Mbest))

易知，算法5的時間復(fù)雜度為O(nN)+O(nlogn)+O(n)+itermax*(N*(O(n)+O(n)+O(n)+O(n)))=O(n3)，因此LDECSA也是一個復(fù)雜度為多項式時間的進化算法。

4　仿真實驗與分析

本文實驗所用計算機的硬件配置為Intel Core i3- 4005u CPU- 1.70 GHz，4 GB 內(nèi)存(3.75 GB 可用)，操作系統(tǒng)為Windows 7(64位)，C語言編程，Matlab繪圖。

計算所使用的四類大規(guī)模實例[7]為不相關(guān)實例(Uncorrelated instances of D{0-1}KP, UDKP)、弱相關(guān)實例(Weakly correlated instances of D{0-1}KP, WDKP)、強相關(guān)實例(Strongly correlated instances of D{0-1}KP, SDKP)和逆向強相關(guān)實例(Inversestrongly correlated instances of D{0-1}KP, IDKP)，每一類實例包含10個實例，實例規(guī)模3n∈{300,600,900,…,3 000}，實例的具體數(shù)據(jù)請參考文獻[7]。

首先，不同算法在不同參數(shù)fl和AP下獨立運行若干實例30次，分析其計算結(jié)果所對應(yīng)的箱線圖確定fl和AP的合理取值；然后通過實驗確定采用的差分算子形式；最后利用四類D{0-1}KP 實例的計算結(jié)果比較 SecEGA[7]、SecBFO[9]、CSA、DECSA、LCSA和LDECSA的求解性能。

4.1　確定AP和fl的值

在實驗中，fl∈{1.0,2.0,3.0,4.0,5.0}，AP∈{0.1,0.2,0.3,0.4} ，因此(fl，AP)共20種不同的組合，所有組合的ID值見表1。下面對每一組(fl，AP)進行實驗以確定fl和AP的合理取值。限于篇幅，針對每一種組合形式，僅給出CSA和LCSA兩種算法在規(guī)模為3n=900的實例UDKP3、WDKP3、SDKP3和IDKP3的計算結(jié)果及其所對應(yīng)的箱線圖。

表1　(fl，AP)及其IDTab. 1　(fl，AP) and its ID

圖1是(fl，AP)在20種組合情況下獨立運行CSA 30次求解UDKP3、WDKP3、SDKP3和IDKP3四個實例的最好值比較。由圖1(a)可知，求解UDKP3實例，ID=9時所求最優(yōu)值和平均值都最好；由圖1(b)可知，求解WDKP3實例，ID=16時所求最優(yōu)值最好，但ID=15時平均值最好；由圖1(c)可知，求解SDKP3實例，ID=1時所求最優(yōu)值最好，ID=6時所求平均值最好；由圖1(d)可知，求解IDKP3實例，ID=10時所求最優(yōu)值最好，ID=8時所求平均值最好。本文采用的是取得平均值最好的組合。DECSA和CSA采用相同的參數(shù)。

圖2是(fl，AP)在20種組合情況下獨立運行LCSA 30次求解UDKP3、WDKP3、SDKP3和IDKP3四個實例的最好值比較。由圖2可知，求解四個實例時，很多組合所求的最優(yōu)值相同，在此，選取ID=3即AP=0.1，fl=3的組合形式。LDECSA和LCSA采用相同的參數(shù)。

圖1　CSA求解四個實例的性能比較Fig. 1　Performance comparison of CSA for solving 4 instances

圖2　LCSA求解四個實例的性能比較Fig. 2　Performance comparison of LCSA for solving 4 instances

4.2　差分策略的選擇

差分算子為DE/best/1/Bin或DE/best/1/Exp，記DE/best/1/Bin的ID為1，DE/best/1/Exp的ID為2。下面分別對兩種差分算子進行實驗，以確定合理的差分算子。限于篇幅，僅給出DECSA和LDECSA在規(guī)模為3n=900的實例UDKP3、WDKP3、SDKP3和IDKP3獨立運行30次的計算結(jié)果及其所對應(yīng)的箱線圖。由圖3、4可以看出，DECSA和LDECSA都是ID為1時的差分算子能獲得更好的最優(yōu)解，故均采用DE/best/1/Bin形式的差分算子。

圖3　DECSA在兩種差分算子下的求解實例比較Fig. 3　Comparative results of DECSA with two differential operators

圖4　LDECSA在兩種差分算子下求解實例比較Fig. 4　Comparative results of LDECSA with two differential operators

4.3　仿真實驗結(jié)果

求解四類D{0-1}KP實例時，設(shè)置參數(shù)N=40，itermax=500。其中，CSA和DECSA求解UDKP類實例時，AP=0.2，fl=4；求解WDKP類實例時，AP=0.3，fl=5；求解SDKP類實例時，AP=0.2，fl=1；求解IDKP類實例時，AP=0.2，fl=3。LCSA和LDECSA求解四類D{0-1}KP實例時，AP=0.1，fl=3.0；DECSA和LDECSA中差分算子為DE/best/1/Bin，交叉概率Cr=0.5。結(jié)果見表2～5，其中動態(tài)規(guī)劃法求解D{0-1}KP(Dynamic programming based algorithms for the discounted {0-1} Knapsack Problem, DPDKP)的數(shù)據(jù)來自文獻[6]，SecEGA算法的計算結(jié)果來自文獻[7]，SecBFO算法的計算結(jié)果來自文獻[9]，CSA、DECSA、LCSA和LDECSA的計算結(jié)果均為算法獨立運行30次所得。

由表2的數(shù)據(jù)分析得到圖5，Opt/Best和Opt/Mean分別得到最好值近似比和平均值近似比[7]。圖5(a)為求解UDKP類實例時6種算法的最好近似比值比較圖，其中CSA和DECSA的求解性能最差，SecEGA的求解性能較差，這三個算法的最優(yōu)近似比值在1.1～1.25；SecBFO、LCSA和LDECSA的求解性能較前三者要好，LDECSA最好，LCSA比LDECSA稍差，比SecBFO稍好，這三個算法的近似比值在1.0～1.025。圖5(b)為求解UDKP類實例時6種算法的平均近似比值比較圖，與圖5(a)相比，CSA和DECSA基本重合，其他算法變化不大。

由圖5還可以看出，差分策略在解質(zhì)量不高的情況下，效果并不好，在解質(zhì)量較高的情況下，能提高最優(yōu)解的質(zhì)量。在圖5(b)中，應(yīng)用了差分策略的DECSA比CSA也僅僅在UDKP2和UDKP3上效果好一點，其余實例不如CSA或兩個算法求解性能相當(dāng)；而LCSA本身能獲得較好的最優(yōu)解，應(yīng)用了差分策略后，LDECSA所獲得的最優(yōu)解進一步得到優(yōu)化，但優(yōu)化能力有限，故LDECSA的性能比LCSA好，但差別不大。

由表3的數(shù)據(jù)分析得到圖6。圖6(a)為求解WDKP類實例時6種算法的最好值近似比比較圖，其中CSA和DECSA的求解性能最差，且隨著問題規(guī)模的增大，近似比值增大，說明求解質(zhì)量下降；LDECSA、LCSA、SecEGA和SecBFO四種算法近似比值都在1.0～1.01，且LDECSA最優(yōu)，最優(yōu)近似比值幾乎為1，LCSA次之，SecEGA和SecBFO稍差。圖6(b)為求解WDKP類實例時6種算法的平均近似比值比較圖，與圖6(a)相比，CSA和DECSA幾乎重合，求解性能仍然是最差，SecEGA平均性能下降，明顯不如SecBFO、LCSA和LDECSA，LDECSA的平均求解性能最優(yōu)。

表2　求解UDKP實例的結(jié)果比較Tab. 2　Results comparison for solving UDKP instances

圖5　求解UDKP類實例的近似比比較Fig. 5　Comparison of approximate ratio for solving UDKP instances

由表4的數(shù)據(jù)分析得到圖7。圖7(a)為求解SDKP實例時6種算法的最好值近似比比較圖，其中CSA和DECSA的求解性能最差，且隨著問題規(guī)模的增大，近似比值逐漸增大，LDECSA近似比值最小，接近1，LCSA比LDECSA略差，SecEGA和SecBFO比LCSA稍差，且在大部分實例上兩種算法求解能力相當(dāng)，僅在求解SDKP4和SDKP7時，SecEGA不如SecBFO。圖7(b)為求解SDKP實例時6種算法的平均近似比值比較圖，與圖7(a)相比，CSA和DECSA幾乎重合，求解性能仍然是最差，SecEGA平均求解性能下降，明顯不如SecBFO，LDECSA的平均求解性能最優(yōu)。

由表5的數(shù)據(jù)分析得到圖8。圖8(a)為求解IDKP類實例時6種算法的最優(yōu)近似比值比較圖，其中CSA和DECSA的求解性能最差，且隨著問題規(guī)模的增大，近似比值逐漸增大，其余四種算法求解能力相當(dāng)，能求得近似最優(yōu)解或最優(yōu)解。圖8(b)為求解IDKP類實例時6種算法的平均近似比值比較圖，跟圖8(a)相比，CSA和DECSA幾乎重合，求解性能仍然最差，SecEGA變化明顯，求解性能下降，SecBFO僅在求解IDKP2時性能略有下降，LCSA和LDECSA基本重合，由表5也可以看出，兩種算法所得數(shù)據(jù)差別不大，求解性能最優(yōu)。

由圖5～8可以看出， LCSA的求解性能明顯比DECSA要好，LDECSA的求解性能比LCSA要好，因此，在求解四類D{0-1}KP實例時，Lévy飛行能有效地改進CSA，差分策略能輔助Lévy飛行策略取得更令人滿意的近似解或最優(yōu)解。

圖9為LDECSA在求解四類D{0-1}KP實例時最優(yōu)近似比比較的箱線圖。由圖9可以看出，LDECSA在求解IDKP時，性能最佳，近似比值接近1，10個實例基本能得到最優(yōu)解或近似最優(yōu)解；LDECSA在求解WDKP時，性能較好，近似比值稍微大于1，能獲得較滿意解；LDECSA在求解SDKP時，近似比值都在1.005以下；相比較而言，LDECSA求解UDKP時性能較差。這也說明，LDECSA不能同時滿足四類實例都獲得最優(yōu)解或近似最優(yōu)解。

表3　求解WDKP實例的結(jié)果比較Tab. 3　Results comparison for solving WDKP instances

圖6　求解WDKP類實例的近似比比較Fig. 6　Comparison of approximate ratio for solving WDKP instances

表4　求解SDKP實例的結(jié)果比較Tab. 4　Results comparison for solving SDKP instances

圖7　求解SDKP類實例的近似比比較Fig. 7　Comparison of approximate ratio for solving SDKP instances

表5　求解IDKP實例的結(jié)果比較Tab. 5　Results comparison for solving IDKP instances

圖8　求解IDKP類實例的近似比比較Fig. 8　Approximate ratio for solving IDKP instances

為了進一步驗證算法LDECSA的求解性能，取其最好值與基于差分策略的混沌烏鴉算法(Chaotic Crow Search Algorithm based on Differential Evolution strategy，DECCSA)[17]進行比較，DECCSA的計算結(jié)果參照文獻[17]，比較結(jié)果如圖10所示。由圖10(a)可以看出，對UDKP類實例，LDECSA的求解性能更佳，近似比值不大于1.02，DECCSA的近似比值在1.02～1.15；由圖10(b)可知，LDECSA的求解性能更佳，近似比值不大于1.001，DECCSA的近似比值在1.00～1.006；由圖10(c)可知，LDECSA的求解性能更佳，近似比值不大于1.003，DECCSA的近似比值在1.003～1.02；由圖10(d)可知，對于IDKP類實例，算法DECCSA和LDECSA各有優(yōu)劣，近似比值基本等于1，差別不大?？偟膩碚f，算法LDECSA優(yōu)于DECCSA。

綜上所述：對于大規(guī)模的四類 D{0-1}KP 實例，LCSA和LDECSA均能夠快速求得一個近似比接近于1的近似解，且LDECSA的求解性能比LCSA更好，因此LDECSA是適于求解大規(guī)模難D{0-1}KP 的有效且實用的進化算法。

圖9　LDECSA在四類實例上的最好值近似比比較Fig. 9　Best approximate ratio comparison of LDECSA on 4 kinds of instances

圖10　LDECSA和DECCSA的最好值近似比比較Fig. 10　Best approximate ratio comparison of LDECSA and DECCSA

5　結(jié)語

烏鴉搜索算法是一種新穎的模擬烏鴉搜索食物的演化算法，D{0-1}KP 是新型的{0-1}KP，有三種數(shù)學(xué)模型，本文研究的是如何利用改進的烏鴉搜索算法求解第二數(shù)學(xué)模型的D{0-1}KP。在此，烏鴉個體采用整數(shù)向量編碼方式，并采用新的貪心策略修復(fù)和優(yōu)化非正常編碼個體；為了避免CSA中的烏鴉個體過早地陷入局部最優(yōu)，在算法中引入Lévy飛行；為了提高收斂速度，在算法中引入差分策略。仿真實驗表明：對于大規(guī)模的D{0-1}KP 實例，LDECSA能夠快速求得一個近似比接近于 1的近似解，因此非常適合求解大規(guī)模D{0-1}KP。

由于LDECSA在四類實例上的求解性能不盡相同，如何針對UDKP類實例設(shè)計出更有效的算法是下一步的研究內(nèi)容。此外，由于CSA提出的時間較短，該算法的應(yīng)用還很少，如何把CSA應(yīng)用到其他領(lǐng)域中也是一個值得研究的問題。

參考文獻:

[1]FAYARD D, PLATEAU G. Resolution of the 0- 1 knapsack problem: comparison of methods [J]. Mathematical Programming, 1975, 8(1): 272-307.

[2]CHU P C, BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem [J]. Journal of Heuristics, 1998, 4(1): 63-86.

[3]CHEN Y, HAO J-K. An iterated “hyperplane exploration” approach for the quadratic knapsack problem [J]. Computers & Operations Research, 2017, 77: 226-239.

[4]HILEY A, JULSTROM B A. The quadratic multiple knapsack problem and three heuristic approaches to it [C]// GECCO ’06: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2006: 547-552.

[5]GULDAN B. Heuristic and exact algorithms for discounted knapsack problems [D]. Erlangen and Nuremberg, Bavaria, Germany: University of Erlangen-Nürnberg, 2007: 1-78.

[6]RONG A, 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.

[7]賀毅朝,王熙照,李文斌,等.基于遺傳算法求解折扣{0-1}背包問題的研究[J].計算機學(xué)報,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.)

[8]HE Y-C, WANG X-Z, HE Y-L, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem [J]. Information Sciences, 2016, 369: 634-647.

[9]劉雪靜,賀毅朝,吳聰聰,等.基于細菌覓食算法求解折扣{0-1}背包問題的研究[J/OL]. 計算機工程與應(yīng)用 (2017- 02- 16) [2017- 08- 30]. 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- 02- 16) [2017- 08- 18]. http://kns.cnki.net/kcms/detail/11.2127.TP.20170216.1044.038.html.)

[10]吳聰聰,賀毅朝,陳嶷瑛,等.變異蝙蝠算法求解折扣{0-1}背包問題[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.)

[11]ZHU H, HE Y, WANG X, et al. Discrete differential evolutions for the discounted {0-1} knapsack problem [J]. International Journal of Bio-inspired Computation, 2017, 10(4): 219-238.

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

[13]賀毅朝,王熙照,寇應(yīng)展.一種具有混合編碼的二進制差分演化算法[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.)

[14]REYNOLDS A M. Cooperative random Lévy flight searches and the flight patterns of honeybees [J]. Physics Letters A, 2006, 354(5/6): 384-388.

[15]YANG X-S, DEB S. Cuckoo search via Lévy flights [C]// NaBIC 2009: Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway, NJ: IEEE, 2009: 210-214.

[16]NOMAN N, IBA H. Enhancing differential evolution performance with local search for high dimensional function optimization [C]// GECCO ’05: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2005: 967-974.

[17]劉雪靜,賀毅朝,路鳳佳,等.基于差分策略的混沌烏鴉算法求解折扣{0-1}背包問題[J].計算機應(yīng)用，2018，38(1)：137-145. (LIU X J, HE Y C, LU F J, et al, Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem [J]. Journal of Computer Applications, 2018， 38(1)： 137-145.)