求解折扣{0-1}背包問題的新遺傳算法

吳聰聰，賀毅朝，趙建立，2

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

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

1 引言

背包問題（Knapsack Problem，KP）[1-2]是一種著名的組合優(yōu)化問題，它在現(xiàn)實(shí)世界有廣泛的應(yīng)用，也有重要的理論價(jià)值，吸引了很多學(xué)者對(duì)其進(jìn)行研究[3-5]。折扣{0-1}背包問題[6-7]（Discounted{0-1}Knapsack Problem，D{0-1}KP）是經(jīng)典0-1 背包問題的一個(gè)擴(kuò)展形式，它是比0-1 背包更難求解的NP-hard 問題。可以這樣描述D{0-1}KP：給定n 個(gè)均含有3 個(gè)項(xiàng)（或物品）的項(xiàng)集，項(xiàng)集i(0 ≤i ≤n-1)中含有的3 個(gè)項(xiàng)分別記為3i，3i+1，3i+2；其中前兩項(xiàng)具有的價(jià)值分別為v3i，v3i+1，具有的重量分別為w3i和w3i+1；前兩項(xiàng)合并得到第三項(xiàng)3i+2，它具有的價(jià)值為v3i+2=v3i+v3i+1，重量為w3i+2，滿足w3i+2＜w3i+w3i+1且w3i+2＞w3i，w3i+2＞w3i+1；對(duì)于每個(gè)項(xiàng)集i(0 ≤i ≤n-1)的項(xiàng)3i，3i+1，3i+2 最多有一個(gè)被選中裝入背包中。問題是如何選擇裝入背包的各項(xiàng)，使得在被裝入背包的所有項(xiàng)的重量之和不超過背包載重C 的前提下價(jià)值和最大？

在現(xiàn)實(shí)世界，許多實(shí)際問題能映射成D{0-1}KP 的模型，比如項(xiàng)目決策、投資和預(yù)算控制等。目前求解D{0-1}KP 的方法主要有兩大類：以動(dòng)態(tài)規(guī)劃法為主的精確算法[6-8]和基于群搜索的各種演化算法[9-11]。使用動(dòng)態(tài)規(guī)劃法求解D{0-1}KP 問題時(shí)計(jì)算量和存儲(chǔ)量都很大，當(dāng)問題規(guī)模很大時(shí)，難于求解[9]?；诖耍墨I(xiàn)[9]提出了基于精英保留策略的遺傳算法（Elitist Genetic Algorithm，EGA）求解D{0-1}KP，運(yùn)用兩種模型分別對(duì)D{0-1}KP進(jìn)行了求解，開啟使用演化算法求解D{0-1}KP的研究；隨后使用蝙蝠算法[10]、蝴蝶算法[11]等演化算法求解D{0-1}KP的方法被相繼提出。這些算法雖然在求解精度上高于文獻(xiàn)[9]的兩個(gè)遺傳算法，但由于其原始算法都是為求解連續(xù)問題而設(shè)計(jì)的，求解D{0-1}KP 需要編碼轉(zhuǎn)換，再加之引入一些復(fù)雜的策略，使得算法時(shí)間效率不高。

應(yīng)用研究表明，常規(guī)遺傳算法并不一定是針對(duì)某一問題的最佳求解方法。將遺傳算法與問題特有知識(shí)集成到一起所構(gòu)成的混合遺傳算法，卻有可能產(chǎn)生出求解性能極佳的方法[12]。本文針對(duì)D{0-1}KP提出了一種新遺傳算法（GADKP）。GADKP 使用四進(jìn)制編碼對(duì)D{0-1}KP問題進(jìn)行求解。與文獻(xiàn)[9]提出的求解D{0-1}KP 的遺傳算法不同的是，本文結(jié)合啟發(fā)式搜索技術(shù)設(shè)計(jì)了3種交叉算子和1種變異算子，4種算子都能夠保證解的可行性，不用專門進(jìn)行不可行解的修復(fù)。本文嘗試了一種求解D{0-1}KP 的新途徑。3 種交叉算子從3 個(gè)不同的角度提高算法的搜索能力。在變異算子中，根據(jù)D{0-1}KP 的問題特征，采用逐層貪心機(jī)制保證子代個(gè)體在產(chǎn)生過程中得到最大的優(yōu)化。通過4 組共40 個(gè)不同特征和規(guī)模的實(shí)例測(cè)試比較，GADKP有36個(gè)實(shí)例求解精度都好于文獻(xiàn)[9]提出的遺傳算法。從算法的時(shí)間復(fù)雜度和具體實(shí)例的執(zhí)行時(shí)間看，算法有較好的時(shí)間效率，適合求解大規(guī)模的D{0-1}KP。

