求解0-1背包問題的改進(jìn)樹種優(yōu)化算法

張 小 萍

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院， 廣西 南寧 530004)

0-1背包問題是一個(gè)經(jīng)典的NP-hard問題，也是一個(gè)組合優(yōu)化問題。0-1背包問題在生產(chǎn)和生活中應(yīng)用較廣，如物件裝箱、投資組合和金融決策等，因此，0-1背包問題受到很多學(xué)者的關(guān)注。0-1背包問題可描述為：有D件物品，每件物品不可分割，第j件物品(j=1，2，…，D)的重量是wj，價(jià)值是pj，現(xiàn)有一個(gè)承載重量限制為C的背包，如何選擇物品放入背包使得背包中物品的總重量不超過C且物品的總價(jià)值達(dá)到最大。0-1背包的數(shù)學(xué)模型可以表示為：

xj∈{0，1}，j=1，2，…，D

(1)

求解0-1背包問題的算法包括動(dòng)態(tài)規(guī)劃法、遞歸算法和回溯法等確定性算法，這類算法能夠求解出問題的全局最優(yōu)解，但是算法的時(shí)間復(fù)雜度與問題的規(guī)模呈指數(shù)關(guān)系，只能用于求解維度比較小的0-1背包問題。而智能優(yōu)化算法只能求解出0-1背包問題的最優(yōu)解域，不一定能夠求解出全局最優(yōu)解，但智能優(yōu)化算法的時(shí)間復(fù)雜度比較低，可以用于求解高維的0-1背包問題。隨著智能優(yōu)化算法的發(fā)展，涌現(xiàn)出多種用于求解0-1背包問題的算法，這些算法在基本算法的基礎(chǔ)上加入了改進(jìn)策略來(lái)加快算法的收斂速度。周洋等人[1]在基本粒子群算法中加入貪婪策略(GOPSO)求解0-1背包問題，提高了算法的收斂性能。任靜敏等人[2]通過在基本螢火蟲算法中加入慣性權(quán)重、變異算子和貪婪策略(WGFA)，提高了算法的全局搜索能力。劉雪靜等人[3]改進(jìn)了烏鴉算法(BCSA)，先利用Chebyshev映射產(chǎn)生混沌序列初始化種群，使種群的初始分布比較均勻，然后使用貪婪策略修復(fù)不可行解和對(duì)可行解進(jìn)行優(yōu)化。周洋等人[4]設(shè)計(jì)了一個(gè)離散雞群算法(DCSO)，引入了自適應(yīng)權(quán)重組合變異算子來(lái)更新公雞個(gè)體位置，采用定向變異策略改進(jìn)了種群中小雞位置的更新方式，這樣的改進(jìn)使得算法尋優(yōu)時(shí)能夠避免盲目的隨機(jī)搜索，進(jìn)一步提高了算法的穩(wěn)定性。這些算法在求解0-1背包問題時(shí)獲得了較好的優(yōu)化效果，但隨著物品數(shù)目的增加，求解問題難度加大了，算法存在著收斂速度慢，難以獲得全局最優(yōu)解的問題，算法需要進(jìn)一步優(yōu)化。

1 基本樹種優(yōu)化算法

樹種優(yōu)化算法(TSA)[5]是一種新興的智能優(yōu)化算法，是2015年由 Kiran 提出的，算法的思想是模擬大自然樹木生長(zhǎng)繁衍的過程。樹種優(yōu)化算法的結(jié)構(gòu)簡(jiǎn)單，尋優(yōu)能力較強(qiáng)，在彩色圖像多閾值分割[6]、短期電力負(fù)荷預(yù)測(cè)[7]和結(jié)構(gòu)損傷識(shí)別等領(lǐng)域中應(yīng)用都獲得了較好的效果。

在樹種優(yōu)化算法的初始化階段，使用式(2)生成一批樹木：

Ti，j=Lj+ri，j(Hj-Lj)

(2)

式中：Ti，j是樹木i位置的第j個(gè)元素；ri，j是[0，1]中的隨機(jī)數(shù)；Hj是搜索空間的最大值；Lj是搜索空間的最小值。若優(yōu)化問題是最小值問題，需要利用式(3)找到當(dāng)前最優(yōu)樹的位置：

B=min{f(Ti)}，i=1，2，…，N

(3)

然后，樹木要生成種子，TSA使用了2種機(jī)制來(lái)生成種子在全局搜索和局部搜索中獲得平衡，利用式(4)或(5)生成種子：

Si，j=Ti，j+αi，j(Ti，j-Tr，j)

(4)

Si，j=Ti，j+αi，j(Bj-Tr，j)

(5)

式中：Si，j表示第i棵樹繁衍的第i個(gè)種子的第j個(gè)元素；Tr，j表示第r棵樹位置的第j個(gè)元素；Bj表示當(dāng)前最優(yōu)樹的位置的第j個(gè)元素；αi，j是[-1，1]中的隨機(jī)數(shù)，表示步長(zhǎng)因子。

