基于Lévy飛行的差分烏鴉算法求解折扣{0-1}背包問題

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

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

0　引言

0-1背包問題(0-1 Knapsack Problem, 0-1 KP)[1]是計算機科學中典型的優化難題，已應用于很多領域，如資源分配、項目組合、整數規劃等。多維背包問題(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源于商業領域的打折思想，是新型的0-1KP，目前D{0-1}KP的研究成果相對較少。

2007年,Guldan[5]首先提出了D{0-1}KP，并利用動態規劃法求解；Rong等[6]將D{0-1}KP的核(Core)問題與動態規劃法相結合求解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數學模型的求解算法；吳聰聰等[10]提出利用變異蝙蝠算法求解D{0-1}KP，能得到較好的最優解；Zhu等[11]利用差分演化求解D{0-1}KP，給出了求解該問題的三個高效離散演化算法。目前，D{0-1}KP是{0-1}KP的一個熱點問題，如何利用啟發式算法快速求解D{0-1}KP是一個非常值得研究的問題。

針對D{0-1}KP的第二數學模型的編碼和優化問題，本文利用改進的烏鴉算法(Crow Search Algorithm，CSA)[12]進行求解。首先介紹D{0-1}KP的第二數學模型，并利用混合編碼方式解決其整數編碼問題；其次采用新的貪心修復與優化算法(New greedy Repair and Optimization Algorithm, NROA)處理潛在解；然后，對CSA進行改進，分別引入差分策略和Lévy飛行策略，進一步提高算法的收斂速度和求解精度。實驗表明：改進的烏鴉算法非常適于求解D{0-1}KP，其效果優于文獻[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的價值系數為p3i，重量系數為w3i；項3i+1的價值系數為p3i+1，重量系數為w3i+1；項3i+2的價值系數為p3i+2，且p3i+2為p3i和p3i+1的和，重量系數為w3i+2，且w3i+2分別大于w3i和w3i+1，并小于w3i和w3i+1的和；每一項集中至多有一項可以被裝入背包中。D{0-1}KP為如何選擇裝入背包的項，使得裝入背包的所有項的價值系數之和達到最大且其重量系數之和不超過背包載重C。

文獻[5]給出了D{0-1}KP的第一數學模型，本文研究如何基于D{0-1}KP的第二數學模型[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]內服從均勻分布的隨機數。

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

(5)

CSA的算法描述如下：

算法1CSA。

輸入參數N,n,itermax,AP，fl；

輸出最優解Mbest及其目標函數值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))

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

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

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

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

3.1　混合編碼方式

基本CSA用來求解連續空間的優化問題，而D{0-1}KP是離散域的問題，本文利用混合編碼方式[13]實現CSA對離散空間問題的求解。所用的編碼轉換方法如式(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　新的貪心修復與優化算法

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

算法2NROA。

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

輸出修復與優化后的個體Y=[y0,y1,…,yn-1]及其適應度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修復為正常編碼個體并存于Y中，其時間復雜度為O(n)；步驟11)～16)對Y作進一步的優化處理，其時間復雜度為O(n)，因此算法NROA的時間復雜度為O(n)。

3.3　基于Lévy飛行的CSA

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

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

(7)

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

算法3LCSA。

輸入參數N,n,itermax,AP，fl,a；

輸出最優解Mbest及其目標函數值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)按價值系數密度對各項進行快排序，并把下標放入數組H中。在LCSA中，Lévy飛行的時間復雜度為O(n)，算法QuickSort的時間復雜度為O(nlogn)，生成初始種群的時間復雜度為O(nN)，NROA的時間復雜度為O(n)。由于N和itermax是關于n的線性函數，因此算法3的時間復雜度為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值不一定好，可能導致算法收斂較慢，因此，在算法中引入差分策略改進烏鴉的跟蹤方式。差分演化(Differential Evolution, DE)算法中變異算子的一般形式為DE/x/y/z[16]，其中：x代表被擾動的基向量；y代表使用的差分向量的個數；z代表交叉的類型，Bin代表二項式交叉，Exp代表指數交叉。由于在CSA的跟蹤過程中僅涉及烏鴉i和烏鴉j兩個個體，故本文僅對DE/best/1/Bin和DE/best/1/Exp這兩種變異算子形式進行實驗來決定采用哪種形式的跟蹤方式，實驗結果見4.2節。基于差分的CSA(Crow Search Algorithm based on Differential Evolution, DECSA)描述如下。

算法4DECSA。

輸入參數N,n,itermax,AP，fl,Cr；

輸出最優解Mbest及其目標函數值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。易知，算法的時間復雜度O(nN)+O(nlogn)+O(n)+itermax*(N*(O(n)+O(n)+O(n))=O(n3)，即DECSA是一個復雜度為多項式時間的進化算法。

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

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

算法5LDECSA。

輸入參數N,n,itermax,AP，fl,a,Cr；

輸出最優解Mbest及其目標函數值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的時間復雜度為O(nN)+O(nlogn)+O(n)+itermax*(N*(O(n)+O(n)+O(n)+O(n)))=O(n3)，因此LDECSA也是一個復雜度為多項式時間的進化算法。

4　仿真實驗與分析

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

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

首先，不同算法在不同參數fl和AP下獨立運行若干實例30次，分析其計算結果所對應的箱線圖確定fl和AP的合理取值；然后通過實驗確定采用的差分算子形式；最后利用四類D{0-1}KP 實例的計算結果比較 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兩種算法在規模為3n=900的實例UDKP3、WDKP3、SDKP3和IDKP3的計算結果及其所對應的箱線圖。

表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時所求最優值和平均值都最好；由圖1(b)可知，求解WDKP3實例，ID=16時所求最優值最好，但ID=15時平均值最好；由圖1(c)可知，求解SDKP3實例，ID=1時所求最優值最好，ID=6時所求平均值最好；由圖1(d)可知，求解IDKP3實例，ID=10時所求最優值最好，ID=8時所求平均值最好。本文采用的是取得平均值最好的組合。DECSA和CSA采用相同的參數。

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

圖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在規模為3n=900的實例UDKP3、WDKP3、SDKP3和IDKP3獨立運行30次的計算結果及其所對應的箱線圖。由圖3、4可以看出，DECSA和LDECSA都是ID為1時的差分算子能獲得更好的最優解，故均采用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　仿真實驗結果

求解四類D{0-1}KP實例時，設置參數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。結果見表2～5，其中動態規劃法求解D{0-1}KP(Dynamic programming based algorithms for the discounted {0-1} Knapsack Problem, DPDKP)的數據來自文獻[6]，SecEGA算法的計算結果來自文獻[7]，SecBFO算法的計算結果來自文獻[9]，CSA、DECSA、LCSA和LDECSA的計算結果均為算法獨立運行30次所得。

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

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

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

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

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

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

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

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

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

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

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

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

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

表5　求解IDKP實例的結果比較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的計算結果參照文獻[17]，比較結果如圖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各有優劣，近似比值基本等于1，差別不大。總的來說，算法LDECSA優于DECCSA。

綜上所述：對于大規模的四類 D{0-1}KP 實例，LCSA和LDECSA均能夠快速求得一個近似比接近于1的近似解，且LDECSA的求解性能比LCSA更好，因此LDECSA是適于求解大規模難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　結語

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

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

參考文獻:

[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].計算機學報,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]. 計算機工程與應用 (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].計算機應用,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]賀毅朝,王熙照,寇應展.一種具有混合編碼的二進制差分演化算法[J].計算機研究與發展,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].計算機應用，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.)