matlab 分布估計算法完成 camel 函數尋優_模拟退火(Simulated Annealing, SA)算法簡介與MATLAB實作...

模拟退火算法概述

模拟退火算法(Simulated Annealing，簡稱SA)的思想最早是由Metropolis等提出的。其出發點是基于實體中固體物質的退火過程與一般的組合優化問題之間的相似性。模拟退火法是一種通用的優化算法，其實體退火過程由以下三部分組成：

• 加溫過程。其目的是增強粒子的熱運動，使其偏離平衡位置。當溫度足夠高時，固體将熔為液體，進而消除系統原先存在的非均勻狀态
• 等溫過程。對于與周圍環境交換熱量而溫度不變的封閉系統，系統狀态的自發變化總是朝自由能減少的方向進行的，當自由能達到最小時，系統達到平衡狀态。
• 冷卻過程。使粒子熱運動減弱，系統能量下降，得到晶體結構。

加溫過程相當于對算法設定初值，等溫過程對應算法的Metropolis抽樣過程，冷卻過程對應控制參數的下降。這裡能量的變化就是目标函數，我們要得到的最優解就是能量最低态。其中Metropolis準則是SA算法收斂于全局最優解的關鍵所在，Metropolis準則以一定的機率接受惡化解，這樣就使算法跳離局部最優的陷阱。

SA算法的Metropolis準則允許接受一定的惡化解，具體來講，是以一定機率來接受非最優解。舉個例子，相當于保留一些“潛力股”，使解空間裡有更多的可能性。對比輪盤賭法，從機率論來講，它是對非最優解給予機率0，即全部抛棄。

模拟退火本身是求一個最小值問題，但可以轉化為求最大值問題，隻需要對目标函數加個負号或者取倒數。

算法步驟

其中，P為算法選擇較差解的機率；T 為溫度的模拟參數；

當T很大時，

，此時算法以較大機率選擇非目前最優解；P的值随着T的減小而減小；

當T趨于0時，

，此時算法幾乎隻選擇最優解，等同于貪心算法。

算法特點

• 與遺傳算法、粒子群優化算法和蟻群算法等不同，模拟退火算法不屬于群優化算法，不需要初始化種群操作。

• 收斂速度較慢。原因在于

1)它初始溫度一般設定得很高，而終止溫度設定得低，這樣才符合物體規律，認為物質處于最低能量平衡點；

2)它接受惡化解，并不是全程都在收斂的過程中。這一點可以類比GA中的變異，使得它不是持續在收斂的，是以耗時更多一些。

• 溫度管理(起始、終止溫度)、退火速度(衰減函數)等對尋優結果均有影響。比如T的衰減速度如果太快，就會導緻可能尋找不到全局最優解。

模拟退火算法MATLAB實作

【例1】一進制/多元函數優化

一進制函數：x = [1,2]範圍内 y = sin(10*pi*x) / x 的極值

二進制函數：

在x,y都是[-5,5]範圍内找z = x.^2 + y.^2 - 10*cos(2*pi*x) - 10*cos(2*pi*y) + 20 的極值

【例2】TSP問題

我們的TSP中城市是自己虛拟的14座城市。

main.m:

計算距離的函數Distance.m：

畫出路徑的函數DrawPath.m：

輸出路徑函數OutputPath.m：

PathLength.m:

增加随機擾動産生新解NewAnswer.m：

我們的做法是随機産生兩個城市讓他們交換位置，進而得到一個新的路徑。當然，這隻是這個問題的一個做法，也有其他“增加随機擾動”的做法，而且對于多元函數問題更加簡單，隻要在目前解的附近增加一些小的值即可。

Metropolis準則的實作：

程式結果：

【例3】

選擇30個點作為仿真研究對象，它們在坐标平面的坐标 (Location)如表1所示。

采用上述程式中随機排列的方法産生初始路徑 ，其 排列結果如圖1所示 。選擇接受函數為Boltzmann 機率分布函數，溫度的起始值為70，溫度下降律為0.5，經過運作最終得到結果如圖2所示，由該 圖可知經過優化後找到了最小路徑。

參考資料

曲 強 ，陳 雪 波，基 于 M A TL A B 的模拟 退火算 法 的實作 

CSDN部落客，奔跑的Yancy，模拟退火(Simulated Annealing, SA)算法簡介與MATLAB實作

- End -

模友們可能已經發現：現在公衆号推送文章的順序，已經不會按時間排列了。這種變化，可能會讓各位模友錯過我們每天的推送。

是以，如果你還想像往常一樣，聚焦數模樂園，就需要将“數模樂園”标為星标公衆号，同時在閱讀完文章後，别忘了給一個“在看”哦。

星标步驟

(1)點選頁面最上方“數模樂園”，進入公衆号首頁

(2)點選右上角的小點點，在彈出頁面點選“設為星标”，就可以啦。

掃碼關注我們

2020夏令營QQ交流群

球分享

球點贊

球在看