基于貪婪策略整體分布優(yōu)化算法的0－1背包問(wèn)題求解

薛翠平，劉靜宜，肖 冬

（1.東北大學(xué)理學(xué)院，遼寧 沈陽(yáng)110004；2.東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng)110004）

0 引言

20世紀(jì)50年代末，Daunts首次提出0－1背包問(wèn)題（Knapsack problem），它是一類(lèi)非常經(jīng)典的Np問(wèn)題［1］，在實(shí)際生活中，網(wǎng)絡(luò)資源分配問(wèn)題、調(diào)運(yùn)裝載、生產(chǎn)安排、信息加密等問(wèn)題都能建出0－1背包問(wèn)題的數(shù)學(xué)模型［2－4］，因此對(duì)該問(wèn)題的研究在理論上和現(xiàn)實(shí)中都具有重要的意義.

0－1背包問(wèn)題可以簡(jiǎn)單描述為：給定n種物品集合N＝｛1，2，…，n｝和一背包.已知物品i的質(zhì)量為wi（＞0），價(jià)值為vi（i＝1，2，…，n），背包容量為c.求最優(yōu)裝包方案（x1，x2，…，xn），xi∈｛0，1｝（xi＝0表示不把第i個(gè)物品放入背包，xi＝1表示把第i個(gè)物品裝入背包），使背包獲得的價(jià)值達(dá)到最大.在選擇裝包物品時(shí)，不能將物品裝入背包多次，也不能將物品分割裝入，數(shù)學(xué)模型如下：

許多學(xué)者對(duì)該問(wèn)題進(jìn)行了行之有效的研究，主要包括適用于小規(guī)模問(wèn)題的分支限界法、遞歸法、回溯法、動(dòng)態(tài)規(guī)劃法等及適用于大規(guī)模問(wèn)題的智能計(jì)算方法（遺傳算法、人工魚(yú)群算法、模擬退火算法、粒子群算法、免疫算法等［5－8］）.目前這方面的文獻(xiàn)很多，每種方法各有優(yōu)劣，但總體來(lái)說(shuō)思想還是比較復(fù)雜.

1 算法

整體分布優(yōu)化算法是粒子群優(yōu)化算法衍生出來(lái)的一種新智能優(yōu)化算法［9］，本文將貪婪思想嵌入到整體分布優(yōu)化算法中，得到基于貪婪策略的整體分布優(yōu)化算法.該算法主要具有結(jié)構(gòu)簡(jiǎn)單、實(shí)現(xiàn)容易、代碼較少和參數(shù)少的優(yōu)點(diǎn).種群相對(duì)價(jià)值較高，程序?qū)?nèi)存要求較小，種群的個(gè)體可以逐一形成，不需要存儲(chǔ).算法的基本思想是首先在定義域范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)初始種群，在種群中找到最優(yōu)粒子，然后直接在最優(yōu)粒子附近由柯西分布產(chǎn)生新的種群，周而復(fù)始，直到達(dá)到最大的迭代次數(shù)為止.決定該算法性能的因素主要產(chǎn)生種群的概率分布形式及其參數(shù)的選取，算法的收斂策略及其對(duì)應(yīng)參數(shù)的選取.根據(jù)貪婪思想，將所有物品按照價(jià)值密度（每種物品的價(jià)值系數(shù)vi與其質(zhì)量wi的比值）從大到小編號(hào).將相應(yīng)的vi和wi按照價(jià)值密度順序大小做相應(yīng)的調(diào)整.新的問(wèn)題記為：

以下內(nèi)容是在新問(wèn)題的基礎(chǔ)上求解的：首先，整體分布式優(yōu)化算法需要編碼，在0－1背包問(wèn)題中只存在裝入和不裝入2種情況，所以算法采用二進(jìn)制編碼，0表示不裝入，1表示裝入，編碼長(zhǎng)度為所需裝入物品的數(shù)量；其次，整體分布優(yōu)化算法需要適應(yīng)度函數(shù)，這里我們把適應(yīng)度函數(shù)定義為0－1背包問(wèn)題的目標(biāo)函數(shù)

