吳聰聰，趙建立，2，劉雪靜，陳嶷瑛

WU Congcong1,ZHAO Jianli1，2,LIU Xuejing1,CHEN Yiying1

1.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊 050031

2.全北國立大學(xué) 電子信息工程學(xué)院，韓國 全州 54896

1.College of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China

2.School of Electronics&Information Engineering,ChonBuk National University,Jeonju 54896,Republic of Korea

1 引言

多維背包問題（The Multidimensional Knapsack Problem，MKP）是運(yùn)籌學(xué)中一個典型的組合優(yōu)化問題，廣泛地應(yīng)用于資源分配[1]、車輛裝載[2]、經(jīng)濟(jì)[3]等領(lǐng)域。MKP問題是將n個物品放入背包中，每個物品i有一個非負(fù)價值 pi，并且占用m個維度的資源wi,1,wi,2,…,wi,m；背包也有m個維度，并且每個維度有一個資源的限制Cj，j={1,2,…,m}。要求選擇若干物品裝入背包，使得物品在每個維度不超過背包限制的前提下裝入物品的價值和最大。用數(shù)學(xué)公式表示如公式（1）～（3）所示：

目前，解決MKP問題的方法主要分為兩大類：一類是精確算法，一般用分支定界法[4-5]和動態(tài)規(guī)劃法[6-7]；一類是用啟發(fā)式算法[8-14]。由于精確算法在求解大規(guī)模數(shù)據(jù)時耗費(fèi)的時間和空間開銷都很大，所以不適合求解較大規(guī)模的MKP問題[9-10]，而啟發(fā)式算法求解速度快，求解精度也能滿足實際要求。最早使用啟發(fā)式算法求解MKP問題的是文獻(xiàn)[8]，他們使用GA算法求解MKP問題，證明了在適度的計算量的基礎(chǔ)上可以得到較好的解。近年來涌現(xiàn)出很多求解MKP問題的啟發(fā)式算法：基于PSO算法的求解法[11-12]、分布估計法[9]、改進(jìn)的二進(jìn)制果蠅算法[13]、人工魚群[14]、二進(jìn)制微分搜索法[10]等等。

求解精度和運(yùn)算速度是求解MKP問題關(guān)注的核心，差分演化算法是一種優(yōu)秀的全局優(yōu)化的啟發(fā)式算法，第一屆國際演化計算（ICEO）競賽中，差分演化算法被證明是速度最快的進(jìn)化算法。但采用差分演化算法解決多維背包問題[15]的研究開展得卻很少。本文提出了一種改進(jìn)的二進(jìn)制差分演化算法（Modified Binary Differential Evolution，MBDE）求解MKP問題，首先，設(shè)計了二進(jìn)制差分演化算法（Binary Differential Evolution，BDE）的編碼形式，使得差分演化算法能夠解決離散問題；為提高算法的探索能力，加入了自適應(yīng)反向測試搜索策略；另外，在此基礎(chǔ)上，設(shè)計了一種精英局部搜索策略來提高求解精度和收斂速度；最后，為修復(fù)不可行解和優(yōu)化可行解，采用一種更準(zhǔn)確衡量物品有效價值的價值密度方法，并提出了貪心裝載策略。為驗證本文算法的有效性，進(jìn)行了三組實驗，和其他幾種啟發(fā)式算法進(jìn)行比較，實驗結(jié)果顯示，本文提出的算法求解精度更高，從算法運(yùn)行時間上看，MBDE算法求解速度非?？?，適合求解大規(guī)模MKP問題。

2 二進(jìn)制差分演化算法

差分演化算法[16-17]是眾所周知的一種優(yōu)秀的進(jìn)化計算技術(shù)[18]，因其有效性使差分演化算法被廣泛地應(yīng)用于各個領(lǐng)域[19-23]。原差分演化算法主要用于解決連續(xù)函數(shù)的優(yōu)化問題，要求解MKP問題，首先要解決算法的離散化問題，即編碼問題。

2.1 編碼設(shè)置和二進(jìn)制差分算子的實現(xiàn)

