考慮主觀需求的0-1背包問題及其求解算法

張玉州，陶 朗

（安慶師范大學(xué)計算機與信息學(xué)院，安徽安慶246133）

背包問題[1]（knapsack problem，KP）于20世紀50年代由Dantzing提出，作為一類經(jīng)典的組合優(yōu)化問題，屬于NP-hard問題。該問題具有眾多的變種，包括0-1背包問題[2]、有界背包問題、多背包問題、多維背包問題[3]、二次背包問題和折扣0-1背包問題[4]等。背包問題的約束條件一般都是背包的額定容量，即便是較為復(fù)雜的折扣0-1背包問題，除了需要考慮編碼結(jié)構(gòu)的可行性，其約束條件也同樣是背包的額定容量。但在實際生活中，不僅需要考慮問題本身的約束，決策者的自身需求同樣值得考慮。

目前，針對背包問題的研究算法主要有貪心算法[5]、動態(tài)規(guī)劃算法、窮舉法等精確算法和遺傳算法[6]、蟻群算法[7]、和聲搜索算法[8]、蝙蝠算法[9]、獅群算法[10]等近似算法。貪心算法局部收斂性太強，學(xué)者通常是將其與其他近似算法結(jié)合使用，以求達到提高算法收斂性能和防止陷入局部最優(yōu)的目的。模擬退火算法[11]、禁忌搜索算法[12]和果蠅算法[13]等全局搜索能力較弱，對初始解的要求十分嚴格。因此，貪心算法通常會以算子的形式與其他近似算法結(jié)合，用來修補優(yōu)化初始解以期提升算法的全局收斂性能和解的質(zhì)量。文獻[13]就將貪心算法作為果蠅算法的修復(fù)補償策略，修復(fù)非法解和優(yōu)化可行解，有效提升了果蠅算法的求解質(zhì)量。文獻[14]針對背包問題的特點在遺傳算法中引入貪心算子，提升了種群中解的質(zhì)量和算法的收斂性能。在一些較新的背包問題上，遺傳算法同樣展現(xiàn)出了極強的適用性，文獻[15]借鑒啟發(fā)式搜索思想，設(shè)計了3種交叉算子與1種變異算子，有效解決了折扣0-1背包問題的無效編碼結(jié)構(gòu)，保證了算法進化中解的可行性。當(dāng)然，遺傳算法演化過程中的交叉操作同樣作用非凡，文獻[16]就將其引入蝙蝠算法中，建立了全新的位置轉(zhuǎn)移方式，提升了算法的求解效率。本文結(jié)合實際，將決策者的主觀需求與背包問題結(jié)合，提出考慮決策者需求上限的0-1背包問題，并設(shè)計一種混合貪心遺傳算法（Hybird Greedy Genetic Algorithm，HGGA）來對問題進行求解。

1 問題分析與建模

供選擇的每一個物品都有自己的固有屬性（價值和重量），這些物品又分為若干類，決策者對于每一類物品都有自己的需求，在盡量滿足自身需求和不超過背包額定限重的前提下，使得背包內(nèi)的物品總價值最大。本文的研究含三類物品，若物品的需求上限之和大于背包的額定載重，那么至少有一類物品必然無法滿足其需求上限，在此前提下，如何根據(jù)決策者對各類物品的主觀需求合理地規(guī)劃并分配背包空間，最大化包內(nèi)物品的總價值，便成為解決此類問題的核心。

給定若干個物品，共分為3類，數(shù)量分別為n1、n2、n3，每一類物品都有它的重量和價值。決策者對每類物品的需求上限分別為G1、G2、G3，背包的額定載重為G，要求在不超過背包額定限重和各類物品需求上限的前提下，使得裝入背包中的所有物品的總價值最大，該問題的數(shù)學(xué)模型表示如下：

