蛾群演算法

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

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

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

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

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

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

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

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

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