姚若俠 薛丹 謝娟英 范虹

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

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

中圖分類號：TP301

文獻標志碼：A

文章編號：1000-5641（2020）06-0090-09

0引言

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

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

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

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

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

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

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

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

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

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

設10個物品的價值集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=（1011100010），粒子X優(yōu)化前，重量為275（>C），價值為196.算法1執(zhí)行后，粒子X=（1110100010），重量為247（196）.

1.3模擬退火策略

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

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

2仿真實驗

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

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

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

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

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

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

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

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

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

3結(jié)束語

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

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