模擬退火算法

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

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

產(chǎn)生新?tīng)顟B(tài)；模擬退火算法

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

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

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

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

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