現代優化演算法pdf

Ⅰ 《高效演算法競賽、應試與提高必修128例》pdf下載在線閱讀，求百度網盤雲資源

《高效演算法》（[法] Christoph Dürr）電子書網盤下載免費在線閱讀

資源鏈接：

鏈接：https://pan..com/s/17jSKaBY6XgJIvU0DczbbOA

提取碼：ettv

書名：高效演算法

作者：[法] Christoph Dürr

譯者：史世強

出版社：人民郵電出版社

出版年份：2018-5

頁數：204

內容簡介：

本書旨在探討如何優化演算法效率，詳細闡述了經典演算法和特殊演算法的實現、應用技巧和復雜度驗證過程，內容由淺入深，能幫助讀者快速掌握復雜度適當、正確率高的高效編程方法以及自檢、自測技巧，是參加ACM/ICPC、Google Code Jam 等國際編程競賽、備戰編程考試、提高編程效率、優化編程方法的參考書目。

作者簡介：

Christoph Dürr

法國國家科學研究院研究員，巴黎皮埃爾-瑪麗•居里大學博士生導師，Operation Research科研組研究主任。

Jill-Jênn Vie

法國高等電力學院博士、演算法講師，擔任法國高等師范學院Paris-Saclay團隊在ACM競賽中的演算法導師；曾任法國國際編程大賽Prologin主席，並於2014年獲Google RISE Award。

Ⅱ 傳統優化演算法和現代優化演算法包括哪些.區別是什麼

1. 傳統優化演算法一般是針對結構化的問題，有較為明確的問題和條件描述，如線性規劃，二次規劃，整數規劃，混合規劃，帶約束和不帶約束條件等，即有清晰的結構信息；而智能優化演算法一般針對的是較為普適的問題描述，普遍比較缺乏結構信息。

2. 傳統優化演算法不少都屬於凸優化范疇，有唯一明確的全局最優點；而智能優化演算法針對的絕大多數是多極值問題，如何防止陷入局部最優而盡可能找到全局最優是採納智能優化演算法的根本原因：對於單極值問題，傳統演算法大部分時候已足夠好，而智能演算法沒有任何優勢；對多極值問題，智能優化演算法通過其有效設計可以在跳出局部最優和收斂到一個點之間有個較好的平衡，從而實現找到全局最優點，但有的時候局部最優也是可接受的，所以傳統演算法也有很大應用空間和針對特殊結構的改進可能。

3. 傳統優化演算法一般是確定性演算法，有固定的結構和參數，計算復雜度和收斂性可做理論分析；智能優化演算法大多屬於啟發性演算法，能定性分析卻難定量證明，且大多數演算法基於隨機特性，其收斂性一般是概率意義上的，實際性能不可控，往往收斂速度也比較慢，計算復雜度較高。

Ⅲ 優化演算法筆記（七）差分進化演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
差分進化演算法（Differential Evolution Algorithm，DE）是一種基於群體的進化演算法，它模擬了群體中的個體的合作與競爭的過程。演算法原理簡單，控制參數少，只有交叉概率和縮放比例因子，魯棒性強，易於實現。
差分進化演算法中，每一個個體的基因表示待求問題的一個候選解。每次迭代將先進行變異操作，選擇一個或多個個體的基因作為基，然後選擇不同的個體的差分來構成差分基因，最後將作為基的基因與差分基因相加來得出新的個體。交叉操作將新的個體將於父代的對應個體交叉，然後進行選擇操作，比較交叉後的個體與父代的對應個體，選擇較優的個體保留至下一代。在迭代完成之後將選擇種群中最優個體的基因作為解。
差分進化演算法可以算是我所使用過的優化演算法中大魔王級別的演算法，雖然它每個方面都沒有強到離譜，但是綜合起來的效果好於大多數演算法。它就像一個每個科目都能考到90分（百分制）的學生，雖然沒門課都不是最優秀的，但是論綜合，論總分，它有極大的概率是第一名。

在我研究優化演算法的小路上，我的目標就是找到一個能打敗大魔王或是能在大多數方面壓制魔王的演算法。

這次的主角就選魔王軍吧（或者蟻王軍，為了與蟻群演算法區別還是叫魔王軍吧），個體則稱之為魔王兵。
魔王兵的能力取決於它們的基因，它們可以根據環境或者需要改變自己的基因使得自己更加強大，更方便的處理問題，問題的維度與基因維度相同。

表示第i個魔王兵在進化了第t次後的基因，該個體有D位基因。
與遺傳演算法同為進化演算法的差分進化演算法，它們的操作（運算元）也都非常相似的，都是交叉，變異和選擇，流程也幾乎一樣（遺傳演算法先交叉後變異，差分進化演算法先變異後交叉）。

說到差分進化演算法中的變異，我就想到一句論語 「三人行，必有我師焉。擇其善者而從之，其不善者而改之。」 ，其實這句論語已經向我們說明了差分進化演算法的整個流程：
「三人行，必有我師焉」——變異，交叉。
「擇其善者而從之，其不善者而改之」——選擇。
差分進化演算法中，當一個魔王兵變異時，它會先找來3個小夥伴，當然是隨機找來3個小夥伴，避免同化。在一個小夥伴的基因上加上另外兩個小夥伴基因之差作為自己的目標基因。其變異公式如下：

