模擬退火算法0852

《模擬退火算法0852》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、5.2模擬退火算法SimulatedAnnealing模擬退火算法1、基本思想(1)是基于MonteCarlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。(2)結(jié)合爬山法和隨機(jī)行走注：SA算法最早是由Metropolis等(1953)提出模擬退火算法1、基本思想模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部?jī)?yōu)解能概率性地跳出并最終趨于全局最優(yōu)解。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。模擬退火算法

2、的設(shè)計(jì)與原理猜想物質(zhì)自動(dòng)趨向的最低能態(tài)與函數(shù)最小值之間有相似性?。?！我們能不能設(shè)計(jì)一種算法求函數(shù)最小值，就像物質(zhì)”自動(dòng)”地趨向最低能態(tài)？降溫圖像離散函數(shù)圖像相似性?最小值最低能態(tài)模擬退火算法的設(shè)計(jì)與原理物理模型——固體退火退火俗稱固體降溫先把固體加熱至足夠高溫，使固體中所有粒子處于無(wú)序的狀態(tài)（最高的熵值），然后將溫度緩慢下降，粒子漸漸有序（熵值下降），這樣只要溫度上升得足夠高，冷卻過(guò)程足夠慢，則所有粒子最終會(huì)處于最低能態(tài)（最低的熵值）。最低能態(tài)時(shí)間溫度模擬退火算法2、物理退火過(guò)程和Metropolis準(zhǔn)則⑵等溫過(guò)程。物理學(xué)的知識(shí)告訴我們，對(duì)

3、于與周圍環(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)。優(yōu)化與物理退火相似性模擬退火算法2、物理退火過(guò)程和Metropolis準(zhǔn)則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為

4、Boltzmann常數(shù)。模擬退火算法2、物理退火過(guò)程和Metropolis準(zhǔn)則這種重要性采樣過(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)則通常稱為Metropolis準(zhǔn)則。模擬退火算法2、算法步驟標(biāo)準(zhǔn)模擬退火算法的一般步驟可描述如下：⑴給定初溫，隨機(jī)產(chǎn)生初始狀態(tài)，令；⑵Repeat:①Repeat產(chǎn)生新?tīng)顟B(tài)；模擬退火算法Until抽樣穩(wěn)定準(zhǔn)則滿足；②退溫，并令；Until算法終止準(zhǔn)則滿足；⑶輸出算法搜索結(jié)果。模擬退火算法3、算法關(guān)

5、鍵參數(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算法性能也有很大影響。模擬退火算法3、算法關(guān)鍵參數(shù)和操作的設(shè)定⑴狀態(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)生的概率分布。模擬退火算法3、算法關(guān)鍵參數(shù)和操作的設(shè)定⑵狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接

6、受概率的形式不同。設(shè)計(jì)狀態(tài)接受概率，應(yīng)該遵循以下原則：①在固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)值上升的候選解的概率；模擬退火算法3、算法關(guān)鍵參數(shù)和操作的設(shè)定⑵狀態(tài)接受函數(shù)②隨溫度的下降，接受使目標(biāo)函數(shù)值上升的解的概率要逐漸減??；③當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)值下降的解。狀態(tài)接受函數(shù)的引入是SA算法實(shí)現(xiàn)全局搜索的最關(guān)鍵的因素，SA算法中通常采用min[1,exp(-△C/kt)]作為狀態(tài)接受函數(shù)。模擬退火算法3、算法關(guān)鍵參數(shù)和操作的設(shè)定⑶初溫初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則通常被稱為退火歷程(ann

7、ealingschedule)。實(shí)驗(yàn)表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費(fèi)的計(jì)算時(shí)間將增加。因此，初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用方法包括：模擬退火算法3、算法關(guān)鍵參數(shù)和操作的設(shè)定⑶初溫①均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。②隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，然后依據(jù)差值，利用一定的函數(shù)確定初溫。譬如，其中為初始接受概率③利用經(jīng)驗(yàn)公式給出。模擬退火算法3、算法關(guān)鍵參數(shù)和操作的設(shè)定⑷溫度更新函數(shù)溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。目前，最常用的溫度更新函數(shù)為指數(shù)退溫函數(shù)。模擬退火算

8、法3、算法關(guān)鍵參數(shù)和操作的設(shè)定⑸內(nèi)循環(huán)終止準(zhǔn)則內(nèi)循環(huán)終止準(zhǔn)則，或稱Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。在非時(shí)齊SA算