《模擬退火719》ppt課件

1、第三講 模擬退火模型1 導(dǎo) 入 為了找出地球上最高的山，一群有志氣的兔子們開場(chǎng)想方法。 方案一：兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機(jī)落到了地球上的某些地方。他們不知道本人的使命是什么。但是，假設(shè)他過幾年就殺死一部分海拔低的兔子，多產(chǎn)的兔子們本人就會(huì)找到珠穆朗瑪峰。遺傳算法 方案二：兔子們知道一個(gè)兔子的力量是微小的。于是，它們相互轉(zhuǎn)告著，哪里的山曾經(jīng)找過，并且找過的每一座山他們都留下一只兔子做記號(hào)。這樣，它們制定了下一步去哪里尋覓的戰(zhàn)略。忌諱搜索法 方案三：兔子們用酒將本人灌醉了。它們隨機(jī)地跳了很長(zhǎng)時(shí)間。在這期間，它們能夠走向高處，也能夠踏入平地。但是，隨著時(shí)間的流逝，它們漸漸清醒了并朝

2、最高方向跳去。 模擬退火法 算法的提出：模擬退火算法最早的思想由Metropolis等(1953)提出，1983年Kirkpatrick等將其運(yùn)用于組合優(yōu)化。算法的目的處理NP復(fù)雜性問題；抑制優(yōu)化過程墮入部分極小；抑制初值依賴性。 在對(duì)固體物質(zhì)進(jìn)展模擬退火處置時(shí)，通常先將它加溫熔化，使其中的粒子可自在運(yùn)動(dòng)，然后隨著溫度的逐漸下降，粒子也逐漸構(gòu)成了低能態(tài)的晶格。假設(shè)在凝結(jié)點(diǎn)附近的溫度下降速率足夠慢，那么固體物質(zhì)一定會(huì)構(gòu)成最低能態(tài)的基態(tài)。 組合優(yōu)化問題解空間中的每一點(diǎn)都代表一個(gè)具有不同目的函數(shù)值的解。所謂優(yōu)化，就是在解空間中尋覓目的函數(shù)最小大解的過程。假設(shè)把目的函數(shù)看成能量函數(shù)，某一控制參數(shù)視為溫

3、度T，解空間當(dāng)作形狀空間，那么尋覓基態(tài)的過程也就是求目的函數(shù)極小值的優(yōu)化過程。模擬退火算法與模型物理退火過程：什么是退火？退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)陳列形狀，然后逐漸降溫使之冷卻，最后分子以低能形狀陳列，固體到達(dá)某種穩(wěn)定形狀。 模擬退火算法與模型(C.)物理退火過程：加溫過程加強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先能夠存在的非均勻態(tài)；等溫過程對(duì)于與環(huán)境換熱而溫度不變的封鎖系統(tǒng)，系統(tǒng)形狀的自發(fā)變化總是朝自在能減少的方向進(jìn)展，當(dāng)自在能到達(dá)最小時(shí)，系統(tǒng)到達(dá)平衡態(tài)；冷卻過程使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體構(gòu)造。 數(shù)學(xué)描畫：假設(shè)用粒子的能量定義資料的形狀，Met

4、ropolis 算法用一個(gè)簡(jiǎn)單的數(shù)學(xué)模型描畫了退火過程。 假設(shè)資料在形狀i 之下的能量為E(i) ，那么資料在溫度T 時(shí)從形狀i 進(jìn)入形狀j 就遵照如下規(guī)律：假設(shè)E(j)E(i) ，接受該形狀被轉(zhuǎn)移假設(shè)E(j) E(i) ，那么形狀轉(zhuǎn)換以如下的概率被接受 expE(i)- E(j)/KT其中，K是物理學(xué)中的波爾茲曼常數(shù)，T是資料溫度數(shù)學(xué)描畫：在某一個(gè)特定溫度T下，進(jìn)展了充分的轉(zhuǎn)換之后，資料將到達(dá)熱平衡。這時(shí)資料處于形狀i的概率滿足波爾茲曼分布：其中，x表示資料當(dāng)前形狀的隨機(jī)變量，S表示形狀空間集合SjKTjEKTiETeeiExEP)()()()(數(shù)學(xué)描畫：其中，|S|表示形狀空間集合中形狀的

5、數(shù)量。這就闡明，一切形狀在高溫下具有一樣的概率。SeeSjKTjEKTiET1lim)()(數(shù)學(xué)描畫：而當(dāng)溫度下降時(shí)：上式闡明當(dāng)溫度降至很低時(shí)，資料會(huì)以很大約率進(jìn)入最小能量形狀。數(shù)學(xué)描畫：從另外一個(gè)角度來看：在同一個(gè)溫度T，選定兩個(gè)能量E101數(shù)學(xué)描畫：針對(duì)上述景象，Metropolis提出了著名的Metropolis準(zhǔn)那么1953以概率接受新形狀來模擬這一過程： 固體在恒定溫度下到達(dá)熱平衡的過程可以用Monte Carlo方法計(jì)算機(jī)隨機(jī)模擬方法加以模擬，雖然該方法簡(jiǎn)單，但必需大量采樣才干得到比較準(zhǔn)確的結(jié)果，計(jì)算量很大。Metropolis準(zhǔn)那么(1953)以概率接受新形狀：假設(shè)在溫度T，當(dāng)前

6、形狀i 新形狀j 假設(shè)Ej=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)那么滿足； 退溫tk+1=update(tk)并令k=k+1； Until 算法終止準(zhǔn)那么滿足； 輸出算法搜索結(jié)果。算法關(guān)鍵參數(shù)和操作的設(shè)定：從算法流程上看，模擬退火算法包括三函數(shù)兩準(zhǔn)那么，即形狀產(chǎn)生函數(shù)、形狀接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)那么和外循環(huán)終止準(zhǔn)那么，這些環(huán)節(jié)的設(shè)計(jì)將決議模擬退火算法的優(yōu)化性能。此外，初溫的選擇對(duì)模擬退火算法性能也有很大影響。 形狀產(chǎn)生函數(shù)：原那么：設(shè)計(jì)形狀產(chǎn)生函數(shù)鄰域函數(shù)的出發(fā)點(diǎn)應(yīng)該是盡能夠保證產(chǎn)生的候選解遍及全部的解空間。通常，形狀產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和

