求解0-1背包問(wèn)題的貪心優(yōu)化粒子群算法

周 洋，潘大志

(西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009)

0 引 言

背包問(wèn)題(knapsack problem，KP)是在20世紀(jì)50年代由Dantzing提出來(lái)的一種組合優(yōu)化問(wèn)題，也是一類經(jīng)典的NP難問(wèn)題，在預(yù)算控制、信息加密、投資決策和貨物裝載等領(lǐng)域具有重要的應(yīng)用價(jià)值。而如何快速、簡(jiǎn)潔地求解0-1背包問(wèn)題成為現(xiàn)階段一個(gè)研究目標(biāo)。目前，關(guān)于KP問(wèn)題的求解主要有精確算法和近似算法兩大類。其中，精確算法包括動(dòng)態(tài)規(guī)劃法、分支界定法、回溯法等，這些精確算法盡管能夠找到問(wèn)題的精確解，然而相對(duì)于物品的數(shù)量而言，它的時(shí)間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)，因此并不適合求解大規(guī)模KP問(wèn)題。為了改進(jìn)這一缺陷，許多學(xué)者基于生物的群體智能性，開(kāi)始尋求智能優(yōu)化算法求解KP問(wèn)題，目前的近似算法包含遺傳算法(GA)、粒子群算法(PSO)、蟻群算法(AC)、貪婪算法(GTA)等，這些智能算法在求解大規(guī)模背包問(wèn)題時(shí)表現(xiàn)出明顯的優(yōu)勢(shì)，但是在一定程度上仍有不足之處，因此，對(duì)于KP問(wèn)題的高效求解算法仍然在不斷研究。

粒子群算法(Particle Swarm Optimization，PSO)是由美國(guó)社會(huì)心理學(xué)家James Kennedy和電氣工程師Russell Eberhart于1995年共同提出的一種新的進(jìn)化算法(Evolutionary Algorithm，EA)，它是除了魚群算法、蟻群算法之外的一種新的群體智能優(yōu)化算法[1]。粒子群算法起初源于對(duì)鳥群捕食行為的研究，是一種基于迭代思想的優(yōu)化算法，它的規(guī)則比遺傳算法更簡(jiǎn)易，參數(shù)設(shè)置相對(duì)較少，實(shí)現(xiàn)起來(lái)更加方便。近幾年，國(guó)內(nèi)外很多學(xué)者利用粒子群算法這一優(yōu)越性，將其他算法與其融合并應(yīng)用于背包問(wèn)題等實(shí)際領(lǐng)域中，取得了很好的研究成果。陶新民等人將雙尺度變異策略加入到粒子群算法中，利用此操作更新粒子的飛行速度，在避免算法陷入局部最優(yōu)的同時(shí)，大大提高了最優(yōu)解的精度[2]；張其亮等人考慮到解的多樣性，在粒子群算法中融入模擬退火(SA)思想，設(shè)計(jì)了粒子群——模擬退火算法，進(jìn)一步提高解的質(zhì)量[3]；賀毅朝等人引入了貪心思想，將其與遺傳算法結(jié)合，得到一種基于貪心策略的遺傳算法(GMOGAs),該算法有效地處理了KP問(wèn)題中的非正常編碼個(gè)體，關(guān)于大規(guī)模KP問(wèn)題能較快地找到最優(yōu)解，改善了遺傳算法的求解效率[4]。本文受貪心算法的啟發(fā)，將文獻(xiàn)[4]中的貪心修正算子(GMO)和貪心優(yōu)化算子(GOO)融入到傳統(tǒng)粒子群算法中，設(shè)計(jì)了一種貪心優(yōu)化粒子群算法(GOPSO)，并通過(guò)仿真實(shí)驗(yàn)將該算法與GMOGAs、離散二進(jìn)制粒子群算法(BPSO)、AC在收斂速度、求解效果等方面進(jìn)行比較。

1 背包問(wèn)題的數(shù)學(xué)模型

