1. 帝王蝶算法簡(jiǎn)介
（以下描述，均不是學(xué)術(shù)用語(yǔ)，僅供大家快樂(lè)的閱讀）
上一篇記錄了蝴蝶算法（Butterfly Algorithm），這一篇接著記錄帝王蝶算法（Monarch butterfly optimization）。
介紹之前我們先看看帝王蝶的百科，了解其特性，這將有利于我們對(duì)算法的理解和記憶。
帝王蝶算法（Monarch butterfly optimization）是根據(jù)帝王蝶的遷徙行為提出的優(yōu)化算法。帝王蝶算法也是于2015年提出，相關(guān)的論文也比較多了（這兩個(gè)蝴蝶算法都有這么多人關(guān)注嗎？）。其流程相對(duì)蝴蝶算法來(lái)說(shuō)有點(diǎn)復(fù)雜，不過(guò)其論文對(duì)算法描述非常的清晰，大家可以去閱讀原文。
帝王蝶算法中，每只蝴蝶的位置代表一個(gè)可行解，蝴蝶群體將會(huì)被分布在兩個(gè)大陸上，這兩塊大陸上的帝王蝶分別有不同的行為：1.遷徙，2適應(yīng)環(huán)境。帝王蝶算法組合了這兩種行為來(lái)搜索解空間中的最優(yōu)位置。
2.算法流程
帝王蝶算法中每只蝴蝶的為，該位置的優(yōu)劣由其適應(yīng)度函數(shù)F(X)計(jì)算得出。
帝王蝶群體分布在兩塊大陸上，分別是land1和land2上。對(duì)于一只隨機(jī)帝王蝶來(lái)說(shuō)，它位于land1上的概率為p,位于land2上的概率為1-p。以此可以將總?cè)悍譃?個(gè)群體，論文中p取值維5/12。
Land1上的群體的行為為遷徙，而land2上的群體的行為為適應(yīng)環(huán)境。
2.1遷徙
位于land1上的群體的行為為遷徙，這部分個(gè)體在種群中的比例為p。其計(jì)算公式如下：
其中
新個(gè)體屬于land1群體，如果該個(gè)體優(yōu)于對(duì)應(yīng)的父類個(gè)體則取代父類位置，否則將被拋棄。
從公式中也可以看出，這是一個(gè)無(wú)法脫離局部最優(yōu)的操作，沒(méi)有產(chǎn)生新的位置，當(dāng)群體收斂于一點(diǎn)后新個(gè)體將不會(huì)有太大變化，有點(diǎn)類似遺傳算法的交叉操作。
2.2適應(yīng)環(huán)境
不同與land1上的群體，land2上的群體的行為為適應(yīng)環(huán)境，其計(jì)算公式如下：
其中
計(jì)算可以得出新維度取上述3個(gè)值的概率為5/12=41.7%, (7/12)*(5/12)=24.3%, (7/12)*(7/12)=34.0%。
論文中的常數(shù)取的非常的不對(duì)稱，其來(lái)源是根據(jù)帝王蝶在各地停留、活動(dòng)的月數(shù)站全年的比例計(jì)算而來(lái)，非常的寫(xiě)實(shí)。
2.3總體流程
從2.2和2.3可看出，帝王蝶算法的流程也非常的簡(jiǎn)單，過(guò)程中也只有兩個(gè)公式。
可以看出，帝王蝶算法的流程和蝴蝶算法的流程幾乎一模一樣（廢話，流程圖直接copy的，當(dāng)然一樣），兩個(gè)算法的個(gè)體都是擁有兩種行為，蝴蝶算法的行為比較整體，宏觀操作，新個(gè)體由2-3個(gè)個(gè)體得出，而帝王蝶算法的行為比較零散，微觀操作，每一維來(lái)自一個(gè)個(gè)體。兩個(gè)算法也都使用了levy飛行，考慮到兩個(gè)算法竟然還是同一年的，莫非，難道……
不過(guò)從細(xì)節(jié)來(lái)看，兩個(gè)算法差異還是比較大的，不過(guò)兩個(gè)算法的性能也都算是中規(guī)中矩的那種，沒(méi)有特別突出的特點(diǎn)。
3.實(shí)驗(yàn)
適應(yīng)度函數(shù)。
實(shí)驗(yàn)一：
| 值 | |
|---|---|
| 問(wèn)題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| p | 5/12 |
| peri | 1.2 |
| BAR | 5/12 |
| S_max | 1 |
| 值 | |
|---|---|
| 最優(yōu)值 | 6.616787285876675E-7 |
| 最差值 | 0.2237125217553702 |
| 平均值 | 0.02237985875889385 |
從圖像中可以看出，帝王蝶算法收斂的非常之快，幾乎在10代以內(nèi)就聚集在了目標(biāo)解附近。從結(jié)果中也可以看出，10次結(jié)果中僅有一次較差，其它結(jié)果也都很接近0。效果比較好，我總覺(jué)得參數(shù)的設(shè)置不太對(duì)稱，改成對(duì)稱試試結(jié)果。
實(shí)驗(yàn)二：修改參數(shù)p=0.5,peri = 1,BAR=0.5,即遷徙操作兩個(gè)種群各占一半維度，適應(yīng)環(huán)境操作最優(yōu)個(gè)體站一半維度，1/4進(jìn)行l(wèi)evy飛行。
| 值 | |
|---|---|
| 問(wèn)題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| p | 1/2 |
| peri | 1 |
| BAR | 1/2 |
| S_max | 1 |
| 值 | |
|---|---|
| 最優(yōu)值 | 5.316420564900669E-8 |
| 最差值 | 305.487133867145 |
| 平均值 | 46.55311876057846 |
從結(jié)果可以看出，將參數(shù)改為對(duì)稱后效果差了不少。圖像我選取一副較差的圖像，從圖像可以看出在最后，種群收斂到了目標(biāo)解外的一點(diǎn)。收斂的過(guò)程很像遺傳算法和差分進(jìn)化算法，個(gè)體的運(yùn)動(dòng)軌跡在一個(gè)類似十字架的圖案上。但是這個(gè)適應(yīng)度函數(shù)非常簡(jiǎn)單，不存在局部最優(yōu)解，問(wèn)題應(yīng)該出在步長(zhǎng)上。整個(gè)算法只有l(wèi)evy飛行那一步會(huì)產(chǎn)生新的位置，其他步驟都是現(xiàn)有位置的組合。
下面將最大步長(zhǎng)改大試試。
實(shí)驗(yàn)三：在實(shí)驗(yàn)二的基礎(chǔ)上，將S_max改為100。
| 值 | |
|---|---|
| 問(wèn)題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| p | 1/2 |
| peri | 1 |
| BAR | 1/2 |
| S_max | 100 |
| 值 | |
|---|---|
| 最優(yōu)值 | 0.03327980532491267 |
| 最差值 | 1.372619091077949 |
| 平均值 | 0.2681765191162244 |
結(jié)果比實(shí)驗(yàn)二好了不少，但精度有所下降，但是比不上實(shí)驗(yàn)一。最大步長(zhǎng)設(shè)的太大會(huì)影響精度，設(shè)得太小又會(huì)讓種群提前收斂。實(shí)驗(yàn)三中最大步長(zhǎng)為100，最大迭代次數(shù)為50，則由最大步長(zhǎng)影響的精度為100/(50*50)=0.04,這與實(shí)驗(yàn)結(jié)果相差不太多。權(quán)衡利弊，S_max的取值還是大一點(diǎn)的好，否則，種群未在正解附近收斂得到的結(jié)果會(huì)很差，結(jié)果會(huì)很不穩(wěn)定。
實(shí)驗(yàn)四： 在實(shí)驗(yàn)一的基礎(chǔ)上將S_max修改為100，與實(shí)驗(yàn)三比較原文其他參數(shù)是否合適。
| 值 | |
|---|---|
| 問(wèn)題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| p | 5/12 |
| peri | 1.2 |
| BAR | 5/12 |
| S_max | 1 |
| 值 | |
|---|---|
| 最優(yōu)值 | 0.0041091205735400115 |
| 最差值 | 0.6353414477079234 |
| 平均值 | 0.1801414787350149 |
從結(jié)果可以看出，這次的結(jié)果要好于實(shí)驗(yàn)三的結(jié)果，這說(shuō)明原文中給出的這一系列不對(duì)稱的參數(shù)效果還是好于實(shí)驗(yàn)二實(shí)驗(yàn)三中的對(duì)稱參數(shù)。圖像與實(shí)驗(yàn)三的圖像類似，步長(zhǎng)改大之后個(gè)體很容易飛出邊界，然后由越界的處理方法使其留在邊界上，所以在算法開(kāi)始后不久就可以看到群體都停留在了邊界上，不過(guò)問(wèn)題不大，最終還是會(huì)收斂與正解附近。
與實(shí)驗(yàn)一相比，實(shí)驗(yàn)四的結(jié)果差了不少，這是因?yàn)闇y(cè)試函數(shù)比較簡(jiǎn)單，當(dāng)選用較為復(fù)雜的測(cè)試函數(shù)后，較大的步長(zhǎng)能夠提高算法的全局搜索能力，讓算法的結(jié)果更加穩(wěn)定。
4.總結(jié)
帝王蝶算法是根據(jù)帝王蝶的遷徙行為提出的算法。位于兩塊大陸上的帝王蝶群體有著不同的行為，遷徙行為類似于進(jìn)化算法的雜交操作，適應(yīng)環(huán)境行為類似于進(jìn)化算法的變異操作，不過(guò)其變異位置在當(dāng)前最優(yōu)個(gè)體附近。算法中的levy飛行是其變異操作的具體實(shí)現(xiàn)，不過(guò)由于受最大步長(zhǎng)的影響，levy飛行的作用并不明顯。帝王蝶的最大飛行步長(zhǎng)對(duì)結(jié)果的影響較為明顯，步長(zhǎng)較小時(shí)算法的全局搜索能力較差，局部搜索能力較強(qiáng)，精度較高，反之，全局搜索能力較強(qiáng)，局部搜索能力較差，精度較低但是更加穩(wěn)定。
帝王蝶算法的參數(shù)非常奇特，按論文中所說(shuō)是根據(jù)蝴蝶在各地活動(dòng)的月數(shù)而設(shè)定的。雖然不是最佳參數(shù)，但也優(yōu)于均勻?qū)ΨQ的參數(shù)。有興趣的同學(xué)可以試試怎么設(shè)置能讓算法的性能達(dá)到最佳。
接連兩篇筆記記錄了都是蝴蝶算法，它們的總體流程結(jié)構(gòu)相差不大，一個(gè)是宏觀行為，個(gè)體之間互動(dòng)，一個(gè)是微觀行為，維度之間互動(dòng)。這兩個(gè)蝴蝶算法的性能也相差不多，中規(guī)中矩，沒(méi)有太亮眼的地方，而且都用了levy飛行來(lái)提供跳出局部最優(yōu)的能力。不過(guò)levy作為非常規(guī)武器，不應(yīng)該在原始算法中給出，其操作與levy飛行不搭且沒(méi)有提供相應(yīng)的能力（可能我看到的不是原始論文）。
參考文獻(xiàn)
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
以下指標(biāo)純屬個(gè)人yy,僅供參考
| 指標(biāo) | 星數(shù) |
|---|---|
| 復(fù)雜度 | ★★☆☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★★★☆☆☆ |
| 全局搜索 | ★★★☆☆☆☆☆☆☆ |
| 局部搜索 | ★★★★★☆☆☆☆☆ |
| 優(yōu)化性能 | ★★★☆☆☆☆☆☆☆ |
| 跳出局部最優(yōu) | ★★★☆☆☆☆☆☆☆ |
| 改進(jìn)點(diǎn) | ★★★☆☆☆☆☆☆☆ |