在求解MKP的BDE算法中，種群中每個個體X=[x1,x2,…,xn]代表一個MKP的解，用一個n位二進(jìn)制位串表示，每一位為0或1。受文獻(xiàn)[13]和文獻(xiàn)[24]的啟發(fā)，在BDE算法中，每個個體X的每一個二進(jìn)制位xi對應(yīng)一個實數(shù) p(xi)表示xi為1的可能性，每個個體X根據(jù)其對應(yīng)的概率向量P(X)=[p(x1),p(x2),…,p(xn)]來確定，映射公式如公式（4）。

BDE算法和標(biāo)準(zhǔn)差分演化算法[16-17]一樣主要包括變異、交叉、選擇三個步驟，在BDE中，種群的變異操作由個體概率向量P(X)引導(dǎo)進(jìn)行，變異公式如公式（5）。

其中P(Xk1),P(Xk2),P(Xk3)是三個和當(dāng)前個體不同的另外三個個體對應(yīng)的概率向量，F(xiàn)是取值范圍在[0，1]之間的縮放比例因子。P(T)是變異產(chǎn)生的臨時個體對應(yīng)的概率向量，根據(jù)公式（4）將P(T)的值轉(zhuǎn)換成中間臨時個體T=[t1,t2,…,tn]。

在種群的交叉操作中，BDE算法對種群個體和其對應(yīng)的概率向量同時處理，處理方法如程序片段1所示。差分算法中的交叉一般有兩種形式：指數(shù)交叉和二項交叉。這里采用了類似于標(biāo)準(zhǔn)的DE算法[16]中的二項式交叉：首先對每一個變量都生成一個均勻分布在0到1之間的隨機(jī)數(shù)rnd，如果rnd小于交叉因子Cr，則保留當(dāng)前個體的原對應(yīng)分量，否則接受臨時個體的對應(yīng)分量。

程序片段1

在選擇算子中，BDE和標(biāo)準(zhǔn)的DE算法一樣采用貪心選擇方式，對于新臨時個體T和當(dāng)前個體X選擇較好的個體進(jìn)入下一代。

其中 fvalue是求個體適應(yīng)度的函數(shù)，即公式（1）。

2.2 二進(jìn)制差分演化算法流程

根據(jù)上面的說明，下面給出二進(jìn)制差分演化算法的執(zhí)行流程，如算法1。

算法1BDE算法

步驟1隨機(jī)產(chǎn)生N個概率向量P(Xi)=[p(xi,1),p(xi,2),…,p(xi,n)]，i=1,2,…,N ，p(xi,j)∈[0,1)，根據(jù)公式（4）產(chǎn)生N個二進(jìn)制個體Xi=[xi,1,xi,2,…,xi,n]，i=1,2,…,N，計算每個個體的適應(yīng)度值。

步驟2對于種群中每個個體Xi和個體對應(yīng)的概率向量P(Xi)：

（1）隨機(jī)選擇另外三個個體的概率向量根據(jù)公式（5）執(zhí)行變異操作，再通過公式（4）生成臨時個體Ti=[ti,1,ti,2,…,ti,n]。

（2）將臨時個體Ti與當(dāng)前個體按“程序段1”進(jìn)行交叉操作。

（3）將交叉后的Ti與當(dāng)前個體 Xi比較，選擇較好的個體進(jìn)入下一代。

步驟3如果終止條件滿足，輸出最優(yōu)個體，否則返回步驟2。

從二進(jìn)制差分演化算法的流程可以看出，和標(biāo)準(zhǔn)差分演化算法[16]一樣，它具有記憶個體最優(yōu)解和種群內(nèi)信息共享的特點，通過保優(yōu)貪婪策略保證了算法的收斂能力。在時間復(fù)雜度上，因為只是平行地增加了從實數(shù)向量（概率向量）向二進(jìn)制向量的轉(zhuǎn)換，所以和標(biāo)準(zhǔn)的差分演化算法的時間復(fù)雜度一樣。如令算法的最大迭代次數(shù)為M，種群數(shù)為N，個體維度為n，則BDE算法時間復(fù)雜度為O(NMn)，是多項式時間的算法。

