1. 混合蛙跳算法簡介

（以下描述，均不是學術(shù)用語首妖，僅供大家快樂的閱讀）
　　混合蛙跳算法（Shuffled Frog Leaping Algorithm）是根據(jù)青蛙在石塊上覓食時的種群分布變化而提出的算法娜庇。算法提出于2003年塔次，時間有點久遠，但相關(guān)的論文并不是特別多名秀，仍有較大的研究和改進空間励负。
　　混合蛙跳算法中，每個青蛙的位置代表了一個可行解匕得。青蛙所在的池塘中有數(shù)塊石塊继榆，每一代，青蛙們會被分配到石塊上汁掠。在這一代中略吨，只有石塊上位置最差的青蛙會跳動。該青蛙首先會向著同一個石塊上的最優(yōu)位置的青蛙跳動考阱，如果新的位置比原位置差則向則全局最優(yōu)位置跳動翠忠，若該位置仍舊比原位置差則在解空間內(nèi)隨機跳動一次∑蛘ィ可以看出每只跳動青蛙在每代中至少跳動一次秽之，至多跳動三次当娱，但由于每次跳動的青蛙數(shù)量等于石塊數(shù)，故當石塊數(shù)<青蛙數(shù)/3時考榨，每代總跳動次數(shù)小于青蛙總數(shù)跨细。
　　（查找文獻追根溯源的時候看到了一個有趣的現(xiàn)象河质，原始的提出論文提出于2000年（Shuffled frog leaping algorithm:a memetic meta-heuristic for combinatorial optimization.）但是到2006年才出版扼鞋，而2003年的論文（Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm）引用了2000年的原始論文，并標注為出版中愤诱。到了2006年出版時，原始論文引用了2003年發(fā)表的那篇論文捐友，即這兩篇論文相互引用淫半，真是奇妙。估計是原始論文被拒了后又修改了結(jié)果到2006年才發(fā)表匣砖。）

2. 算法流程

這次的主角就是青蛙了科吭。（沒有石塊就用荷葉代替吧）。

　　每一只青蛙只有兩個屬性：位置猴鲫，當前位置的適應度值对人。
　　池塘中一共有m片荷葉，青蛙總數(shù)為n拂共。
　　每一代中牺弄，將所有的青蛙按位置從優(yōu)到劣排列，并依此放置在m個荷葉上宜狐。舉個栗子势告，有5片荷葉（m1-m5）和21只青蛙（f1-f21,按適應度值從優(yōu)到劣排列）。

　　即m1荷葉上的青蛙有{f1,f6,f11,f16,f21},m2荷葉上的青蛙有{f2,f7,f12,f17},依此類推抚恒。
　　每代中最差的青蛙會首先向著當前荷葉上最優(yōu)位置的青蛙跳動咱台，即該代中f21會向著f1跳動，f17向著f2跳動俭驮，f18向著f3跳動回溺，f19向著f4跳動，f20向著f5跳動混萝。
　　如果f21遗遵、f17、f18逸嘀、f19瓮恭、f20這五只青蛙沒有找到優(yōu)于自己當前位置的位置，則它們會向著全局最優(yōu)位置的青蛙f1跳動厘熟，如果新的位置仍然差于自己的原位置屯蹦，則該青蛙跳到一個隨機的位置维哈。

在D維空間內(nèi)青蛙f1的位置 ，其適應度值為 登澜。

（1）青蛙f17向f2跳動后的新位置為 ：

若 優(yōu)于則青蛙f17跳到阔挠，否則跳到（2）。

（2）由于f1在全局最優(yōu)位置脑蠕，故在這一步购撼，f17會向f1跳動：

優(yōu)于則青蛙f17跳到，否則跳到（3）谴仙。

（3）f17會跳到解空間內(nèi)的隨機位置：

若 優(yōu)于則青蛙f17跳到迂求。

混合蛙跳算法流程

　　可以看出混合蛙跳算法的流程灰常的簡單，跳動的算子也非常的簡單晃跺，而且每次跳動的青蛙的數(shù)量等于荷葉的數(shù)量揩局，所有其迭代次數(shù)會快于多數(shù)其他的優(yōu)化算法。
　　我自己特別喜歡這個優(yōu)化算法掀虎，總能從中體會出分治的思想凌盯。下面我們來看看實驗，看看其效果如何烹玉。

3. 實驗

適應度函數(shù)驰怎。
實驗一：

荷葉數(shù)為1的圖像及結(jié)果如下：

