求解0-1背包問(wèn)題的混合粒子群改進(jìn)算法研究

姚若俠 薛丹 謝娟英 范虹

摘要：針對(duì)0-1背包問(wèn)題求解，將離散二進(jìn)制粒子群優(yōu)化算法、貪心優(yōu)化策略和模擬退火算法有機(jī)結(jié)合，提出了一種改進(jìn)算法：帶貪心優(yōu)化的混合粒子群和模擬退火算法.基于新算法，完成了9組不同維度數(shù)據(jù)的仿真實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，BPSOSA-CGOO算法能夠以較小的種群規(guī)模及迭代次數(shù)實(shí)現(xiàn)0-1背包問(wèn)題的有效求解，并在問(wèn)題維度為20維的測(cè)試數(shù)據(jù)中找到優(yōu)于已知最優(yōu)解的解;獨(dú)立重復(fù)實(shí)驗(yàn)驗(yàn)證了，無(wú)論對(duì)于低維度還是高維度背包問(wèn)題，BPSOSA-CGOO算法均能以較高概率命中最優(yōu)解，提高了高維度背包問(wèn)題求解的穩(wěn)定性和可靠性.

關(guān)鍵詞：背包問(wèn)題;粒子群優(yōu)化算法;貪心優(yōu)化策略;模擬退火算法

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1000-5641（2020）06-0090-09

0引言

0-1背包問(wèn)題（0-1 Knapsack Problem，0-1 KP）是經(jīng)典的組合優(yōu)化問(wèn)題，也是—個(gè)NP（Non-deterministicPolynomial）-難問(wèn)題.背包問(wèn)題具有深遠(yuǎn)的理論意義和重要的實(shí)踐應(yīng)用研究?jī)r(jià)值，自20世紀(jì)50年代被Dantzig提出以來(lái)，引起了國(guó)內(nèi)外學(xué)者極大的研究熱情，且已被廣泛應(yīng)用于投資決策、資源分配和貨物裝載等金融和工業(yè)領(lǐng)域.

0-1 KP簡(jiǎn)要描述如下：共有N種待選定的物品，每種物品只有1個(gè)且不可分割，物品j的價(jià)值為Pj，重量為hj，只有1個(gè)背包且能容納物品的總重量為C問(wèn)題：如何選擇裝入這個(gè)背包的物品，使背包中裝入物品的總重量不超過(guò)C且總價(jià)值最大？0-1 KP的數(shù)學(xué)模型公式為