目標函數(shù)（1）表示最大化裝入包中三類物品的總價值，其中，vij表示的是第i類物品中第j號物品的價值，wij表示的是第i類物品中第j號物品的重量。約束式（2）分別表示第i類物的需求上限為Gi和裝入包中的物品總重量不得超過背包的額定載重G。式（3）中，xij表示第i類物品中第j號物品的決策變量，1表示選擇對應(yīng)物品放入包內(nèi)，0表示不選擇對應(yīng)物品放入包內(nèi)。

2 算法設(shè)計

2.1 貪心算子

貪心算子的物品選擇策略主要分為價值和價值密度，價值密度定義為pi=viwi。通過實驗，對比2種策略產(chǎn)生的解的質(zhì)量，以價值密度作為物品選擇策略的解的質(zhì)量通常高于以價值作為選擇策略的解的質(zhì)量。本文采用貪心算子作為優(yōu)化解的方法，采用價值密度策略，以保證解的質(zhì)量。

結(jié)合本文提出的模型特點，考慮背包的客觀約束和決策者對各類物品的主觀需求約束，所有解的修復(fù)方案分為2種：（1）先考慮客觀約束，再考慮主觀需求，在滿足背包容量需求的前提下，根據(jù)決策者對各類物品的需求對當(dāng)前解進行調(diào)整，得到最終解；（2）先考慮主觀需求，再考慮客觀約束，考慮各類物品需求得到初步解，判斷此解是否滿足背包容量約束，最后對此解進行調(diào)整與優(yōu)化。

試驗證明，第1種策略得到的解需要進行二次調(diào)整才能夠得到與第2種策略相同質(zhì)量的解。第2種策略在修復(fù)解的時候無需二次調(diào)整，更加簡便、高效。因此，本文采用第2種策略對當(dāng)前解進行修復(fù)優(yōu)化，具體操作如下。

步驟1分別計算當(dāng)前解X對應(yīng)的包內(nèi)3類物品的重量wA、wB、wC。

步驟2分別對物品A、B、C進行修復(fù)操作，得到中間解X′。

1）若此類物品的總重量w大于此類物品的需求D，則將已選的物品按照價值密度遞減的順序進行排列，依次選取放入包內(nèi)直到滿足此類物品的需求D，并將當(dāng)前解X對應(yīng)的二進制位點進行調(diào)整。

2）若此類物品的總重量w小于此類物品的需求D，則將未選的物品按照價值密度遞減的順序進行排列，依次選取放入包內(nèi)直到滿足此類物品的需求D，并將當(dāng)前解X對應(yīng)的二進制位點進行調(diào)整。

3）輸出中間解X′。

步驟3計算中間解X″對應(yīng)的所有物品總重量W″，確定所有已選物品。將所有已選物品按照價值密度遞減的順序進行排列，依次選取放入包內(nèi)直到滿足背包的容量G。將中間解X″對應(yīng)的二進制位點進行調(diào)整，得到最終解X″。

2.2 局部搜索算子

初始解的質(zhì)量對于局部搜索算法的效率影響至關(guān)重要[17-18]，考慮到遺傳算法的全局尋優(yōu)能力與局部搜索算法的高效局部搜索能力，本文在遺傳算法的基本框架中加入改進的局部搜索算子，實現(xiàn)對局部最優(yōu)個體的進一步優(yōu)化。文獻[15]提出的隨機選取3個位點的方式過于野蠻，往往會產(chǎn)生較多的無用結(jié)構(gòu)。例如，X=[ ]0100111100，當(dāng)隨機選取到第2、5、6號位點，進行取反后得到新的個體X′=[0000001100]，顯然，這些位點的取反是沒有意義的，會增加算法運行時間。本文結(jié)合果蠅算法的局部搜索特點并改進取反位點的選擇方式，設(shè)計一種新的局部搜索算子，具體操作描述如下。

步驟1根據(jù)局部最優(yōu)解個體xbest的編碼信息，獲取已選物品的序列index 1和未選取物品的序列index 0。

步驟2在序列index 1中隨機選擇p，將個體xbest中位置p的1取反為0。