3 改進(jìn)的二進(jìn)制差分演化算法（MBDE）求解MKP問題

3.1 可行解的生成和優(yōu)化

無論是初始化得到的隨機(jī)個體，還是進(jìn)化過程中得到的新個體，都會出現(xiàn)不滿足約束條件的情況，通常稱之為不可行解，對不可行解的修復(fù)是求解MKP問題的關(guān)鍵。目前有兩種常用的方法對不可行解修復(fù)：一種是采用基于偽效用比率的修改機(jī)制[8]，其核心操作是代理對偶方法[25]。由于該修復(fù)方法需要先求得MKP對偶問題的最優(yōu)解，加大了算法的計算量，降低了算法的效率[13]。另一種對不可行解修復(fù)的方法是依賴MKP問題本身的結(jié)構(gòu)[8，13，26]確定物品偽使用率。這兩種修復(fù)策略修復(fù)不可行解的過程都分為兩步：第一步是按照某種次序?qū)⑽锲窂谋嘲心贸?，直到各維均不再超重，即得到了可行解；第二步是將沒在背包中的物品依次試著裝入背包，裝入的過程中背包各維不能超重，如果超重就不裝入。這兩種方法一個共同的特點就是先要按照個體信息將物品裝入背包，然后再調(diào)整（卸載+再裝入），這種開始不考慮背包限制，而后再修正的方式，增加了計算的工作量。本文借鑒文獻(xiàn)[27]中的GROA算法，基于MKP問題結(jié)構(gòu)的特點，提出一種新的修復(fù)和優(yōu)化方法——貪心裝載法GLM（Greedy Load Method）。該方法在針對每個個體計算適應(yīng)度值時使用，不用反復(fù)進(jìn)行將物品裝入和卸載的過程。下面詳細(xì)介紹具體操作。

在MBDE算法中，對需要計算適應(yīng)度值的每個個體進(jìn)行GLM，即在計算個體的適應(yīng)度值時，按照個體中的信息和物品的價值密度（也可以將價值密度看成偽使用率）將物品裝入背包。價值密度是指單位重量的物品價值，對于多維背包，物品在多個維度相當(dāng)于有多個重量，應(yīng)該如何計算價值密度是值得分析的問題，選擇一種能體現(xiàn)物品本身放入背包的性價比的價值密度會使GLM更有效。比較了幾種價值密度設(shè)置方法后，本文采用物品價值與物品在背包各維度占重量比率和之比作為價值密度，如公式（7）所示。這不僅考慮了物品各個維度所占資源對價值密度的影響，同時加入了每個維度上物品與背包限制的關(guān)系影響，能更準(zhǔn)確地體現(xiàn)物品的價值密度。

首先對物品按照價值密度從大到小排序，將排序后的物品序號寫入vsort數(shù)組中。然后根據(jù)vsort中的序號順序和差分算法中個體本身的信息將物品放入背包，前提是各個維度均不超出背包的限制。具體過程如算法2所示。vsort[i]表示價值密度排在第i位的物品的編號。X=[x1,x2,…,xn]是要計算適應(yīng)度值的個體，B=[b1,b2,…,bn]是經(jīng)過修復(fù)和優(yōu)化后的個體，value是經(jīng)過GLM計算的適應(yīng)度值。

算法2GLM

整個修復(fù)過程可以看成兩個階段：第一個階段是將個體選中的物品（該位為1）按價值密度由大到小的次序嘗試裝入背包；第二個階段是將個體中沒有選中的物品（該位為0）按價值密度由大到小的次序嘗試裝入背包，最后，得到修正和優(yōu)化后的個體B。這種修復(fù)方法不但起到對不可行解修復(fù)的作用，同時對可行解有優(yōu)化作用，并且不重復(fù)物品的裝入過程，減小了計算量，從而提升了MBDE算法求解MKP問題的速度。從GLM算法的偽代碼可以看出，第一階段和第二階段的時間復(fù)雜度都為O(nm)，所以GLM算法時間復(fù)雜度為O(nm)。其中n是物品數(shù)，m是背包的維度。一般用nm表示MKP問題的規(guī)模，所以GLM算法的時間復(fù)雜度和MKP的問題規(guī)模是線性關(guān)系。實驗證明，此修復(fù)優(yōu)化策略對大規(guī)模的MKP問題的求解產(chǎn)生了重要作用。

