模擬退火算法

1、姓名：姓名：盛媛媛班級：班級：研控計(jì)1322學(xué)號：學(xué)號：1132227140指導(dǎo)老師：指導(dǎo)老師：黃從智模擬退火算法的簡介和原理模擬退火的基本思想和步驟模擬退火算法的基本程序講解介紹模擬退火前，先介紹爬山算法。爬山算法是一種簡單的介紹模擬退火前，先介紹爬山算法。爬山算法是一種簡單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。假設(shè)假設(shè)C C點(diǎn)為當(dāng)前解，爬山算法搜索到點(diǎn)為當(dāng)前解，爬山算法搜索到A A點(diǎn)這個(gè)局部最優(yōu)解就會(huì)點(diǎn)這個(gè)局部最優(yōu)解就會(huì)停止搜索，因?yàn)樵?/p>

2、停止搜索，因?yàn)樵贏 A點(diǎn)無論向那個(gè)方向小幅度移動(dòng)都不能得到點(diǎn)無論向那個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解更優(yōu)的解爬山算法實(shí)現(xiàn)很簡單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而爬山算法實(shí)現(xiàn)很簡單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。不一定能搜索到全局最優(yōu)解。 爬山法是完完全全的貪心法，每次都鼠目寸爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是它的搜索過程引入了隨機(jī)因素。模擬退火但是它的搜索過程引入了隨機(jī)因素。模擬退火算法以一定的

3、概率來接受一個(gè)比當(dāng)前解要差的算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解到全局的最優(yōu)解。什么是模擬退火算法呢？什么是模擬退火算法呢？模擬退火算法模擬退火算法（Simulate Anneal Arithmetic，SAA）最早的思想是由N. Metropolis等人于1953年提出。1983 年,S. Kirkpatrick 等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo（蒙特卡羅）迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模

4、擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用，諸如生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號處理等領(lǐng)域。模擬退火來自冶金學(xué)的專有名詞退火。什么是退火呢？退火是將材料加熱后再經(jīng)特定速率冷卻，目的是增大晶粒的體積，并且減少晶格中的缺陷。材料中的原子原來會(huì)停留在使內(nèi)能有局部最小值的位置，加熱使能量變大，原子會(huì)離開原來位置，而隨機(jī)在其他位置中移動(dòng)。退火冷卻時(shí)速度較慢，使得原子有較多可能可以找到

5、內(nèi)能比原先更低的位置。物理退火過程：加溫過程-增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程-對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡。冷卻過程-是例子熱運(yùn)動(dòng)減弱并漸趨于有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。模擬退火的原理也和金屬退火的原理近似：將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動(dòng)能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對命題的合適程度。演算法先以搜尋空間內(nèi)一個(gè)任意點(diǎn)作起始：每一步先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有

6、位置到達(dá)“鄰居”的概率。定義：將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。模擬退火算法描述： 若J( Y(i+1) )= J( Y(i) ) (即移動(dòng)后得到更優(yōu)解)，則總是接受該移動(dòng) 若J( Y(i+1) ) J( Y(i) ) (即移動(dòng)后的解比當(dāng)前解要差)，則以一定的概率接受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移逐漸降低（逐漸降以一定的概率接受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）低才能趨向穩(wěn)定）這里的“一定的概率”的計(jì)算參考了金屬冶煉的退火過程，這也

7、是模擬退火算法名稱的由來。根據(jù)熱力學(xué)的原理，在溫度為T時(shí)，出現(xiàn)能量差為E的降溫的概率為P(E)，表示為：P(P(E) = exp(E) = exp(E/(E/(kTkT) ) )其中k是一個(gè)常數(shù)，exp表示自然指數(shù)，且E0。這條公式說白了就是：溫度越高，出現(xiàn)一次能量差為E的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。又由于E總是小于0（否則就不叫退火了），因此E/kT 0 ，所以P(E)的函數(shù)取值范圍是(0,1) 。隨著溫度T的降低，P(E)會(huì)逐漸降低。我們將一次向較差解的移動(dòng)看做一次溫度跳變過程，我們以概率P(E)來接受這樣的移動(dòng)。 仍以上圖為例仍以上圖為例，模擬退火算法在搜索到局部

8、，模擬退火算法在搜索到局部最優(yōu)解最優(yōu)解A A后，會(huì)以一定的概率接受到后，會(huì)以一定的概率接受到E E的移動(dòng)。也許經(jīng)的移動(dòng)。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)過幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)D D點(diǎn)，于是點(diǎn)，于是就跳出了局部最大值就跳出了局部最大值A(chǔ) A。關(guān)于爬山算法與模擬退火，有一個(gè)有趣的比喻：關(guān)于爬山算法與模擬退火，有一個(gè)有趣的比喻：爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠(yuǎn)處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這不遠(yuǎn)處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。就是爬

