模擬退火算法解決0-1背包問題的研究與實(shí)現(xiàn)

晏 杰（武夷學(xué)院，福建 武夷山 354300）

1 0-1背包問題描述

在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2，W3……Wn，與之相對(duì)應(yīng)的價(jià)值為P1,P2,P3……Pn.求出獲得最大價(jià)值的解決方案.需要說明的是所有的體積值均為整數(shù),也就是說,每件物品只有取或者不取兩種可能,不可以分解物品.0-1背包問題可以形式化地描述為：

其中：式(1)為目標(biāo)函數(shù)，式(2)和(3)為約束條件，X為一個(gè)n維的向量，ci表示第i個(gè)物品的價(jià)值，wi表示第i個(gè)物品的重量，n為物品的數(shù)量.如果第i個(gè)物品放入背包中，則xi=1，否則xi=0.問題的目標(biāo)就是要在背包盡量裝滿但又不超過其容量的情況下，使所裝入背包中的物體價(jià)值最大.

2 模擬退火算法

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小.根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù).用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程.退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S.

2.1 退火算法思想

(1)初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L.

(2)對(duì) k=1，……，L做第(3)至第 6步：

(3)產(chǎn)生新解S'

(4)計(jì)算增量Δt'=C(S')-C(S)，其中C(S)為評(píng)價(jià)函數(shù)

(5)若Δt'<0則接受S'作為新的當(dāng)前解，否則以概率exp(-Δt'/T)接受S'作為新的當(dāng)前解.

(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序.

終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法.

(7)T逐漸減少，且T->0，然后轉(zhuǎn)第2步.

模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟：

第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響.

第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差.因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算.事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法.

第三步是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則:若Δt'<0則接受S'作為新的當(dāng)前解S，否則以概率exp(-Δt'/T)接受S'作為新的當(dāng)前解S.

第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可.此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代.可在此基礎(chǔ)上開始下一輪試驗(yàn).而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn).

2.2 退火算法解決0-1背包關(guān)鍵代碼

模擬退火算法解決0-1背包問題的代碼較長(zhǎng),這里給出關(guān)鍵的代碼如下:

2.3 結(jié)果分析

在此假設(shè)鏈長(zhǎng)系數(shù)為3，截止溫度為0.001，退溫系數(shù)為0.80，溫度初值為200，則運(yùn)行結(jié)果為0000110011，重量為7.63，價(jià)值為29.98，時(shí)間為5毫秒，如下圖所示：

3 參數(shù)研究

模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點(diǎn)：

4.1 溫度T的初始值設(shè)置問題.

溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響.實(shí)際應(yīng)用過程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整.

4.2 退火速度問題.

模擬退火算法的全局搜索性能也與退火速度密切相關(guān).一般來說，同一溫度下的“充分”搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間.實(shí)際應(yīng)用中，要針對(duì)具體問題的性質(zhì)和特征設(shè)置合理的退火平衡條件.

4.3 溫度管理問題.

溫度管理問題也是模擬退火算法難以處理的問題之一.實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問題，常采用如下所示的降溫方式：T(t+1)＝k×T(t),式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù).

〔1〕宋海生，傅仁毅.求解多背包問題的混合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2009（20）.

〔2〕喻學(xué)才，張?zhí)镂?多維背包問題的一個(gè)蟻群優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào)，2008（05）.

〔3〕龔文引，蔡之華.一種新的求解0-1背包問題的自適應(yīng)算法[J].微型機(jī)與應(yīng)用，2005（12）.

〔4〕毅朝.求解多選擇背包問題的改進(jìn)差分演化算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2007（09）.