3.2 反向測試搜索

Tizhoosh[28]提出了反向?qū)W習(xí)（Opposition-based Learning，OBL）的概念，并認(rèn)為智能搜索的最根本任務(wù)就是不斷地學(xué)習(xí)、優(yōu)化和搜索。反向?qū)W習(xí)的目的是擴(kuò)大估計范圍（同時評價當(dāng)前解和反向解）從而得到更優(yōu)秀的近似解。反向?qū)W習(xí)能夠有效提高種群的多樣性，對算法跳出局部極值有很大幫助。Rahnamayan等[29]將反向?qū)W習(xí)引入到差分演化算法中，主要用于種群初始化和子代產(chǎn)生中，提高了算法的收斂速度和求解精度。本文針對MKP問題，采用的反向?qū)W習(xí)策略與原OBL的方式有所不同，反向點的設(shè)置，主要針對個體的概率向量進(jìn)行。二進(jìn)制個體向量隨之改變，具體定義如下：

定義1（反向點[28]）

設(shè)是d維搜索空間中的可行解，，那么它的反向點（反向解）

定義2（反向個體）

設(shè)Xi=[xi,1,xi,2,…,xi,n]是求解MKP問題的二進(jìn)制個體，P(Xi)=[p(xi,1),p(xi,2),…,p(xi,n)]是其對應(yīng)的概率向量，首先 ，求得個體Xi的反向概率向量，反向概率向量的各項可由公式（9）得到。之后，根據(jù)反向概率向量和公式（4）求得反向個體。然后利用 GLM 算法得到反向個體的適應(yīng)度，如果該適應(yīng)度大于原個體則由反向個體替換原個體，否則原個體不變。

公式（9）中，θ∈[0,1]是符合均勻分布的隨機(jī)數(shù)。

3.3 精英局部搜索

群體中的精英個體和全局最優(yōu)解之間的親和度要大于群體中其他個體和全局最優(yōu)解之間的親和度，并且與精英個體有較大親和度的個體也應(yīng)有較高的適應(yīng)度[30]。因此，精英個體對種群的進(jìn)化起著重要的推動作用，充分利用精英個體的特征信息是保證算法性能的關(guān)鍵[31]。在精英個體周圍展開精細(xì)搜索，可以加快算法尋優(yōu)的速度和提高解的質(zhì)量，增強(qiáng)MBDE的開發(fā)能力。

本文采用的精英局部搜索策略是：每次迭代后，隨機(jī)選擇全局最優(yōu)個體的k位，使該位上的0，1互換，然后計算這個臨時個體的適應(yīng)度，如果其優(yōu)于原最優(yōu)個體，則由局部搜索得到的臨時個體替代原最優(yōu)個體。k值的選擇表示著搜索區(qū)域離最優(yōu)個體的遠(yuǎn)近，k值越大，表示距離越遠(yuǎn)。經(jīng)過反復(fù)測試，本文選取k值為3，效果最好。因為是以精英個體為基礎(chǔ)，這種看似簡單的局部搜索，用很小的工作量卻能達(dá)到很好的效果。

3.4 求解MKP問題的MBDE算法流程

通過以上幾節(jié)的闡述，可以綜合得到求解MKP問題的改進(jìn)的差分演化算法。下面用“(Xi,f(Xi))←GLM(Xi)”表示對個體Xi使用GLS算法修復(fù)和優(yōu)化并得到目標(biāo)函數(shù)值（也是適應(yīng)度）f(Xi)；用“vsort[1…n]←QuickSort({d(v1),d(v2),…,d(vn)})”表示n個物品按照價值密度d(vi)，i=1,2,…,n，由大到小排序后將物品下標(biāo)依次存入數(shù)組vsort[1…n]中；則MBDE算法求解MKP問題的流程描述如算法3所示。