2 D{0-1}KP數(shù)學(xué)模型

文獻(xiàn)[6]首次提出D{0-1}KP，并給出了數(shù)學(xué)模型，本文稱之為模型1，描述如下：

其中，二元變量xj(0 ≤j ≤3n-1)表示項(xiàng)j 是否被裝入背包中，即xj=1 表示第j 項(xiàng)被裝入了背包，xj=0 表示第j 項(xiàng)未被裝入背包。

賀毅朝等在文獻(xiàn)[9]中提出了另一種D{0-1}KP 數(shù)學(xué)模型，這里稱之為模型2，描述如下：

模型2 中：xi有4 種取值，為0 時(shí)，表示項(xiàng)集i 中沒有項(xiàng)被裝入，當(dāng)xi為1 時(shí)，表示項(xiàng)集i 中第1 項(xiàng)（即第3i 項(xiàng)）被裝入，當(dāng)xi為2 時(shí)，表示項(xiàng)集i 中第2 項(xiàng)（即第3i+1項(xiàng)）被裝入；當(dāng)xi為3 時(shí)，表示項(xiàng)集i 中第3 項(xiàng)（即第3i+2 項(xiàng)）被裝入背包。很容易看出，對(duì)于解向量X=[x0,x1,…,xn-1]，是問題的潛在解，只有滿足條件（6），才是可行解。

不失一般性，上面兩個(gè)描述中價(jià)值、重量和背包載重都是非負(fù)數(shù)。

3 求解D{0-1}KP的新遺傳算法

因?yàn)楹湍Ｐ? 相比，模型2 的變量在取值上隱式的滿足了每組最多只有一個(gè)項(xiàng)被選中的約束條件，使得算法在處理潛在解時(shí)減少了工作量，有利于提高時(shí)間效率，所以本文基于模型2求解D{0-1}KP。根據(jù)模型2求解D{0-1}KP，使用的編碼為四進(jìn)制整型編碼，即：個(gè)體X=[x0,x1,…,xn-1]，xi∈{0,1,2,3}，0 ≤i ≤n-1。個(gè)體X 就是問題的解向量，當(dāng)X 滿足公式（6）時(shí)，其為可行解，否則為不可行解。

GADKP 首先第一步是按照物品的價(jià)值密度比進(jìn)行組內(nèi)和組間排序的預(yù)備工作；通過逐層貪心策略產(chǎn)生優(yōu)秀的初始群；之后是針對(duì)D{0-1}KP 設(shè)計(jì)的3 種交叉算子Crossover1、Crossover2、Crossover3和變異算子Mutation 的執(zhí)行；為了更好地保證群體的多樣性，算法設(shè)置了監(jiān)測(cè)功能，當(dāng)發(fā)現(xiàn)群體進(jìn)化情況不佳時(shí)，會(huì)及時(shí)補(bǔ)充新個(gè)體進(jìn)入。

3.1 預(yù)備工作

