NO IMAGE

求解某一個方程fun(x)的極小值,很常見的以一種情況是當前的x不管增大還是減小,函式值fun(x)均是增大,這時x就是極值。這是一種完完全全的貪心演算法。這樣求出的極小值,並不一定整段函式的全域性極小值,而極可能是區域性極小值。

例如下圖



 

可以看出,有三個點,均是極小值點,在這是三個點處,不管增大變數,或是減小變數,目標函式的值都會增大。而只有最左邊的那個點,才是全域性最優解。

從數學模型上來看,是一種全域性極小值求解問題,擴充套件到物理意義上,舉幾個例子:

我們什麼PID引數,才是最優秀的呢?我們什麼PID引數,才能讓控制達到快準狠?自己一個一個的去套嗎,累死。當然也可以用計算機一個一個去套,但是這樣仍然非常花時間。利用模擬退火演算法,就可以很好的求出最優PID引數。

再比如我們的聚類演算法,什麼樣的碼本設計,才能使得向量量化的誤差減為最小,這仍然是一個全域性最優搜尋問題。

 

求解全域性最優解,有很多方法,模擬退火法只是我們其中一個,

除此之外,還有遺傳演算法、禁忌搜尋演算法、蟻群演算法、粒子群演算法等等。各有優缺點。

 

模擬退火演算法,顯著的缺點是 相較其他演算法,其穩定速度較慢,優點是在引數合適的情況下基本上可以100%得到全域性最優解。

求解一個一維輸入一維輸出函式的全域性最小解。這個思想也可以擴充套件到求解任意函式,輸出point時,的輸入應該為多少。

例如:已知函式F(x),我們想求輸出3時的輸入x為多少。我們可以將目標函式變換為

M(x) = (F(x)-3).^2 (平方或是求絕對值)

這樣就轉換為求解M(x)全域性最小值0的問題。即當x滿足F(x)=3 時,M(x)才能滿足全域性最小值。

 

我的vc程式碼裡面是求解sin(x) cos(0.3*x)這函式,x範圍[-10 ,10]的全域性極小值。

關於模擬退火,有一個有趣的比喻,幫助大家學習和理解:

  一般區域性極小值演算法:兔子朝著比現在高的地方跳去。它找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山演算法,它不能保證區域性最優值就是全域性最優值。

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

模擬退火演算法是用來求解最優化問題的演算法。比如著名的TSP問題函式最大值最小值問題等等。接下來將以如下幾個方面來詳細介紹模擬退火演算法。

   1. 模擬退火演算法認識

   2. 模擬退火演算法描述

   3. 費馬點問題求解

   4. 最小包含球問題求解

   5. 函式最值問題求解

   6. TSP問題求解