論文模擬退火算法

1、1 引言 引言1.1 模擬退火算法的背景模擬退火算法來源于對固體退火過程的模擬，將固體加熱到足夠高的溫度，使分子成隨機排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。根據(jù) Metropolis 準(zhǔn)則,粒子在溫度 T 時趨于平衡的概率為 ，其中 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 開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減 t 的值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表 （Cooling Schedule）控制，包括參數(shù)的初值 t 及衰減因子 、每個 t 值時的迭代 t ?次數(shù) L 和停止條件 S。1

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

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

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

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

7、 S(5)若 ，則接受 作為當(dāng)前的解，即 ；否則計算 的接受概率 0 df ? 2 S 1 2 S S ? 2 S，即隨機產(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ù)若干個新解都沒有接受時終止算法。 (7)

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

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

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