整體分布優(yōu)化算法的初始種群通過(guò)下面的子算法1給出.

算法1 初始種群的產(chǎn)生，種群規(guī)模為m，變量的維數(shù)為n

Step 2 將第一步產(chǎn)生的解轉(zhuǎn)換成可行解，思想為貪婪思想，即盡量將下角標(biāo)小的物品裝入背包.比如，當(dāng)前已經(jīng)考慮到第k個(gè)物品，若x［i］［k］＝0，則第k個(gè)物品不裝入背包；若x［i］［k］＝1，考慮將第k個(gè)物品裝入背包，看看是否超重，若不超重，則裝入，否則，該物品不應(yīng)裝入背包，置x［i］［k］＝0.

下面給出完整的整體分布式優(yōu)化算法.

算法2 貪婪策略整體分布優(yōu)化算法

Step 1：初始化.在整個(gè)定義域內(nèi)按照子算法1產(chǎn)生初始種群，同時(shí)初始化柯西分布的半徑為覆蓋整個(gè)定義域的0.5倍，初始化參數(shù).柯西分布尺度參數(shù)γ＝0.1，種群直徑遞減率α＝0.93，停滯次數(shù)β＝9，最大迭代次數(shù)10 000或者種群直徑的標(biāo)度小于0.000 001，種群的規(guī)模為70.

Step 2：計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，找出本次最好的個(gè)體并與上次的最好個(gè)體比較，如果好于上次，則進(jìn)行替換，種群的直徑保持不變.

如果差于上次的最好個(gè)體，則保留上次，同時(shí)使停滯次數(shù)減1，若停滯次數(shù)為0，則使種群直徑縮減為原來(lái)直徑的0.93，同時(shí)使停滯次數(shù)變?yōu)?；若停滯次數(shù)不為0，則保持原來(lái)的種群直徑不變.迭代次數(shù)減1.

Step 3：以已經(jīng)找到的最好個(gè)體的坐標(biāo)為中心，用柯西分布產(chǎn)生新的種群.

Step 4：如果當(dāng)前迭代次數(shù)達(dá)到了預(yù)先設(shè)定的最大次數(shù)或種群直徑的標(biāo)度小于0.000 001，則停止迭代、輸出最優(yōu)解、否則轉(zhuǎn)到Step 2.

2 實(shí)例

為了驗(yàn)證本文算法在求解0－1背包問(wèn)題上的有效性，這里引用文獻(xiàn)［7］中的3個(gè)實(shí)例，3個(gè)例子的規(guī)模從小到大倍增，通過(guò)3個(gè)實(shí)例比較了幾種算法結(jié)果的優(yōu)劣及本文算法點(diǎn)列的收斂趨勢(shì)及速度.

例1 物品個(gè)數(shù)n＝20，物品價(jià)值集合P＝｛92，4，43，83，84，68，92，82，6，44，32，18，56，83，25，96，70，48，14，58｝，物品質(zhì)量 集 合W ＝｛44，46，90，72，9l，40，75，35，8，54，78，40，77，15，61，17，75，29，75，63｝，背包容量C＝878，具體結(jié)果見(jiàn)表1和圖1.

表1 例1中7種算法的最好結(jié)果對(duì)比

例2 物品個(gè)數(shù)n＝50，物品價(jià)值集合P＝｛220，208，195，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｝，物品質(zhì)量集合W ＝｛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，25，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，10，4，4，2，1｝，背包容量C＝1 000，具體結(jié)果見(jiàn)表2和圖2.

圖1 例1中本文算法1次執(zhí)行過(guò)程不同初始點(diǎn)向最優(yōu)點(diǎn)收斂圖形

表2 例2中7種算法的最好結(jié)果對(duì)比