步驟3在序列index 0中隨機選擇p或p1與p2，以概率的形式實現(xiàn)位點數(shù)目的選擇方式。當(dāng)隨機概率P>0.5時，選擇一個位點，將個體xbest中位置p的0取反為1；當(dāng)隨機概率P≤0.5時，選擇2個位點，將個體xbest中位置p1與p2的0取反為1。

步驟4返回步驟2，重復(fù)100次，得到種群pop_temp，求出新種群中物品總價值大于xbest對應(yīng)的物品總價值且滿足各個約束的新個體xtemp，并將xbest更新為xtemp。

步驟5返回第1步，重復(fù)100次，得到最終個體xbetter。

2.3 遺傳算法框架設(shè)計

（1）編碼方式與種群初始化

針對0-1背包問題的特點，采取二進制編碼方式，編碼串中的1表示選擇對應(yīng)序號的物品放入背包內(nèi)，0表示對應(yīng)序號的物品不放入背包內(nèi)。參照文獻[17]-[18]的初始化方法，采取概率向量的方式生成初始種群，直接隨機生成一個概率向量P(X)=[p(x1),p(x2),p(x3),…,p(xn)]來確定對應(yīng)的二進制個體X=[x1,x2,x3,…,xn]，映射如下：

結(jié)合本文的模型，編碼結(jié)構(gòu)如下：

（2）適應(yīng)度函數(shù)

無論何種背包問題，都屬于帶約束條件的最大值問題。對于此類問題，除了上文提到的針對解的修復(fù)優(yōu)化方法，還有罰函數(shù)法。通過對不滿足約束條件的解增加一個懲罰系數(shù)或是一個負值罰分，來降低此類解進入到下一次迭代進化的可能性。本文考慮到算法的整體性能，采用懲罰系數(shù)方法，適應(yīng)度函數(shù)的設(shè)計如下：

（3）標準遺傳算法框架

針對問題模型的特殊性，分別對遺傳算法框架中的經(jīng)典算子進行設(shè)計如下。

選擇操作本文采用經(jīng)典的輪盤賭選擇算子與精英保留機制結(jié)合。一方面能夠保證每一代種群中優(yōu)秀個體都有較大的機會參與到下一代的迭代演化過程，保證優(yōu)秀基因結(jié)構(gòu)繼承下去；另一方面能夠降低遺傳算法的其他操作破壞優(yōu)秀基因結(jié)構(gòu)的可能性，保證算法一直朝著理論最優(yōu)解的方向進化。

交叉操作隨機選取種群中的2個解作為父代個體與母代個體，按照交叉概率Pc進行交叉操作?？紤]到問題模型和編碼結(jié)構(gòu)的特點，本文設(shè)計一種新的均勻交叉操作，采用選擇隨機數(shù)的策略來確定交叉部位，然后在確定部位進行交叉操作，具體步驟描述如下。

步驟1在數(shù)組{1,2,3}中隨機選取1個數(shù)。

步驟2當(dāng)隨機數(shù)為1時，在代表A類物品的染色體結(jié)構(gòu)上隨機選擇1個點作為交叉位點，進行單點交叉操作；當(dāng)隨機數(shù)為2時，在代表B類物品的染色體結(jié)構(gòu)處進行交叉操作；當(dāng)隨機數(shù)為3時，表示在代表C類物品的染色體結(jié)構(gòu)處進行交叉操作。

變異操作對子代個體按照變異概率Pm進行變異操作，分別選取表示A、B、C三類物品的染色體結(jié)構(gòu)上的任意3個點，進行0/1取反操作。

2.4 算法流程設(shè)計

本文僅對初始種群進行貪心修補與優(yōu)化，以保證算法的收斂性能。按照概率對每一代的局部最優(yōu)個體進行精細化搜索，在盡量減少算法耗時的前提下，提升解的質(zhì)量，具體算法描述如下。

步驟1以概率向量初始化的方式生成初始種群pop，種群規(guī)模為popsize。

步驟2調(diào)用貪心算子，將初始種群pop中的所有個體進行修正與優(yōu)化，得到新的種群pop1。

