與演算法筆記
『壹』 優化演算法筆記（十二）煙花演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
煙花演算法（Firework Algorithm,FWA）是一種受煙花爆炸產生火星，並繼續分裂爆炸這一過程啟發而得出的演算法。演算法的思想簡單，但具體實現復雜。演算法提出時間並不長，但是已經有了不少的改進研究和較為全面的應用。
煙花演算法中，每一個煙花的位置都代表了一個可行解。煙花的爆炸產生的火星有兩種，正常的火星與特別的火星。每個火星都會爆炸產生數個正常火星，某些火星有一定的概率產生一個特別的火星。正常的火星根據當前火星的振幅隨機均勻分布在該火星的周圍，而特別的火星將在當前火星附近以正態分布方式產生。每次迭代產生的火星數量多於每一代應有的火星數，演算法將參照火星位置的優劣，隨機留下指定數量的火星，已保持火星數目的穩定。
煙花演算法的主角毫無疑問就是煙花了。
式（1）為適應度值越小越優的情況，而式（2）則是適應度值越大越優的情況。 為一個極小的值，以保證分母不為0。
每個火星產生的正常火星數量也由其適應度值來決定。
其中 表示第i個火星將要產生的正常火星數， 是產生正常火星的總數為一個常數，從式（3）,（4）可以看出適應度值越好的火星能夠產生更多的正常火星，反之，火星適應度越差，能夠產生的火星數越少。
由於式（3），（4）計算出的值為小數，煙花演算法中使用式（5）將其轉化為整數。
從式（3）和式（4）中可以看出，在每一代中將會產生出 個正常火星。產生的正常火星的位置與當前火星的振幅有關，可以從式（1），（2）看出，適應度越優的火星的振幅越小，那麼它產生的正常火星將在它自己周圍，而適應度越差的火星的振幅越大，它產生的正常火星將會出現在離自己較遠的位置。
當前火星每次爆炸會從D維搜索空間內隨機選擇z維進行更新從而產生新的火星。正常火星的位置由如下公式產生。
其中z為取值1-D的均勻隨機正整數，rand(-1,1)表示-1到1內的均勻隨機數。從式(6)中可以看出，正常火星的位置與其振幅有直接關系，振幅越大產生的新火星距當前火星的距離約遠。
每次迭代過程中，會產生m個特別的火星，即在這N個火星中隨機選擇m個火星，每個火星產生一個特別的火星。特別的火星的由下面的公式產生：
由上面的過程可知，在每一代中，有N個火星，將會產生出 個正常火星以及m個特別的火星。但是每一代中只能從這 個火星中選擇N個火星保留至下一代。
每次會先從 個火星中選擇最優的火星保留至下一代，然後再從中選擇N-1個火星。選擇某個火星的概率如下：
其中R(X)表示該火星距其他所有火星的距離之和，即距其它火星越遠的火星，被選擇保留至下一代的概率較大。
個火星，而且
,所有煙花演算法每次迭代的計算復雜度要大於其他演算法，這簡直就是一個作弊行為。別的演算法每次只搜索了N個位置，而煙花演算法卻搜索了 個位置。與其他優化演算法對比時，其他演算法的種群數量應該取 ，否則這將是一場不公正的對決。
適應度函數還是這個簡單的小白鼠
實驗一 ：標准煙花演算法
以上數據來自原論文，現在看一看實驗的圖像以及實驗結果。
從圖像可以看出每次只選擇保留了5個火星，它們的收斂速度很慢，實驗結束時距離目標點還有一段距離。
看看實驗結果
從實驗結果可以看出，演算法的性能很不穩定，而造成這一點的原因很可能是其收斂速度較慢，演算法仍在收斂過程中，所以結果看上去很差。將最大迭代次數修改為100代，重新試驗，其結果如下：
結果好了一些但還是難以接受，為什麼煙花演算法的結果不理想呢？
原因可能是保留機制（2.3節）的問題，煙花演算法中保留火星的概率是根據該火星與其他火星的距離和，距離群體越大的個體被保留下的概率越大。這樣做有什麼好處呢？好處是火星相對分散，這是一個對抗局部最優的策略，但是，距離群體較遠的個體是一個較差的個體的概率非常大，壞處就是，集中於當前最優位置的火星被保留的概率較小，演算法的局部搜索能力將較弱。
實驗二 . 隨機選擇的方式保留火星
為了加快煙花演算法的收斂速度，增強局部搜索能力，我移除了標准煙花演算法的選擇過程，使用隨機選擇的方式保留火星，當然，最優個體依然會被保留至下一代。其他參數保持不變。
可以看出這次的圖像相比實驗一收斂速度快了不少，在迭代結束時已經相對在一個較小的區域。這次的結果也明顯優於實驗一。將選擇過程改為隨機選擇後，由於較優的火星產生的較多且分布在自己周圍，因此選擇到這些較優的火星的概率也相對較大，演算法的收斂速度相對較快。與此同時，演算法跳出局部最優的能力比修改前要弱。
對於較簡單的問題來說當然是隨機選擇收斂較快結果較好，而復雜的問題則需要更強的跳出局部最優能力。問題的關鍵仍然是，我們無法在一開始就知道問題的復雜程度。
實驗三 .增加火星的種群數量，減少每代產生的正常火星總數
為什麼要減少產生的正常火星數，這樣演算法搜索的次數減少了，效果不會更差嗎？其實與直覺相反，減少正常火星總數，增加火星總群數，實際上是讓較優的火星產生的正常火星被保留下來的概率變大了，這樣也可以解決實驗一中的問題，加快演算法的收斂速度。
從圖像中可以看出，演算法在50代之前已經收斂，但是之後只在小范圍內進行搜索。實驗圖像與之前的描述相符，收斂速度加快但是跳出局部最優能力減弱。看看實驗結果，實驗結果好了不少且結果更加穩定。
其實實驗二與實驗三，使用了不同的策略，但都達到了同樣的目的——保留更多的優質火星到下一代，它們促進了局部搜索但是擠佔了較劣火星的位置，削弱了種群的多樣性。
每代留下的火星多了，圖像看上去是不是更像煙花？
煙花演算法的探究遠不止如此，幾年前作為一個較新的演算法來學習時卻已經有了大量的論文和書籍，可見大家對煙花演算法已經有了較為深入的研究，而我能做的只是應用演算法解決問題以及稍作改進讓演算法與問題的適應性更高。
煙花演算法產生正常火星的過程為演算法提供了搜索能力，產生特殊火星的過程和選擇過程為演算法提供了跳出局部最優的能力。但是個人認為選擇過程與其他過程的適應性不是很好。標準的選擇過程會丟失掉許多較優的個體，使之前產生的正常火星得到的成果沒有保留。
煙花演算法其實還有比較多的改進點，對演算法產生最大的參數應該就是正常火星的總數以及振幅了。簡單粗暴的改進：在每一代可以對這兩個參數進行變化或者隨機化，讓演算法的搜索能力與跳出局部最優能力在整個流程中動態變化，以均衡兩種能力。
以下指標純屬個人yy,僅供參考
參考文獻
Tan Y , Zhu Y . Fireworks Algorithm for Optimization[C]// Advances in Swarm Intelligence, First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings, Part I. Springer-Verlag, 2010. 提取碼：yaj0
目錄
上一篇 優化演算法筆記（十一）群搜索演算法
下一篇 優化演算法筆記（十三）鯨魚演算法
優化演算法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實現
『叄』 機試指南與演算法筆記哪個好
《演算法筆記》好培明。
《演算法筆記》和《王配升告道考研計算機考研機試指南》，前者詳細，可以用來學習，後者比笑並較粗一點，可以拿來復盤。
《演算法筆記》是一本零基礎就能讀懂的演算法書籍，讀者不需要因為自己沒有語言基礎而畏懼。
『肆』 演算法設計與分析筆記之NP完備性理論
三類問題都會涉及到多項式時間演算法，我們先解決什麼是多項式時間演算法。
多項式時間的演算法的形式化定義是，對於規模為n的輸入，在最壞情況下的運行時間是 ，其中k為某一 確定常數 。相對應的，有偽多項式時間演算法，典型的0-1背包問題演算法復雜度為 ，其運行時間與輸入的規模相關，是偽多項式的。
如以下表格中的都是P類問題。
NP問題能找到多項式時間的驗證演算法。
什麼叫驗證？例如，在哈密爾頓圈問題中，Z為圖中點的一個序列。如果我們能設計一個多項式時間的判定演算法，判定這個序列是否是一個哈密爾頓圈，那麼稱這個問題能在多項式時間內驗證，序列Z是這個問題的一個證書（Certificate）。
如何證明一個問題是NP問題？
注意 ：不用證明這個問題沒有多項式時間求解演算法，因為P類問題是NP問題的子集，只需有證書驗證過程即可。
非形式化定義 ，如果一個NP問題和其他任早數咐何NP問題一陸純樣「不易解決」（歸約），那麼我們認為這一問題是NPC類問題或稱之為NP完全問題。
形式化定義 ，問題X是NP完全的，如果：
NP問題可在多項式時間歸約到NPC問題。特殊地，如果一個問題滿足2，而 不一定 滿足1，則稱它是NP難度（NP-Hard）的。
反過來，要證明一個問題Y是NP完全的。可以採用如下步驟：
寫了這么多，我還是看不懂。就這樣理解叭，P類問題是可以在多項式時間求解的問題，但大部分問題都是不能的。因此我們想用一些數據去驗證它是不是這個問題的解，如果能在多項式時間驗證出來，那麼這個問題就是NP問題。其中，NP里最難的問題我們叫它NPC問題，但有些問題跟NPC問題差不多難，然而它又不是NP問題，就只好說它是NP難度的，也就是NP難問題（NP-Hard）。
目的：我們希望在多項式時間內解決一個 判斷 問題。
准備：某一特定問題（A）的輸入為該問題的實例。畢鏈例如，尋找路徑（PATH）問題的實例可以是圖G、G中特定的點u和v以及一個特定的整數k（是否存在u到v長度為k的路徑）。
假設有另一不同的判定問題B，已知在多項式時間解決它的演算法。我們將A的任何實例 α 轉化成B的具有以下特徵的某個實例 β：
這一過程就是 多項式時間歸約演算法 。它提供了一種在多項式時間內解決A的方法：
參考資料 ：《演算法導論》
『伍』 優化演算法筆記（一）優化演算法的介紹
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
我們常見常用的演算法有排序演算法,字元串遍歷演算法,尋路演算法等。這些演算法都是為了解決特定的問題而被提出。
演算法本質是一種按照固定步驟執行的過程。
優化演算法也是這樣一種過程，是一種根據概率按照固定步驟尋求問題的最優解的過程。與常見的排序演算法、尋路演算法不同的是，優化演算法不具備等冪性，是一種 概率演算法 。演算法不斷的 迭代 執行同一步驟直到結束，其流程如下圖。
等冪性即 對於同樣的輸入，輸出是相同的 。
比如圖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
[目錄]
[下一篇 優化演算法筆記（二）優化演算法的分類]
『陸』 優化演算法筆記（二）優化演算法的分類
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
在分類之前，我們先列舉一下常見的優化演算法（不然我們拿什麼分類呢？）。
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）
『柒』 數據結構與演算法之美筆記——散列表（上）
摘要:
我們已經知道隨機訪問數組元素時間復雜度只有 ，效率極高，當我們想利用數組的這個特性時就需要將元素下標與存儲信息對應。例如，一個商店只有四件商品，依次編號 0 至 3，這樣就可以將四件商品信息按照編號對應下標的方式存儲到數組中，依據編號就可以快速從數組中找到相應商品信息。
如果一段時間之後，商店盈利並且重新進貨 100 件商品，商家想對大量商品在編號上區分類別，這時陵鋒頌候需要使用類別編號加順序編號的方式標識每件商品，這種編號變得復雜，並不能直接對應數組下標，此時的商品編號又該如何對應數組下標以實現快速查找商品的功能？這時候我們可以將類別編號去除之後按照順序編號對應數組下標，同樣也能享受數組高效率隨機訪問的福利。這個例子中，商品編號稱為「 鍵 」或「 關鍵字 」，將鍵轉化為數組對應下標的方法就是「 散列函數 」或「 Hash 函數 」，由散列函數生成的值叫做「 散列值 」或「 Hash 值 」，而這樣的數組就是散列表。
從散列表的原理來看，數據通過散列函數計算得到散列值是關鍵，這個步驟中散列函數又是其中的核心，一個散列函數需要遵守以下三個原則。
因為散列函數生成的散列值對應數組下標，而數組下標就是非負整數，所以需要滿足第一個原則；兩個相等的數據經過散列演算法得到的散列值肯定相等，否則利用散列值在散列表中查找數據就無從談起；至於第三個原則雖然在情理之中，卻不那麼容易做到，即使是被廣泛運用的散列演算法也會出現散列值沖突的情況，導致無法滿足第三個原則。
散列函數作為散列表的核心部分，尺鄭必然不能拖散列表的執行效率後腿，畢竟散列表的查詢、插入和刪除操作都需要經過基告散列函數，所以散列函數不能太復雜，執行效率不能太低。由於散列函數不可避免地都會出現散列沖突情況，散列函數要盡量降低散列沖突，使散列值能夠均勻地分布在散列表中。
解決散列沖突主要有「 開放定址 」（open addressing）和「 鏈表法 」（chaining）兩類方法。
開放定址法是指插入操作時，當生成的散列值對應槽位已經被其他數據佔用，就探測空閑位置供插入使用，其中探測方法又分為「 線性探測 」（Linear Probing）、「 二次探測 」（Quadratic Probing）和「 雙重散列 」（Double hashing）三種。
線性探測是其中較為簡單的一種，這種探測方式是當遇到散列沖突的情況就順序查找（查找到數組尾部時轉向數組頭部繼續查找），直到查找到空槽將數據插入。當進行查找操作時，也是同樣的操作，利用散列值從散列表中取出對應元素，與目標數據比對，如果不相等就繼續順序查找，直到查找到對應元素或遇到空槽為止，最壞情況下查找操作的時間復雜度可能會下降為 。
散列表除了支持插入和查找操作外，當然也支持刪除操作，不過並不能將需刪除的元素置為空。如果刪除操作是將元素置為空的話，查找操作遇到空槽就會結束，存儲在被刪除元素之後的數據就可能無法正確查找到，這時的刪除操作應該使用標記的方式，而不是使用將元素置空，當查找到被標識已刪除的元素將繼續查找，而不是就此停止。
線性探測是一次一個元素的探測，二次探測就是使用都是線性探測的二次方步長探測。例如線性探測是 ，那二次探測對應的就是 。
雙重探測是當第一個散列函數沖突時使用第二個散列函數運算散列值，利用這種方式探測。例如，當 沖突時，就使用 計算散列值，如果再沖突就使用 計算散列值，依此類推。
關於散列表的空位多少使用「 裝載因子 」（load factor）表示，裝載因子滿足數學關系 ，也就是說裝載因子越大，散列表的空閑空間越小，散列沖突的可能性也就越大，一般我們會保持散列表有一定比例的空閑空間。
為了保持散列表一定比例的空閑空間，在裝載因子到達一定閾值時需要對散列表數據進行搬移，但散列表搬移比較耗時。你可以試想下這樣的步驟，在申請一個新的更大的散列表空間後，需要將舊散列表的數據重新通過散列函數生成散列值，再存儲到新散列表中，想想都覺得麻煩。
散列表搬移的操作肯定會降低散列表的操作效率，那能不能對這一過程進行改進？其實可以將低效的擴容操作分攤至插入操作，當裝載因子達到閾值時不一次性進行散列表搬移，而是在每次插入操作時將一個舊散列表數據搬移至新散列表，這樣搬移操作的執行效率得到了提高，插入操作的時間復雜度也依然能保持 的高效。當新舊兩個散列表同時存在時查詢操作就要略作修改，需先在新散列表中查詢，如果沒有查找到目標數據再到舊散列表中查找。
當然，如果你對內存有更高效的利用要求，可以在裝載因子降低至某一閾值時對散列表進行縮容處理。
除了開放定址之外，還可以使用鏈表法解決散列沖突的問題。散列值對應的槽位並不直接存儲數據，而是將數據存儲在槽位對應的鏈表上，當進行查找操作時，根據散列函數計算的散列值找到對應槽位，再在槽位對應的鏈表上查找對應數據。
鏈表法操作的時間復雜度與散列表槽位和數據在槽位上的分布情況有關，假設有 n 個數據均勻分布在 m 個槽位的散列表上，那鏈表法的時間復雜度為 。鏈表法可以不用像開放定址一樣關心裝載因子，但需要注意散列函數對散列值的計算，使鏈表結點能夠盡可能均勻地分布在散列表槽位上，避免散列表退化為鏈表。有時黑客甚至會精心製造數據，利用散列函數製造散列沖突，使數據集中某些槽位上，造成散列表性能的極度退化。
面對這樣的惡意行為散列表只能坐以待斃嗎？其實不然，當槽位上的鏈表過長時，可以將其改造成之前學習過的跳錶等，鏈表改造為跳錶後查詢的時間復雜度也只是退化為 ，依然是可以接受的范圍。
鏈表法在存儲利用上比開放定址更加高效，不用提前申請存儲空間，當有新數據時申請一個新的結點就行。而且鏈表法對裝載因子也不那麼敏感，裝載因子的增高也只是意味著槽位對應的鏈表更長而已，鏈表增長也有將鏈表改造為跳錶等結構的應對策略，所以鏈表法在裝載因子超過 1 的情況下都可保持高效。
開放定址不存在像鏈表法一樣有鏈表過長而導致效率降低的煩惱，不過裝載因子是開放定址的晴雨表，裝載因子過高會造成散列沖突機率的上升，開放定址就需要不斷探測空閑位置，演算法的執行成本會不斷被提高。而且在刪除操作時只能將數據先標記為刪除，對於頻繁增刪的數據效率會受到影響。
當然也可以在這種風險出現前進行散列表的動態擴容，不過這樣就會出現大量空閑的存儲空間，導致存儲的利用效率過低，這種現象在數據量越大的情況下越明顯。所以開放定址比較適用於數據量較小的情況。
鏈表法對於散列沖突的處理更加靈活，同時對存儲空間的利用效率也更高，但鏈表結點除了存儲數據外還需要存儲指針，如果存儲數據較小指針佔用的存儲甚至會導致整體存儲翻倍的情況，但存儲數據較大時指針佔用的存儲也就可以忽略不計，所以鏈表法較適合存儲數據對象較大，但頻繁的增刪操作不會對鏈表法造成明顯的影響。因為這樣的特點，鏈表法更加適合大數據量，或者數據對象較大的時候，如果數據操作頻繁，那鏈表法更是不二之選。
散列表由數組擴展而來，使用散列函數將鍵計算為散列值，散列值對應數據存儲的數組下標。雖然散列表的執行效率較高，但會有散列沖突的問題，可以通過開放定址法和鏈表法解決此問題。
開放定址存儲利用效率較低，適用數據量較小並且增刪不頻繁的情況，如果數據量較大，增刪頻繁的情況更加適用鏈表法，相對之下鏈表法更加普適。
『捌』 優化演算法筆記（二十六）和聲搜索演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
和聲搜索演算法（Harmony Search）是受音樂中的和聲啟發而提出的啟發式演算法，其提出（發表）年份為2001年，算是一個比較老的演算法了。和聲搜索演算法放在現在，其性能非常一般，不過它提出了一種領域搜索的具體實現方式，可以和不同的演算法融合，提高其他演算法的性能。
單獨看一個和聲意義不大，一個和聲的一個維度會根據群體中該維度的所以取值來確定其領域范圍，然後再進行領域搜索。
原演算法受音樂啟發，所以它所解決的目標問題也是離散的問題。
和聲搜索演算法中的一個個體被稱為和聲記憶（Harmony Memory,HM），群體中和聲記憶的數量為N,每個和聲記憶中的音數（維度）為D。每一維的取值范圍為 。
原演算法中每個維度的取值范圍L是一組有序的離散的值，即在指定的變數值中選取一個作為和聲記憶的值。
每個和聲記憶每次迭代只能變為其領域的值。
和聲演算法中有兩種操作：1.移動到領域，2.變異到領域
其概率分別為Harmony Memory Considering Rate(HMCR)和Pitch Adjusting Rate(PAR)。
其中HMCR取值約為0.95，PAR取值約為0.10。
可以看出該演算法的步驟和數值參考了遺傳演算法，而且兩者都是為了處理離散問題。
例子如下：
和聲記憶的數量為3，維度為2，其中第1維的取值范圍為{A,B,C,D,E,F,G},第2維的取值為{3,4,5,6}。
第1代，三個個體的取值如下
在計算第2代時，每個個體的每一維只能去到該維度的鄰域的值。
個體1_2能取到的值為(A,3) (A,4) (B,3) (B,4)
個體2_2能取到的值為(F,4)(F,5)(F,6)(G,4)(G,5)(G,6)
個體3_2能取到的值為(C,3)(C,4)(C,5)(D,3)(D,4)(D,5)(E,3)(E,4)(E,5),
圖中標出了這三個個體能夠到達的鄰域。
變異到鄰域到操作也很簡單，該操作是對標了遺傳演算法中的變異操作。
變異到鄰域操作時，該維度不會變異到當前已有的值。
如個體1_1變異第1維，由於群體中第1維的取值為{A,D,G}故該維度只能取到{B,C,E,F}。
下圖中標有顏色的塊出了變異操作無法到達的位置，空白位置為變異操作能夠到達的位置。（如果沒有空白位置呢？概率非常小，畢竟個體位置遠少於解空間位置，如果出現了，不變異或者隨機一個位置都行）
迭代過後，如果新的位置更好，則保留該和聲記憶，並去除最差的和聲記憶。
最後文章給出了判斷找到的解是否是最優解的判斷函數
其中Hr=HMCR,Hi會在該維度找到更好值時隨著迭代次數遞增。該公式的作用主要是為了判斷何時去結束演算法程序，不過在之前我們都是使用的最大迭代次數來結束演算法程序，所有好像沒多大用處。
演算法的流程也挺簡單的：
和聲搜索的原演算法是根據音樂中和聲概念提出的，音符是離散的，所有演算法也是離散的，對標遺傳演算法用於處理離散解空間問題，那麼如何修改和聲搜索演算法使其能處理連續數值問題呢？
最關鍵的點是如何處理「鄰域」，在連續解空間上，很難定義出一個點的領域，而且每個維度上的取值數量也是無窮的。
為和聲搜索演算法定義鄰域也有幾種思路：
1 . 將所有的個體定義為該個體的鄰域，即每次隨機從群體中選擇一個個體，該維度移動到所選中的個體處。
其中D,E,F分別為AB,AC,BC的中點，A,B,C三個和聲記憶的鄰域將由DEF這三個點及解空間邊界決定，此時的鄰域比思路2中的更小，也不會出現重疊部分。
當某一維度的兩個領域值相等時，上述（二維）的鄰域（面）將會退化成鄰域（線），可能會導致該維度快速收斂到該值，故此時需要忽略重復值，將鄰域重新展開（成為面）。
在連續演算法中，當滿足HCMR條件時，演算法將根據上面的色塊在鄰域中隨機選擇一個值；當滿足PAR條件時，由於無法剔除指定值，簡單起見，直接移動到隨機的和聲記憶的該維度。
後續的實驗由於是求解連續函數最值，故會選擇上述連續演算法中的三種思路來進行。
適應度函數 。
實驗一 ： 思路一
從圖像可以看出，思路一的策略與遺傳演算法非常的相似，移動路線類似於十字架，最終也收斂到了正解附近。前期搜索主要靠鄰域移動，後期移動則是靠變異。
從結果也可以看出與遺傳演算法的差距不大，演算法不是很穩定，其策略是飛到相鄰的和聲記憶上，所以跨越度比較大，精度全靠變異。
實驗二 ： 思路二
從圖像中可以看出，種群的搜索路徑不在像實驗一中那樣直來直去的十字路徑，收斂的速度也慢了不少，但是仍能在正解附近收斂。
從結果中可以看出，思路二的結果好了不少，同時也更加穩定（誤，運氣好，之前實驗出現過不好的結果，沒能重現）。該思路的鄰域搜索麵積會更大，且個體之間的鄰域存在重疊部分，故會有可能收斂於不好的位置，不過概率也較小。
實驗三 ： 思路三
圖像逐漸貪吃蛇化！前期的圖像與思路一相似，後期的圖像有點類似遺傳演算法，可能是鄰域的面積逐漸縮小成了長條狀所致，不過最終「貪吃蛇」還是吃到了食物。
結果可以看出，思路三的穩定性不太行，當全部個體收斂到了一點後會開始進行思路一的替換操作，但無論如何替換都是相同的值，難以找到更優的位置，於是會出現一個較差的結果。這里也可以增加范圍隨機來跳出局部最優。
和聲搜索演算法是根據和聲樂理知識提出的演算法。由於音符是離散的值，演算法也對標了遺傳演算法，故原演算法也是針對離散問題提出的。在解決連續性問題時，需要對其鄰域概念進行擴展和修改，最終的效果與遺傳演算法相差不大。
在現在看來，和聲搜索演算法的效果屬實一般，對於其的針對性研究也不太多，該演算法主要提出了其不同於遺傳演算法的遍歷解空間的方式。所以在很多論文中都能看到用和聲搜索演算法與其他演算法融合來進行改進的例子。
與遺傳演算法相比，和聲搜索演算法的鄰域概念，將遺傳演算法的基因由線擴展到了面上。這一點有點類似於SVM和卷積神經網路的關系，不過，遺傳演算法和和聲搜索演算法的差別並沒有那麼大，只是搜索方式不同罷了。
參考文獻
Geem Z W , Kim J H , Loganathan G V . A New Heuristic Optimization Algorithm: Harmony Search[J]. Simulation, 2001, 2(2):60-68. 提取碼：4udl
Omran M , Mahdavi M . Global-best harmony search[J]. Applied Mathematics and Computation, 2008, 198(2):643-656. 提取碼：pk3s
以下指標純屬個人yy,僅供參考
目錄
上一篇 優化演算法筆記（二十五）飛蛾撲火演算法
下一篇 優化演算法筆記（二十七）蜉蝣演算法
『玖』 優化演算法筆記（七）差分進化演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
差分進化演算法（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實現
『拾』 優化演算法筆記（二十四）帝王蝶演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
上一篇記錄了蝴蝶演算法（Butterfly Algorithm），這一篇接著記錄帝王蝶演算法（Monarch butterfly optimization）。
介紹之前我們先看看帝王蝶的網路，了解其特性，這將有利於我們對演算法的理解和記憶。
帝王蝶演算法（Monarch butterfly optimization）是根據帝王蝶的遷徙行為提出的優化演算法。帝王蝶演算法也是於2015年提出，相關的論文也比較多了（這兩個蝴蝶演算法都有這么多人關注嗎？）。其流程相對蝴蝶演算法來說有點復雜，不過其論文對演算法描述非常的清晰，大家可以去閱讀原文。
帝王蝶演算法中，每隻蝴蝶的位置代表一個可行解，蝴蝶群體將會被分布在兩個大陸上，這兩塊大陸上的帝王蝶分別有不同的行為：1.遷徙，2適應環境。帝王蝶演算法組合了這兩種行為來搜索解空間中的最優位置。
帝王蝶演算法中每隻蝴蝶的為 ，該位置的優劣由其適應度函數F(X)計算得出。
帝王蝶群體分布在兩塊大陸上，分別是land1和land2上。對於一隻隨機帝王蝶來說，它位於land1上的概率為p,位於碧純land2上的概率為1-p。以此可以將總群分為2個群體，論文中p取值維5/12。
Land1上的群體的行為為遷徙，而land2上的群體的行為為適應環境。
位於land1上的群體的行為為遷徙，這部分個體在種群中的比例為p。其計算公式如下：
不同與land1上的群體，land2上的群體的行為為適應環境，其計算公式如下櫻慧段：
從2.2和2.3可看出，帝王蝶演算法的流程也非常的簡單，過程中也只有兩個公式。
可以看出，帝王蝶演算法的流程和蝴蝶演算法的流程幾乎一模一樣（廢話，流程圖直接的，當然一樣），兩個演算法的個體都是擁有兩種行為，蝴蝶演算法的行為比較整體，宏觀操作，新個體由2-3個個體得出，而帝王蝶演算法的行為比較零散，微觀操作，每一維來自一個個體。兩個演算法也都使用了levy飛行，考慮到兩個演算法竟然還是同一年的，莫非，難道……
不過從細節來看，兩個演算法差異還是比較大的，不過兩個演算法的性能也都算是中規中矩的那種，沒有特別突出的特點。
適應度函數 。
實驗一 ：
從圖像中可以看出，帝王蝶演算法收斂的非常之快，幾乎在10代以內就聚集在了目標解附近。從結果中也可以看出，10次結果中僅有一次較差，其它結果也都很接近0。效果比較好，我總覺得參數的設置不太對稱，改成對稱試試結果。
實驗二 ：修改參數p=0.5,peri = 1,BAR=0.5,即遷徙操作兩個種群各佔一半維度，適應環境操作最優個體站一半維度，1/4進行levy飛行。
從結果可以看出，將參數改為對稱後效果差了不少。圖像我選取一副較差的圖像，從圖像可以看出在最後，種群收斂到了目標解外的一點。收斂的過程很像遺傳演算法和差分進化演算法，個體的運動軌跡在一個類似十字架的圖案上。但是這個適應度函數非常簡單，不存在局部最優解，問題應該出在步長上。整個演算法只有levy飛行那一步會產生新的位置，其他步驟都是現有位置的組合。
下面將最大步長改大試試。
實驗三 ：在實驗二的基礎上，將S_max改為100。
結果比實驗二好了不少，但精度有所下降，但是比不上實驗一。最大步長設的太大會影響精度，設得太小又會讓種群提前收斂。實驗三中最脊譽大步長為100，最大迭代次數為50，則由最大步長影響的精度為100/(50*50)=0.04,這與實驗結果相差不太多。權衡利弊，S_max的取值還是大一點的好，否則，種群未在正解附近收斂得到的結果會很差，結果會很不穩定。
實驗四 ： 在實驗一的基礎上將S_max修改為100，與實驗三比較原文其他參數是否合適。
從結果可以看出，這次的結果要好於實驗三的結果，這說明原文中給出的這一系列不對稱的參數效果還是好於實驗二實驗三中的對稱參數。圖像與實驗三的圖像類似，步長改大之後個體很容易飛出邊界，然後由越界的處理方法使其留在邊界上，所以在演算法開始後不久就可以看到群體都停留在了邊界上，不過問題不大，最終還是會收斂與正解附近。
與實驗一相比，實驗四的結果差了不少，這是因為測試函數比較簡單，當選用較為復雜的測試函數後，較大的步長能夠提高演算法的全局搜索能力，讓演算法的結果更加穩定。
帝王蝶演算法是根據帝王蝶的遷徙行為提出的演算法。位於兩塊大陸上的帝王蝶群體有著不同的行為，遷徙行為類似於進化演算法的雜交操作，適應環境行為類似於進化演算法的變異操作，不過其變異位置在當前最優個體附近。演算法中的levy飛行是其變異操作的具體實現，不過由於受最大步長的影響，levy飛行的作用並不明顯。帝王蝶的最大飛行步長對結果的影響較為明顯，步長較小時演算法的全局搜索能力較差，局部搜索能力較強，精度較高，反之，全局搜索能力較強，局部搜索能力較差，精度較低但是更加穩定。
帝王蝶演算法的參數非常奇特，按論文中所說是根據蝴蝶在各地活動的月數而設定的。雖然不是最佳參數，但也優於均勻對稱的參數。有興趣的同學可以試試怎麼設置能讓演算法的性能達到最佳。
接連兩篇筆記記錄了都是蝴蝶演算法，它們的總體流程結構相差不大，一個是宏觀行為，個體之間互動，一個是微觀行為，維度之間互動。這兩個蝴蝶演算法的性能也相差不多，中規中矩，沒有太亮眼的地方，而且都用了levy飛行來提供跳出局部最優的能力。不過levy作為非常規武器，不應該在原始演算法中給出，其操作與levy飛行不搭且沒有提供相應的能力（可能我看到的不是原始論文）。
參考文獻
Monarch butterfly optimization[J]. Neural Computing and Applications, 2015, 31:1995-2014. 提取碼：fg2m
Wang G G , Zhao X , Deb S . A Novel Monarch Butterfly Optimization with Greedy Strategy and Self-adaptive Crossover Operator[C]// 2015 2nd Intl. Conference on Soft Computing & Machine Intelligence (ISCMI 2015). IEEE, 2015. 提取碼：9246
以下指標純屬個人yy,僅供參考
目錄
上一篇 優化演算法筆記（二十三）蝴蝶演算法
下一篇 優化演算法筆記（二十五）飛蛾撲火演算法