9、山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。模擬退火：兔子喝醉了。它隨機(jī)地跳了很長時(shí)間。這模擬退火：兔子喝醉了。它隨機(jī)地跳了很長時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。這就是模擬退火。清醒了并朝最高方向跳去。這就是模擬退火。模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。模擬退火的基本步驟:(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L(2) 對k=1，L做第(3)至第6步：(3) 產(chǎn)生新解S(4) 計(jì)算增量t=C(S)-C(S)，其中C(S)為評價(jià)

10、函數(shù)(5) 若t0，然后轉(zhuǎn)第2步。1、設(shè)置終止溫度的閾值2、設(shè)置外循環(huán)迭代次數(shù)3、算法搜索到的最優(yōu)值連續(xù) 若干步保持不變4、概率分析方法常用常用MetropolisMetropolis抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則1、檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定2連續(xù)若干步的目標(biāo)值變化較小3、按一定的步數(shù)抽樣模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點(diǎn)：(1) (1) 溫度溫度T T的初始值設(shè)置問題。的初始值設(shè)置問題。溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但

11、全局搜索性能可能受到影響。實(shí)際應(yīng)用過程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。(2) (2) 退火速度問題。退火速度問題。模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來說，同一溫度下的“充分”搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間。實(shí)際應(yīng)用中，要針對具體問題的性質(zhì)和特征設(shè)置合理的退火平衡條件。(3) (3) 溫度管理問題。溫度管理問題。溫度管理問題也是模擬退火算法難以處理的問題之一。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問題，常采用如下所示的降溫方式: T（t+1）=K*T(t) 式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù)。 模擬退火算法是一種隨機(jī)算法，并不

12、一定能找到全局的最優(yōu)解，可以比較快的找到問題的近似最優(yōu)解。 如果參數(shù)設(shè)置得當(dāng)，模擬退火算法搜索效率比窮舉法要高。模擬退火算法是通過賦予搜索過程一種時(shí)變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法。TSP，即Traveling Saleman Problem，也就是旅行商問題，又譯為旅行推銷員問題、貨郎擔(dān)問題，簡稱為TSP問題，是數(shù)學(xué)領(lǐng)域著名的問題之一。TSP問題是最基本的路線問題，該問題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。模擬退火解決TSP的思路：1. 產(chǎn)生一條新的遍歷路徑P(i+1)，計(jì)算路徑P(

13、i+1)的長度L( P(i+1) )；2. 若L(P(i+1) L(P(i)，則接受P(i+1)為新的路徑，否則以模擬退火的概率接受P(i+1) ，然后降溫；3. 重復(fù)步驟1，2直到滿足退出條件產(chǎn)生新的遍歷路徑的方法有很多，下面列舉其中3種：1. 隨機(jī)選擇2個(gè)節(jié)點(diǎn)，交換路徑中的這2個(gè)節(jié)點(diǎn)的順序。2. 隨機(jī)選擇2個(gè)節(jié)點(diǎn)，將路徑中這2個(gè)節(jié)點(diǎn)間的節(jié)點(diǎn)順序逆轉(zhuǎn)。3. 隨機(jī)選擇3個(gè)節(jié)點(diǎn)m，n，k，然后將節(jié)點(diǎn)m與n間的節(jié)點(diǎn)移位到節(jié)點(diǎn)k后面。交換又稱2-OPT算法，是最常用的一種算法，其主要思想是在所有城市中隨機(jī)選取兩個(gè)城市，然后將2個(gè)城市在路徑中的序列交換位置產(chǎn)生新的路徑。例如：解空間S是邊防每個(gè)城市恰好一次的所有路徑，解樂意表示為W1，W2， Wn是1,2， 的一個(gè)排列，表明W1城市出發(fā)，經(jīng)過W2， Wn城市，在返回W1城市。新路徑的產(chǎn)生：隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m。不妨設(shè)km,則將原路徑W1，W2 ,Wk , W(k+1), ,Wm , W(m+1), Wn變?yōu)樾侣窂剑篧1，W2 , Wm , W(k+1), Wk , W(m+1) , Wn置換的主要思想是：隨即在路徑中選出兩個(gè)城市，然后將兩個(gè)城市之間的城市順序完全倒置得出新的路徑。如上例：產(chǎn)生兩個(gè)相異數(shù)k和m（假設(shè)km）,則將原路徑W1，W2 W(k-1) ,Wk , W(k+1), W(m-1),Wm , W(m+1