解析演算法筆記

A. 演算法設計與分析筆記之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的方法：

參考資料 ：《演算法導論》

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

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
灰狼演算法（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實現

C. 優化演算法筆記（二十四）帝王蝶演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
上一篇記錄了蝴蝶演算法（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,僅供參考

目錄
上一篇 優化演算法筆記（二十三）蝴蝶演算法
下一篇 優化演算法筆記（二十五）飛蛾撲火演算法

D. 優化演算法筆記（二十六）和聲搜索演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
和聲搜索演算法（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,僅供參考

目錄
上一篇 優化演算法筆記（二十五）飛蛾撲火演算法
下一篇 優化演算法筆記（二十七）蜉蝣演算法

E. 演算法筆記之博弈問題——貓和老鼠

博弈問題，需要注意，對於每個玩家，都會爭取：

LeetCode913. 貓和老鼠

兩位玩家分別扮演貓和老鼠，在一張 無向 圖上進行游戲，兩人輪流行動。

圖的形式是：graph[a] 是一個列表，由滿足 ab 是圖中的一條邊的所有節點 b 組成。

老鼠從節點 1 開始，第一個出發；貓從節點 2 開始，第二個出發。在節點 0 處有一個洞。

在每個玩家的行動中，他們 必須 沿著圖中與所在當前位置連通的一條邊移動。例如，如果老鼠在節點 1 ，那麼它必須移動到 graph[1] 中的任一節點。

此外，貓無法移動到洞中（節點 0）。

然後，游戲在出現以下三種情形之一時結束：

如果貓和老鼠出現在同一個節點，貓獲勝。
如果老鼠到達洞中，老鼠獲勝。
如果某一位置重復出現（即，玩家的位置和移動順序都與上一次行動相同），游戲平局。
給你一張圖 graph ，並假設兩位玩家都都以最佳狀態參與游戲：

如果老鼠獲勝，則返回 1；
如果貓獲勝，則返回 2；
如果平局，則返回 0 。

題目描述比較長，但其實還是很好理解的。需要注意，每個玩家都會爭取自己獲勝。本題就是簡單的深度優先搜素+記憶化問題了。

這里考慮的是怎麼才能算平局，我們採取的方法是，如果有n個節點，到2n輪如果還沒出結果，就認為可以平局了。

需要注意的是記憶化，memo[i][j][k] 代表貓在i，老鼠在j，在第k輪的結果。

F. 優化演算法筆記（二十五）飛蛾撲火演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
飛蛾撲火演算法（Moth-Flame Optimization）是受飛蛾圍繞火焰飛行啟發而提出的演算法。演算法提出於2015年5月（投稿日期），雖可算作一個新演算法，不過無數研究者就像飛蛾見了火一樣，發表了如此之多的論文，驚了。
飛蛾撲火演算法中有兩種個體，飛蛾和火焰，飛蛾選擇並圍繞火焰以螺線方式飛行搜索，搜索完後，火焰將移動位置，以保持火焰是飛蛾和火焰群體中最優的位置。
演算法的流程簡單，螺線搜索在之前的鯨魚演算法中也出現過，這里會較為詳細的記錄記錄螺線搜索的具體情況。

顯然,飛蛾撲火演算法中有兩種角色,飛蛾與火焰。初始時飛蛾與火焰的數量均為N。為了方便查看，將飛蛾的位置表示為XM ，火焰的位置為 XF。
初始化時，會在解空間內初始化N個飛蛾與M(M=N)個火焰。在演算法過程中，飛蛾將會圍繞它所選擇的火焰飛行，之後將這N個飛蛾與M個火焰按優劣排序，並將M個火焰移動到較優的前M個個體的位置。其中火焰的數量M會隨著迭代次數的改變而不斷變化，論文中階梯遞減至1。
演算法的主要步驟如下：
1. 飛蛾選擇火焰（將火焰分配給飛蛾）。
2. 飛蛾圍繞火焰飛行。
3. 移動火焰到相應位置。
從步驟可以看出，演算法中飛蛾的飛行是一種無貪心演算法的操作，而火焰的移動則是一種變相的貪心操作。

初始化時，會有N個飛蛾和N個火焰（M=N）,故每隻飛蛾都可以選擇互不相同的火焰。隨著迭代次數的遞增，火焰的數量會遞減。其數量根據以下公式計算得出：

其圖像如下圖所示：

其實就是將火焰數量M線性遞減到1，由於火焰數量是正數，故圖像呈階梯狀。
隨著迭代次數增加，火焰數量遞減，每隻飛蛾無法選擇互不相同的火焰，此時可以隨機選擇火焰或者飛蛾群體按順序依次往後選取，類似於取模。兩種方式的差別不大。

該步驟是演算法的核心計算步驟。
對於飛蛾 ,它圍繞火焰 飛行後到達的新位置XM_new根據以下公式計算得出：

其圖像如下

而演算法中的飛行軌跡應該是這樣的：

取出一維看看

其中i為計算次數。

圖像就是cos函數圖像的變形。考慮到飛蛾與火焰之間的距離會越來越短，其飛行圖像應該與上圖相反，即振幅越來越小，局部搜索能力越來越強。