表示第i個魔王兵找到了編號為r1、r2和r3的三個魔王兵，當然了i、r1、r2、r3為互不相同的整數，F為縮放比例因子，通常 ，一般取F=0.5。 為第i個魔王兵交叉後的目標基因圖紙，不過這是個半成品，再經過交叉後，目標基因圖紙才算完成。
其實現在我們已經有了5個基因圖紙了 ，接下來將進行交叉操作。由於變異操作，差分進化演算法的種群中個體數至少為4，即魔王軍中至少有4個小兵。

交叉操作中，魔王兵i會將目標基因圖紙 進行加工得到 ，加工過程如下：

其中 。 為交叉概率，其值越大，發生交叉的概率越大，一般取 。 為{1,2,…,D}中的隨機整數，其作用是保證交叉操作中至少有一維基因來自變異操作產生的基因，不能讓交叉操作的努力白費。
從公式上可以看出交叉操作實際上是從變異操作得出的基因圖紙上選擇至少一位基因來替換自己的等位基因，得到最終的基因圖紙。

選擇操作相對簡單，魔王兵i拿到了最終的基因圖紙 ，大喊一聲，進化吧，魔王兵i的基因改變了。它拿出了能力測量器fitness function,如果發現自己變強了，那麼就將基因 保留到下一代，否則它選擇放棄進化，讓自己還原成 。

實驗又來啦，還是那個實驗 ，簡單、易算、好畫圖。
實驗1 ：參數如下

圖中可以看出在第20代時，群體已經非常集中了，在來看看最終得出的結果。

這結果真是好到令人發指，惡魔在心中低語「把其他的優化演算法都丟掉吧」。不過別往心裡去，任何演算法都有優缺點，天下沒有免費的午餐，要想獲得某種能力必須付出至少相應的代價。
實驗2：
將交叉率CR設為0,即每次交叉只選擇保留一位變異基因。

看看了看圖，感覺跟實驗1中相比沒有什麼變化，那我們再來看看結果。

結果總體來說比實驗1好了一個數量級。為什麼呢？個人感覺應該是每次只改變一位基因的局部搜索能力比改變多位基因更強。下面我們將交叉率CR設為1來看看是否是這樣。
實驗3：
將交叉率CR設為1,即每次交叉只選擇保留一位原有基因。

實驗3的圖與實驗1和實驗2相比好像也沒什麼差別,只是收斂速度好像快了那麼一點點。再來看看結果。

發現結果比實驗2的結果還要好？那說明了實驗2我得出的結論是可能是錯誤的，交叉率在該問題上對差分進化演算法的影響不大，它們結果的差異可能只是運氣的差異，畢竟是概率演算法。
實驗4：
將變異放縮因子設為0，即變異只與一個個體有關。

收斂速度依然很快，不過怎麼感覺結果不對，而且個體收斂的路徑好像遺傳演算法，當F=0，時，差分進化演算法退化為了沒有變異、選擇操作的遺傳演算法，結果一定不會太好。

果然如此。下面我們再看看F=2時的實驗。
實驗5：
將變異放縮因子設為2。

實驗5的圖可以明顯看出，群體的收斂速度要慢了許多，到第50代時，種群還未完全收斂於一點，那麼在50代時其結果也不會很好，畢竟演算法還未收斂就停止進化了。

結果不算很好但也算相對穩定。

通過上面5個實驗，我們大致了解了差分進化演算法的兩個參數的作用。
交叉率CR，影響基因取自變異基因的比例，由於至少要保留一位自己的基因和變異的基因導致CR在該問題上對演算法性能的影響不大（這個問題比較簡單，維度較低，影響不大）。
變異放縮因子F，影響群體的收斂速度，F越大收斂速度越慢，F絕對值越小收斂速度越快，當F=0是群體之間只會交換基因，不會變異基因。

差分進化演算法大魔王已經如此強大了，那麼還有什麼可以改進的呢？當然有下面一一道來。
方案1 .將3人行修改為5人行，以及推廣到2n+1人行。
實驗6：
將3人行修改為5人行，變異公式如下：

五人行的實驗圖看起來好像與之前並沒有太大的變化，我們再來看看結果。

結果沒有明顯提升，反而感覺比之前的結果差了。反思一下五人行的優缺點，優點，取值范圍更大，缺點，情況太多，減慢搜索速度。

可以看出演算法的收斂速度比之前的變慢了一點，再看看結果。

比之前差。

差分進化演算法的學習在此也告一段落。差分進化演算法很強大，也很簡單、簡潔，演算法的描述都充滿了美感，不愧是大魔王。不過這里並不是結束，這只是個開始，終將找到打敗大魔王的方法，讓新的魔王誕生。
由於差分進化演算法足夠強，而文中實驗的問題較為簡單導致演算法的改進甚至越改越差（其實我也不知道改的如何，需要大量實驗驗證）。在遙遠的將來，也會有更加復雜的問題來檢驗魔王的能力，總之，後會無期。
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（六）遺傳演算法
下一篇 優化演算法筆記（八）人工蜂群演算法