演化算法求解背包問題中，使用價(jià)值密度作為衡量物品裝入背包的選擇尺度是常用的策略。D{0-1}KP與普通的0-1KP 不同，物品以項(xiàng)集為單位進(jìn)行選擇，每項(xiàng)集只能有一項(xiàng)被選中。GADKP 算法利用了D{0-1}KP這一特征使用逐層貪心策略選擇物品。為此，需要完成下面的預(yù)備工作。按物品的價(jià)值密度進(jìn)行了逐層排序：對(duì)每組物品項(xiàng)3i，3i+1 和3i+2，(0 ≤i ≤n-1)按價(jià)值密度vj/wj(j ∈{3i,3i+1,3i+2})非升序排序，將排好序的組內(nèi)序號(hào)存入二維數(shù)組H[0…n-1,0…2]的第i 行對(duì)應(yīng)位置。然后，將各組中第一名按他們的價(jià)值密度比以非升序排序，排序后的序號(hào)存入二維數(shù)組G[0…n-1,0…2]的第一列；將各組第二名按他們的價(jià)值密度比非升序排序，排序后的序號(hào)存入數(shù)組G 的第二列；將各組第三名按他們的價(jià)值密度比非升序排序，排序后的序號(hào)存入數(shù)組G 的第三列。例如一個(gè)包括7 組項(xiàng)目組的D{0-1}KP 實(shí)例，價(jià)值集合V={{125，821，946}，{359，987，1346}，{258，763，1021}，{107，622，729}，{474，744，1218}，{150，640，490}，{260，497，757}}，重量集合為W={{25，721，725}，{259，887，934}，{158，663，777}，{7，522，528}，{374，644，664}，{50，390，410}，{160，397，549}}。那么，其對(duì)應(yīng)的二維數(shù)組H 如表1所示，對(duì)應(yīng)的數(shù)組G 如表2所示。G[0，0]中數(shù)字為3，表示第3組（組序號(hào)從0開始）的價(jià)值比最高的項(xiàng)在所有組中最高，而第3組價(jià)值比最高的項(xiàng)就是H[3,0]的值，本實(shí)例中為0，即表示第3組中第0項(xiàng)（組內(nèi)序號(hào)從0編號(hào)）。

表1 組內(nèi)排序后序號(hào)存入數(shù)組H示例

表2 組間排序后組序號(hào)存入數(shù)組G示例

3.2 初始化

使用遺傳算法求解約束優(yōu)化的核心問題是如何處理約束，因?yàn)檫z傳算子常會(huì)產(chǎn)生不可行的后代[13]。已有的求解D{0-1}KP 的群智能算法[9-11]都是在沒有約束的條件下產(chǎn)生解，然后再使用修復(fù)算子對(duì)不可行解進(jìn)行修復(fù)，這樣做無疑會(huì)增加很多計(jì)算量。GADKP 的特點(diǎn)之一就是針對(duì)D{0-1}KP 特征，使用了產(chǎn)生可行解的遺傳算子，避免附加的運(yùn)算。

進(jìn)化過程中解的可行性首要前提是初始解的可行，這就要求GADKP 初始化產(chǎn)生的個(gè)體是滿足約束條件（即公式（6））的可行解。具體做法為：隨機(jī)產(chǎn)生N 個(gè)個(gè)體{X1,X2,…,XN}，Xk=[xk,0,xk,1,xk,n-1]，xk,i∈{0，1，2，3}，1 ≤k ≤N，0 ≤i ≤n-1。對(duì)于每個(gè)個(gè)體，當(dāng)xk,i≠0時(shí)，將第i 組的第xk,i個(gè)物品項(xiàng)裝入，前提是背包不超重。如裝入超重，則將xk,i設(shè)置為0。對(duì)全部組處理完畢后得到可行解Xk。為使初始化個(gè)體更優(yōu)秀，GADKP算法使用貪心策略對(duì)其進(jìn)行了進(jìn)一步的優(yōu)化處理（如算法1所示）。

算法1Initial population

輸入：D{0-}KP實(shí)例，預(yù)備工作得到的數(shù)組H

輸出：初始化的群個(gè)體

for k=1 to N do

隨機(jī)產(chǎn)生個(gè)體Xk=[xk,0,xk,1,…,xk,n-1]，xk,i∈{0，1，2，3}，0 ≤i ≤n-1

weight=0,value=0

for i=0 to n-1 do