N只飛蛾圍繞M個火焰飛行後，會到N個新位置，計算這N個新位置的適應度值，將這N個新位置與M個火焰這（N+M）個位置按優劣排序，並將其中較優的M個位置作為下一輪中火焰的位置。

其飛蛾撲火演算法流程圖如下：

由於飛蛾撲火演算法可以說是對蟻獅演算法和鯨魚演算法的結合，這里就看看演算法的圖像，不再做其他處理了。
適應度函數 。

實驗一：

從結果看來，飛蛾撲火演算法的性能穩定也優於蟻獅演算法，從圖像看演算法收斂性不如蟻獅演算法但局部搜索性能要強於蟻獅演算法。
可見螺線的局部搜索能力還是強於隨機遊走的，不過其全局搜索要弱於隨機遊走。相比蟻獅演算法，飛蛾撲火演算法更容易陷入局部最優（其實與蟻獅差不多，只要火焰/蟻獅陷入局部最優基本完蛋，不過蟻獅數量恆定，火焰數量遞減，所有火焰更容易局部最優）。

飛蛾撲火演算法是根據飛蛾圍繞火焰飛行的行為而提出的演算法。演算法的結構比較簡單，與蟻獅演算法類似，只是搜索步驟將隨機遊走替換成了螺線搜索（當然還有跟多細節上的不同，可以看看原文）。演算法的局部搜索能力非常強，依靠螺線就提供了全局搜索和局部搜索能力，其全局搜索和局部搜索能力強弱由其極半徑決定，演算法中由b決定。不過演算法缺少跳出局部最優的能力，在平滑函數中的效果非常好，在局部最優較多的函數中效果中規中矩。

參考文獻
Mirjalili S . Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems, 2015, 89(NOV.):228-249.. 提取碼：koy9
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（二十四）帝王蝶演算法
下一篇 優化演算法筆記（二十六）和聲搜索演算法

G. 【演算法筆記】字元串匹配

BF 演算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配演算法，也叫樸素匹配演算法：

主串和模式串：
在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m

我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。

BF 演算法的時間復雜度是 O(n*m)

等價於

比如匹配Google 和Goo 是最好時間復雜度，匹配Google 和ble是匹配失敗的最好時間復雜度。

KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth與J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特—莫里斯—普拉特演算法。KMP演算法主要分為兩個步驟：字元串的自我匹配，目標串和模式串之間的匹配。

看來網上很多的文章，感覺很多的都沒有說清楚，這里直接復制阮一峰的內容，講的很清晰
內容來自 http://www.ruanyifeng.com/blog/

首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜索詞"ABCDABD"的第一個字元，進行比較。因為B與A不匹配，所以搜索詞後移一位。

因為B與A不匹配，搜索詞再往後移。

就這樣，直到字元串有一個字元，與搜索詞的第一個字元相同為止。

接著比較字元串和搜索詞的下一個字元，還是相同。

直到字元串有一個字元，與搜索詞對應的字元不相同為止。

這時，最自然的反應是，將搜索詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經比較過的位置，重比一遍。

一個基本事實是，當空格與D不匹配時，你其實知道前面六個字元是"ABCDAB"。KMP演算法的想法是，設法利用這個已知信息，不要把"搜索位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。

怎麼做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，後面再介紹，這里只要會用就可以了。

已知空格與D不匹配時，前面六個字元"ABCDAB"是匹配的。查表可知，最後一個匹配字元B對應的"部分匹配值"為2，因此按照下面的公式算出向後移動的位數：

因為 6 - 2 等於4，所以將搜索詞向後移動4位。

因為空格與C不匹配，搜索詞還要繼續往後移。這時，已匹配的字元數為2（"AB"），對應的"部分匹配值"為0。所以，移動位數 = 2 - 0，結果為 2，於是將搜索詞向後移2位。

因為空格與A不匹配，繼續後移一位。

逐位比較，直到發現C與D不匹配。於是，移動位數 = 6 - 2，繼續將搜索詞向後移動4位。

逐位比較，直到搜索詞的最後一位，發現完全匹配，於是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數 = 7 - 0，再將搜索詞向後移動7位，這里就不再重復了。

下面介紹《部分匹配表》是如何產生的。

首先，要了解兩個概念："前綴"和"後綴"。 "前綴"指除了最後一個字元以外，一個字元串的全部頭部組合；"後綴"指除了第一個字元以外，一個字元串的全部尾部組合。

"部分匹配值"就是"前綴"和"後綴"的最長的共有元素的長度。以"ABCDABD"為例，

"部分匹配"的實質是，有時候，字元串頭部和尾部會有重復。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分匹配值），就可以來到第二個"AB"的位置。

BM（Boyer-Moore）演算法。它是一種非常高效的字元串匹配演算法，有實驗統計，它的性能是著名的KMP 演算法的 3 到 4 倍。

BM 演算法包含兩部分，分別是壞字元規則（bad character rule）和好後綴規則（good suffix shift）

未完待續

參考文章：
字元串匹配的Boyer-Moore演算法