例3 隨機(jī)產(chǎn)生的實(shí)例，n＝100，物品價(jià)值集合P＝｛68，101，125，159，65，146，28，92，143，37，5，154，183，117，96，127，139，113，100，95，12，134，65，112，69，45，158，60，142，179，36，43，107，143，49，6，130，151，102，149，24，155，41，177，109，40，124，139，83，142，116，59，131，107，187，146，73，30，174，113，9l，37，168，175，53，151，125，31，192，138，88，184，110，159，189，147，31，169，192，56，160，138，84，42，151，37，21，22，200，85，135，200，139，189，68，94，84，22，18，115｝，物 品 的 質(zhì) 量 集 合W ＝｛42，35，70，79，63，6，82，62，96，28，92，3，93，22，19，48，72，70，68，36，4，23，74，42，54，48，63，38，24，30，17，9l，89，4l，65，47，91，71，7，94，30，85，57，67，32，45，27，38，19，30，34，40，5，78，74，22，25，7l，78，98，87，62，56，56，32，5l，42，67，8，8，58，54，46，10，22，23，7，14，l，63，11，25，49，96，3，92，75，97，49，69，82，54，19，1，28，29，49，8，11，14｝，背包容量C＝2 010，具體結(jié)果見(jiàn)表3和圖3.

表3 例3中7種算法的最好結(jié)果對(duì)比

圖2 例2中本文算法1次執(zhí)行過(guò)程不同初始點(diǎn)向最優(yōu)點(diǎn)收斂圖形

圖3 例3中本文算法1次執(zhí)行過(guò)程不同初始點(diǎn)向最優(yōu)點(diǎn)收斂圖形

由表1—3可以看出，本文基于貪婪策略整體分布優(yōu)化算法對(duì)3個(gè)算例求解的最好結(jié)果與最優(yōu)解優(yōu)于其他幾個(gè)算法.由圖1—3又可以看出本文算法向最優(yōu)點(diǎn)收斂的速度非?？?

3 結(jié)論

本文程序都是用C＋＋語(yǔ)言編寫(xiě)，每個(gè)實(shí)驗(yàn)均從不同的隨機(jī)初始種群運(yùn)行10次，整體分布優(yōu)化算法與其他算法相比，取得了較好的效果，不但取得了最好的優(yōu)化效果，而且優(yōu)化結(jié)果非常穩(wěn)定，每次優(yōu)化結(jié)果的值變化不大.說(shuō)明整體分布優(yōu)化算法對(duì)0－1背包問(wèn)題是可行的，為有效求解此類(lèi)問(wèn)題提供了一種新的可行方法，同時(shí)也拓展了整體分布優(yōu)化算法的應(yīng)用領(lǐng)域.

［1］SYSLO M M.Discrete optimization algorithm［M］.New Jersey：Prentice－Hall，1983：118－165.

［2］SOOJEONG CHOI，SUNJU PARK，HAK－MAN KIM.The application of the 0－1knapsack problem to the load－shedding problem in microgrid operation［J］.Communications in Computer and Information Science：Control and Automation，and Energy－System Engineering，2011，256（1）：227－234.

［3］NAONORI KAKIMURA，KAZUHISA MAKINO，KENTO SEIMI.Computing knapsack solutions with cardinality robustness［J］.Lecture Notes in Computer Science Algorithms and Computation，2011，7074：693－702.

［4］LAIH C S，LEE J Y，HAM L，et.A linearly shift knapsack public－key cryptosystem［J］.IEEE Journal Selected Areas Communication，1989，7（4）：534－539.

［5］秦玲，白云，章春芳，等.解0－1背包問(wèn)題的蟻群算法［J］.計(jì)算機(jī)工程，2006，3（6）：212－214.

［6］沈顯君，王偉武，鄭波盡，等.基于改進(jìn)的微粒群優(yōu)化算法的0－1背包問(wèn)題求解［J］.計(jì)算機(jī)程，2006（18）：23－24，38.

［7］王秋芬，梁道雷.一種求解0－1背包問(wèn)題的啟發(fā)式遺傳算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2013，30（2）：33－37，57.

［8］賀毅朝，劉坤起，張翠軍，等.求解背包問(wèn)題的貪心遺傳算法及其應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（11）：2655－2657.

［9］余炳輝.整體分布優(yōu)化算法研究及應(yīng)用［M］.成都：西南交通大學(xué)出版社，2012：129－140.