目前求解0-1 KP的主要算法大致分為精確算法、群智能優(yōu)化算法、混合算法這3類.精確算法主要包括貪心算法（Greedy Algorithm，GA）、動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）算法、分支界定（Branch and Bound，BB）算法群智能優(yōu)化算法主要包括遺傳算法、煙花算法（Fireworks Algorithm，F(xiàn)A）、粒子群優(yōu)化算法等.混合算法主要包括貪心遺傳算法、貪心螢火蟲算法、基于直覺(jué)模糊熵的粒子群-模擬退火算法、貪心優(yōu)化粒子群算法等.文獻(xiàn)[11]應(yīng)用貪心算法、動(dòng)態(tài)規(guī)劃算法、分支界定算法求解0-1 KP，其實(shí)驗(yàn)結(jié)果表明，貪心算法高效但卻不一定能給出最優(yōu)解;在問(wèn)題維數(shù)較低的情況下，動(dòng)態(tài)規(guī)劃、分支界定的算法性能較好，但隨著問(wèn)題規(guī)模的增大，時(shí)間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)，同時(shí)動(dòng)態(tài)規(guī)劃算法的內(nèi)存消耗也很大，這意味著它們對(duì)大規(guī)模0-1 KP的解決只是理論層面的.為了以較低的時(shí)間和空間消耗來(lái)較優(yōu)地解決高維度背包問(wèn)題，大量學(xué)者將目光轉(zhuǎn)移向了群智能優(yōu)化算法及其混合算法.文獻(xiàn)[8]應(yīng)用遺傳算法等6個(gè)算法，求解大量的0-1 KP測(cè)試數(shù)據(jù)，實(shí)驗(yàn)結(jié)果表明，混合遺傳算法和模擬退火算法性能較優(yōu).文獻(xiàn)[21-22]提出了貪心遺傳算法（GGA），并對(duì)文獻(xiàn)[11]中的貪心策略進(jìn)行了改進(jìn)，提出了貪心修正算子（CMO）和貪心優(yōu)化算子（COO），使得應(yīng)用遺傳算法在求解0-1 KP時(shí)不僅可以對(duì)不合法的解進(jìn)行校正，也可以對(duì)合法解給出優(yōu)化，有效提升了種群在進(jìn)化過(guò)程中優(yōu)質(zhì)解所占的比率，增強(qiáng)了遺傳算法求解0-1 KP的能力，拓展了應(yīng)用群智能優(yōu)化算法求解組合優(yōu)化問(wèn)題的思路.文獻(xiàn)[24]結(jié)合粒子群優(yōu)化算法和模擬退火策略，提出了基于直覺(jué)模糊熵的粒子群-模擬退火算法，通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性，而且，該算法對(duì)于較小規(guī)模的背包問(wèn)題能夠以100%的概率命中已知解.文獻(xiàn)[25]結(jié)合粒子群優(yōu)化算法、貪心修正算子和貪心優(yōu)化算子，提出了貪心優(yōu)化粒子群算法，通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法具有良好的尋優(yōu)能力，并且可以快速收斂至最優(yōu)解.以上研究成果顯示，混合群智能優(yōu)化算法對(duì)求解0-1 KP具有良好的表現(xiàn)，由此啟發(fā)本文嘗試采用帶貪心優(yōu)化的混合粒子群和模擬退火（BPSOSA-CGOO）算法來(lái)求解0-1 KP.

基于對(duì)0-1 KP現(xiàn)狀的研究和分析，本文結(jié)合離散二進(jìn)制粒子群優(yōu)化算法（BPSO）可以快速收斂至潛在最優(yōu)解和對(duì)于組合優(yōu)化問(wèn)題有廣泛適應(yīng)性的特點(diǎn)、貪心修正算子（GMO）和貪心優(yōu)化算子（GOO）能夠在種群進(jìn)化過(guò)程中提升優(yōu)質(zhì)解占有率的特點(diǎn)、模擬退火算法能夠概率性地跳出局部極值等特點(diǎn)，提出了帶貪心優(yōu)化的混合粒子群和模擬退火算法（BPSOSA-CGOO），拓展了求解0-1 KP更為穩(wěn)定和有效的算法集.通過(guò)對(duì)文獻(xiàn)[24]中的背包數(shù)據(jù)進(jìn)行測(cè)試，BPSOSA-CGOO算法使求解0-1 KP的尋優(yōu)能力和命中已知最優(yōu)解的概率得到了有效的提高.下文對(duì)BPSOSA-CGOO算法進(jìn)行詳細(xì)介紹.

1帶貪心優(yōu)化的混合粒子群和模擬退火算法

本文提出的BPSOSA-CGOO算法，主要在離散二進(jìn)制粒子群優(yōu)化算法（BPSO）的基礎(chǔ)上進(jìn)行了以下兩個(gè)優(yōu)化.

（1）在種群初始化及更新粒子后，本文調(diào)用合并的貪心優(yōu)化算子對(duì)更新后的粒子進(jìn)行優(yōu)化，以此保證在種群合法性的基礎(chǔ)上價(jià)值最大，使得種群在進(jìn)化過(guò)程中優(yōu)質(zhì)解的占比增高，進(jìn)而提升種群的尋優(yōu)能力.

（1）按照u（p_i）由大到小的順序?qū)αＷ右堰x擇的商品進(jìn)行檢查，如果已選擇的商品加入背包后，不大于背包總承重，則加入背包，否則，取出該商品.