算法3MBDE求解MKP

步驟1初始化

（1）隨機(jī)產(chǎn)生 N個概率向量 P(Xi)=[p(xi,1),p(xi,2),…,p(xi,n)]，i=1,2,…,N ，p(xi,j)∈[0,1)，根據(jù)公式（4）生成N個二進(jìn)制個體Xi=[xi,1,xi,2,…,xi,n]，i=1,2,…,N ，(Xi,f(Xi))←GLM(Xi),i=1,2,…,N 。

步驟2變異和交叉

對于種群中每個個體Xi和個體對應(yīng)的概率向量P(Xi),i=1,2,…,N：

（1）隨機(jī)選擇另外三個個體，將三個個體對應(yīng)的概率向量根據(jù)公式（5）執(zhí)行變異操作，再通過公式（4）生成臨時個體Ti={ti,1,ti,2,…,ti,n}。

（2）將臨時個體Ti與當(dāng)前個體按“程序段1”進(jìn)行交叉操作。

步驟3反向測試搜索

對于種群中每個個體Xi和個體對應(yīng)的概率向量P(Xi),i=1,2,…,N ：

（1）按公式（9）和公式（4）求得反向個體對應(yīng)的概率向量和反向個體。

步驟4精英局部搜索

（1）Xbest=種群最優(yōu)個體。

（2）隨機(jī)選擇的Xbest的3位進(jìn)行0，1互換得臨時個體 Xtemp，(Xtemp,f(Xtemp))←GLM(Xtemp)。

步驟5如果達(dá)到最大迭代次數(shù)，則RETURN(Xbest)，否則返回步驟2。

在MBDE算法中，步驟1是初始化工作，生成初始群體并使用貪心裝載法GLM計算個體適應(yīng)度，使用快速排序方法對物品按價值密度排序，總的時間復(fù)雜度為O(Nn+Nnm+nlbn)；步驟2是二進(jìn)制差分演化算法的交叉、變異和選擇操作，時間復(fù)雜度為O(Nn+Nnm)；步驟3是對個體進(jìn)行反向搜索，時間復(fù)雜度為O(Nn+Nnm)；步驟4是在精英個體周圍進(jìn)行局部搜索，時間復(fù)雜度為O(nm)；故MBDE算法的時間復(fù)雜度為O(Nn+Nnm+nlbn)+M×(2O(Nn+Nnm)+O(nm))。這里N為種群規(guī)模，M為最大迭代次數(shù)。

4 仿真實驗

為測試算法MBDE的性能，本文使用世界上廣泛使用的 Benchmark數(shù)據(jù)集（http：//www.cs.nott.ac.uk/～psxjd2/mkp/index.html），第1個數(shù)據(jù)集包括5個混合規(guī)模測試實例，第2個數(shù)據(jù)集包括30個中等規(guī)模測試實例，背包數(shù)量為5，物品數(shù)為30～90；第3個數(shù)據(jù)集包括11個大規(guī)模實例，物品數(shù)量從100到2 500。所有這些實驗采用C++編碼，每個實例獨(dú)立運(yùn)行50次，計算平臺為：Intel Core?i7（主頻 2.6 GHz），4 GB RAM，Microsoft Windows 10。

4.1 參數(shù)的選擇

任何啟發(fā)式算法都有兩個重要的參數(shù)：種群規(guī)模和最大迭代次數(shù)，雖然較大的種群規(guī)模和迭代次數(shù)可以獲得更好的解，但會增加時間消耗，所以選擇種群規(guī)模為30，最大迭代次數(shù)為2 000次。在MBDE算法中另外兩個參數(shù)是縮放因子F和交叉因子Cr，為每個參數(shù)設(shè)置了5個可能的值。使用一個中等規(guī)模的實例sento2（背包數(shù)目30個，物品數(shù)60個）用口田實驗法[32]對參數(shù)進(jìn)行測試選擇。表1給出了測試的正交矩陣L25（52），avg是每個參數(shù)組合獨(dú)立運(yùn)行程序100次求得的平均值。