m=1

荷葉數(shù)為2的圖像及結(jié)果如下：

m=2

荷葉數(shù)為3的圖像及結(jié)果如下：

m=3

荷葉數(shù)為4的圖像及結(jié)果如下：

m=4

從上述的四個實驗可以看出继效，隨著荷葉數(shù)的增加芹枷，算法的收斂速度在不斷的加快。同時莲趣，隨著荷葉數(shù)的增加鸳慈，每代青蛙跳動的次數(shù)也在不斷的增加。荷葉數(shù)為1時喧伞，每代青蛙總共會跳動1-3次走芋，荷葉數(shù)為2時每代青蛙總共跳動2-6次，當荷葉數(shù)為10時潘鲫，每代青蛙會跳動10-30次翁逞。由于每片荷葉上至少得有2只青蛙，所以荷葉數(shù)最多為總?cè)簲?shù)的一半溉仑。
　　算法的效果比較穩(wěn)定挖函，但好像沒有體現(xiàn)出其跳出局部最優(yōu)能力，在種群收斂后其全搜索能力較弱浊竟，大多在進行局部搜索怨喘。
　　看了看算法的結(jié)構(gòu)津畸，其跳出局部最優(yōu)操作為第三段跳動，而這次跳動仍舊按照貪心算法跳到優(yōu)于當前位置的隨機位置”亓現(xiàn)在我將其增強為：如果進行了第三段跳動（隨機跳動）肉拓，則無論該位置的好壞，青蛙都將跳到該隨機位置梳庆。

實驗二： 永遠接受公式（3）得到的隨機位置

實驗二

可以看出在種群收斂后，仍然會有一些個體隨機出現(xiàn)在解空間內(nèi)膏执，并繼續(xù)收斂驻售。比較結(jié)果可以看出實驗二的結(jié)果中的最優(yōu)值不如實驗一，但是其均值和最差值均優(yōu)于實驗一更米，說明對原算法進行修改后算法更加穩(wěn)定欺栗，且算法的性能和全局搜索能力有一定的提升，算法跳出局部最優(yōu)能力更強壳快。

4. 總結(jié)

混合蛙跳算法是提出近20年，其實現(xiàn)的方式與分治的思想有異曲同工之處镇草。由于每次都更新的是每片荷葉上的最差位置的青蛙眶痰，故群體不容易集中于較小的范圍。同時由于“三段跳”的操作梯啤，讓混合蛙跳算法有了一定的跳出局部最優(yōu)能力竖伯。其全局搜索能力和局部搜索能力應該差不多，當最差的部分青蛙跳走后因宇，次差的部分青蛙則會變成了最差的青蛙七婴，此時群體不會過分集中。當群體相對分散時察滑，為搜索范圍較大的全局搜索打厘，反之為搜索范圍較小的局部搜索，由于收斂速度不算很快贺辰，所以進行全局搜索和局部搜索的時間相對均衡户盯。
　　混合蛙跳算法的流程非常簡單，幾乎可以說是流程最簡單的優(yōu)化算法饲化。其中的算子也很簡單莽鸭，優(yōu)化的能力由種群的結(jié)構(gòu)提供。算法的文章中比較了“模因”與“基因”吃靠，模因類似與思想硫眨，其傳播可以在同代中快速傳播，比如音樂巢块，幾分鐘就可以傳播給其他人礁阁，而基因則只能有父母輩傳遞給子女背巧号，傳遞的時間比較久。這也決定了混合優(yōu)化算法的最重要的部分在于其群體的結(jié)構(gòu)而不是其中的優(yōu)化算子氮兵，實驗說明這樣的效果也不錯裂逐，簡單明了的算法也能有不錯的效果。

參考文獻
Eusuff M , Lansey K , Pasha F . Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization[J]. Engineering Optimization, 2006, 38(2):129-154.提取碼：ttgx

Eusuff, M.M. and Lansey, K.E., Optimization of water distribution network design using the shuf?ed frog leaping algorithm (SFLA). J.Water Resources Planning Mgmt,Am. Soc. Civ. Engrs, 2003, 129(3), 210–225.提取碼：cyu8

以下指標純屬個人yy,僅供參考

目錄
上一篇 優(yōu)化算法筆記（十五）蝙蝠算法
下一篇 優(yōu)化算法筆記（十七）萬有引力算法

優(yōu)化算法matlab實現(xiàn)（十六）混合蛙跳算法matlab實現(xiàn)