0-1背包問(wèn)題的一般描述為：假設(shè)有n個(gè)物品g1，g2，…，gn和一個(gè)背包，第j件物品的重量及其價(jià)值分別為wj>0和pj>0(j=1,2,…,n)，背包的最大載重限制為C，選擇部分物品放入背包，使得在不超過(guò)背包最大載重限制的前提下，所放入物品的總價(jià)值最大[5]。為描述n個(gè)物品是否放入背包，定義決策變量xj：

(1)

(2)

(3)

2 基本粒子群算法

在基本粒子群算法中，每一個(gè)解都是搜索空間中的一只鳥，將其抽象為一個(gè)沒(méi)有任何質(zhì)量和體積的粒子，并延伸至D維空間，每一個(gè)粒子有三個(gè)屬性：位置、速度和由目標(biāo)函數(shù)決定的適應(yīng)度。粒子知道自己所在位置和目前為止自己發(fā)現(xiàn)的最好位置(pbest)，這個(gè)視為粒子自身的飛行經(jīng)驗(yàn)。除此之外，粒子還知道目前為止整個(gè)鳥群中所有粒子發(fā)現(xiàn)的最好位置(gbest)，這個(gè)視為粒子同伴的經(jīng)驗(yàn)。粒子通過(guò)自身的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)這二者來(lái)共同調(diào)整自己的飛行方向和速度，從而尋找全局最優(yōu)解[6]。

假設(shè)在一個(gè)D維搜索空間中，有m個(gè)粒子組成了一個(gè)種群X=(X1，X2，…，Xm)，其中第i個(gè)粒子的位置為Xi=(xi1,xi2，…，xiD)，i=1，2，…，m，其速度為Vi=(vi1，vi2，…,viD)，每個(gè)粒子的位置代表可行域中的一個(gè)可行解，解的優(yōu)劣由適應(yīng)度的大小來(lái)衡量。每進(jìn)行一次迭代，粒子便根據(jù)這兩個(gè)“極值”對(duì)自身進(jìn)行一次更新，第i個(gè)粒子迄今為止搜索到的最優(yōu)解為個(gè)體最優(yōu)位置記為：Pi=(Pi1，Pi2，…，PiD)；整個(gè)粒子群即同伴中發(fā)現(xiàn)的最優(yōu)解為全局最優(yōu)位置記為：Pg=(Pg1，Pg2，…，PgD)。

粒子群算法的優(yōu)化模型如下：

(4)

(5)

基本粒子群算法實(shí)現(xiàn)過(guò)程如下：

算法1PSOAlgorithm

Step1 初始化一個(gè)規(guī)模為m的粒子群，隨機(jī)初始化產(chǎn)生各個(gè)粒子的位置和速度；

Step2 由目標(biāo)函數(shù)值計(jì)算每個(gè)粒子的適應(yīng)度；

Step3 對(duì)于每個(gè)粒子而言，將自身的適應(yīng)度值與其經(jīng)歷過(guò)的最好位置Pi的適應(yīng)度值作比較，若較好，則將其設(shè)置為當(dāng)前的最好位置；

Step4 對(duì)于每個(gè)粒子而言，將自身適應(yīng)度值與全局經(jīng)歷的最好位置Pg的適應(yīng)度值作比較，若較好，則將其設(shè)置為當(dāng)前的全局最優(yōu)位置；

Step5 根據(jù)公式(4)和公式(5)對(duì)粒子的速度和位置分別進(jìn)行動(dòng)態(tài)更新；

Step6 如果滿足終止條件(預(yù)設(shè)的迭代次數(shù)或者精度)，則停止搜索，輸出解，否則返回Step 2。

3 貪心優(yōu)化粒子群算法

