基于差分演化策略的混沌烏鴉算法求解折扣{0- 1}背包問題

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

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

0 引言

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

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

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

1 D{0- 1}KP

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

2 烏鴉算法

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

(5)

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

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

(6)

下面給出CSA的算法描述。

算法1 CSA。

初始化參數：最大迭代次數MITER，飛行長度fl，感知概率AP，種群大小N，問題維度n。

生成初始種群P(0)；

計算適應度值f(P(0))；

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

Whileiter

Fori=1toN

烏鴉i隨機選擇烏鴉j跟蹤

Ifrj≥APj,iter

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

Else

xi,iter+1←任意位置

Endif

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

評價烏鴉i的新位置的適應度值

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

End for

End while

此時M中的最好位置即為問題的最優解。由于MITER、N是關于n的線性函數，故CSA的時間復雜度為O(n3)。

3 求解D{0- 1}KP的改進烏鴉算法

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

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

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

(7)

映射方式如下：

步驟1 隨機產生一個n維向量X0={x0,x1,…,xn-1}，作為第一只烏鴉。

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

由此，初始化步驟完成。

3.2 混合編碼方式

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

(8)

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

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

3.3 差分演化策略

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

(9)

其中，Bestiter為當前迭代的最優值。烏鴉i每次向著最優的個體移動，提高收斂速度。

3.4 貪心修復與優化策略

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

算法2 GROS。

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

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

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

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

圖1 DECCSA流程

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

4 仿真實驗與分析

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

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

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

圖2是在20種組合情況下獨立運行CSA 30次求解UDKP5、WDKP5、SDKP5和IDKP5時所求最好值箱線圖。

圖2 20種組合下CSA求解4個實例的性能比較

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

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

圖3 20種組合下DECCSA求解4個實例的性能比較

4.2 計算結果比較與分析

實驗參數設置如下：CSA求解4類D{0- 1}KP實例時，N=50，MITER=3 000，求解UDKP時，AP=0.4，fl=2；求解WDKP時，AP=0.3，fl=2；求解SDKP時，AP=0.2，fl=3；求解IDKP時，AP=0.3，fl=2。DECCSA求解4類D{0- 1}KP實例時，設置AP=0.1，fl=2.0，N=50，MITER=3 000。不同算法求解各個實例的結果如表2～5所示，其中DPDKP為由動態規劃法所求最優解[7],FirEGA算法求解4類實例的數據來自文獻[10]，FirBFO算法求解4類實例的數據來自文獻[11]，MDBBA算法求解4類實例的數據來自文獻[12]。

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

表2 6種算法求解UDKP實例的結果比較

圖4對CSA和DECCSA求解UDKP類實例時的最好值近似比和平均值近似比進行了比較。

圖4 CSA與DECCSA求解UDKP類實例時的近似比對比

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

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

圖5 DECCSA與另三種算法求解UDKP類實例時的近似比對比

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

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

表3 6種算法求解WDKP實例的結果比較

圖6對CSA和DECCSA求解WDKP類實例時的最好值近似比和平均值近似比進行了比較。

圖6 CSA與DECCSA求解WDKP類實例時的近似比對比

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

圖7 DECCSA與另三種算法求解WDKP類實例時的近似比對比

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

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

表4 6種算法求解SDKP實例的結果比較

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

圖8 CSA與DECCSA求解SDKP類實例時的近似比對比

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

圖9 DECCSA與另三種算法求解SDKP類實例時的近似比對比

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

表5 6種算法求解IDKP實例的結果比較

圖10 CSA與DECCSA求解IDKP類實例時的近似比對比

綜上，對于UDKP類問題，DECCSA與其他算法在求解效果上不相上下；對于WDKP、SDKP和IDKP類問題，DECCSA求解效果明顯比其他算法的更優。之所以產生這樣的結果，一方面是因為CSA的求解速度快且易于擴充，另一方面是它與DE的結合做到了優勢互補，因此體現出了極佳的求解性能。

圖11 DECCSA與另三種算法求解IDKP類實例時的近似比對比

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

圖12 CSA和DECCSA在4個實例上的收斂速度對比

基于上述計算、比較和分析得出以下結論：

對于項的價值系數和重量系數均在大范圍內隨機取值的4類大規模D{0- 1}KP實例，DECCSA能夠快速求得一個近似比接近于1的近似解，是適于求解大規模難D{0- 1}KP的有效且實用的進化算法。另外，求解UDKP實例時，DECCSA和FirEGA、MDBBA的求解性能相當，10個實例各有優劣，FirBFO性能稍差。求解WDKP、SDKP、IDKP三類實例時，DECCSA比FirEGA、FirBFO、MDBBA三算法的求解性能好，從而說明混沌策略和差分演化策略能有效地改進CSA，能夠求得D{0- 1}KP的較滿意解或最優解。

5 結語

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

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

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}背包問題的研究[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.)

[10] 劉雪靜,賀毅朝,吳聰聰,等.基于細菌覓食算法求解折扣{0- 1}背包問題的研究[J/OL].計算機工程與應用,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}背包問題[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.)

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

[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.