帶慣性權(quán)重的Jaya算法求解0-1背包問(wèn)題

張小萍

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

0 引言

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

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

1 0-1背包問(wèn)題

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

(1)

2 基本Jaya算法

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

(2)

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

3.1 二進(jìn)制離散化

(3)

3.2 貪心策略

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

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

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

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

3.3 慣性權(quán)重

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

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

(4)

Jaya公式中個(gè)體位置更新公式(2)改進(jìn)為公式(5)：

(5)

3.4 WJaya算法步驟

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

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

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

步驟4.利用每個(gè)個(gè)體的適應(yīng)度值更新最佳個(gè)體和最差個(gè)體.

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

4 仿真實(shí)驗(yàn)和數(shù)據(jù)分析

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

表1 仿真實(shí)驗(yàn)數(shù)據(jù)對(duì)比

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

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

5 總結(jié)

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