表1 正交矩陣和MBDE的平均運(yùn)行結(jié)果

根據(jù)正交表（表1）得到參數(shù)選擇實驗的極差分析表（表2）和參數(shù)水平對實驗結(jié)果的影響趨勢圖（圖1，圖2），從表2和圖1中可以看出，參數(shù)Cr的影響比F大，主要體現(xiàn)在當(dāng)Cr取第5種值時（即Cr=1.0）算法取得的平均值非常低。也就是說在算法的交叉過程中，沒有一位來自新產(chǎn)生的臨時個體而全部來自原個體的情況下，算法效果最差。Cr取其他值而得到的結(jié)果基本相當(dāng)，但很明顯在取第4種(Cr=0.8)時算法達(dá)到最好。所以在后面的實驗中參數(shù)設(shè)置為：F=1.0，Cr=0.8。

表2MBDE參數(shù)選擇極差分析表

圖1 MBDE參數(shù)F各取值對結(jié)果的影響趨勢

圖2 MBDE參數(shù)Cr各取值對結(jié)果的影響趨勢

4.2 實驗結(jié)果統(tǒng)計與比較

表3～表5展示了算法對3組實例進(jìn)行測試的結(jié)果，為比較算法MBDE的性能，在表3～表5中與近期發(fā)表的其他啟發(fā)式算法的求解結(jié)果進(jìn)行比較，在各表中problem列是實例的名稱；n×m列是實例的規(guī)模，其中n是物品數(shù)，m是背包的維度；Opt列是實例的目前已知最優(yōu)值；SR列是成功率；Mean列是平均值，Std列是標(biāo)準(zhǔn)差，ACT列是平均執(zhí)行時間。各表中其他啟發(fā)式算法的實驗數(shù)據(jù)分別來自文獻(xiàn)[9-10，13，15]。

表3 MBDE算法與SD-BDE算法求解MKP問題比較

表4 MBDE求解數(shù)據(jù)集2實驗結(jié)果及比較

表5 MBDE求解數(shù)據(jù)集3實驗結(jié)果及比較

首先，基于測試集1測試算法MBDE的性能，并與文獻(xiàn)[15]中的隨機(jī)擴(kuò)散二進(jìn)制差分算法（SD-BDE）進(jìn)行比較，對每個實例，獨(dú)立運(yùn)行50次，統(tǒng)計成功率和平均值，SD-BDE的實驗數(shù)據(jù)來自文獻(xiàn)[15]。

從表3中可以明顯看出，MBDE對各個實例的求解成功率和平均值均遠(yuǎn)遠(yuǎn)高于SD-BDE算法，其中有三個實例成功率達(dá)到1，其他兩個實例的成功率也都在0.80以上，說明MBDE有很好的魯棒性。

表4是算法對中等規(guī)模測試數(shù)據(jù)集2的30實例的測試結(jié)果和與文獻(xiàn)[10]中隨機(jī)二進(jìn)制微分算法（TRBDS）和精英二進(jìn)制微分算法（TE-BDS）進(jìn)行比較的情況。MBDE算法有26實例求解成功率為1，TR-BDS算法有10個實例成功率為1，TE-BDS只有3個實例成功率達(dá)到1。說明MBDE對中等規(guī)模的數(shù)據(jù)求解能力非常強(qiáng)。從求解的方差看，MBDE除實例6的方差略高于TR-BDS算法外，其他實例求解的方差均低于TE-BDS和TR-BDS，說明算法MBDE有很好的穩(wěn)定性。從ACT上分析，除了在實例weish06和weish26上的平均執(zhí)行時間為1秒多，算法在每個實例上的平均執(zhí)行時間都不超過1秒，說明MBDE的求解效率非常高。