式(4)側(cè)重于全局搜索，避免算法進(jìn)入局部最優(yōu)解，式(5)側(cè)重于局部搜索，便于算法能夠快速收斂。TSA的算法流程如下：

Step 1 種群初始化。設(shè)種群數(shù)目為N，問題維度為D，設(shè)定一個(gè)搜索趨勢(shì)常數(shù)為ST，使用式(2)對(duì)N棵樹木的位置Ti，j進(jìn)行初始化，利用式(3)計(jì)算出當(dāng)前最優(yōu)樹的位置B。

Step 2 生成種子。確定每棵樹生成種子的數(shù)量，在每個(gè)種子生成時(shí)，產(chǎn)生一個(gè)隨機(jī)數(shù)λ，若λ>ST，使用式(4)生成種子，否則使用式(5)生成種子。

Step 3 選擇最優(yōu)解。在每棵樹Ti生成的種子中選擇出一個(gè)最優(yōu)解，與當(dāng)前的樹Ti作比較，若比樹Ti更優(yōu)，則用種子取代樹的位置。

Step 4 迭代次數(shù)加1，然后判斷是否達(dá)到最大迭代次數(shù)，如果不滿足就跳轉(zhuǎn)到 Step 2，否則輸出最優(yōu)解，算法結(jié)束。

2 改進(jìn)的樹種優(yōu)化算法

2.1 二進(jìn)制編碼

基本的樹種優(yōu)化算法是求解連續(xù)問題的，而0-1背包問題是離散問題，要先對(duì)可行解進(jìn)行二進(jìn)制編碼。設(shè)D表示問題的維度，將實(shí)數(shù)型的向量Ti=[Ti，1，Ti，2，…，Ti，D]編碼為二進(jìn)制向量Yi=[Yi，1，Yi，2，…，Yi，D]，編碼規(guī)則如下：

(6)

2.2 貪婪策略

由于在0-1背包問題中還需要符合不超過背包承重限制的約束條件，因此經(jīng)過二進(jìn)制編碼之后可能會(huì)出現(xiàn)不符合約束條件的不可行解，目前在0-1背包問題求解中，對(duì)不可行解有2種處理方法，一是使用懲罰函數(shù)，二是使用貪婪策略?？傮w來(lái)說，使用貪婪策略要比使用懲罰函數(shù)的性能好，因?yàn)槭褂秘澙凡呗约瓤梢詫?duì)不可行解進(jìn)行修復(fù)，變?yōu)榭尚薪?，又可以?duì)可行解進(jìn)行局部?jī)?yōu)化，加快收斂的速度。假設(shè)vi表示0-1背包問題中的物品的價(jià)值/重量，即vi=pi/wi，貪婪策略的基本過程如下：

Step 1 初始化背包為空，按照vi從大到小的順序?qū)ΧM(jìn)制編碼Yi=[Yi，1，Yi，2，…，Yi，D]選擇的商品(相應(yīng)比特位為1)進(jìn)行檢查，如果已選擇的商品加入背包后，小于等于背包重量限制，就加入背包；否則，取出該商品，則Yi相應(yīng)的比特位置為0。

Step 2 按照vi從大到小的順序?qū)ΧM(jìn)制編碼Yi=[Yi，1，Yi，2，…，Yi，D]未選擇的商品(相應(yīng)的比特位置為0)進(jìn)行嘗試性地加入背包，若該未選擇的商品加入背包后，小于等于背包總承重，則加入背包，Yi相應(yīng)的比特位置為1；否則，不加入。

在Step 1后，無(wú)論Yi=[Yi，1，Yi，2，…，Yi，D]是否是可行解，都將轉(zhuǎn)為可行解。Step 2主要是對(duì)可行解進(jìn)行優(yōu)化，使用貪婪思想盡可能地將vi值比較大的物品加入背包，保證背包中的物品價(jià)值達(dá)到局部最大值。貪婪策略具體的偽代碼可以參考文獻(xiàn)[1]。

2.3 改進(jìn)策略

盡管TSA使用了2種機(jī)制來(lái)生成種子，平衡了全局搜索和局部搜索，但是當(dāng)算法迭代到一定程度后，種群已經(jīng)收斂。種群中個(gè)體的相似度比較高的情況下，無(wú)論是使用式(4)還是式(5)來(lái)生成種子都難以獲得更好的解的情況下，樹木位置無(wú)法更新，算法會(huì)進(jìn)入僵化，種群會(huì)陷入局部最優(yōu)解。在這種情況下，為了增加種群的多樣性，提高算法的全局搜索能力，借鑒人工蜂群優(yōu)化算法探索一個(gè)蜂蜜源經(jīng)過多次開采沒被更新就重新設(shè)置開采蜜源的思想[8]，設(shè)定一個(gè)閾值H，當(dāng)Ti有連續(xù)H代以上沒有更好的種子更新Ti，就使用式(2)對(duì)Ti進(jìn)行重新初始化，其目的是增加種群的多樣性。

2.4 改進(jìn)樹種優(yōu)化算法(ITSA)的具體步驟

