張 小 萍

(廣西大學計算機與電子信息學院， 廣西 南寧 530004)

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

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

(1)

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

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

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

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

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

(2)

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

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

(3)

然后，樹木要生成種子，TSA使用了2種機制來生成種子在全局搜索和局部搜索中獲得平衡，利用式(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個種子的第j個元素；Tr，j表示第r棵樹位置的第j個元素；Bj表示當前最優(yōu)樹的位置的第j個元素；αi，j是[-1，1]中的隨機數(shù)，表示步長因子。

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

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

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

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

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

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

2.1 二進制編碼

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

(6)

2.2 貪婪策略

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

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

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

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

2.3 改進策略

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

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

表1 實驗結(jié)果數(shù)據(jù)對比

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

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

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

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

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

4 結(jié) 語

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