T573029173的個人博客分享 http://www.ueservicedoffices.com/u/T573029173

博文

模擬退火算法求最優解(轉載)

已有 16326 次閱讀 2015-5-29 15:16 |系統分類:科研筆記|關鍵詞:color,style,地球,爬山,兔子| 地球, style, color, 兔子, 爬山

轉自蒼梧的博客:http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html  

一、模擬退火算法概念

關于爬山算法與模擬退火,有一個有趣的比喻,為了找出地球上最高的山,一群有志氣的兔子們開始想辦法:

方法一:兔子朝著比現在高的地方跳去。它找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法(或局部搜索法),它不能保證局部最優值就是全局最優值。

方法二:兔子喝醉了,它隨機地跳了很長時間。這期間,它可能走向高處,也可能踏入平地。但是,它漸漸清醒了并朝最高點跳去。這就是模擬退火。

爬山算法是一種簡單的貪心搜索算法,它每次都鼠目寸光地從當前解臨近的解空間中選擇一個最優解作為當前解,直到得到一個局部最優解。如圖1所示:假設C點為當前解,爬山算法搜索到A點這個局部最優解后就會停止搜索,因為在A點無論向那個方向小幅度移動都不能得到更優的解。因此,爬山算法只能搜索到局部最優值,而不一定能搜索到全局最優解。

圖 1 示意圖

模擬退火是模擬固體退火原理,這也是模擬退火算法名稱的由來。將固體加溫至充分高,再讓其徐徐冷卻,加溫時,固體內部粒子隨溫升變為無序狀,內能增大,而徐徐冷卻時粒子漸趨有序,在每個溫度都達到平衡態,最后在常溫時達到基態,內能減為最小。

模擬退火算法其實也是一種貪心算法,但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解,因此有可能會跳出這個局部的最優解,達到全局的最優解。以圖1為例,模擬退火算法在搜索到局部最優解A后,會以一定的概率接受到E的移動。也許經過幾次這樣的不是局部最優的移動后會到達D點,于是就跳出了局部最大值A。模擬退火算法是一種隨機算法,并不一定能找到全局的最優解,但可以比較快的找到問題的近似最優解。

二、模擬退火算法的關鍵步驟

模擬退火算法的基本思想是:由初始解和控制參數初值開始,對當前解重復“產生新解計算目標函數差接受或舍棄”的迭代,并逐步衰減控制參數值,算法終止時,當前解的值即為近似最優解,這便是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。

2 模擬退火算法流程圖

冷卻參數表、新解產生器、Metropolis接受準則一起構成模擬退火算法的關鍵部分。

1) 冷卻參數表初始化:

我們稱調整模擬退火法的一系列重要參數為冷卻進度表。退火過程由冷卻進度表(Cooling Schedule)控制,具體包括6個參數:

①初始溫度T。一般要求T的初始值要充分大,即一開始處于高溫狀態。

②溫度的衰減因子。衰減函數用于控制溫度的退火速度,一個常用的函數為:T(n + 1) = K*T(n),其中K是一個非常接近于1的常數。

③搜索步長因子。

④每個T值的迭代次數L(馬可夫鏈長度)。在衰減參數T的衰減函數已選定的前提下,L應選得在控制參數的每一取值上都能恢復準平衡。即每一次隨機游走過程,要迭代多少次,才能趨于一個準平衡分布,即一個局部收斂解位置。

⑤初始解狀態i。是算法迭代的起點

⑥結束條件S。有很多種終止條件的選擇,各種不同的條件對算法的性能和解的質量有很大影響,本文只介紹一個常用的終止條件。即上一個最優解與最新的一個最優解的之差小于某個容差,即可停止此次馬爾可夫鏈的迭代。

2) 對k=1,…,L做第3至第5步

3) 產生新解S′的新解產生器。

首先由一個新解產生函數從當前解產生一個位于解空間的新解。為了便于后續的計算和接受,減少算法耗時,通常選擇由當前解經過簡單地變換即可產生新解的方法。

4) Metropolis準則

判斷新解是否被接受,判斷的依據是一個接受準則,最常用的接受準則是Metropo1is準則,這也是模擬退火算法的精髓所在。根據Metropolis準則,系統從一個能量狀態變化到另一個狀態時,相應的能量從E1變化到E2,在溫度T時趨于平衡的概率,其中E為溫度T時的內能,dE為內能的變化量,kBoltzmann常數,exp表示自然指數。用固體退火模擬組合優化問題,將內能E模擬為目標函數值f,溫度T演化成控制參數t,即得到解組合優化問題的模擬退火算法,計算當前解與新解所對應的目標函數差

(1) Δt′= f(X(i+1)) - f(X(i)) < 0 (即移動后得到更優解),則總是接受該移動,將新解S′作為當前解S。

(2) Δt= f(X(i+1)) - J(X(i)) > 0 (即移動后的解比當前解要差),則以一定的概率接受移動,而且這個概率隨著時間推移逐漸降低(逐漸降低才能趨向穩定)。

此公式表明:溫度越高,出現一次能量差為dE的降溫的概率就越大;溫度越低,則出現降溫的概率就越小。隨著溫度T的降低,P(dE)會逐漸降低。又由于-dE/kT < 0,所以P(dE)的函數取值范圍是(0,1)。在無限高溫時,系統立即均勻分布,接受所有提出的變換。T的衰減越小,T到達終點的時間越長;但可使馬可夫鏈越小,到達準平衡分布的時間越短

5) 如果滿足終止條件則輸出當前解作為最優解,結束程序。

終止條件通常取為連續若干個新解都沒有被接受時終止算法。當新解被確定接受時,用新解代替當前解,這只需將當前解中對應于產生新解時的變換部分予以實現,同時修正目標函數值即可。此時,當前解實現了一次迭代?稍诖嘶A上開始下一輪試驗。而當新解被判定為舍棄時,則在原當前解的基礎上繼續下一輪試驗。

6) T逐漸減少,且T->0,然后轉第2步。

補充:模擬退火算法與初始值無關,算法求得的解與初始解狀態S(是算法迭代的起點)無關;模擬退火算法具有漸近收斂性,已在理論上被證明是一種以概率l 收斂于全局最優解的全局優化算法;模擬退火算法具有并行性。

三、模擬退火算法的代碼實現


1) 偽代碼:

while(T > T_min)

{

dE = f(Y(i+1)) - f(Y(i));

if(dE>=0)//表達移動后得到更優解,則總是接受移動

Y(i+1) = Y(i); //接受從Y(i)到Y(i+1)的移動

else

{

//函數exp(dE/T)的取值范圍是(0,1),dE/T越大,則exp(dE/T)也越大

if(exp(dE/T) > random(0,1))

Y(i+1)=Y(i);//接受從Y(i)到Y(i+1)的移動

}

T=r * T; //降溫退火

i++;

}

2) C#代碼

 詳細代碼見 Program.cs





http://www.ueservicedoffices.com/blog-1813407-893984.html

上一篇:分享一些閱讀外文文獻的經驗(整理)
下一篇:應試考試記憶英語單詞

1 蔣迅

該博文允許注冊用戶評論 請點擊登錄 評論 (2 個評論)

數據加載中...

Archiver|手機版|科學網 ( 京ICP備14006957 )

GMT+8, 2019-8-20 02:51

Powered by ScienceNet.cn

Copyright © 2007- 中國科學報社

返回頂部
时时彩平台 望都县  青川县  舞钢市  台东市  枝江市  无极县   庆元县  舞钢市  班戈县  南宫市   新蔡县  鹤岗市  泰宁县  洞头县  汾阳市  广西   西宁市  青神县  蒙山县  娄底市