CH4 模擬退火算法ppt課件

1、模擬退火算法模擬退火算法 Simulated Annealing 簡介簡介 模擬退火法 Simulated Annealing；SA 最早的想法是由 N.Metropolis 等人于 1953 年所提出，在當(dāng)時并沒有遭到注重 直到1983 年由Kirkpatrick et al. 提出 Monte CarloMonteCarlo Simulated概 念的隨機搜索技巧，利用此方法來求解的 組合最正確化問題時，才使此算法遭到注 重。 簡介簡介 SA的概念主要來自于固體加熱至一定的溫 度后，固體間的分子構(gòu)造會被打散瓦解變 為液態(tài)構(gòu)造 接著再對其降溫過程加以控制，當(dāng)完全冷 卻能使其分子在液態(tài)構(gòu)造轉(zhuǎn)變

2、為固體構(gòu)造 時，重新陳列成我們所預(yù)期的穩(wěn)定形狀 簡介簡介 當(dāng)目前情況是落于區(qū)域的最正確解時，模擬 退火法會由重新加熱的動作，透過隨機的過 程，以概率性質(zhì)來接受一個暫劣解使其算法 能跳脫目前的區(qū)域最正確解即部分最優(yōu)， 而有時機能到達另一個最正確解. 簡介簡介 模擬退火法組成 接受法那么Accepting Rule 并用退火程序Annealing Schedule 的參數(shù)演算法進展 而Metroplis接受法那么的概念那么在 于能使求解時跳脫墮入?yún)^(qū)域最正確解 而模擬退火法能否勝利運用在于退火 程序的合理選擇 簡介簡介 當(dāng)j 的本錢C(j) 大于i的本錢C(i)時，SA 會根據(jù)一概率 決議能否要接受

3、j來取代i 成為時間k+1 的新解： 因此當(dāng)搜索到的新解比現(xiàn)有解之本錢大時，會有一個概 率值來決議能否接受交換。 SA 根本上是以Metrolopis 接受法那么為根底，再配合 退火程序，由溫度逐漸的降低來調(diào)整能否接受本錢較差 新解的概率，當(dāng)溫度越低時，概率值也跟著降低. expC bT b即為Boltzmann常數(shù) SA SA 的基理分析的基理分析 四個根本要素 系統(tǒng)形狀Configuration：即在某一個 溫度下，系統(tǒng)產(chǎn)生的初始解，并當(dāng)作目前 的現(xiàn)行解 搜索法那么Search rule：在退火的過 程中，由目前系統(tǒng)形狀經(jīng)由隨機擾動而產(chǎn) 生變化跳至另一種形狀 普通而言，SA 較常用的有梯度

4、搜索法 Gradient Type 和疊代改善法 Iterative Improvement 四個根本要素 本錢函數(shù)Cost Function：用來衡量某一 系統(tǒng)形狀下之能量函數(shù) 退火程序Annealing Process：退火程序 中包含的參數(shù)有初始溫度、降溫機制、冷卻 率和終止溫度 在退火的過程中，在溫度高的時候，雖然是 較差的目的值，也有能夠被接受成目前的目 的值，但隨著溫度漸漸的降低，接受較差目 的值的概率逐漸降低. SASA的根本步驟的根本步驟 No 退火程序的參數(shù)設(shè)定退火程序的參數(shù)設(shè)定 初始溫度 為了防止落入部分最小的圈套，在模擬退火法中 初始溫度的設(shè)定必需使得大部份的轉(zhuǎn)移均可被接

5、 受 初始溫度的設(shè)定可以是一個定值 如Kirkpatrick等學(xué)者 ( 1983 ) 將初始溫度定為 10 Heragu 以及 Alfa ( 1992 )將初始溫度定為999 初始溫度也可由所設(shè)定的轉(zhuǎn)移接受概率的門檻值 P0來反推求得，如Kouvelis 以及 Chiang( 1992 ) 將初始溫度定為 退火程序的參數(shù)設(shè)定退火程序的參數(shù)設(shè)定 終止條件 終止條件最簡單的設(shè)定方式是指定一個固 定的終止溫度，普通是一個接近于0較小的 數(shù)，或是限制降溫次數(shù)不超越預(yù)定值 其它方式那么為檢查所求得的解能否有所 改善，如在1992 年Kouvelis 與 Chiang設(shè) 定假設(shè)經(jīng)過數(shù)次降溫后所得的解仍未改

6、善 或轉(zhuǎn)移接受比率低于一個定值，則將終止 模擬退火法的運算。 退火程序的參數(shù)設(shè)定退火程序的參數(shù)設(shè)定 降溫時機 降溫時機是指馬可夫鏈長度，即在同一溫度下所 應(yīng)反復(fù)進展Metropolis 演算的次數(shù) 最直接的方式是設(shè)定一個固定長度，但此長度與 問題有關(guān)，如在1992 年Kouvelis 與Chiang 將其 設(shè)定為臨近解個數(shù)的比率。 此外也可設(shè)定降溫時機為轉(zhuǎn)移接受次數(shù)已達一定 值 但此一方式當(dāng)溫度降至很低時，轉(zhuǎn)移接受概率將 會很小，進而導(dǎo)致馬可夫鏈過長，因此必需同時 限定馬可夫鏈的長度，以免呵斥求解時間過長 退火程序的參數(shù)設(shè)定退火程序的參數(shù)設(shè)定 溫度控制參數(shù)(冷卻率) 溫度控制參數(shù)是指在計算過程中，假設(shè)到達降溫 時機時，由目前溫度減少到下一個溫度的下降比 率 假設(shè)溫度控制參數(shù)越小，那么溫度下降的差距越 大，那么會呵斥在下一個溫度達成平衡所需的馬 可夫鏈長度越長，使得求解時間添加。 因此，為了防止在新溫度下的馬可夫鏈長度過長， 溫度控制參數(shù)不應(yīng)過小，Kirkpatrick 等學(xué)者 1983將其設(shè)定為0.9，而普通那么設(shè)定在0.5 至0.9 之間 MA