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

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

1.河北地質大學 信息工程學院，石家莊050031

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

1 引言

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

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

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

2 D{0-1}KP數學模型

文獻[6]首次提出D{0-1}KP，并給出了數學模型，本文稱之為模型1，描述如下：

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

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

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

不失一般性，上面兩個描述中價值、重量和背包載重都是非負數。

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

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

GADKP 首先第一步是按照物品的價值密度比進行組內和組間排序的預備工作；通過逐層貪心策略產生優秀的初始群；之后是針對D{0-1}KP 設計的3 種交叉算子Crossover1、Crossover2、Crossover3和變異算子Mutation 的執行；為了更好地保證群體的多樣性，算法設置了監測功能，當發現群體進化情況不佳時，會及時補充新個體進入。

3.1 預備工作

演化算法求解背包問題中，使用價值密度作為衡量物品裝入背包的選擇尺度是常用的策略。D{0-1}KP與普通的0-1KP 不同，物品以項集為單位進行選擇，每項集只能有一項被選中。GADKP 算法利用了D{0-1}KP這一特征使用逐層貪心策略選擇物品。為此，需要完成下面的預備工作。按物品的價值密度進行了逐層排序：對每組物品項3i，3i+1 和3i+2，(0 ≤i ≤n-1)按價值密度vj/wj(j ∈{3i,3i+1,3i+2})非升序排序，將排好序的組內序號存入二維數組H[0…n-1,0…2]的第i 行對應位置。然后，將各組中第一名按他們的價值密度比以非升序排序，排序后的序號存入二維數組G[0…n-1,0…2]的第一列；將各組第二名按他們的價值密度比非升序排序，排序后的序號存入數組G 的第二列；將各組第三名按他們的價值密度比非升序排序，排序后的序號存入數組G 的第三列。例如一個包括7 組項目組的D{0-1}KP 實例，價值集合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}}。那么，其對應的二維數組H 如表1所示，對應的數組G 如表2所示。G[0，0]中數字為3，表示第3組（組序號從0開始）的價值比最高的項在所有組中最高，而第3組價值比最高的項就是H[3,0]的值，本實例中為0，即表示第3組中第0項（組內序號從0編號）。

表1 組內排序后序號存入數組H示例

表2 組間排序后組序號存入數組G示例

3.2 初始化

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

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

算法1Initial population

輸入：D{0-}KP實例，預備工作得到的數組H

輸出：初始化的群個體

for k=1 to N do

隨機產生個體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的時間復雜度為O(Nn)，N 為種群規模，n 為項目組的組數。

3.3 3種交叉算子

交叉算子運用個體之間的交互，實現算法的全局搜索。D{0-1}KP 是較復雜的組合優化問題，使用遺傳算法傳統的單點交叉或多點交叉等基本的交叉算子無法達到期望的尋優效果，而且會產生不可行解。借助D{0-1}KP自身信息，在保證解的可行性的同時，提高搜索精度是GADKP 設計了3 種交叉算子的目標。交叉算子1（Crossover1）的目的是增加種群多樣性，提高算法的全局勘探能力；交叉算子2（Crossover2）的目的是通過將普通個體和種群中最優個體交叉實現群體向優秀個體學習的功能，從而提高算法求解精度；交叉算子3（Crossover3）采用個體之間相互學習，取長補短，提高每個個體的尋優能力。3個交叉算子都保證產生新個體仍然是D{0-1}KP的可行解。

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

算法2Crossover1 operator

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

輸出：個體Xk

weight=0,value=0

for i=0 to n-1 do

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

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）//產生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

if（value ＞Xk的適應度）then

Xk=TEMP

end if

return(Xk)

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

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

算法3Crossover2 operator

輸入：個體Xk(1 ≤k ≤N)，種群中最好個體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的適應度）then

Xk=TEMP

end if

return(Xk)

因為種群中每個個體與最優個體的相同部位是不確定的，那么Crossover2算子中前半部分得到的臨時個體中裝入項和項數也是不確定的，這樣相當于選擇了優秀個體的一部分不變，另一部分進行重新裝入。從最優個體角度分析，Crossover2 算子實際是對優秀個體的變鄰域局部搜索，從而提高解的精度。

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

算法4Crossover3 operator

輸入：個體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)

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

3.4 變異算子

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

算法5Mutation Operator

輸入：個體Xk，變異概率pm

輸出：Xk

weight=0,value=0

for i=0 to n-1 do

if(rand()＜pm)then //rand()產生0到1之間的隨機數

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)

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

1.預備工作

2.初始化

3.選中群中最優個體為Xbest

4.for k=1 to N do

Crossover1(Xk)；Crossover2(Xk)；

任選兩個不同個體Xk1,Xk2

Crossover3(Xk1,Xk2)

6.for k=1 to N do

Mutation(Xk)

7.如果目前種群中最優個體好于Xbest，則代替Xbest，否則保持Xbest不變

8.如果種群連續μ 代沒進化，重新隨機生成20%的新個體

9.如果滿足結束條件，結束并返回Xbest，否則執行第4。

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

4 仿真實驗和分析

仿真實驗使用文獻[9]提供的4組共40個D{0-1}KP實例，這40 個實例分別根據物品重量和質量的相關性產生，物品項數為3n(n ∈{100，200，…，1 000}）。關于實例構造的細節請參閱文獻[9]。實驗使用的硬件環境為Intel Core?i5-7Y54 CPU@1.2 GHz，內存8 GB；操作系統為Windows 10，代碼使用C++編寫。算法的最大迭代次數與實例規模一致，為3n(n ∈{100，200，…，1 000}），種群規模為50。

為驗證新算法GADKP的有效性，將其與文獻[9]中的FirEGA 和SecEGA、文獻[10]中的MDBBA、文獻[16]中的DEMBO進行了對比實驗。GADKP獨立運行每個實例50 次，表3～6 列出了50 次運行結果的的最好值（BEST）、最差值（WORST）、平均值（MEAN）、方差（STD）和平均運行時間（TIME）。表中FirEGA 和SecEGA 的數據來自文獻[9]，MDBBA和DEMBO的數據分別來自文獻[10]和文獻[16]，OPT表示實例的最優解，表中粗體數據表示5個算法求得的最好值，帶花號的數據表示達到了最優解。

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

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

表3 求解不相關D{0-1}KP實例結果

表4 求解弱相關D{0-1}KP實例結果

表5 求解強相關D{0-1}KP實例結果

表6 求解逆強相關D{0-1}KP實例結果

5 結束語

圖1 3個交叉算子在不相關實例中的盒圖比較

圖2 3個交叉算子在弱相關實例中的盒圖比較

圖3 3個交叉算子在強相關實例中的盒圖比較

圖4 3個交叉算子在逆強相關實例中的盒圖比較

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