為進(jìn)一步考察MBDE的性能，表5是MBDE求解大規(guī)模MKP問題測試集3的實驗結(jié)果，通過平均偏差（Ave.Dev）來對算法MBDE與文獻(xiàn)[10]的TR-BDS與TE-BDS，文獻(xiàn)[9]的HEDA2和文獻(xiàn)[13]的FOA2進(jìn)行比較。平均值偏差是指每個實例獨(dú)立運(yùn)行若干次，求得最優(yōu)值的平均值與已知最優(yōu)值的偏差的百分比（平均偏差=（已知最優(yōu)值-平均值）/100），所以平均偏差越小說明算法的求解性能越好。從幾個算法的平均偏差看，MBDE算法在11個大規(guī)模實例中均都低于其他4種算法，MBDE性能最好。為了進(jìn)一步分析算法MBDE的穩(wěn)定性和效率，這里求出50次獨(dú)立運(yùn)行MBDE得到的最優(yōu)值的方差，50次獨(dú)立運(yùn)行中算法每次執(zhí)行的平均時間。從方差看，雖然隨著問題規(guī)模的增大有所增加，但增加的幅度不大，總體看方差很小，說明算法的穩(wěn)定性非常好。從平均執(zhí)行時間ACT看，除了mk_gk11花費(fèi)的時間較長，但也沒有超過4 min，其他實例求解時間都不超過1 min。這說明算法能有效求解較大規(guī)模的MKP問題。

以上的實驗數(shù)據(jù)比較可以說明，算法MBDE對于求解各種規(guī)模的MKP問題具有很強(qiáng)的魯棒性和尋優(yōu)能力。

5 結(jié)束語

本文提出了一種求解MKP問題的改進(jìn)的二進(jìn)制差分算法，提出了一種新的價值密度計算方法，并設(shè)計了一種修復(fù)不可行解和優(yōu)化可行解的方法，算法中加入反向搜索提高算法的開發(fā)性能，精英局部搜索提高算法探索能力，有效提高了算法對MKP問題的求解精度和收斂速度。基于國際標(biāo)準(zhǔn)測試數(shù)據(jù)的仿真實驗表明，MBDE無論對于中小規(guī)模MKP問題，還是大規(guī)模MKP問題，均具有優(yōu)良的尋優(yōu)能力和較強(qiáng)魯棒性以及求解速度。和近期提出的解決MKP問題的其他較優(yōu)秀的啟發(fā)式算法（隨機(jī)二進(jìn)制差分算法、隨機(jī)二進(jìn)制微分算法、精英二進(jìn)制微分算法，混合分布估計法、混合果蠅算法）進(jìn)行了比較，比較結(jié)果顯示MBDE算法求解精度和效能更高，是一種更有效地求解MKP問題的算法。

參考文獻(xiàn)：

[1]Wu Changzhi，Wang Xiangyu，Lin Jiang.Optimizations in project scheduling：A state-of-art survey[M]//Optimization and Control Methods in Industrial Engineering and Construction.Dordrecht：Springer，2014：161-177.

[2]Nawrocki J R，Complak W，Ewicz J B A，et al.The knapsack-lightening problem and its application to scheduling HRT tasks[J].Bulletin of the Polish Academy of Sciences Technical Sciences，2010，57（1）：71-77.

[3]Martello S，Touth P.Knapsack problems：Algorithms and computer implementations[M].New York：Wiley，1990.

[4]Shih W.A branch and bound method for the multiconstraint zero-one knapsack problem[J].Journal of the Operational Research Society，1979，30（4）：369-378.

[5]Freville A，Plateau G.The 0-1 bidimensional knapsack problem：Towards an efficient high-level primitive tool[J].Journal of Heuristics，1996，2：147-167.

[6]Touth P.Dynamic programing algorithms for the zero-one knapsack problem[J].Computing，1980，25（1）：29-45.

[7]Balev S，Yanev N，F(xiàn)reville A，et al.A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem[J].European Journal of Operational Research，2008，166：63-76.

[8]Chu P C，Beasley J E.A genetic algorithm for the multidimensional knapsack problem[J].Journal of Heuristics，1998，4（1）：63-86.