優化演算法matlab實現（七）差分進化演算法matlab實現

Ⅳ 優化演算法筆記（十八）灰狼演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
灰狼演算法（Grey Wolf Algorithm）是受灰狼群體捕獵行為啟發而提出的演算法。演算法提出於2013年，仍是一個較新的演算法。目前為止（2020）與之相關的論文也比較多，但多為演算法的應用，應該仍有研究和改進的餘地。
灰狼演算法中，每隻灰狼的位置代表了解空間中的一個可行解。群體中，占據最好位置的三隻灰狼為狼王及其左右護法（衛）。在捕獵過程中這三隻狼將帶領著狼群蛇皮走位，抓捕獵物，直至找到獵物（最優解）。當然狼王不會一直是狼王，左右護法也是一樣，每一輪走位後，會根據位置的優劣重新選出新的狼王和左右護法。狼群中的每一隻灰狼會向著（也可能背向）這三隻位置最優的灰狼移動一定的距離，來決定這一步自己將如何走位。簡單來說， 灰狼個體會向則群體中最優的三個個體移動 。

很明顯該演算法的主角就是灰狼了。

設定目標灰狼為
，當前灰狼的為 ，則該灰狼向著目標灰狼移動後的位置 可以由一下公式計算得出：

灰狼群體中位置最好的三隻灰狼編號為1,2,3，那麼當前的灰狼i通過觀察灰狼1、灰狼2和灰狼3，根據公式（1）得出的三個位置為Xi1,Xi2,Xi3。那麼灰狼i將要移動到的位置可以根據以下供述計算得出：

可以看出該灰狼的目標位置是通過觀察三隻頭狼得到的三個目標位置的所圍成的區域的質心。（質心超出邊界時，取值為邊界值）。

灰狼演算法的論文描述很多，但是其公式和流程都非常簡單，主要對其參數A和C的作用效果進行了詳細描述。
C主要決定了新位置相對於目標灰狼的方位，而A則決定新位置向目標靠近還是遠離目標灰狼。當|A|>=1時，為遠離目標，表現出更強的全局搜索能力，|A|<1時靠近目標，表現出更強的局部搜索能力。

適應度函數 。
實驗一：

看看這圖像和結果，效果好極了。每當我這么認為時，總會出現意想不到的轉折。
修改一下最優解位置試一試， 。
實驗二 ： 。

其結果比上面的實驗差了不少，但我覺得這才是一個優化演算法應有的搜索圖像。其結果看上去較差只是因為迭代次數較少，收斂不夠迅速，這既是優點也是缺點，收斂慢但是搜索更細致。
仔細分析灰狼演算法的流程，它並沒有向原點靠近的趨勢，那隻能理解為演算法群體總體上向著群體的中心移動。 猜想 ：當初始化群體的中心恰好是正解時，演算法的結果將會非常的好。
下面使用 ，並將灰狼的初始位置限定在（50,100）的范圍內，看看實驗圖像是否和實驗二的圖像一致。

實驗三 . ,初始種群取值范圍為（50,100）

這圖像和結果跟實驗一的不是一樣的嗎?這說明從實驗二中得出的猜想是錯誤的。

從圖像和結果上看，都和實驗二非常相似，當解在解空間的中心時但不在原點時，演算法的結果將差一些。
為什麼會這樣呢？從演算法的流程上看，灰狼演算法的各個行為都是關於頭狼對稱的，當最優解在原點且頭狼在附近時，公式（1）將變為如下：

實驗五 . ,三隻頭狼添加貪心演算法。

從圖像可以看出中心的三個點移動的頻率要比其他點的移動頻率低。從結果上可以看出其結果相對穩定了不少，不過差距非常的小，幾乎可以認為是運氣好所導致。如果所有的個體都添加貪心演算法呢？顯然，演算法的全局搜索能力將進一步減弱，並且更容易向群體中心收斂，這並不是一個好的操作。

實驗六 . ,
在實驗五的基礎上為狼群添加一個統一的步長，即每隻狼每次向著目標狼移動的距離不能大於其步長，將其最大步長設為1，看看效果。

從圖像可以看出，受到步長的約束每隻狼的移動距離較小，在結束時還沒有收斂，其搜索能力較強但收斂速度過慢且極易陷入局部最優。現在將最大步長設置為10（1/10解空間范圍）使其搜索能力和收斂速度相對平衡，在看看效果。

從圖像可以看出，演算法的收斂速度快了不少，但從結果可知，相較於實驗五，演算法的提升並不太大。
不過這個圖像有一種似曾相識的感覺，與螢火蟲演算法（FireFly Algorithm）差不多，仔細對比這兩個演算法可以發現， 灰狼演算法相當於螢火蟲演算法的一個簡化 。實驗六種對灰狼演算法添加步長的修改，讓其離螢火蟲演算法更近了一步。

實驗七 . ,
在實驗六的基礎上讓最大步長隨著迭代次數增加遞減。

從實驗七的圖像可以看出，種群的收斂速度好像快了那麼一點，結果也變好了不少。但是和改進後的螢火蟲演算法相比仍然有一定的差距。
灰狼演算法在全局搜索和局部搜索上的平衡已經比較好了，嘗試過對其進行改進，但是修改使搜索能力更強時，對於局部最優的函數求解效果很差，反之結果的精度較低，總體而言修改後的演算法與原演算法相差無幾。

