模擬退火算法

模擬退火算法

交通與車輛工程學(xué)院剛憲約模擬退火算法

模擬退火算法(simulatedannealing,簡稱SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等將其用于組合優(yōu)化。SA算法是基于MonteCarlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)解。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。模擬退火算法1.物理退火過程和Metropolis準則簡單而言，物理退火過程由以下三部分組成：⑴加溫過程。其目的是增強粒子的熱運動，使其偏離平衡位置。當溫度足夠高時，固體將溶解為液體，從而消除系統(tǒng)原先可能存在的非均勻態(tài)，使隨后進行的冷卻過程以某一平衡態(tài)為起點。溶解過程與系統(tǒng)的熵增過程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大。模擬退火算法⑵等溫過程。物理學(xué)的知識告訴我們，對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行，當自由能達到最小時，系統(tǒng)達到平衡態(tài)。⑶冷卻過程。目的是使粒子的熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。模擬退火算法Metropolis等在1953年提出了重要性采樣法，即以概率接受新狀態(tài)。具體而言，在溫度t,由當前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為，若則接受新狀態(tài)j為當前狀態(tài)；否則，若概率大于區(qū)間內(nèi)的隨機數(shù)則仍舊接受新狀態(tài)j為當前狀態(tài)，若不成立則保留i為當前狀態(tài)，其中k為Boltzmann常數(shù)。模擬退火算法這種重要性采樣過程在高溫下可接受與當前狀態(tài)能量差較大的新狀態(tài)，而在低溫下基本只接受與當前能量差較小的新狀態(tài)，而且當溫度趨于零時，就不能接受比當前狀態(tài)能量高的新狀態(tài)。這種接受準則通常稱為Metropolis準則。模擬退火算法2模擬退火算法的基本思想和步驟1983年Kirkpatrick等意識到組合優(yōu)化與物理退火的相似性，并受到Metropolis準則的啟迪，提出了模擬退火算法。模擬退火算法是基于MonteCarlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理退火過程與組合優(yōu)化之間的相似性，SA由某一較高初溫開始，利用具有概率突跳特性的Metropolis抽樣策略在解空間中進行隨機搜索，伴隨溫度的不斷下降重復(fù)抽樣過程，最終得到問題的全局最優(yōu)解。模擬退火算法標準模擬退火算法的一般步驟可描述如下：⑴給定初溫，隨機產(chǎn)生初始狀態(tài)，令；⑵Repeat:①Repeat

產(chǎn)生新狀態(tài)；模擬退火算法

Until抽樣穩(wěn)定準則滿足；②退溫，并令；

Until算法終止準則滿足；⑶輸出算法搜索結(jié)果。模擬退火算法3.模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)定從算法流程上看，模擬退火算法包括三函數(shù)兩準則，即狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準則和外循環(huán)終止準則，這些環(huán)節(jié)的設(shè)計將決定SA算法的優(yōu)化性能。此外，初溫的選擇對SA算法性能也有很大影響。模擬退火算法⑴狀態(tài)產(chǎn)生函數(shù)設(shè)計狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）的出發(fā)點應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。通常，狀態(tài)產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。模擬退火算法⑵狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的形式不同。設(shè)計狀態(tài)接受概率，應(yīng)該遵循以下原則：①在固定溫度下，接受使目標函數(shù)值下降的候選解的概率要大于使目標值上升的候選解的概率；模擬退火算法②隨溫度的下降，接受使目標函數(shù)值上升的解的概率要逐漸減??；③當溫度趨于零時，只能接受目標函數(shù)值下降的解。狀態(tài)接受函數(shù)的引入是SA算法實現(xiàn)全局搜索的最關(guān)鍵的因素，SA算法中通常采用min[1,exp(-△C/t)]作為狀態(tài)接受函數(shù)。

模擬退火算法⑶初溫初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準則和外循環(huán)終止準則通常被稱為退火歷程(annealingschedule)。實驗表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費的計算時間將增加。因此，初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用方法包括：模擬退火算法①均勻抽樣一組狀態(tài)，以各狀態(tài)目標值的方差為初溫。②隨機產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標值差，然后依據(jù)差值，利用一定的函數(shù)確定初溫。譬如，其中ffsf為初始接受概率③利用經(jīng)驗公式給出。模擬退火算法⑷溫度更新函數(shù)溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。目前，最常用的溫度更新函數(shù)為指數(shù)退溫函數(shù)，即，其中且其大小可以不斷變化。模擬退火算法⑸內(nèi)循環(huán)終止準則內(nèi)循環(huán)終止準則，或稱Metropolis抽樣穩(wěn)定準則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。在非時齊SA算法理論中，由于在每個溫度下只產(chǎn)生一個或少量候選解，所以不存在選擇內(nèi)循環(huán)終止準則的問題。

模擬退火算法而在時齊SA算法理論中，收斂條件要求在每個溫度下產(chǎn)生候選解的數(shù)目趨于無窮大，以使相應(yīng)的馬氏鏈達到平穩(wěn)概率分布，顯然在實際應(yīng)用算法時這是無法實現(xiàn)的。常用的抽樣準則包括：①檢驗?zāi)繕撕瘮?shù)的均值是否穩(wěn)定；②連續(xù)若干步的目標值變化較??；③按一定的步數(shù)抽樣。

模擬退火算法⑹外循環(huán)終止準則外循環(huán)終止準則，即算法終止準則，用