粒子群算法主要用來(lái)處理連續(xù)優(yōu)化問(wèn)題，而0-1背包問(wèn)題又是一種典型的組合優(yōu)化問(wèn)題，因此，將粒子群算法離散化處理具有重要的理論意義和現(xiàn)實(shí)意義。Kennedy和Eberhart在1997年對(duì)基本PSO算法進(jìn)行了改進(jìn)，提出了一種BPSO算法[8]。這一算法一經(jīng)提出，便引起了國(guó)內(nèi)外研究學(xué)者廣泛的關(guān)注，馬慧民等在此基礎(chǔ)上加入了記憶機(jī)制，加快了算法的收斂速度[9]。因此，對(duì)于0-1背包問(wèn)題的求解，我們可采用BPSO算法的離散化處理方式，這樣便成功解決了編碼的問(wèn)題。同時(shí)考慮到背包問(wèn)題的實(shí)質(zhì)為有約束最優(yōu)化問(wèn)題，如果仍然用傳統(tǒng)粒子群算法去求解，對(duì)于大規(guī)模0-1背包問(wèn)題而言，將會(huì)導(dǎo)致算法中出現(xiàn)大量的非正常編碼個(gè)體，這將不能完全保證解的可行性，且算法求解效率較低?，F(xiàn)階段，對(duì)于非正常編碼個(gè)體的處理方法主要有罰函數(shù)法(penalty function method，PFM)和個(gè)體修正法(individual optimization method，IOM)[10]。受文獻(xiàn)[4]中貪心修正算子(GMO)和貪心優(yōu)化算子(GOO)的啟發(fā)，本文將這兩種算子融入到傳統(tǒng)粒子群算法中，不僅能對(duì)非正常編碼個(gè)體進(jìn)行修正處理，還能夠?qū)λ械膫€(gè)體進(jìn)一步優(yōu)化，便于快速找到最優(yōu)解。

算法2GOPSOAlgorithm

Step1 初始化相關(guān)參數(shù)，設(shè)置種群規(guī)模為m，進(jìn)化代數(shù)k=0，最大迭代次數(shù)為T，慣性權(quán)重為ω，加速因子為c1和c2；

Step2 隨機(jī)初始化每個(gè)粒子的位置和速度：

位置的產(chǎn)生方式為：

(6)

(7)

其中rand()表示[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)，vmin和vmax為速度的最大最小限定值；

Step3 利用GMO和GOO算子對(duì)初始種群進(jìn)行修正與優(yōu)化處理；

Step4 計(jì)算粒子的適應(yīng)度值并更新個(gè)體最優(yōu)和全局最優(yōu)位置：

(8)

(9)

(10)

Step5 利用公式(4)和公式(5)更新粒子的速度和位置，對(duì)更新后的新種群的再次進(jìn)行離散化處理，使其變成0-1矩陣，處理方式如下：

(11)

S(x)為sigmoid函數(shù)，rand()為[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)。

Step6 利用GMO和GOO算子對(duì)更新后的位置進(jìn)行修正與優(yōu)化；

Step7 令k=k+1，當(dāng)k>T時(shí)，則停止迭代，否則返回Step 4；

4 實(shí)驗(yàn)與仿真

為了驗(yàn)證GOPSO算法的高效性以及更好地說(shuō)明算法的求解效果，下面選用了兩組常用的KP實(shí)例，例1數(shù)據(jù)取自文獻(xiàn)[10]，其物品數(shù)為50，例2取自文獻(xiàn)[4]，其物品數(shù)為100。分別獨(dú)立運(yùn)行30次，對(duì)比BPSO算法、文獻(xiàn)[4]中的GMOGAs算法以及AC蟻群算法[11]。仿真實(shí)驗(yàn)所選擇的測(cè)試環(huán)境為：處理器為Intel(R) Xeon(R) CPU E3-1240 v5，3.50 GHz，內(nèi)存為8G，操作系統(tǒng)為Windows10，利用Matlab2014a編程求解，并繪制算法迭代收斂曲線。在GOPSO算法中，設(shè)置慣性權(quán)重w=0.8，加速因子c1=c2=0.7;在AC算法中，設(shè)置信息素重要程度因子α=0.9，啟發(fā)函數(shù)重要程度因子β=1，信息素?fù)]發(fā)因子ρ=0.7，信息素總量Q=1。

