1. 帝王蝶算法簡介
（以下描述橄仍，均不是學(xué)術(shù)用語，僅供大家快樂的閱讀）
上一篇記錄了蝴蝶算法（Butterfly Algorithm），這一篇接著記錄帝王蝶算法（Monarch butterfly optimization）侮繁。
介紹之前我們先看看帝王蝶的百科虑粥，了解其特性，這將有利于我們對算法的理解和記憶宪哩。
帝王蝶算法（Monarch butterfly optimization）是根據(jù)帝王蝶的遷徙行為提出的優(yōu)化算法娩贷。帝王蝶算法也是于2015年提出，相關(guān)的論文也比較多了（這兩個蝴蝶算法都有這么多人關(guān)注嗎锁孟？）彬祖。其流程相對蝴蝶算法來說有點復(fù)雜，不過其論文對算法描述非常的清晰品抽，大家可以去閱讀原文储笑。
帝王蝶算法中，每只蝴蝶的位置代表一個可行解圆恤，蝴蝶群體將會被分布在兩個大陸上突倍，這兩塊大陸上的帝王蝶分別有不同的行為：1.遷徙，2適應(yīng)環(huán)境盆昙。帝王蝶算法組合了這兩種行為來搜索解空間中的最優(yōu)位置羽历。
2.算法流程
帝王蝶算法中每只蝴蝶的為，該位置的優(yōu)劣由其適應(yīng)度函數(shù)F(X)計算得出弱左。
帝王蝶群體分布在兩塊大陸上窄陡，分別是land1和land2上。對于一只隨機帝王蝶來說拆火，它位于land1上的概率為p,位于land2上的概率為1-p跳夭。以此可以將總?cè)悍譃?個群體，論文中p取值維5/12们镜。
Land1上的群體的行為為遷徙币叹，而land2上的群體的行為為適應(yīng)環(huán)境。
2.1遷徙
位于land1上的群體的行為為遷徙模狭，這部分個體在種群中的比例為p颈抚。其計算公式如下：
其中
新個體屬于land1群體晰绎，如果該個體優(yōu)于對應(yīng)的父類個體則取代父類位置，否則將被拋棄括丁。
從公式中也可以看出荞下，這是一個無法脫離局部最優(yōu)的操作，沒有產(chǎn)生新的位置躏将，當(dāng)群體收斂于一點后新個體將不會有太大變化锄弱，有點類似遺傳算法的交叉操作。
2.2適應(yīng)環(huán)境
不同與land1上的群體祸憋，land2上的群體的行為為適應(yīng)環(huán)境会宪，其計算公式如下：
其中
計算可以得出新維度取上述3個值的概率為5/12=41.7%, (7/12)*(5/12)=24.3%, (7/12)*(7/12)=34.0%。
論文中的常數(shù)取的非常的不對稱允乐，其來源是根據(jù)帝王蝶在各地停留矮嫉、活動的月數(shù)站全年的比例計算而來，非常的寫實牍疏。
2.3總體流程
從2.2和2.3可看出蠢笋，帝王蝶算法的流程也非常的簡單，過程中也只有兩個公式鳞陨。
可以看出昨寞，帝王蝶算法的流程和蝴蝶算法的流程幾乎一模一樣（廢話，流程圖直接copy的厦滤，當(dāng)然一樣）援岩，兩個算法的個體都是擁有兩種行為，蝴蝶算法的行為比較整體掏导，宏觀操作窄俏，新個體由2-3個個體得出，而帝王蝶算法的行為比較零散碘菜，微觀操作，每一維來自一個個體。兩個算法也都使用了levy飛行忍啸，考慮到兩個算法竟然還是同一年的仰坦，莫非，難道……
不過從細(xì)節(jié)來看计雌，兩個算法差異還是比較大的悄晃，不過兩個算法的性能也都算是中規(guī)中矩的那種，沒有特別突出的特點凿滤。
3.實驗
適應(yīng)度函數(shù)妈橄。
實驗一：
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100，100） |
| 實驗次數(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。效果比較好罢缸，我總覺得參數(shù)的設(shè)置不太對稱篙贸，改成對稱試試結(jié)果。
實驗二：修改參數(shù)p=0.5,peri = 1,BAR=0.5,即遷徙操作兩個種群各占一半維度枫疆，適應(yīng)環(huán)境操作最優(yōu)個體站一半維度爵川，1/4進(jìn)行l(wèi)evy飛行。
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100息楔，100） |
| 實驗次數(shù) | 10 |
| p | 1/2 |
| peri | 1 |
| BAR | 1/2 |
| S_max | 1 |
| 值 | |
|---|---|
| 最優(yōu)值 | 5.316420564900669E-8 |
| 最差值 | 305.487133867145 |
| 平均值 | 46.55311876057846 |
從結(jié)果可以看出寝贡，將參數(shù)改為對稱后效果差了不少。圖像我選取一副較差的圖像钞螟，從圖像可以看出在最后兔甘，種群收斂到了目標(biāo)解外的一點。收斂的過程很像遺傳算法和差分進(jìn)化算法鳞滨，個體的運動軌跡在一個類似十字架的圖案上洞焙。但是這個適應(yīng)度函數(shù)非常簡單，不存在局部最優(yōu)解拯啦，問題應(yīng)該出在步長上澡匪。整個算法只有l(wèi)evy飛行那一步會產(chǎn)生新的位置，其他步驟都是現(xiàn)有位置的組合褒链。
下面將最大步長改大試試唁情。
實驗三：在實驗二的基礎(chǔ)上，將S_max改為100甫匹。
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100甸鸟，100） |
| 實驗次數(shù) | 10 |
| p | 1/2 |
| peri | 1 |
| BAR | 1/2 |
| S_max | 100 |
| 值 | |
|---|---|
| 最優(yōu)值 | 0.03327980532491267 |
| 最差值 | 1.372619091077949 |
| 平均值 | 0.2681765191162244 |
結(jié)果比實驗二好了不少惦费，但精度有所下降，但是比不上實驗一抢韭。最大步長設(shè)的太大會影響精度薪贫，設(shè)得太小又會讓種群提前收斂。實驗三中最大步長為100刻恭，最大迭代次數(shù)為50瞧省，則由最大步長影響的精度為100/(50*50)=0.04,這與實驗結(jié)果相差不太多。權(quán)衡利弊鳍贾，S_max的取值還是大一點的好鞍匾，否則，種群未在正解附近收斂得到的結(jié)果會很差骑科，結(jié)果會很不穩(wěn)定橡淑。
實驗四： 在實驗一的基礎(chǔ)上將S_max修改為100，與實驗三比較原文其他參數(shù)是否合適纵散。
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100梳码，100） |
| 實驗次數(shù) | 10 |
| p | 5/12 |
| peri | 1.2 |
| BAR | 5/12 |
| S_max | 1 |
| 值 | |
|---|---|
| 最優(yōu)值 | 0.0041091205735400115 |
| 最差值 | 0.6353414477079234 |
| 平均值 | 0.1801414787350149 |
從結(jié)果可以看出，這次的結(jié)果要好于實驗三的結(jié)果伍掀，這說明原文中給出的這一系列不對稱的參數(shù)效果還是好于實驗二實驗三中的對稱參數(shù)掰茶。圖像與實驗三的圖像類似，步長改大之后個體很容易飛出邊界蜜笤，然后由越界的處理方法使其留在邊界上濒蒋，所以在算法開始后不久就可以看到群體都停留在了邊界上，不過問題不大把兔，最終還是會收斂與正解附近沪伙。
與實驗一相比，實驗四的結(jié)果差了不少县好，這是因為測試函數(shù)比較簡單围橡，當(dāng)選用較為復(fù)雜的測試函數(shù)后，較大的步長能夠提高算法的全局搜索能力缕贡，讓算法的結(jié)果更加穩(wěn)定翁授。
4.總結(jié)
帝王蝶算法是根據(jù)帝王蝶的遷徙行為提出的算法。位于兩塊大陸上的帝王蝶群體有著不同的行為晾咪，遷徙行為類似于進(jìn)化算法的雜交操作收擦，適應(yīng)環(huán)境行為類似于進(jìn)化算法的變異操作，不過其變異位置在當(dāng)前最優(yōu)個體附近谍倦。算法中的levy飛行是其變異操作的具體實現(xiàn)塞赂，不過由于受最大步長的影響，levy飛行的作用并不明顯昼蛀。帝王蝶的最大飛行步長對結(jié)果的影響較為明顯宴猾，步長較小時算法的全局搜索能力較差圆存，局部搜索能力較強，精度較高仇哆，反之辽剧，全局搜索能力較強，局部搜索能力較差税产，精度較低但是更加穩(wěn)定。
帝王蝶算法的參數(shù)非常奇特偷崩，按論文中所說是根據(jù)蝴蝶在各地活動的月數(shù)而設(shè)定的辟拷。雖然不是最佳參數(shù)，但也優(yōu)于均勻?qū)ΨQ的參數(shù)阐斜。有興趣的同學(xué)可以試試怎么設(shè)置能讓算法的性能達(dá)到最佳衫冻。
接連兩篇筆記記錄了都是蝴蝶算法，它們的總體流程結(jié)構(gòu)相差不大谒出，一個是宏觀行為隅俘，個體之間互動，一個是微觀行為笤喳，維度之間互動为居。這兩個蝴蝶算法的性能也相差不多，中規(guī)中矩杀狡，沒有太亮眼的地方蒙畴，而且都用了levy飛行來提供跳出局部最優(yōu)的能力。不過levy作為非常規(guī)武器呜象，不應(yīng)該在原始算法中給出膳凝，其操作與levy飛行不搭且沒有提供相應(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)純屬個人yy,僅供參考
| 指標(biāo) | 星數(shù) |
|---|---|
| 復(fù)雜度 | ★★☆☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★★★☆☆☆ |
| 全局搜索 | ★★★☆☆☆☆☆☆☆ |
| 局部搜索 | ★★★★★☆☆☆☆☆ |
| 優(yōu)化性能 | ★★★☆☆☆☆☆☆☆ |
| 跳出局部最優(yōu) | ★★★☆☆☆☆☆☆☆ |
| 改進(jìn)點 | ★★★☆☆☆☆☆☆☆ |
