張小萍

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

0 引言

0-1背包問題是一個非常經(jīng)典的組合優(yōu)化問題，這個問題是NP-hard的.在實際應用中，任務調(diào)度、資源分配和材料切割等難解問題都可以轉(zhuǎn)化為0-1背包問題來求解，因此0-1背包問題的求解不論在理論研究和實際應用都具有重要的價值.求解0-1背包問題的算法可以分為兩類，一類是以貪心算法、分支定界法和動態(tài)規(guī)劃法為代表的確定性算法，一類是以智能優(yōu)化為代表的非確定性算法.確定性算法的基本思路是枚舉，即將所有可能的解都進行嘗試比較得到最優(yōu)解，這種算法的時間復雜度呈指數(shù)爆炸，當問題規(guī)模比較大時，難以在有效的時間內(nèi)求得問題的解，因此這類算法只能求解小規(guī)模的0-1背包問題.智能優(yōu)化算法求解0-1背包問題的時間復雜度比較低，可以在多項式時間內(nèi)求解，但一般只能求解得到最優(yōu)解域，不一定獲得精確的最優(yōu)解，這類算法可以用于求解大規(guī)模的0-1背包問題.許多學者在基本的智能優(yōu)化算法基礎上進行改進，提出了能快速求解0-1背包的智能優(yōu)化算法.文獻[1]提出了混沌二進制烏鴉算法(CBCSA),先使用混沌序列初始化種群，使初始種群的分布均勻，然后對個體進行二進制編碼，使用貪心策略來修復和優(yōu)化編碼大大加快了算法的收斂速度.文獻[2]提出了混合蝙蝠算法(HPA)，在基本蝙蝠算法的基礎上進行改進，借鑒遺傳算法中的交叉和反置算子進行位置轉(zhuǎn)移和局部搜索，也結(jié)合了貪心策略來加速算法收斂速度.文獻[3]提出了離散正余弦算法(DSCA)，使用非線性指數(shù)遞減函數(shù)來更新個體步長，避免搜索的盲目性.

Jaya算法[4]是2016年提出的一種新穎的智能優(yōu)化算法，它所需要的參數(shù)相對較少，算法易于理解和實現(xiàn)，能夠獲得較好的尋優(yōu)效果和較快的收斂速度.Jaya算法已經(jīng)被廣泛應用在小型無人直升機航向控制[5]、綠色并行機調(diào)度[6]和無刷直流電機優(yōu)化設計[7]等領域.由于Jaya算法相對于經(jīng)典的智能優(yōu)化算法例如遺傳算法和粒子群算法等出現(xiàn)的時間沒有那么長，因此它的應用領域還相對較少，也還沒有應用到0-1背包問題的求解上.為了更有效地求解0-1背包問題，在基本Jaya算法的基礎上提出具有慣性權(quán)重的Jaya算法，結(jié)合二進制編碼和貪心策略設計了一個適用于求解0-1背包問題的改進算法，并通過仿真實驗的數(shù)據(jù)對比說明提出算法的有效性.

1 0-1背包問題

0-1背包問題是一個有約束條件的優(yōu)化問題，可以描述為：有一個容量為C的背包，有m件物品，每件物品的價值為pi,容積為wi,從m件物品中選擇一些物品裝入背包，使得在不超過背包容量的前提下裝入背包的物品價值最大.若向量Y=(y1,y2,…,ym),yi=0或1，i=1,2,…,m,yi=0表示該物品沒有放入背包，yi=1表示物品放入背包，用數(shù)學模型描述可以表示為：

(1)

2 基本Jaya算法

Jaya在梵語中是“勝利”的意思，算法力求獲得最佳解決方案而取得勝利.算法同時考慮最佳個體和最差個體，在迭代過程中不斷遠離最差個體并逐漸向最佳個體靠近，進而逐步改善解的質(zhì)量.算法的主要迭代公式如公式(2)所示：

(2)

3 帶慣性權(quán)重的Jaya算法(WJaya)

3.1 二進制離散化

(3)

3.2 貪心策略

0-1背包問題是帶有約束條件的，在進行二進制離散化得到的二進制向量有可能因為不滿足約束條件而成為不可行解.目前對不可行解的處理有兩種辦法，一種是使用懲罰函數(shù)，將不可行解的適應度降低，一種是修補不可行解，將它變?yōu)榭尚薪?貪心策略是修補不可行解最常用的方法，一般使用貪心策略要比使用懲罰函數(shù)的方法要好，因為貪心策略在修補不可行解之外還加入了局部優(yōu)化規(guī)則，可以大大加快算法的收斂速度.令ei=pi/wi,那么ei表示每件物品的價值密度比，將物品按照ei從大到小的順序排列，對于一個二進制向量Y=(y1,y2,…，ym)，貪心策略的修復和優(yōu)化分為兩個步驟：