Step 1 初始化系統(tǒng)各個(gè)參數(shù)，迭代次數(shù)初始化為0，設(shè)定求解問題的維度D，種群大小N，迭代最大次數(shù)M，以及ST和H。

Step 2 利用式(2)初始化種群中的樹木位置，并用式(6)對(duì)樹木位置進(jìn)行二進(jìn)制編碼，然后使用貪婪策略對(duì)二進(jìn)制編碼進(jìn)行修補(bǔ)和優(yōu)化，計(jì)算出個(gè)體的適應(yīng)度。為每棵樹木初始化一個(gè)計(jì)數(shù)器Cnti=0。

Step 3 生成種子。確定每棵樹生成種子的數(shù)量，在每個(gè)種子生成時(shí)，產(chǎn)生一個(gè)隨機(jī)數(shù)λ，若λ>ST，使用式(4)生成種子，否則使用式(5)生成種子，對(duì)每個(gè)種子進(jìn)行二進(jìn)制編碼并用貪婪策略修復(fù)和優(yōu)化，計(jì)算出每個(gè)種子的適應(yīng)度。

Step 4 選擇最優(yōu)解。在每棵樹Ti生成的種子中選擇出一個(gè)最優(yōu)解，與當(dāng)前樹Ti的適應(yīng)度作比較，若比樹Ti更優(yōu)，則用種子取代樹的位置，并置Cnti=0；否則，令Cnti=Cnti+1。

Step 5 若Cnti>H，使用式(2)對(duì)Ti進(jìn)行重新初始化。

Step 6 迭代次數(shù)加1，然后判斷是否達(dá)到最大迭代次數(shù)，如果不滿足就跳轉(zhuǎn)到 Step 3，否則輸出最優(yōu)解，算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果分析

用文獻(xiàn)[9]中的4個(gè)物品數(shù)目分別為17、60、100、200的0-1背包測(cè)試案例進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境為8 G內(nèi)存，CPU為Intel(R) Xeon雙核2.4 GHz，使用MATLABR2020b編程。為了公平起見，ITSA的種群數(shù)量設(shè)為30，每棵樹可以生成5個(gè)種子，設(shè)定H=20，ST=0.5。GOPSO、WGFA、BCSA和DCSO算法的種群數(shù)目設(shè)為150。所有算法的迭代次數(shù)都是200次，對(duì)每個(gè)測(cè)試用例都獨(dú)立運(yùn)行20次，測(cè)試這些算法的最優(yōu)解、平均解、最差解以及方差和運(yùn)行時(shí)間等性能指標(biāo)，獲得的實(shí)驗(yàn)結(jié)果見表1。

表1 實(shí)驗(yàn)結(jié)果數(shù)據(jù)對(duì)比

實(shí)驗(yàn)數(shù)據(jù)表明，當(dāng)物品數(shù)量比較小(17，60)時(shí)，5種算法都必定可以找到最優(yōu)解，其中GOPSO的尋優(yōu)性能比較好，所需要的時(shí)間最少，ITSA算法在5種算法所需時(shí)間的比較中略高于GOPSO和BCSA，但是當(dāng)物品數(shù)量增大到100時(shí)，雖然5種算法都可以找到最優(yōu)解，但I(xiàn)TSA算法所需要的時(shí)間最少，當(dāng)物品數(shù)量增大到200時(shí)，只有ITSA算法以95%的概率找到了最優(yōu)解，其他算法都無(wú)法找到最優(yōu)解，而且ITSA所需時(shí)間也比較少，僅僅比BCSA多一點(diǎn)，而BCSA找到的最優(yōu)解只有5 161，方差也比ITSA大得多。分析發(fā)現(xiàn)，ITSA算法在低維和高維的0-1背包問題中都有較好的尋優(yōu)特性，穩(wěn)定性比較高，具有較強(qiáng)的魯棒性。

再使用Knap-100和Knap-200兩個(gè)案例分析5種算法的收斂性，其收斂曲線如圖1、圖2所示。

圖1 5種算法在求解Knap-100時(shí)的收斂曲線

圖2 5種算法在求解Knap-200時(shí)的收斂曲線

ITSA比其他4種算法的收斂速度更快，收斂到最優(yōu)解域需要的迭代次數(shù)更少，特別是在Knap-200中，只有ITSA收斂到了全局最優(yōu)解。

4 結(jié) 語(yǔ)

樹種優(yōu)化算法是一種新穎的智能優(yōu)化算法，針對(duì)基本樹種優(yōu)化算法容易僵化、在收斂階段種群個(gè)體相似度高、易于得到全局最優(yōu)解的問題進(jìn)行了改進(jìn)，若檢測(cè)到樹木位置連續(xù)H代沒有更新，就重新初始化數(shù)據(jù)位置，增加種群的多樣性。改進(jìn)算法結(jié)合貪婪策略運(yùn)用在求解0-1背包問題中，加強(qiáng)了局部搜索的性能。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在求解0-1背包問題中具有良好的全局搜索性能和較強(qiáng)的穩(wěn)定性，特別是在高維的0-1背包問題中表現(xiàn)出優(yōu)越的尋優(yōu)能力。