灰狼演算法是根據灰狼群體的捕獵行動而提出的優化演算法，其演算法流程和步驟非常簡單，數學模型也非常的優美。灰狼演算法由於沒有貪心演算法，使得其有著較強的全局搜索能力同時參數A也控制了演算法的局部搜索范圍，演算法的全局搜索能力和局部搜索能力比較平衡。
從演算法的優化圖像可以看出，灰狼演算法和螢火蟲演算法非常的相似。可以認為，灰狼演算法是對螢火蟲演算法的一種改進。螢火蟲演算法向著由於自己的個體飛行，而灰狼演算法則的條件更為苛刻，向著群體前三強前進，螢火蟲演算法通過步長控制搜索范圍，而灰狼演算法則直接定義搜索范圍參數A，並令A線性遞減。
灰狼演算法的結構簡單，但也不容易改進，數次改進後只是改變了全局搜索能力和局部搜索能力的比例，綜合能力並沒有太大變化。
由於原點對於灰狼演算法有著隱隱的吸引力，當測試函數目標值在原點時，其結果會異常的好。因此，灰狼演算法的實際效果沒有論文中的那麼好，但也不差，算是一個中規中矩的優化演算法。
參考文獻
Mirjalili S , Mirjalili S M , Lewis A . Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69:46-61. 提取碼：wpff

以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（十七）萬有引力演算法
下一篇 優化演算法筆記（十九）頭腦風暴演算法

優化演算法matlab實現（十八）灰狼演算法matlab實現

Ⅳ 優化演算法筆記（二）優化演算法的分類

（以下描述，均不是學術用語，僅供大家快樂的閱讀）

在分類之前，我們先列舉一下常見的優化演算法（不然我們拿什麼分類呢？）。
1遺傳演算法Genetic algorithm
2粒子群優化演算法Particle Swarm Optimization
3差分進化演算法Differential Evolution
4人工蜂群演算法Artificial Bee Colony
5蟻群演算法Ant Colony Optimization
6人工魚群演算法Artificial Fish Swarm Algorithm
7杜鵑搜索演算法Cuckoo Search
8螢火蟲演算法Firefly Algorithm
9灰狼演算法Grey Wolf Optimizer
10鯨魚演算法Whale Optimization Algorithm
11群搜索演算法Group search optimizer
12混合蛙跳演算法Shuffled Frog Leaping Algorithm
13煙花演算法fireworks algorithm
14菌群優化演算法Bacterial Foraging Optimization
以上優化演算法是我所接觸過的演算法，沒接觸過的演算法不能隨便下結論，知之為知之，不知為不知。其實到目前為止優化演算法可能已經有幾百種了，我們不可能也不需要全面的了解所有的演算法，而且優化演算法之間也有較大的共性，深入研究幾個之後再看其他優化演算法上手速度會灰常的快。
優化演算法從提出到現在不過50-60年（遺傳演算法1975年提出），雖種類繁多但大多較為相似，不過這也很正常，比較香蕉和人的基因相似度也有50%-60%。當然演算法之間的相似度要比香蕉和人的相似度更大，畢竟人家都是優化演算法，有著相同的目標，只是實現方式不同。就像條條大路通羅馬，我們可以走去，可以坐汽車去，可以坐火車去，也可以坐飛機去，不管使用何種方式，我們都在去往羅馬的路上，也不會說坐飛機去要比走去更好，交通工具只是一個工具，最終的方案還是要看我們的選擇。

上面列舉了一些常見的演算法，即使你一個都沒見過也沒關系，後面會對它們進行詳細的介紹，但是對後面的分類可能會有些許影響，不過問題不大，就先當總結看了。
再對優化演算法分類之前，先介紹一下演算法的模型，在筆記（一）中繪制了優化演算法的流程，不過那是個較為簡單的模型，此處的模型會更加復雜。上面說了優化演算法有較大的相似性，這些相似性主要體現在演算法的運行流程中。
優化演算法的求解過程可以看做是一個群體的生存過程。

有一群原始人，他們要在野外中尋找食物，一個原始人是這個群體中的最小單元，他們的最終目標是尋找這個環境中最容易獲取食物的位置，即最易存活下來的位置。每個原始人都去獨自尋找食物，他們每個人每天獲取食物的策略只有採集果實、製作陷阱或者守株待兔，即在一天之中他們不會改變他們的位置。在下一天他們會根據自己的策略變更自己的位置。到了某一天他們又聚在了一起，選擇了他們到過的最容易獲取食物的位置定居。
一群原始人=優化演算法中的種群、群體；
一個原始人=優化演算法中的個體；
一個原始人的位置=優化演算法中個體的位置、基因等屬性；
原始人變更位置=優化演算法中總群的更新操作；
該位置獲取食物的難易程度=優化演算法中的適應度函數；
一天=優化演算法中的一個迭代；
這群原始人最終的定居位置=優化演算法所得的解。
優化演算法的流程圖如下：

