論文模擬退火算法

1、1 引言 引言1.1 模擬退火算法的背景模擬退火算法來(lái)源于對(duì)固體退火過(guò)程的模擬，將固體加熱到足夠高的溫度，使分子成隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。根據(jù) Metropolis 準(zhǔn)則,粒子在溫度 T 時(shí)趨于平衡的概率為 ，其中 E 為溫度 T 是的內(nèi)能， 為內(nèi)能的改變量，k 為/( ) E kT e?? E ?Boltzman 常數(shù)，用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E 模擬為目標(biāo)函數(shù)值

2、f，溫度 T 演化成控制參數(shù) t，及可得到解組合優(yōu)化問題的模擬退火算法：由初始解 的控制參數(shù) i初始值 t 開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減 t 的值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表 （Cooling Schedule）控制，包括參數(shù)的初值 t 及衰減因子 、每個(gè) t 值時(shí)的迭代 t ?次數(shù) L 和停止條件 S。1

3、.2 背包問題的基本概念背包問題（Knapsack Problem）是一個(gè) NP 完全問題，在實(shí)際的工程中有著廣泛的應(yīng)用，目前求解背包問題的主要方法有模擬退火算法、貪婪算法、遺傳算法等，還包括許多算法。背包問題（Knapsack Problem）是指假定某人擁有大量的物品，重量各不相同，此人通過(guò)秘密的選擇一部分物品并將它們放到背包中來(lái)加密消息，例如給定 種物品和 1 個(gè)背包，知道某物品的重量和價(jià)值，并且背包的最大容量也是 n已知的，要求

4、選擇物品裝入背包中，是選中的物品的總重量不超過(guò)背包的最大容量，但裝入背包的物品的總價(jià)值最大。它是一種典型的組合優(yōu)化問題，已證 明背包問題是一個(gè) NP-hard 問題，基于智能優(yōu)化算法求解背包問題，是近年來(lái) 剛剛興起的熱門問題。在我們的現(xiàn)實(shí)生活中存在著大量的多目標(biāo)優(yōu)化問題，對(duì)于背包問題（Knapsack Problem）：在實(shí)際中經(jīng)常要同時(shí)考慮多個(gè)目標(biāo)，如價(jià)值 最大、容量最大等多方面的因素。目標(biāo)之間往往出現(xiàn)沖突性。這就需要我們?nèi)绾卧诙鄠€(gè)目

5、標(biāo)中尋找一個(gè)合理的解去解決一個(gè)比較復(fù)雜的問題。1.3 發(fā)展趨勢(shì)背包問題在國(guó)外研究得比較早，范圍也比較廣,Dantzing 在 20 世紀(jì) 50 年代第一個(gè)進(jìn)行了開放性研究，利用貪婪算法求得了背包問題最優(yōu)解的上界。1974 年，horowitz 和 salmi 利用分支界限法解答背包問題，并提出了背包問題的可分性，指出了求解該問題的一條新途徑。接著，balas 和 zemel 提出了 背包問題的“核”思想，是背包問題的研究有了較大的進(jìn)展。

6、十九世紀(jì)九十年代以后，隨著生物仿生技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，就如遺傳算法已經(jīng)在背包問題上 得到較好的應(yīng)用，而蟻群算法等仿生算法也在組合優(yōu)化問題上得到了不錯(cuò)的應(yīng) 用。背包問題（Knapsack Problem）是運(yùn)籌學(xué)中的一個(gè)經(jīng)典組合優(yōu)化問題，也是(4)計(jì)算 的增量 ,其中 是 代價(jià)函數(shù)。 2 S '2 1 ( ) ( ) t df f S f S ? ? ? ? 1 ( ) f S 1

7、 S(5)若 ，則接受 作為當(dāng)前的解，即 ；否則計(jì)算 的接受概率 0 df ? 2 S 1 2 S S ? 2 S，即隨機(jī)產(chǎn)生(0,1)區(qū)間上均勻分布 ,若 exp( / ) df T ? rand exp( / ) df T rand ? ?，也接受 作為新的當(dāng)前解， ；否則保留當(dāng)前解 2 S 1 2 S S ? 1 S(6)如果滿足終止條件則輸出當(dāng)前作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒有接受時(shí)終止算法。 (7)

8、 逐漸減少，且 ，然后轉(zhuǎn)第 2 步。 T 0 T ?2.1.2 模擬退火算法的步驟第一部是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法好時(shí)，通常選擇有當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的領(lǐng)域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函

9、數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被接受，判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是 Metropolis 準(zhǔn)則：若 則接受 作為新的當(dāng)前解 ，否則以概率 ' 0 t ? ? ' S S接受 作為新的當(dāng)前解 。 exp( '/ ) t T ?? ' S S第四步是當(dāng)新解被確定接受時(shí)，用心接代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換

10、部分得以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)即可。此時(shí)，當(dāng)前解 實(shí)現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪實(shí)驗(yàn)。而當(dāng)前解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪實(shí)驗(yàn)。模擬圖火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài) (是算法迭代的 S起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸進(jìn)收斂性，已在理論上被證明是一種以概率 1 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。2.2 背包問題的描述背包問題(Knapsack Problem)是經(jīng)典的 NP 完全