[9]Wang Ling，Wang Shengyao，Xu Ye.An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem[J].Expert Systems with Applications，2012，39（5）：5593-5599.

[10]Liu Jianjun，Wu Changzhi，Cao Jiang，et al.A binary differential search algorithm for the 0-1 multidimensional knapsack problem[J].Applied Mathematical Modelling，2016，40（23/24）：9788-9805.

[11]Bansal J C，Deep K.A modified binary particle swarm optimization for knapsack problems[J].Applied Mathematics Computation，2012，218（22）：11042-11061.

[12]Chih M.Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem[J].Applied Soft Computing，2015，26：378-389.

[13]Wang Ling，Zheng Xiaolong，Wang Shengyao.A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Knowledge-Based Systems，2013，48（2）：17-23.

[14]Azad M A K，Rocha A，F(xiàn)ernandes E.Improved binary artificial fish swarm algorithm for the 0-1 multidimensional knapsack problem[J].Swarm&Evolutionary Computation，2014，14：66-75.

[15]Salman A A，Ahmad I，Omran M.Stochastic diffusion binary differential evolution to solve multidimensional knapsack problem[J].International Journal of Machine Learning and Computing，2016（2）：130-133.

[16]Storm R，Price K.Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces[R].International Computer Science Institute，1995.

[17]Storn R M，Price K V.Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997，11（4）：341-359.

[18]王凌，錢斌.混合差分進(jìn)化與調(diào)度算法[M].北京：清華大學(xué)出版社，2012.

[19]Joshi R，Sanderson A C.Minimal representation multisensor fusion using differential evolution[J].IEEE Trans on Systems，Man and Cybernetics，Part A，1999，29（1）：63-76.

[20]Abbass H A.An evolutionary artificial neural networks approach for breast cancer diagnosis[J].Artificial Intelligence in Medicine，2002，25（3）：265-281.

[21]Kapadi M D，Gudi R D.Optimal control of fed-batch fermentation involving multiple feeds using differential evolution[J].Process Biochemistry，2004，39（11）：1709-1721.

[22]Aydin S，Temeltas H.Fuzzy-differential evolution algorithm for planning time-optimal trajectories of a unicycle mobile robot on predefined path[J].Advanced Robotics，2004，18（7）：725-748.

[23]Tsaiky，Wang F S.Evolutionary optimization with data collocation for reverse engineering of biological networks[J].Bioinformatics，2005，21（7）：1180-1188.

[24]賀毅朝，王熙照，寇英展.一種具有混合編碼的二進(jìn)制差分演化算法[J].計算機(jī)研究與發(fā)展，2007，44（9）：1476-1484.

[25]Pirkul H.A heuristic solution procedure for the multiconstraint zero-one knapsack problem[J].Naval Research Logistics，1987，34（2）：161-172.

[26]Zhang Biao，Pan Quanke，Zhang Xinli，et al.An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems[J].Applied Soft Computing Jounal，2015，29（C）：288-297.

[27]賀毅朝，王熙照，李文斌，等.基于遺傳算法求解折扣背包問題的研究[J].計算機(jī)學(xué)報，2016，39（12）：2614-2629.

[28]Tizhoosh H R.Opposition-based learning：A new scheme for machine intelligence[C]//Proceedings of IEEE Computational Intelligence for Modelling，Control and Automation，Vienna，Austria，2005：695-701.

[29]Rahnamayan S，Tizhoosh H R，Salama M M A.Opposition-based differential evolution[J].IEEE Transactions on Evolutinary Computation，2008，12（1）：64-79.

[30]孟偉，韓學(xué)東，洪炳.蜜蜂進(jìn)化型遺傳算法[J].電子學(xué)報，2006，34（7）：1294-1300.

[31]劉全，王曉燕，傅啟明，等.雙精英協(xié)同進(jìn)化遺傳算法[J].軟件學(xué)報，2012，23（4）：765-775.

[32]Wadley F M.The design and analysis of experiments[J].Yale Journal of Biology&Medicine，1953，6（5）：18.