對優化演算法分類得有個標准，按照不同的標准分類也會得到不一樣的結果。首先說一下我所使用的分類標准（動態更新，有了新的感悟再加）：

按由來分類比較好理解，就是該演算法受何種現象啟發而發明，本質是對現象分類。

可以看出演算法根據由來可以大致分為有人類的理論創造而來，向生物學習而來，受物理現象啟發。其中向生物學習而來的演算法最多，其他類別由於舉例有偏差，不是很准確，而且物理現象也經過人類總結，有些與人類現象相交叉，但仍將其獨立出來。
類別分好了，那麼為什麼要這么分類呢？

當然是因為要湊字數啦，啊呸，當然是為了更好的理解學習這些演算法的原理及特點。
向動物生存學習而來的演算法一定是一種行之有效的方法，能夠保證演算法的效率和准確性，因為，如果使用該策略的動物無法存活到我們可以對其進行研究，我們也無法得知其生存策略。（而這也是一種倖存者偏差，我們只能看到行之有效的策略，但並不是我們沒看到的策略都是垃圾，畢竟也發生過小行星撞地球這種小概率毀滅性事件。講個冷笑話開cou心一shu下:一隻小恐龍對他的小夥伴說，好開心，我最喜歡的那顆星星越來越亮了（完）。）但是由於生物的局限性，人們所創造出的演算法也會有局限性：我們所熟知的生物都生存在三維空間，在這些環境中，影響生物生存的條件比較有限，反應到演算法中就是這些演算法在解決較低維度的問題時效果很好，當遇到超高維（維度>500）問題時，結果可能不容樂觀，沒做過實驗，我也不敢亂說。

按更新過程分類相對復雜一點，主要是根據優化演算法流程中更新位置操作的方式來進行分類。更新位置的操作按我的理解可大致分為兩類：1.跟隨最優解；2.不跟隨最優解。
還是上面原始人的例子，每天他有一次去往其他位置狩獵的機會，他們採用何種方式來決定今天自己應該去哪裡呢？
如果他們的策略是「跟隨最優解」，那麼他們選取位置的方式就是按一定的策略向群體已知的最佳狩獵位置（歷史最佳）或者是當前群體中的最佳狩獵位置（今天最佳）靠近，至於是直線跑過去還是蛇皮走位繞過去，這個要看他們群體的策略。當然，他們的目的不是在最佳狩獵位置集合，他們的目的是在過去的途中看是否能發現更加好的狩獵位置，去往已經到過的狩獵地點再次狩獵是沒有意義的，因為每個位置獲取食物的難易程度是固定的。有了目標，大家都會朝著目標前進，總有一日，大家會在謀個位置附近相聚，相聚雖好但不利於後續的覓食容易陷入局部最優。
什麼是局部最優呢？假設在當前環境中有一「桃花源」，擁有上帝視角的我們知道這個地方就是最適合原始人們生存的，但是此地入口隱蔽「山有小口，彷彿若有光」、「初極狹，才通人。」，是一個難以發現的地方。如果沒有任何一個原始人到達了這里，大家向著已知的最優位置靠近時，也難以發現這個「桃源之地」，而當大家越聚越攏之後，「桃源」被發現的可能性越來越低。雖然原始人們得到了他們的解，但這並不是我們所求的「桃源」，他們聚集之後失去了尋求「桃源」的可能，這群原始人便陷入了局部最優。

如果他們的策略是「不跟隨最優解」，那麼他們的策略是什麼呢？我也不知道，這個應該他們自己決定。畢竟「是什麼」比「不是什麼」的范圍要小的多。總之不跟隨最優解時，演算法會有自己特定的步驟來更新個體的位置，有可能是隨機在自己附近找，也有可能是隨機向別人學習。不跟隨最優解時，原始人們應該不會快速聚集到某一處，這樣一來他們的選擇更具多樣性。
按照更新過程對上面的演算法分類結果如下

可以看出上面不跟隨最優解的演算法只有遺傳演算法和差分進化演算法，他們的更新策略是與進化和基因的重組有關。因此這些不跟隨最優解的演算法，他們大多依據進化理論更新位置（基因）我把他們叫做進化演算法，而那些跟隨群體最優解的演算法，他們則大多依賴群體的配合協作，我把這些演算法叫做群智能演算法。

目前我只總結了這兩種，分類方法，如果你有更加優秀的分類方法，我們可以交流一下：

目錄
上一篇 優化演算法筆記（一）優化演算法的介紹
下一篇 優化演算法筆記（三）粒子群演算法（1）

Ⅵ 優化演算法總結

本文介紹一下機器學習和深度學習中常用的優化演算法和優化器以及一些其他我知道的優化演算法,部分演算法我也沒有搞懂,就先記錄下來以後慢慢研究吧.*_*.

1.梯度下降演算法(Gradient Descent)

梯度下降法可以參考我另一篇文章 機器學習-線性回歸 里的講解,這里就不在重復敘述.這里需要強調一下,深度學習里常用的SGD,翻譯過來是隨機梯度下降,但是實質是mini-batch梯度下降(mini-batch-gd),或者說是兩者的結合更准確一些.