（2）按照u（p_i）由大到小的順序?qū)αＷ游催x擇的商品進(jìn)行嘗試性地加入背包，如果未選擇的商品加入背包后，不大于背包總承重，則加入背包，否則，不加入.

為了更清楚地描述BPSOSA-CGOO算法中CGOO算子的優(yōu)化過(guò)程，本文以1個(gè)10維背包問(wèn)題為例，列舉某不合法粒子X(jué)經(jīng)過(guò)CGOO算子優(yōu)化后的結(jié)果，結(jié)果如下.

設(shè)10個(gè)物品的價(jià)值集P={55，10，47，5，4，50，8，61，85，87），重量集H={95，4，60，32，23，72，80，62，65，46），背包最大容量C=269，粒子X(jué)=（1011100010），粒子X(jué)優(yōu)化前，重量為275（>C），價(jià)值為196.算法1執(zhí)行后，粒子X(jué)=（1110100010），重量為247（196）.

1.3模擬退火策略

模擬退火操作的基本思想由Metropolis于1953年提出，1983年首次應(yīng)用于解決組合優(yōu)化問(wèn)題.目前，模擬退火操作有許多改進(jìn)版本，本文選用最基本的模擬退火策略，即在降溫的過(guò)程中根據(jù)馬爾科夫鏈長(zhǎng)，重復(fù)執(zhí)行如下迭代過(guò)程：①產(chǎn)生新解;②計(jì)算價(jià)值差;③判斷是否接收新解;④接收或舍棄;⑤返回①.

BPSOSA-CGOO算法不僅可以保證粒子在進(jìn)化過(guò)程中都合法，提高種群中優(yōu)質(zhì)解的占有率，而且還可以通過(guò)模擬退火操作概率性地修改個(gè)體極值，有助于種群在進(jìn)化過(guò)程中趨于全局最優(yōu).BPSOSA-CGOO算法的程序流程如圖2所示.

2仿真實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境為，Win 10操作系統(tǒng)，Intel Core（TM）i7-8550U CPU處理器，8GB內(nèi)存，Python3.5編程語(yǔ)言，PyCharm2018.1.4開發(fā)環(huán)境.實(shí)驗(yàn)參數(shù)設(shè)置為，種群規(guī)模=問(wèn)題維數(shù)/2，迭代次數(shù)=200，學(xué)習(xí)因子c1=c2=1，慣性系數(shù)ω=0.9，速度的最大值V_max=6，初始溫度T₀=1000，馬爾科夫鏈長(zhǎng)L=20，降溫因子α=0.99，冷凍點(diǎn)f=0.0001.采用文獻(xiàn)[24]中的9組不同維度的測(cè)試數(shù)據(jù)，對(duì)9組測(cè)試數(shù)據(jù)各執(zhí)行1次，實(shí)驗(yàn)結(jié)果見表1，其中進(jìn)化次數(shù)代表收斂至已知最優(yōu)解的進(jìn)化次數(shù).

表1實(shí)驗(yàn)結(jié)果揭示，BPSOSA-CGOO算法對(duì)于9組不同維度的測(cè)試用例，均能搜索到已知最優(yōu)解，且測(cè)試數(shù)據(jù)3（表1加粗部分）搜索到的最優(yōu)解（1042（價(jià)值）878（重量））優(yōu)于文獻(xiàn)[24]中的解（1024（價(jià)值）871（重量））.

為了進(jìn)一步分析算法的穩(wěn)定性和有效性，本文在實(shí)驗(yàn)參數(shù)設(shè)置不變的基礎(chǔ)上，對(duì)相同的測(cè)試數(shù)據(jù)，分別執(zhí)行了20次獨(dú)立重復(fù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表2.表2中，S_SN代表成功實(shí)驗(yàn)的次數(shù)，A_VIN代表成功實(shí)驗(yàn)中平均進(jìn)化代數(shù).假定認(rèn)為命中已知最優(yōu)解為一次成功實(shí)驗(yàn)，則A_VIN的計(jì)算公式為其中，E_i為第i次成功實(shí)驗(yàn)對(duì)應(yīng)的進(jìn)化代數(shù).

表2所示的實(shí)驗(yàn)結(jié)果揭示了，在9組不同測(cè)試數(shù)據(jù)的20次獨(dú)立重復(fù)實(shí)驗(yàn)結(jié)果中，有7組實(shí)驗(yàn)命中最優(yōu)解的次數(shù)都為20次，標(biāo)準(zhǔn)差為0;測(cè)試數(shù)據(jù)5命中最優(yōu)解的次數(shù)為18次，標(biāo)準(zhǔn)差為2.48;測(cè)試數(shù)據(jù)8命中最優(yōu)解1次，標(biāo)準(zhǔn)差為13.82.這說(shuō)明：①BPSOSA-CGOO算法對(duì)于大多數(shù)測(cè)試數(shù)據(jù)能以較高的概率命中最優(yōu)解，體現(xiàn)了有效性;②標(biāo)準(zhǔn)差是反映數(shù)據(jù)集離散程度的統(tǒng)計(jì)量，表2中的標(biāo)準(zhǔn)差數(shù)據(jù)表明，BPSOSA-CGOO算法具有較強(qiáng)的穩(wěn)定性.

為了更加全面地分析BPSOSA-CGOO算法求解0-1背包問(wèn)題的穩(wěn)定性，本文基于文獻(xiàn)[25]中的算法思想對(duì)GOPSO算法進(jìn)行了Python實(shí)現(xiàn)，并對(duì)上述9組不同維度的測(cè)試用例分別執(zhí)行了20次獨(dú)立重復(fù)實(shí)驗(yàn).實(shí)驗(yàn)環(huán)境為本文上述環(huán)境;實(shí)驗(yàn)參數(shù)設(shè)置為，種群規(guī)模=問(wèn)題維數(shù)/2，迭代次數(shù)=200，學(xué)習(xí)因子c1=c2=1，慣性系數(shù)ω=0.9，速度最大值V_max=6.本文所提的BPSOSA-CGOO算法命中最優(yōu)解的次數(shù)與IFEPSOSA算法和GOPSO算法的對(duì)比見圖3.

圖3表明，GOPSO算法、BPSOSA-CGOO算法除測(cè)試數(shù)據(jù)8以外，均能以較高的次數(shù)命中最優(yōu)解.針對(duì)GOPSO和BPSOSA-CGOO算法在測(cè)試數(shù)據(jù)8上表現(xiàn)出的特殊情況，本文做了分析并給出先驗(yàn)推測(cè)：這很可能是由種群規(guī)模引起的.故本文嘗試將種群規(guī)模=問(wèn)題維數(shù)/2修改為與文獻(xiàn)[24]一致，即種群規(guī)模=100，其余參數(shù)保持不變，對(duì)測(cè)試數(shù)據(jù)8執(zhí)行20次獨(dú)立重復(fù)實(shí)驗(yàn)，執(zhí)行結(jié)果見表3和圖4，命中最優(yōu)解次數(shù)與文獻(xiàn)[24]中IEFPSOSA算法的對(duì)比見圖5.

表3所示的實(shí)驗(yàn)結(jié)果揭示，BPSOSA-CGOO算法的最差解、平均值、標(biāo)準(zhǔn)差均優(yōu)于GOPSO算法.圖4表明，BPSOSA-CGOO算法在20次獨(dú)立重復(fù)實(shí)驗(yàn)中找到的實(shí)驗(yàn)最優(yōu)解的數(shù)值波動(dòng)較小，較為穩(wěn)定.由圖5可以看出，BPSOSA-CGOO算法在獨(dú)立重復(fù)實(shí)驗(yàn)中命中已知最優(yōu)解13次，體現(xiàn)了該算法在命中最優(yōu)解的次數(shù)上的優(yōu)勢(shì).

此外，為了充分驗(yàn)證BPSOSA-CGOO算法在高維度背包問(wèn)題求解上的穩(wěn)定性，本文對(duì)文獻(xiàn)[16]中100維的背包算例進(jìn)行了10次獨(dú)立重復(fù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表4.表4所示的實(shí)驗(yàn)結(jié)果揭示，雖然BPSOSA-CGOO算法的實(shí)驗(yàn)最優(yōu)解稍小于文獻(xiàn)[16]中的已知解，但獨(dú)立重復(fù)實(shí)驗(yàn)的標(biāo)準(zhǔn)差遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[16]中的147，實(shí)驗(yàn)最差解大于文獻(xiàn)[16]中的7753，且隨著種群規(guī)模和迭代次數(shù)的增大，BPSOSA-CGOO算法標(biāo)準(zhǔn)差隨之減小，最差解也在增大.這表明，對(duì)于高維度背包問(wèn)題，BPSOSA-CGOO算法能夠以較高的穩(wěn)定性找出較優(yōu)解.

上述實(shí)驗(yàn)數(shù)據(jù)及結(jié)果表明，BPSOSA-CGOO算法不僅可以有效求解0-1背包問(wèn)題，而且能夠在種群規(guī)模、迭代次數(shù)均較小的條件下，對(duì)高維度背包問(wèn)題以較高概率尋得最優(yōu)解/較優(yōu)解，表現(xiàn)出了較強(qiáng)的穩(wěn)定性和可靠性.

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

本文基于對(duì)離散二進(jìn)制粒子群優(yōu)化算法的兩個(gè)優(yōu)化，提出了帶貪心優(yōu)化的混合粒子群和模擬退火算法——BPSOSA-CGOO算法，采用該算法求解0-1背包問(wèn)題，完成了9組不同維度背包數(shù)據(jù)的測(cè)試后，得到了以下結(jié)論：①BPSOSA-CGOO算法對(duì)于9組背包數(shù)據(jù)均能以較小的種群和進(jìn)化代數(shù)找到已知最優(yōu)解，且背包數(shù)據(jù)3找到的解優(yōu)于已知最優(yōu)解;②在獨(dú)立重復(fù)實(shí)驗(yàn)中，有7組實(shí)驗(yàn)以100%的概率命中最優(yōu)解，其余兩組命中最優(yōu)解的概率分別為90%和65%.

BPSOSA-CGOO算法在本文實(shí)驗(yàn)環(huán)境下，無(wú)論對(duì)于高維度還是低維度的測(cè)試數(shù)據(jù)，均能以較高的概率命中最優(yōu)解，在求解0-1 KP的穩(wěn)定性、可靠性方面，性能均獲得明顯提升.此外，谷鵬等根據(jù)粒子群優(yōu)化算法提出了一種改進(jìn)的粒子群優(yōu)化算法，并結(jié)合擴(kuò)展的卡爾曼濾波跟蹤算法，提高了目標(biāo)跟蹤的精度，該算法雖然能夠隨機(jī)搜索潛在最優(yōu)解，但是容易陷入局部最優(yōu)的特點(diǎn).李鵬等通過(guò)將粒子群優(yōu)化算法與遺傳算法相結(jié)合，在種群中進(jìn)行交叉、變異等操作提高了種群多樣性，克服了粒子群優(yōu)化算法容易陷入局部極值的缺點(diǎn)，并將其成功應(yīng)用于無(wú)人機(jī)航路規(guī)劃中，取得了良好的應(yīng)用效果.郭玉潔等提出了一種雙種群協(xié)同多目標(biāo)粒子群優(yōu)化算法，將其應(yīng)用于油田開采，以實(shí)現(xiàn)油田開采利潤(rùn)最大化為目標(biāo)，并應(yīng)用于油田開采優(yōu)化模型，取得了良好的效果.后續(xù)也可以將該算法應(yīng)用到折扣背包問(wèn)題、動(dòng)靜態(tài)背包問(wèn)題、機(jī)器人路線規(guī)劃、油田開采模型優(yōu)化等的實(shí)際工作中，使其發(fā)揮更大更廣泛的實(shí)際應(yīng)用價(jià)值.