步驟1.將背包初始置為空，對向量Y中相應比特位為1的物品按ei從大到小的順序嘗試加入背包，若新加入物品后總體積沒有超過背包容量則加入，否則不加入背包，將相應的比特位重新置為0.

步驟2.對向量Y中相應比特位為0的物品按ei從大到小的順序嘗試加入背包，若新加入物品后總體積沒有7超過背包容量則加入，將相應的比特位重新置為1；否則不加入背包.

步驟1的作用是將不可行解修復為可行解，將超過背包容量的一部分物品拿出來.步驟2是對解進一步優(yōu)化，在沒有超過背包容量的前提下，優(yōu)先將價值密度比比較高的物品放入背包，提高解的質(zhì)量并加快算法的收斂速度.

3.3 慣性權(quán)重

在粒子群算法[8]中慣性權(quán)重控制著飛行速度的變化，當慣性權(quán)重比較大時，粒子的飛行速度會發(fā)生較大的變化，全局搜索的能力比較強，局部搜索能力比較弱；當慣性權(quán)重比較小時，局部搜索的能力增強，全局搜索的能力會減弱.慣性權(quán)重在整個尋優(yōu)過程中起著平衡全局尋優(yōu)和局部尋優(yōu)能力的作用.在一個好的尋優(yōu)算法中，一般要求在算法迭代初期主要進行全局搜索，以便盡快確定全局最優(yōu)解的大致位置，在迭代后期，主要進行局部搜索，以便提高尋優(yōu)的精度.受粒子群算法的啟發(fā)，為了增強Jaya算法的尋優(yōu)能力，引入了線性遞減的慣性權(quán)重，設置慣性權(quán)重的最大值為βmax，最小值為βmin,T是算法的最大迭代次數(shù)，則慣性權(quán)重β是與當前迭代次數(shù)t呈線性遞減的關系，在迭代初期β比較大，在迭代后期β比較小，其具體公式為：

β=βmax-(βmax-βmin)t/T

(4)

Jaya公式中個體位置更新公式(2)改進為公式(5)：

(5)

3.4 WJaya算法步驟

步驟1.對系統(tǒng)參數(shù)進行初始化.

步驟2.對種群個體初始化并進行二進制離散化得到個體的二進制向量，然后使用貪心策略修復和優(yōu)化二進制向量，計算每個個體的適應度值，求解出當前的最佳個體和最差個體.

步驟3.利用公式(4)(5)對個體進行更新，二進制編碼后使用貪心策略修復和優(yōu)化二進制向量，計算每個個體的適應度值.

步驟4.利用每個個體的適應度值更新最佳個體和最差個體.

步驟5.判斷結(jié)束條件是否滿足，若滿足則輸出最優(yōu)解后結(jié)束，否則回到步驟3.

4 仿真實驗和數(shù)據(jù)分析

為了測試WJaya算法的尋優(yōu)效果，利用文獻[1]提供的維度分別為50至200的0-1背包的7個測試案例進行仿真實驗，分別與CBCSA,HPA和DSCA進行對比分析，其中在WJaya中定義βmax=1.5，βmin=0.6，其他算法的參數(shù)設置按照其原參考文獻的定義.仿真計算實驗的硬件環(huán)境為：操作系統(tǒng)64位的Windows 7,內(nèi)存8G,編程環(huán)境MatlabR2019b.為避免實驗的偶然性，每個算法在每個測試案例中都單獨測試20次，算法的迭代次數(shù)都是200次，種群個體數(shù)為50，分別計算迭代后的最小值、平均值、最大值、方差和命中理論最優(yōu)解的比率，獲得的實驗數(shù)據(jù)如表1所示.

表1 仿真實驗數(shù)據(jù)對比

從表1可以看出，WJaya在KP1，KP2，KP3，KP4和KP6中每次都能找到理論最優(yōu)解，方差全為0,不遜于其他三種算法，而在KP5中，WJaya的平均值是所有算法中最大的，而且找到理論最優(yōu)值的比率也是最高的，達到了40%，方差是所有算法中最小的，在KP7中，只有WJaya以20%的概率找到了理論最優(yōu)解，其他算法都沒有找到，而且WJaya的平均值是所有算法中最大的.

綜上所述，WJaya的整體尋優(yōu)效果要好于其他三種算法，不僅可以有效求解低維度的背包問題，對于高維度的背包問題也能獲得更好的尋優(yōu)效果.

5 總結(jié)

Jaya是一種新興的智能優(yōu)化算法，本文提出了具有慣性權(quán)重的Jaya算法求解0-1背包問題，將種群個體二進制離散化，利用貪心策略修復不可行解并對可行解局部優(yōu)化，結(jié)合使用慣性權(quán)重平衡全局搜索和局部搜索能力.仿真實驗表明，提出算法在低維和高維0-1背包問題中都具有良好的全局尋優(yōu)能力，避免早熟，易于跳出局部最優(yōu)解，找到全局最優(yōu)解.