SGD的優點是,演算法簡單,計算量小,在函數為凸函數時可以找到全局最優解.所以是最常用的優化演算法.缺點是如果函數不是凸函數的話,很容易進入到局部最優解而無法跳出來.同時SGD在選擇學習率上也是比較困難的.

2.牛頓法

牛頓法和擬牛頓法都是求解無約束最優化問題的常用方法,其中牛頓法是迭代演算法,每一步需要求解目標函數的海森矩陣的逆矩陣,計算比較復雜.

牛頓法在求解方程根的思想:在二維情況下,迭代的尋找某一點x,尋找方法是隨機一個初始點x_0,目標函數在該點x_0的切線與x坐標軸的交點就是下一個x點,也就是x_1.不斷迭代尋找x.其中切線的斜率為目標函數在點x_0的導數(梯度),切必過點(x_0,f(x_0)).所以迭代的方程式如圖1,為了求該方程的極值點,還需要令其導數等於0,也就是又求了一次導數,所以需要用到f(x)的二階導數.

在最優化的問題中,牛頓法提供了一種求解的辦法. 假設任務是優化一個目標函數f, 求函數ff的極大極小問題, 可以轉化為求解函數f導數等於0的問題, 這樣求可以把優化問題看成方程求解問題(f的導數等於0). 剩下的問題就和牛頓法求解方程根的思想很相似了.

目標函數的泰勒展開式:

化簡後:

這樣就得到了與圖1相似的公式,這里是二維的,在多維空間上,求二階導數就是求海森矩陣,因為是分母,所以還需要求海森矩陣的逆矩陣.

牛頓法和SGD的區別:

牛頓法是二階求導,SGD是一階求導,所以牛頓法要收斂的更快一些.SGD只考慮當前情況下梯度下降最快的方向,而牛頓法不僅考慮當前梯度下降最快,還有考慮下一步下降最快的方向.

牛頓法的優點是二階求導下降速度快,但是因為是迭代演算法,每一步都需要求解海森矩陣的逆矩陣,所以計算復雜.

3.擬牛頓法(沒搞懂,待定)

考慮到牛頓法計算海森矩陣比較麻煩,所以它使用正定矩陣來代替海森矩陣的逆矩陣,從而簡化了計算過程.

常用的擬牛頓法有DFP演算法和BFGS演算法.

4.共軛梯度法(Conjugate Gradient)

共軛梯度法是介於最速下降法與牛頓法之間的一個方法,它僅需利用一階導數信息,但克服了最速下降法收斂慢的缺點,又避免了牛頓法計算海森矩陣並求逆的缺點.共軛梯度法不僅是解決大型線性方程組最有用的方法之一,也是解大型非線性最優化最有效的演算法之一.

5.拉格朗日法

參考SVM里的講解 機器學習-SVM

6.動量優化法(Momentum)

動量優化法主要是在SGD的基礎上,加入了歷史的梯度更新信息或者說是加入了速度更新.SGD雖然是很流行的優化演算法,但是其學習過程很慢,因為總是以同樣的步長沿著梯度下降的方向.所以動量是為了加速學習的方法.

其中第一行的減號部分是計算當前的梯度,第一行是根據梯度更新速度v,而α是新引進的參數,在實踐中,α的一般取值為 0.5,0.9 和 0.99.和學習率 一樣,α 也會隨著時間不斷調整.一般初始值是一個較小的值,隨後會慢慢變大.

7.Nesterov加速梯度(NAG, Nesterov accelerated gradient)

NAG是在動量優化演算法的基礎上又進行了改進.根據下圖可以看出,Nesterov 動量和標准動量之間的區別體現在梯度計算上, Nesterov 動量中,梯度計算在施加當前速度之後.因此,Nesterov 動量可以解釋為往標准動量方法中添加了一個校正因子

8.AdaGrad演算法

AdaGrad演算法,自適應優化演算法的一種,獨立地適應所有模型參數的學習率,縮放每個參數反比於其所有梯度歷史平均值總和的平方根.具有代價函數最大梯度的參數相應地有個快速下降的學習率,而具有小梯度的參數在學習率上有相對較小的下降.通俗一點的講,就是根據實際情況更改學習率,比如模型快要收斂的時候,學習率步長就會小一點,防止跳出最優解.

其中g是梯度,第一行的分母是計算累計梯度的平方根, 是為了防止分母為0加上的極小常數項,α是學習率.

Adagrad的主要優點是不需要人為的調節學習率,它可以自動調節.但是依然需要設置一個初始的全局學習率.缺點是隨著迭代次數增多,學習率會越來越小,最終會趨近於0.

9.RMSProp演算法

RMSProp修改 AdaGrad 以在非凸設定下效果更好,改變梯度積累為指數加權的移動平均.AdaGrad旨在應用於凸問題時快速收斂.

10.AdaDelta演算法

11.Adam演算法

Adam是Momentum和RMSprop的結合體,也就是帶動量的自適應優化演算法.

12.Nadam演算法

13.模擬退火演算法

14.蟻群演算法

15.遺傳演算法

動量是為了加快學習速度,而自適應是為了加快收斂速度,注意學習速度快不一定收斂速度就快,比如步長大學習速度快,但是很容易跳出極值點,在極值點附近波動,很難達到收斂.