if(xk,i≠0&&w3i+xk,i-1≤C-weight）then

weight=weight+w3i+xk,i-1

value=value+v3i+xk,i-1

else

xk,i=0；

end if

end for

for i=0 to n-1 do

if(xk,i=0&&w3i+Hi,0≤C-weight）then

weight=weight+w3i+Hi,0

value=value+v3i+Hi,0

xk,i=Hi,0

end if

end for

end for

return({X1,X2,…,XN})

由上面的初始化的偽代碼很容易看出，算法1的時(shí)間復(fù)雜度為O(Nn)，N 為種群規(guī)模，n 為項(xiàng)目組的組數(shù)。

3.3 3種交叉算子

交叉算子運(yùn)用個(gè)體之間的交互，實(shí)現(xiàn)算法的全局搜索。D{0-1}KP 是較復(fù)雜的組合優(yōu)化問題，使用遺傳算法傳統(tǒng)的單點(diǎn)交叉或多點(diǎn)交叉等基本的交叉算子無法達(dá)到期望的尋優(yōu)效果，而且會(huì)產(chǎn)生不可行解。借助D{0-1}KP自身信息，在保證解的可行性的同時(shí)，提高搜索精度是GADKP 設(shè)計(jì)了3 種交叉算子的目標(biāo)。交叉算子1（Crossover1）的目的是增加種群多樣性，提高算法的全局勘探能力；交叉算子2（Crossover2）的目的是通過將普通個(gè)體和種群中最優(yōu)個(gè)體交叉實(shí)現(xiàn)群體向優(yōu)秀個(gè)體學(xué)習(xí)的功能，從而提高算法求解精度；交叉算子3（Crossover3）采用個(gè)體之間相互學(xué)習(xí)，取長補(bǔ)短，提高每個(gè)個(gè)體的尋優(yōu)能力。3個(gè)交叉算子都保證產(chǎn)生新個(gè)體仍然是D{0-1}KP的可行解。

Crossover1的實(shí)現(xiàn)如下：對(duì)于個(gè)體Xk(1 ≤k ≤N)，任選兩個(gè)和其不同的個(gè)體Xk1，Xk2(1 ≤k1≤N,1 ≤k2≤N,k ≠k1≠k2)，將3個(gè)個(gè)體中完全相同的位保留，其他位設(shè)為0，得到臨時(shí)個(gè)體TEMP=[temp0,temp1,…,tempn-1]。對(duì)TEMP 中為0的位隨機(jī)選擇一個(gè)1到3之間的整數(shù)，如果選中的數(shù)字對(duì)應(yīng)的該組的物品項(xiàng)放入背包不超重，則選中該整數(shù)，否則該位保持0 不變。Crossover1 的具體實(shí)現(xiàn)如算法2。

算法2Crossover1 operator

輸入：個(gè)體Xk，與Xk不同的兩個(gè)互不相同的個(gè)體Xk1，Xk2

輸出：個(gè)體Xk

weight=0,value=0

for i=0 to n-1 do

與開頭呼應(yīng)，我以為，95后的一代人，是真正的新人，是全球化乃至信息、智能時(shí)代的新新人類，而85年之前的，大抵還屬于農(nóng)耕時(shí)代。兒子之表現(xiàn)及95后大學(xué)生的表現(xiàn)，使我心生感慨。其實(shí)我們這一代人，已經(jīng)完全不了解新一代了。而新一代，他們的起點(diǎn)乃至對(duì)當(dāng)下、未來世界的理解和掌控，顯然超出了我們的想象和預(yù)期。

if(xk,i=xk1,iand xk,i=xk2,i) then

tempi=xk,i

if(xk,i≠0) then

weight=weight+w3i+xk,i-1

value=value+v3i+xk,i-1

end if

end if

end for

if(tempi=0) then

k=rand1（1，3）//產(chǎn)生1到3的隨機(jī)整數(shù)

if（weight+w3i+k-1≤C）then

weight=weight+w3i+k-1

value=value+v3i+k-1

tempi=k

end if

end if

if（value ＞Xk的適應(yīng)度）then

Xk=TEMP

end if

return(Xk)

從算法2 的偽代碼可以看出，交叉算子1 保證了新解的可行性。另外，該算子使用3 個(gè)不同個(gè)體進(jìn)行交叉，旨在提高群的多樣性，從而增強(qiáng)算法的探索能力。

種群中的最優(yōu)個(gè)體對(duì)尋找最優(yōu)解有很大的指導(dǎo)作用，Crossover2 設(shè)計(jì)的目的是充分利用最優(yōu)個(gè)體，通過保留和最優(yōu)個(gè)體相同部位的信息，使普通個(gè)體向最優(yōu)個(gè)體學(xué)習(xí)，提高群體的尋優(yōu)性能；Crossover2 的實(shí)現(xiàn)可以這樣描述：令Xbest=[xbest,0,xbest,1,…,xbest,n-1](xbest,i∈{0,1,2,3},0 ≤i ≤n-1)是種群中最好個(gè)體，對(duì)于任意個(gè)體Xk=[xk,0,xk,1,…,xk,n-1](xk,i∈{0,1,2,3},1 ≤k ≤N,0 ≤i ≤n-1)，將Xk中和Xbest完全相同的位保留，其他位設(shè)為0，得到臨時(shí)個(gè)體TEMP=[temp0,temp1,…,tempn-1]，對(duì)TEMP 中為0 的位的處理和Crossover1 中處理相同。Crossover2的具體實(shí)現(xiàn)如算法3。

算法3Crossover2 operator

輸入：個(gè)體Xk(1 ≤k ≤N)，種群中最好個(gè)體Xbest

輸出：Xk

weight=0,value=0

for i=0 to n-1 do

if(xk,i=xbest,i) then

tempi=xk,i

if(xk,i≠0) then

weight=weight+w3i+xk,i-1

value=value+v3i+xk,i-1

end if

end if

end for

for i=0 to n-1 do

if(tempi=0) then

k=rand1（1，3）

if(weight+w3i+k-1≤C) then

weight=weight+w3i+k-1

value=value+v3i+k-1

tempi=k

end if

end if

end for

i（fvalue ＞Xk的適應(yīng)度）then

Xk=TEMP

end if

return(Xk)

因?yàn)榉N群中每個(gè)個(gè)體與最優(yōu)個(gè)體的相同部位是不確定的，那么Crossover2算子中前半部分得到的臨時(shí)個(gè)體中裝入項(xiàng)和項(xiàng)數(shù)也是不確定的，這樣相當(dāng)于選擇了優(yōu)秀個(gè)體的一部分不變，另一部分進(jìn)行重新裝入。從最優(yōu)個(gè)體角度分析，Crossover2 算子實(shí)際是對(duì)優(yōu)秀個(gè)體的變鄰域局部搜索，從而提高解的精度。

與前兩個(gè)交叉算子不同，Crossover3 目的在于提高每個(gè)個(gè)體自身的搜索性能。選中種群中任意兩個(gè)個(gè)體Xk1，Xk2(1 ≤k1≤N,1 ≤k2≤N,)，對(duì)兩個(gè)個(gè)體中不相同且都不為0的位進(jìn)行擇優(yōu)交叉處理，使得交叉產(chǎn)生的子代是更優(yōu)化的可行解。具體操作如算法4。令個(gè)體Xk1，Xk2裝入物品的總價(jià)值和總重量分別為valueXk1，weightXk1，valueXk2，weightXk2。Crossover3的具體實(shí)現(xiàn)如算法4。

算法4Crossover3 operator

輸入：個(gè)體Xk1,Xk2

輸出：Xk1,Xk2

for i=0 to n-1 do

if(xk1,i≠xk2,iand xk1,i≠0 and xk2,i≠0）then

if(v3i+xk1,i-1 ＞v3i+xk2,i-1) then

if(weightXk2-w3i+xk2,i-1+w3i+xk1,i-1≤C) then

weightXk2=weightXk2-w3i+xk2,i-1+w3i+xk1,i-1

valueXk2=valueXk2-v3i+xk2,i-1+v3i+xk1,i-1

end if

else

if(weightXk1-w3i+xk1,i-1+w3i+xk2,i-1 ≤C)

weightXk1=weightXk1-w3i+xk1,i-1+w3i+xk2,i-1

valueXk1=valueXk2-v3i+xk2,i-1+v3i+xk2,i-1

end if

end if

end if

end for

return(Xk1,Xk2)

從算法的偽代碼可以很容易計(jì)算，3 個(gè)交叉算子的時(shí)間復(fù)雜度均為O(n)，n 為D{0-1}KP實(shí)例的項(xiàng)目組的組數(shù)。

3.4 變異算子

GADKP 算法根據(jù)D{0-1}KP 問題中每組只有一個(gè)物品被選中的約束，在變異算子中使用逐層貪心的策略對(duì)物品進(jìn)行選擇。對(duì)于個(gè)體Xk(1 ≤k ≤N)首先按變異概率將某些位設(shè)置為0，然后針對(duì)所有為0的位，將組內(nèi)排名第一的物品按組間的縱向排名次序測(cè)試放入背包；將組內(nèi)排名第二的物品按組間的縱向排名次序測(cè)試放入背包；將組內(nèi)排名第三的物品按組間的縱向排名次序測(cè)試放入背包。令valueXk是個(gè)體Xk的適應(yīng)度值，即裝入背包的物品的價(jià)值和。具體變異算子實(shí)現(xiàn)如算法5所示。

算法5Mutation Operator

輸入：個(gè)體Xk，變異概率pm

輸出：Xk

weight=0,value=0

for i=0 to n-1 do

if(rand()＜pm)then //rand()產(chǎn)生0到1之間的隨機(jī)數(shù)

tempi=0

else

tempi=xk,i

if(tempi≠0) then

weight=weight+w3i+xk,i-1

value=value+v3i+xk,i-1

end if

end if

end for

for i=0 to n-1 do

k1=G[i][0]；k2=H[k1][0]

if(tempk1=0 and weight+w3k1+k2-1≤C) then

tempk1=k2；

weight=weight+w3k1+k2-1

value=value+v3k1+k2-1

end if

end for

for i=0 to n-1 do

k1=G[i][1]；k2=H[k1][1]

if(tempk1=0 and weight+w3k1+k2-1≤C）then

tempk1=k2；

weight=weight+w3k1+k2-1

value=value+v3k1+k2-1

end if

end for

for i=0 to n-1 do

k1=G[i][2]；k2=H[k1][2]

if（tempk1=0 and weight+w3k1+k2-1≤C)then

tempk1=k2；

weight=weight+w3k1+k2-1

value=value+v3k1+k2-1

end if

end for

if(value ＞valueXk) then

TEMP代替Xk

end if

return(Xk)

變異算子的時(shí)間復(fù)雜度為O(n)，n 為項(xiàng)目組組數(shù)。GADKP 中的變異算子在對(duì)個(gè)體隨機(jī)變異的基礎(chǔ)上，依賴D{0-1}KP 問題本身特征，通過逐層貪心策略，有效地提高了局部搜索中尋優(yōu)的性能。GADKP算法的總體框架：

1.預(yù)備工作

2.初始化

3.選中群中最優(yōu)個(gè)體為Xbest

4.for k=1 to N do

Crossover1(Xk)；Crossover2(Xk)；

任選兩個(gè)不同個(gè)體Xk1,Xk2

Crossover3(Xk1,Xk2)

6.for k=1 to N do

Mutation(Xk)

7.如果目前種群中最優(yōu)個(gè)體好于Xbest，則代替Xbest，否則保持Xbest不變

8.如果種群連續(xù)μ 代沒進(jìn)化，重新隨機(jī)生成20%的新個(gè)體

9.如果滿足結(jié)束條件，結(jié)束并返回Xbest，否則執(zhí)行第4。

GADKP 算法的總流程分析：GADKP 算法中預(yù)備工作使用快速排序算法[14-15]進(jìn)行排序，所以時(shí)間復(fù)雜度是O(nlogn)；總流程中第2 和第8 步的時(shí)間復(fù)雜度均是O(Nn)；第3步和第7步的時(shí)間復(fù)雜度均為O(n)；第4至6步是交叉和變異，時(shí)間復(fù)雜度為O(Nn)；所以GADKP算法總的時(shí)間復(fù)雜度為(maxiterNn)，其中maxiter 是算法的迭代次數(shù)，N 為種群數(shù)，n 為項(xiàng)目數(shù)。

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

仿真實(shí)驗(yàn)使用文獻(xiàn)[9]提供的4組共40個(gè)D{0-1}KP實(shí)例，這40 個(gè)實(shí)例分別根據(jù)物品重量和質(zhì)量的相關(guān)性產(chǎn)生，物品項(xiàng)數(shù)為3n(n ∈{100，200，…，1 000}）。關(guān)于實(shí)例構(gòu)造的細(xì)節(jié)請(qǐng)參閱文獻(xiàn)[9]。實(shí)驗(yàn)使用的硬件環(huán)境為Intel Core?i5-7Y54 CPU@1.2 GHz，內(nèi)存8 GB；操作系統(tǒng)為Windows 10，代碼使用C++編寫。算法的最大迭代次數(shù)與實(shí)例規(guī)模一致，為3n(n ∈{100，200，…，1 000}），種群規(guī)模為50。

為驗(yàn)證新算法GADKP的有效性，將其與文獻(xiàn)[9]中的FirEGA 和SecEGA、文獻(xiàn)[10]中的MDBBA、文獻(xiàn)[16]中的DEMBO進(jìn)行了對(duì)比實(shí)驗(yàn)。GADKP獨(dú)立運(yùn)行每個(gè)實(shí)例50 次，表3～6 列出了50 次運(yùn)行結(jié)果的的最好值（BEST）、最差值（WORST）、平均值（MEAN）、方差（STD）和平均運(yùn)行時(shí)間（TIME）。表中FirEGA 和SecEGA 的數(shù)據(jù)來自文獻(xiàn)[9]，MDBBA和DEMBO的數(shù)據(jù)分別來自文獻(xiàn)[10]和文獻(xiàn)[16]，OPT表示實(shí)例的最優(yōu)解，表中粗體數(shù)據(jù)表示5個(gè)算法求得的最好值，帶花號(hào)的數(shù)據(jù)表示達(dá)到了最優(yōu)解。

從表3～6 可以看出，新遺傳算法GADKP 對(duì)于求解弱相關(guān)（WDKP）、強(qiáng)相關(guān)（SDKP）和逆向強(qiáng)相關(guān)（IDKP）的實(shí)例表現(xiàn)最好，在最好值、最差值和平均值3 個(gè)方面都優(yōu)于其他4個(gè)算法（文獻(xiàn)[16]未給出求解IDKP的實(shí)驗(yàn)數(shù)據(jù)）；在求解不相關(guān)（UDKP）的10 個(gè)實(shí)例中，DEMBO求解效果最好，其次是本文提出的GADKP 算法。另外，GADKP在求解逆向相關(guān)的實(shí)例中，有5個(gè)實(shí)例能求得最優(yōu)值。所以，總的來說GADKP求解性能要優(yōu)于其他4個(gè)算法。從GADKP的50次運(yùn)行結(jié)果的方差看，求解弱相關(guān)，強(qiáng)相關(guān)和逆向強(qiáng)相關(guān)的D{0-1}KP問題時(shí)，算法穩(wěn)定性非常好，求解不相關(guān)D{0-1}KP的實(shí)例時(shí)，不如求解其他3種實(shí)例穩(wěn)定。從求解的平均時(shí)間上看，對(duì)于項(xiàng)目數(shù)為3 000 的實(shí)例也能在15 s 左右得到結(jié)果，說明GADKP具有求解大規(guī)模D{0-1}KP的能力。

為了比較3種交叉算子在整個(gè)GADKP算法中的作用，分別測(cè)試了它們的性能。這里將分別只使用交叉算子Crossover1、Crossover2 或Crossover3 的GADKP 命名為GA1、GA2和GA3，圖1～4是這3個(gè)算法和GADKP算法運(yùn)行40 個(gè)實(shí)例所得結(jié)果構(gòu)建的盒圖。從圖1 中可以看出，在求解不相關(guān)實(shí)例（UDKP）時(shí)，3 個(gè)算子中，交叉算子Crossover2在7個(gè)實(shí)例中表現(xiàn)好于其他2種交叉算子。從圖2、3、4 中可以看出，交叉算子Crossover3 在求解弱相關(guān)（WDKP）、強(qiáng)相關(guān)（SDKP）和逆向強(qiáng)相關(guān)（IDKP）的大多數(shù)實(shí)例中表現(xiàn)優(yōu)于交叉算子Crossover1和Crossover2。另外，從圖1～4分析，在求解不相關(guān)和強(qiáng)相關(guān)實(shí)例中，3 種交叉算子結(jié)合后的GADKP 算法求解性能明顯好于單獨(dú)使用其中任何一個(gè)算子；在求解弱相關(guān)（WDKP）的實(shí)例中，Crossover3 在規(guī)模較大的實(shí)例中（WDKP5，WDKP6，WDKP7，WDKP9，WDKP10）表現(xiàn)出優(yōu)于GADKP 的求解性能；在逆向相關(guān)的實(shí)例中，Crossover3 也在部分實(shí)例（IDKP1，IDKP3，IDKP9）中表現(xiàn)出優(yōu)于GADKP的求解性能。所以，在求解弱相關(guān)和逆向相關(guān)的D{0-1}KP 問題時(shí)，可以考慮只使用交叉算子Crossover3。在未知問題特征的情況下，3 種交叉算子結(jié)合使用更適合。

表3 求解不相關(guān)D{0-1}KP實(shí)例結(jié)果

表4 求解弱相關(guān)D{0-1}KP實(shí)例結(jié)果

表5 求解強(qiáng)相關(guān)D{0-1}KP實(shí)例結(jié)果

表6 求解逆強(qiáng)相關(guān)D{0-1}KP實(shí)例結(jié)果

5 結(jié)束語

圖1 3個(gè)交叉算子在不相關(guān)實(shí)例中的盒圖比較

圖2 3個(gè)交叉算子在弱相關(guān)實(shí)例中的盒圖比較

圖3 3個(gè)交叉算子在強(qiáng)相關(guān)實(shí)例中的盒圖比較

圖4 3個(gè)交叉算子在逆強(qiáng)相關(guān)實(shí)例中的盒圖比較

本文提出一種有效求解D{0-1}KP 問題的新遺傳算法GADKP，該算法主要由3 種交叉算子和1 種變異算子組成，4 個(gè)算子的設(shè)計(jì)中引入了啟發(fā)式搜索思想。交叉算子1 增加了種群多樣性，提高了算法的全局勘探能力；交叉算子2 實(shí)現(xiàn)了優(yōu)秀個(gè)體的變鄰域搜索，提升了算法的求解精度；交叉算子3 通過個(gè)體取長補(bǔ)短交叉，提高了群整體的尋優(yōu)能力。在變異算子中，針對(duì)D{0-1}KP 問題特征，采用一種逐層貪心的策略，提高了算法局部開發(fā)的能力；另外，GADKP所設(shè)計(jì)的交叉算子和變異算子都能保證產(chǎn)生子代仍然是可行解。通過4類40 個(gè)不同規(guī)模的實(shí)例測(cè)試表明，本文提出的新遺傳算法GADKP 優(yōu)于文獻(xiàn)[9]提出的2 種求解D{0-1}KP 的遺傳算法，優(yōu)于文獻(xiàn)[10]的MDBBA 和文獻(xiàn)[16]的DEMBO算法，是一種有效的快速求解D{0-1}KP的算法。