步驟3將新種群pop1代入遺傳算法框架中，調(diào)用輪盤賭選擇算子。計算所有個體的適應(yīng)度值，并找到適應(yīng)度值最大的個體，記為best_ind，最后得到規(guī)模相同的新種群pop2。

步驟4交叉操作。隨機選擇新種群pop2中的任意兩個個體作為父代和母代個體，并將其按照概率Pc進行交叉操作，最后得到新的種群pop3。

步驟5變異操作。對新種群pop3中的所有個體按照概率Pm進行變異操作，得到新種群pop4。

步驟6計算并找到種群pop4中適應(yīng)度最大的個體記為better_ind與最小的個體記為worst_ind，按照概率PILS對個體better_ind進行局部搜索，得到新種群pop5。

步驟7調(diào)用精英保留算子。比較pop5中適應(yīng)度最大的個體better_ind與種群pop1中適應(yīng)度最大的個體best_ind的適應(yīng)度大小。若better_ind的適應(yīng)度值小于best_ind，則將pop5中適應(yīng)度最小的個體worst_ind替換為best_ind個體；反之，則不進行任何操作。最后得到最終種群pop6。

步驟8判斷是否達到算法最大迭代次數(shù)，若是，則輸出最優(yōu)解并結(jié)束；否則返回步驟3，并將新種群pop1替換為種群pop6，重復(fù)以上操作。

具體流程如圖1所示。

圖1 HGGA算法流程圖

3 仿真實驗與結(jié)果分析

3.1 仿真數(shù)據(jù)

為了驗證算法性能，參考文獻[14]、[19]中的數(shù)據(jù)構(gòu)造方法，造物品維數(shù)為150、300和600的背包數(shù)據(jù)集，每種規(guī)模的物品數(shù)據(jù)分為無相關(guān)、強相關(guān)與弱相關(guān)，共3類9個算例。每個算例包含3類物品，具體物品種類劃分規(guī)則為：每1/3維數(shù)的物品為一類。例如，維數(shù)為150的算例，1號至50號物品劃為A類物品，51號至100號物品劃為B類物品，101號至150號物品劃為C類物品。算例數(shù)據(jù)分類特征如表1所示。

表1 算例數(shù)據(jù)分類特征

背包的額定容量G用系數(shù)0.75乘以所有物品的總重量，結(jié)果取整。各類物品的需求D用系數(shù)0.8乘以對應(yīng)種類的物品總重量，結(jié)果取整。確保3類物品的需求之和大于背包的額定容量G。相同維數(shù)的算例使用相同的重量集合W和不同的價值集合V，故同一維數(shù)的算例的客觀約束與主觀需求是相同的。算例的各類物品的主觀需求D和客觀約束背包容量G等具體信息如表2所示。

表2 約束信息

3.2 算法參數(shù)及實驗環(huán)境

遺傳算法框架中的參數(shù)設(shè)置：最大迭代次數(shù)為300，種群規(guī)模為100，交叉概率為0.85，變異概率為0.05，每個算法獨立運行30次。在遺傳算法框架中，局部搜索的種群規(guī)模和搜索次數(shù)不僅會影響算法的尋優(yōu)能力，也會影響算法整體耗時。為了平衡種群規(guī)模和搜索次數(shù)對于算法整體性能的影響，本文經(jīng)過多次嘗試，最終確定局部搜索種群規(guī)模和局部搜索次數(shù)均為100次，局部搜索概率為0.05。表3給出了詳細的算法參數(shù)信息。

表3 參數(shù)設(shè)置

實驗的硬件環(huán)境為惠普ProDesk 400 G4 MT Bussiness PC，CPU型號為Intel Core i5-7500 CPU@3.40GHz-3.41GHz，內(nèi)存8 G，軟件環(huán)境為64位Windows10操作系統(tǒng)，算法在Matlab 2016中編寫。

3.3 實驗結(jié)果與分析

為了檢驗HGGA算法性能，本文使用3.1節(jié)構(gòu)造的9個不同規(guī)模、不同相關(guān)性的算例進行實驗，并分別與簡單遺傳算法（SGA）和貪心遺傳算法（GGA）進行對比。經(jīng)過30次的實驗，統(tǒng)計最優(yōu)解、最差解、平均解、標準差和30次實驗的平均耗時，結(jié)果如表4所示。