未完待定....

參考:

《統計學習方法》  李航    著

《深度學習》  花書

Ⅶ 優化演算法筆記（一）優化演算法的介紹

（以下描述，均不是學術用語，僅供大家快樂的閱讀）

        我們常見常用的演算法有排序演算法,字元串遍歷演算法,尋路演算法等。這些演算法都是為了解決特定的問題而被提出。

        演算法本質是一種按照固定步驟執行的過程。

        優化演算法也是這樣一種過程，是一種根據概率按照固定步驟尋求問題的最優解的過程。與常見的排序演算法、尋路演算法不同的是，優化演算法不具備等冪性，是一種 概率演算法 。演算法不斷的 迭代 執行同一步驟直到結束，其流程如下圖。

        等冪性即 對於同樣的輸入，輸出是相同的 。

        比如圖1，對於給定的魚和給定的熊掌，我們在相同的條件下一定可以知道它們誰更重，當然，相同的條件是指魚和熊掌處於相同的重力作用下，且不用考慮水分流失的影響。在這些給定的條件下，我們（無論是誰）都將得出相同的結論，魚更重或者熊掌更重。我們可以認為，秤是一個等冪性的演算法（工具）。

        現在把問題變一變，問魚與熊掌你更愛哪個，那麼現在，這個問題，每個人的答案可能不會一樣，魚與熊掌各有所愛。說明喜愛這個演算法不是一個等冪性演算法。當然你可能會問，哪個更重，和更喜歡哪個這兩個問題一個是客觀問題，一個是主觀問題，主觀問題沒有確切的答案的。當我們處理主觀問題時，也會將其轉換成客觀問題，比如給喜歡魚和喜歡熊掌的程度打個分，再去尋求答案，畢竟計算機沒有感情，只認0和1（量子計算機我不認識你）。

        說完了等冪性，再來說什麼是概率演算法。簡單來說就是看臉、看人品、看運氣的演算法。

        有一場考試，考試的內容全部取自課本，同時老師根據自己的經驗給同學們劃了重點，但是因為試卷並不是該老師所出，也會有考試內容不在重點之內，老師估計試卷中至少80%內容都在重點中。學霸和學渣參加了考試，學霸為了考滿分所以無視重點，學渣為了pass，因此只看了重點。這樣做的結果一定是score(學霸)>=score(學渣)。

        當重點跟上圖一樣的時候，所有的內容都是重點的時候，學霸和學渣的學習策略變成了相同的策略，則score(學霸)=score(學渣)。但同時，學渣也要付出跟學霸相同的努力去學習這些內容，學渣心裡苦啊。

        當課本如下圖時

        學霸？學霸人呢，哪去了快來學習啊，不是說學習一時爽，一直學習一直爽嗎，快來啊，還等什麼。

        這時，如果重點內容遠少於書本內容時，學渣的學習策略有了優勢——花費的時間和精力較少。但是同時，學渣的分數也是一個未知數，可能得到80分也可能拿到100分，分數完全取決於重點內容與題目的契合度，契合度越高，分數越高。對學渣來說，自己具體能考多少分無法由自己決定，但是好在能夠知道大概的分數范圍。

        學霸的學習策略是一種遍歷性演算法，他會遍歷、通讀全部內容，以保證滿分。

        學渣的學習策略則是一種概率演算法，他只會遍歷、學習重點內容，但至於這些重點是不是真重點他也不知道。

        與遍歷演算法相比，概率演算法的結果具有不確定性，可能很好，也可能很差，但是會消耗更少的資源，比如時間（人生），空間（記憶）。概率演算法的最大優點就是 花費較少的代價來獲取最高的收益 ，在現實中體現於節省時間，使用很少的時間得到一個不與最優解相差較多的結果。

        「莊子：吾生也有涯，而知也無涯；以有涯隨無涯，殆矣。」的意思是：人生是有限的，但知識是無限的（沒有邊界的），用有限的人生追求無限的知識，是必然失敗的。

        生活中概率演算法（思想）的應用其實比較廣泛，只是我們很少去注意罷了。關於概率演算法還衍生出了一些有趣的理論，比如墨菲定律和倖存者偏差，此處不再詳述。

        上面說到，優化演算法就是不停的執行同樣的策略、步驟直到結束。為什麼要這樣呢？因為優化演算法是一種概率演算法，執行一次操作就得到最優結果幾乎是不可能的，重復多次取得最優的概率也會增大。

        栗子又來了，要從1-10這10個數中取出一個大於9的數，只取1次，達到要求的概率為10%，取2次，達到要求的概率為19%。

        可以看出取到第10次時，達到要求的概率幾乎65%，取到100次時，達到要求的概率能接近100%。優化演算法就是這樣簡單粗暴的來求解問題的嗎？非也，這並不是一個恰當的例子，因為每次取數的操作之間是相互獨立的，第2次取數的結果不受第1次取數結果的影響，假設前99次都沒達到要求，那麼再取一次達到要求的概率跟取一次達到要求的概率相同。

        優化演算法中，後一次的計算會依賴前一次的結果，以保證後一次的結果不會差於前一次的結果。這就不得不談到馬爾可夫鏈了。

        由鐵組成的鏈叫做鐵鏈，同理可得，馬爾可夫鏈就是馬爾可夫組成的鏈。

        言歸正傳, 馬爾可夫鏈（Markov Chain, MC） ,描述的是 狀態轉移的過程中,當前狀態轉移的概率只取決於上一步的狀態,與其他步的狀態無關 。簡單來說就是當前的結果只受上一步的結果的影響。每當我看到馬爾可夫鏈時，我都會陷入沉思，生活中、或者歷史中有太多太多與馬爾可夫鏈相似的東西。西歐封建等級制度中「附庸的附庸不是我的附庸」與「昨天的努力決定今天的生活，今天的努力決定明天的生活」，你的下一份工作的工資大多由你當前的工資決定，這些都與馬爾可夫鏈有異曲同工之處。

        還是從1-10這10個數中取出一個大於9的數的這個例子。基於馬爾可夫鏈的概率演算法在取數時需要使當前取的數不小於上一次取的數。比如上次取到了3，那麼下次只能在3-10這幾個數中取，這樣一來，達到目標的概率應該會顯著提升。還是用數據說話。

        取1次達到要求的概率仍然是

        取2次內達到要求的概率為

        取3次內達到要求的概率為

        取4次內……太麻煩了算了不算了

        可以看出基於馬爾可夫鏈來取數時，3次內能達到要求的概率與不用馬爾可夫鏈時取6次的概率相當。說明基於馬爾可夫鏈的概率演算法求解效率明顯高於隨機概率演算法。那為什麼不將所有的演算法都基於馬爾可夫鏈呢？原因一，其實現方式不是那麼簡單，例子中我們規定了取數的規則是復合馬爾可夫鏈的，而在其他問題中我們需要建立適當的復合馬爾科夫鏈的模型才能使用。原因二，並不是所有的問題都符合馬爾科夫鏈條件，比如原子內電子出現的位置，女朋友為什麼會生（lou）氣，彩票號碼的規律等，建立模型必須與問題有相似之處才能較好的解決問題。

        介紹完了優化演算法，再來討論討論優化演算法的使用場景。

        前面說了優化演算法是一種概率演算法，無法保證一定能得到最優解，故如果要求結果必須是確定、穩定的值，則無法使用優化演算法求解。

        例1，求城市a與城市b間的最短路線。如果結果用來修建高速、高鐵，那麼其結果必定是唯一確定的值，因為修路寸土寸金，必須選取最優解使花費最少。但如果結果是用來趕路，那麼即使沒有選到最優的路線，我們可能也不會有太大的損失。

        例2，求城市a與城市b間的最短路線，即使有兩條路徑，路徑1和路徑2，它們從a到b的距離相同，我們也可以得出這兩條路徑均為滿足條件的解。現在將問題改一下，求城市a到城市b耗時最少的線路。現在我們無法馬上得出確切的答案，因為最短的線路可能並不是最快的路線，還需要考慮到天氣，交通路況等因素，該問題的結果是一個動態的結果，不同的時間不同的天氣我們很可能得出不同的結果。

        現實生產、生活中，也有不少的場景使用的優化演算法。例如我們的使用的美圖軟體，停車場車牌識別，人臉識別等，其底層參數可能使用了優化演算法來加速參數計算，其參數的細微差別對結果的影響不太大，需要較快的得出誤差范圍內的參數即可；電商的推薦系統等也使用了優化演算法來加速參數的訓練和收斂，我們會發現每次刷新時，推給我們的商品都有幾個會發生變化，而且隨著我們對商品的瀏覽，系統推給我們的商品也會發生變化，其結果是動態變化的；打車軟體的訂單系統，會根據司機和客人的位置，區域等來派發司機給客人，不同的區域，不同的路況，派發的司機也是動態變化的。

        綜上我們可以大致總結一下推薦、不推薦使用優化演算法的場景的特點。

        前面說過，優化演算法處理的問題都是客觀的問題，如果遇到主觀的問題，比如「我孰與城北徐公美」，我們需要將這個問題進行量化而轉換成客觀的問題，如身高——「修八尺有餘」，「外貌——形貌昳麗」，自信度——「明日徐公來，孰視之，自以為不如；窺鏡而自視，又弗如遠甚」，轉化成客觀問題後我們可以得到各個解的分數，通過比較分數，我們就能知道如何取捨如何優化。這個轉化過程叫做問題的建模過程，建立的問題模型實際上是一個函數，這個函數對優化演算法來說是一個黑盒函數，即不需要知道其內部實現只需要給出輸入，得到輸出。

        在優化演算法中這個黑盒函數叫做 適應度函數 ， 優化演算法的求解過程就是尋找適應度函數最優解的過程 ，使用優化演算法時我們最大的挑戰就是如何將抽象的問題建立成具體的模型，一旦合適的模型建立完成，我們就可以愉快的使用優化演算法來求解問題啦。（「合適」二字談何容易）

        優化演算法的大致介紹到此結束，後面我們會依次介紹常見、經典的優化演算法，並探究其參數對演算法性能的影響。

——2019.06.20

[目錄]

[下一篇 優化演算法筆記（二）優化演算法的分類]