7、候選解產(chǎn)生的概率分布方法：在當(dāng)前形狀的鄰域構(gòu)造內(nèi)以一定概率方式均勻分布、正態(tài)分布、指數(shù)分布等產(chǎn)生形狀接受函數(shù)：原那么：函數(shù)普通以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的方式不同。設(shè)計(jì)形狀接受概率，應(yīng)該遵照以下原那么：(1)在固定溫度下，接受使目的函數(shù)下降的候選解的概率要大于使目的函數(shù)上升的候選解概率；(2)隨溫度的下降，接受使目的函數(shù)上升的解的概率要逐漸減?。?3)當(dāng)溫度趨于零時(shí)，只能接受目的函數(shù)下降的解。方法：形狀接受函數(shù)的引入是模擬退火算法實(shí)現(xiàn)全局搜索的最關(guān)鍵的要素，模擬退火算法中通常采用min1,exp(-C/t)作為形狀接受函數(shù)初始溫度：初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)

8、那么和外循環(huán)終止準(zhǔn)那么通常被稱為退火歷程。原那么：經(jīng)過實(shí)際分析可以得到初溫的解析式，但處理實(shí)踐問題時(shí)難以得到準(zhǔn)確的參數(shù)；實(shí)踐運(yùn)用時(shí)往往要讓初溫充分大。實(shí)驗(yàn)闡明：初溫越大，獲得高質(zhì)量解的機(jī)率越大，但破費(fèi)較多的計(jì)算時(shí)間。方法：1)均勻抽樣一組形狀，以各形狀目的值的方差為初溫；2)隨機(jī)產(chǎn)生一組形狀，確定兩兩形狀間的最大目的值差，根據(jù)差值，利用一定的函數(shù)確定初溫，譬如 ，其中 為初始接受概率； 3)利用閱歷公式。rptln/0rp溫度更新函數(shù)：溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修正溫度值。常用的算法溫度下降函數(shù)：1) ：越接近1溫度下降越慢，且其大小可以不斷變化；2 ：其中t0為起始溫度，

9、K為算法溫度下降的總次數(shù)。10 , 0 ,1kttkk0tKkKtk內(nèi)循環(huán)終止準(zhǔn)那么：常用的Metropolis抽樣穩(wěn)定準(zhǔn)那么：1檢驗(yàn)?zāi)康暮瘮?shù)的均值能否穩(wěn)定；2延續(xù)假設(shè)干步的目的值變化較小；3按一定的步數(shù)抽樣。外循環(huán)終止準(zhǔn)那么1設(shè)置終止溫度的閾值； 2設(shè)置外循環(huán)迭代次數(shù)； 3算法搜索到的最優(yōu)值延續(xù)假設(shè)干步堅(jiān)持不變； 4概率分析方法。模擬退火算法的優(yōu)缺陷：優(yōu)點(diǎn)：質(zhì)量高；初值魯棒性強(qiáng)；簡(jiǎn)單、通用、易實(shí)現(xiàn)。缺陷由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長(zhǎng)。模擬退火算法的流程巡航問題：知敵方100 個(gè)目的的經(jīng)度、緯度如表所示：模擬退火算法的實(shí)例巡航問題：知敵方100 個(gè)目的的經(jīng)度、緯度如表所示：我方有一個(gè)基地，經(jīng)度和緯度為70,40。假設(shè)我方飛機(jī)的速度為10