優化二——啟發式演算法
啟發式演算法：這類演算法算是演算法在實際應用過程中的技術性演算法，因為在實際計算過程中，很有可能第一：無確定的目標函數；第二：無法找到真實的最優解；第三：計算代價非常大，現有的計算機技術都無法解決此類問題。所以人們就找到另一種情況，使得在可接受的計算成本內去搜尋最好的解，但不一定能保證所得的可行解和最優解，甚至在多數情況下，無法闡述所得解同最優解的近似程度。 通熟點講就是求出來的解可能不是最好的，只能說是相對較好的，但是這個相對程度就不敢保證了。雖然是這樣，但是在工程應用上來說已經非常好了。
後面講的時候可能會讓你懷疑人生，這是演算法嗎？不過它們在工程上來講確實就是。第一個要講的是模擬退火演算法，這個當年是俺對它進行了幾次改造的，結合（SPSA）隨機擾動演算法，來在一定程度上解決此山最優的局限(測試過幾次，解決低維問題還行，還有一定的局限，就是初值的選取非常重要，必須在初值選取的時候就要接近真實值，這其實是很扯淡的，在自動歷史擬合中，很多時候我們都是要進行初值的篩選的，不過這個時候初值的篩選過程就一定得有一定的依據，什麼灰色關聯啊什麼的都出來了，反正非常大的系統知識)——扯遠了。
模擬退火是什麼意思呢？它不管你什麼梯度啊什麼步長，給定一個最低溫度Tmin（這個值無限小）他只管其中一個事情，就是我們在求解的過程中，新迭代出來的函數結果與舊的函數的差值結果f(x_new)-f(x)>0時就無條件接受這個值，但是如果f(x_new)-f(x)<0，則以一定的概率（exp((f(xnew)-f(x))/k*T)）來接受這個值，然後對溫度T進行一次更新，這個降溫方法為T= a*T (0<a<1)，一般a取接近1的值。最後如果當前溫度<Tmin時就退出循環了。 看根本就和什麼梯度什麼步長沒關係。那麼為什麼要這樣呢？我用通熟的方法給你們解釋一下：
對於這樣的一個函數，當前我們的內函數優化演算法都只能求解極值，如果極值是最值，那還好說，如果極值不是最值，那麼就很尷尬了，模擬退火就是幹嘛呢？假設求解最大值，就像圖裡面看到的X0是初值點，不論你用梯度什麼方向，什麼步長，他最終會收斂在（X1，Y1）這個點，整個過程叫做絕對上山過程，這個叫做局部最優，而模擬退火就是說你選擇了X0作為初值點，假設下一個迭代的點X1帶入目標函數F（X1）的值小於F（X0）的的值，也就是說下山了，咱也以一定的概率接受。這樣就在一定概率上可以解決局部最優的情況。不知道這個說法合不合適。當然模擬退火它所謂的全局最優也只是人們在心裏面的一個理想狀態，實際在求解過程中，真的很少能夠達到。
接下來講另一種演算法：信賴域演算法。這個演算法更簡單粗暴，它的主要修正是步長，也就是說，我們先在當前初始值附近構建一個近似原目標函數的近似模型。假設一個比較大的步長（試探步長），從初值迭代到新的值，對比兩個模型的結果之間的比值γ，如果這個值接近1，說明近似函數與原函數的近似程度很好，此時應該增大一下原來的試探步長，如果這個值大於0但是不接近1，那麼就保持原步長，如果這個值接近於0，則此時要縮小步長。通俗點來說我以某個圖像來說吧，還是圖像比較實在：
就是說你選了一個試探步長，結果呢算出來的值太小，（紅色圈內的黑色圈就是表示算的太小），那就加大這個步長，如果這個黑色圈太大，那就縮小這個試探步長，直到合適為止。這玩意說來說去它還是只能在一定程度上來進行局部最優，如果說最優解的點根本不是這個紅色圈，紅色圈只是一個極值點，那麼它還是不能說是最優解。這個時候，只能說在約束範圍內盡量求解最優。至於怎麼編程，網上都有好多呢，我只是講講這個概念。【圖文】信賴域方法_百度文庫
到後面的發展，人類根據動物的一些行為，出現了遺傳演算法、粒子群演算法、神經網路演算法、禁忌搜索等等，太多了，反正挺有意思
我看別人講了關於啟發式演算法的一些小故事挺有道理，啟發式演算法總結 - E_ROAD_BY_U的博客 - CSDN博客如下：
啟發式演算法蘊含著許多人生哲學，它雖不是數學方法，其思想更類似於人類解決問題的思想和一些人生中總結的道理，值得好好體會。最後用網上一段描述局部搜索的例子來作為總結：
為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。
· 兔子朝著比現在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是Iterative Improvement，它不能保證局部最優值就是全局最優值。
·兔子喝醉了。他隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了並朝最高方向跳去。這就是模擬退火。
·兔子們知道一個兔的力量是渺小的。他們互相轉告著，哪裡的山已經找過，並且找過的每一座山他們都留下一隻兔子做記號。他們制定了下一步去哪裡尋找的策略。這就是禁忌搜索。
兔子們吃了失憶藥片，並被發射到太空，然後隨機落到了地球上的某些地方。他們不知道自己的使命是什麼。但是，如果你過幾年就殺死一部分海拔低的兔子，多產的兔子們自己就會找到珠穆朗瑪峰。這就是遺傳演算法。
太累了，以後再來慢慢講這幾個演算法的通俗理解吧。 然後最後會講講我讀書的時候學習的兩個用的最多的演算法——SPSA演算法和魯棒優化演算法。
推薦閱讀：