表4 實驗結(jié)果

結(jié)合表4給出的最優(yōu)解、最差解和平均解，HGGA算法在KP3和KP5算例上解的質(zhì)量略低于GGA算法，在其他7個算例上均取得了不錯的結(jié)果。標準方差是評價算法魯棒性的重要指標，方差越小，算法的魯棒性越強；反之，魯棒性則越差。同樣，HGGA算法的標準方差在KP3和KP5以外的其他7個算例上也展現(xiàn)出了優(yōu)勢。

就算法的平均耗時而言，隨著算例規(guī)模的擴大，算法耗時也在明顯增加。在相同規(guī)模的算例上，雖然SGA算法耗時最短，但其易陷入早熟收斂，SGA算法求解精度和魯棒性都是3種算法中最差的。HGGA算法耗時在同等規(guī)模的算例中雖然耗時最大，并隨著數(shù)據(jù)規(guī)模的增加，同其他2類算法的差距也會逐漸增加，但求解精度和算法魯棒性上則表現(xiàn)出一定的優(yōu)勢。

就算法的求解精度而言，隨著數(shù)據(jù)規(guī)模的增加，解空間也會不斷擴大。HGGA算法在傳統(tǒng)遺傳算法中增加了更為有效的局部搜索算子，進一步探索了局部最優(yōu)解附近的解空間，大大提升了算法的局部搜索能力和求解精度。結(jié)合表4中的實驗結(jié)果，在規(guī)模不同、相關(guān)性一致的3類算例中，本文提出的HGGA算法在KP3和KP5算例以外的其他7個算例中無論是最優(yōu)解、最差解還是平均解均優(yōu)于SGA算法和GGA算法。而在KP3和KP5算例上，HGGA算法的最優(yōu)解與GGA算法的最優(yōu)解相同，最差解和平均解雖然略低于GGA算法，但差距較小?；谏鲜龇治?，隨著數(shù)據(jù)規(guī)模的增加，本文的算法求解精度會得到保證。

結(jié)合算例的相關(guān)性差異進行分析，圖2給出了規(guī)模同為150的3類相關(guān)性算例的算法收斂折線圖。由表4可知SGA算法的整體求解精度較差，故在圖2中僅繪出GGA算法與HGGA的收斂折線圖。從圖2可以看出，當(dāng)算例規(guī)模相同時，HGGA算法在無相關(guān)算例上表現(xiàn)出的收斂效果和求解精度明顯優(yōu)于GGA算法；但在強相關(guān)和弱相關(guān)2類算例上收斂效果和求解精度與GGA算法不相上下。結(jié)合表4中的算例3和算例5的結(jié)果，可知HGGA算法在求解無相關(guān)的數(shù)據(jù)時，其綜合性能在3類算法中表現(xiàn)最好；在處理具有一定相關(guān)性的數(shù)據(jù)時，HGGA算法的性能難以與GGA算法拉開差距，甚至劣于GGA算法。

圖2 不同算例的算法收斂對比

4 總結(jié)

考慮到實際生活中存在“主觀需求”和“客觀約束”，將其與0-1背包問題相結(jié)合，本文提出了考慮決策者需求的0-1背包問題，構(gòu)建了具體的數(shù)學(xué)模型，并針對遺傳算法全局搜索能力強、易早熟收斂和局部搜索能力弱的缺點，提出了混合貪心遺傳算法。算法在不改變遺傳算法框架的前提下，針對問題特點對貪心修正優(yōu)化算子進行了改進，增強了遺傳算法的收斂性能。同時，設(shè)計了一種局部搜索算子，改進其擾動位點的選擇規(guī)則，提升了遺傳算法的局部搜索能力。在9個隨機生成的規(guī)模不同、相關(guān)性不同的算例上進行仿真實驗，與同類型的遺傳算法比較，本文算法求解精度高、魯棒性強。