跳出演算法

⑴ 優化演算法筆記（十六）混合蛙跳演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
混合蛙跳演算法（Shuffled Frog Leaping Algorithm）是根據青蛙在石塊上覓食時的種群分布變化而提出的演算法。演算法提出於2003年，時間有點久遠，但相關的論文並不是特別多，仍有較大的研究和改進空間。
混合蛙跳演算法中，每個青蛙的位置代表了一個可行解。青蛙所在的池塘中有數塊石塊，每一代，青蛙們會被分配到石塊上。在這一代中，只有石塊上位置最差的青蛙會跳動。該青蛙首先會向著同一個石塊上的最優位置的青蛙跳動，如果新的位置比原位置差則向則全局最優位置跳動，若該位置仍舊比原位置差則在解空間內隨機跳動一次。可以看出每隻跳動青蛙在每代中至少跳動一次，至多跳動三次，但由於每次跳動的青蛙數量等於石塊數，故當石塊數<青蛙數/3時，每代總跳動次數小於青蛙總數。
（查找文獻追根溯源的時候看到了一個有趣的現象，原始的提出論文提出於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年發表的那篇論文，即這兩篇論文相互引用，真是奇妙。估計是原始論文被拒了後又修改了結果到2006年才發表。）

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

每一隻青蛙只有兩個屬性：位置，當前位置的適應度值。
池塘中一共有m片荷葉，青蛙總數為n。
每一代中，將所有的青蛙按位置從優到劣排列，並依此放置在m個荷葉上。舉個栗子，有5片荷葉（m1-m5）和21隻青蛙（f1-f21,按適應度值從優到劣排列）。

即m1荷葉上的青蛙有{f1,f6,f11,f16,f21},m2荷葉上的青蛙有{f2,f7,f12,f17},依此類推。
每代中最差的青蛙會首先向著當前荷葉上最優位置的青蛙跳動，即該代中f21會向著f1跳動，f17向著f2跳動，f18向著f3跳動，f19向著f4跳動，f20向著f5跳動。
如果f21、f17、f18、f19、f20這五隻青蛙沒有找到優於自己當前位置的位置，則它們會向著全局最優位置的青蛙f1跳動，如果新的位置仍然差於自己的原位置，則該青蛙跳到一個隨機的位置。

在D維空間內青蛙f1的位置 ，其適應度值為 。

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

若 優於 則青蛙f17跳到 ，否則跳到（2）。

（2）由於f1在全局最優位置，故在這一步，f17會向f1跳動：

優於 則青蛙f17跳到 ，否則跳到（3）。

（3）f17會跳到解空間內的隨機位置：

若 優於 則青蛙f17跳到 。

可以看出混合蛙跳演算法的流程灰常的簡單，跳動的運算元也非常的簡單，而且每次跳動的青蛙的數量等於荷葉的數量，所有其迭代次數會快於多數其他的優化演算法。
我自己特別喜歡這個優化演算法，總能從中體會出分治的思想。下面我們來看看實驗，看看其效果如何。

適應度函數 。
實驗一：

荷葉數為1的圖像及結果如下：

荷葉數為2的圖像及結果如下：

荷葉數為3的圖像及結果如下：

荷葉數為4的圖像及結果如下：

從上述的四個實驗可以看出，隨著荷葉數的增加，演算法的收斂速度在不斷的加快。同時，隨著荷葉數的增加，每代青蛙跳動的次數也在不斷的增加。荷葉數為1時，每代青蛙總共會跳動1-3次，荷葉數為2時每代青蛙總共跳動2-6次，當荷葉數為10時，每代青蛙會跳動10-30次。由於每片荷葉上至少得有2隻青蛙，所以荷葉數最多為總群數的一半。
演算法的效果比較穩定，但好像沒有體現出其跳出局部最優能力，在種群收斂後其全搜索能力較弱，大多在進行局部搜索。
看了看演算法的結構，其跳出局部最優操作為第三段跳動，而這次跳動仍舊按照貪心演算法跳到優於當前位置的隨機位置。現在我將其增強為：如果進行了第三段跳動（隨機跳動），則無論該位置的好壞，青蛙都將跳到該隨機位置。

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

可以看出在種群收斂後，仍然會有一些個體隨機出現在解空間內，並繼續收斂。比較結果可以看出實驗二的結果中的最優值不如實驗一，但是其均值和最差值均優於實驗一，說明對原演算法進行修改後演算法更加穩定，且演算法的性能和全局搜索能力有一定的提升，演算法跳出局部最優能力更強。

混合蛙跳演算法是提出近20年，其實現的方式與分治的思想有異曲同工之處。由於每次都更新的是每片荷葉上的最差位置的青蛙，故群體不容易集中於較小的范圍。同時由於「三段跳」的操作，讓混合蛙跳演算法有了一定的跳出局部最優能力。其全局搜索能力和局部搜索能力應該差不多，當最差的部分青蛙跳走後，次差的部分青蛙則會變成了最差的青蛙，此時群體不會過分集中。當群體相對分散時，為搜索范圍較大的全局搜索，反之為搜索范圍較小的局部搜索，由於收斂速度不算很快，所以進行全局搜索和局部搜索的時間相對均衡。
混合蛙跳演算法的流程非常簡單，幾乎可以說是流程最簡單的優化演算法。其中的運算元也很簡單，優化的能力由種群的結構提供。演算法的文章中比較了 「模因」 與 「基因」 ，模因類似與思想，其傳播可以在同代中快速傳播，比如音樂，幾分鍾就可以傳播給其他人，而基因則只能有父母輩傳遞給子女背，傳遞的時間比較久。這也決定了混合優化演算法的最重要的部分在於其群體的結構而不是其中的優化運算元，實驗說明這樣的效果也不錯，簡單明了的演算法也能有不錯的效果。

參考文獻
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 shuffled frog leaping algorithm (SFLA). J.Water Resources Planning Mgmt,Am. Soc. Civ. Engrs, 2003, 129(3), 210–225. 提取碼：cyu8

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

目錄
上一篇 優化演算法筆記（十五）蝙蝠演算法
下一篇 優化演算法筆記（十七）萬有引力演算法

優化演算法matlab實現（十六）混合蛙跳演算法matlab實現