例1 物品個(gè)數(shù)N=50，背包載重C=1 000，物品價(jià)值集P[1，…，50]=[220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1]，物品重量集W[1，…，50]=[80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1]。該實(shí)例利用動(dòng)態(tài)規(guī)劃法求解得到最優(yōu)解為3103，對(duì)應(yīng)的總重量為1000，這里設(shè)置種群規(guī)模為50，最大迭代次數(shù)為50，每個(gè)算法獨(dú)立運(yùn)行30次，測(cè)試結(jié)果見(jiàn)表1，算法的迭代收斂曲線如圖1。

表1 4種算法求解例1的計(jì)算結(jié)果

例2 物品個(gè)數(shù)N=100，背包載重C=1 000，物品價(jià)值集P[1，…，100]=[998,997,991,986,978,977,939,936,924,920,911,901,901,885,880,866,866,863,856,842,809,794,792,789,778,767,764,764,763,759,756,747,739,708,707,706,694,693,684,680,676,652,644,640,628,612,607,597,593,570,560,556,556,556,542,538,530,530,520,498,487,466,464,461,459,456,452,443,412,399,391,383,381,378,377,359,353,351,327,317,311,295,289,287,283,269,249,248,235,193,189,189,134,108,93,74,51,48,23,8]；物品重量集W[1，…，100]=[353,180,377,230,87,174,157,390,186,213,56,86,77,215,252,90,360,187,294,379,372,384,93,328,283,99,114,374,383,183,248,164,323,263,266,318,296,196,10,324,128,376,19,280,229,225,217,134,233,35,361,302,166,374,392,319,241,15,384,82,158,322,139,239,110,44,115,23,267,82,30,198,173,70,329,125,220,107,148,159,351,56,17,99,308,396,327,235,213,223,372,376,191,299,304,277,292,391,120,37]；該實(shí)例利用動(dòng)態(tài)規(guī)劃法得出的最優(yōu)解為40 627，對(duì)應(yīng)的總重量為9 793，設(shè)置種群規(guī)模為100，最大迭代次數(shù)為50，測(cè)試結(jié)果見(jiàn)表2，算法的迭代收斂圖見(jiàn)圖2。

表2 4種算法求解例2的計(jì)算結(jié)果

分析表1、表2以及圖1、圖2可知，本文提出的GOPSO算法與文獻(xiàn)[4]中的GMOGAs算法求解性能基本一致，在最大迭代次數(shù)內(nèi)，均能找到問(wèn)題的最優(yōu)解，但是從收斂速度以及平均進(jìn)化代數(shù)來(lái)看，GOPSO 算法較GMOGAs算法收斂得更快。明顯地，對(duì)于大規(guī)模0-1背包問(wèn)題的求解，不論是GOPSO算法還是GMOGAs算法，在總體上關(guān)于解的質(zhì)量以及收斂速度等方面均遠(yuǎn)遠(yuǎn)優(yōu)于BPSO算法和AC算法，這足以說(shuō)明本文提出的貪心優(yōu)化粒子群算法是一種比BPSO算法更高效的新方法，更加適合于求解大規(guī)模背包問(wèn)題。

5 結(jié)束語(yǔ)

基于貪心的思想，將GMO算子和GOO算子融入到基本粒子群算法中，設(shè)計(jì)了貪心優(yōu)化粒子群算法，給出該算法的實(shí)現(xiàn)流程，并將該算法應(yīng)用于0-1背包問(wèn)題的求解。通過(guò)對(duì)文獻(xiàn)中的兩個(gè)實(shí)例進(jìn)行仿真實(shí)驗(yàn)，測(cè)試結(jié)果表明：GOPSO算法表現(xiàn)出了良好的尋優(yōu)能力以及較快的收斂速度，并且成功率較高，大大減少了算法的運(yùn)行時(shí)間，這充分說(shuō)明了新算法的高效性與可行性。