演算法跳青蛙

『壹』 跪求演算法大牛解釋一下青蛙跳，也就是綠色和褐色青蛙互換問題的回溯演算法！！！

Frog[191] ：初始化游戲中的n只青蛙，以1-n/2代表左邊的青蛙，n/2+1-n代表右邊的青蛙，
Frog[]初始化即為青蛙最初的位置，如果輸入n=7，Frog[]={1,2,3,0,4,5,6}
Done[191] ：該數組值只取0或1，其中1代表用於表示此刻，在第i(1-n) 墩上的青蛙已換位成功。反之，取0。
DO[1926] ：該數組用於記錄空墩移位的狀況，元素的取值范圍為0-n-1(在計算機中的表示)。根據在第i步，可以根據元素值DO[i-1] 進行回溯操作。
這個演算法中DO[ ]記錄的是石頭的移動步驟，回溯的其實是回溯DO[ ]，返回上一步的操作

『貳』 優化演算法筆記（十六）混合蛙跳演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
混合蛙跳演算法（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實現

『叄』 蛙跳演算法怎麼計算各個青蛙的適應值

對於青蛙群體，具有全局最好適應度的解表示為U g；對於每一個子族群，具有最好適應度的解表示為UB，最差適應度的解表示為UW。首先對每個子族群進行局部搜索，即對子族群中最差適應度的青蛙個體進行更新操作，更新策略為
青蛙更新距離 Ds=rand()*(Pb-Pw) （1）
更新後的青蛙 newDw=oldPw+Ds（-Dmax≦Ds≦Dmax） （2）
其中， Ds 表示青蛙個體的調整矢量， Dmax表示青蛙個體允許改變的最大步長。如設Uw=[1 3 5 4 2],UB=[2 1 5 3 4],允許改變的最大步長Dmax =3，若rand=0.5 ，則U q(1) =1+min{int[0.5 × (2−1)],3}=1;U q(2) =3+max{int[0.5×(1−3)], −3}=2;依此相同的操作完成更新策略後可得到一個新解U q=[1 2 5 4 3].

『肆』 【數據結構與演算法】青蛙跳台階問題解析

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

因為n級台階，第一步有n種跳法：跳1級、跳2級、到跳n級 跳1級，剩下n-1級，則剩下跳法是f(n-1) 跳2級，剩下n-2級，則剩下跳法是f(n-2) 所以f(n)=f(n-1)+f(n-2)+...+f(1) 因為f(n-1)=f(n-2)+f(n-3)+...+f(1) 所以f(n)=2*f(n-1)

如果target = 0,說明是直接跳過來，否則返回1；否則，總是有target中選擇，把每種選擇包含的步驟起來就行了，遞歸到0結束循環，並合並結果。

『伍』 蛙跳演算法的過程

全局搜索過程
步驟l 初始化。確定蛙群的數量、種群以及每個種群的青蛙數。
步驟2 隨機產生初始蛙群，計算各個蛙的適應值。
步驟3 按適應值大小進行降序排序並記錄最好解Px，並且將蛙群分成族群。把F個蛙分配到m個族群Y，Y，Y…,Y中去，每個族群包含n個蛙，從而使得Yk=[X(j),f(j)|X(j)=X(k+m*(j-1), f(j)=f(k+m*(j-1),j=1,…,n,k=1,…,m].這里X（j）表示蛙群中的第j蛙，f(j)表示第j個蛙的目標函數值。
步驟4根據SFLA演算法公式，在每個族群中進行元進化。
步驟5將各個族群進行混合。在每個族群都進行過一輪元進化之後，將各個族群中的蛙重新進行排序和族群劃分並記錄全局最好解Px。
步驟6檢驗計算停止條件。如果滿足了演算法收斂條件，則停止演算法執行過程，否則轉到步驟3。通常而言，如果演算法在連續幾個全局思想交流以後，最好解沒有得到明顯改進則停止演算法。某些情況下，最大函數評價次數也可以作為演算法的停止准則。
局部搜索過程
局部搜索過程是對上述步驟4的進一步展開，具體過程
如下：
步驟4—1設im=O，這里im是族群的計數器。用來與族群總數m進行比較。設iN=0，這里iN是局部進化的計數器，用來與Ls進行比較。
步驟4-2根據式(1)在第l，，1個族群中選擇q個蛙進入子族群，確定Pb和Pw並設im=im+1。
步驟4-3設iN=iN+1。
步驟4—4根據式(2)和式(3)改進子族群中的最差蛙的位置。
步驟4—5如果步驟4—4改進了最差蛙的位置(解)，就用新產生的位置取代最差蛙的位置。否則就採用Px代替式(2)中的PB，重新更新最差蛙的位置。
步驟4—6如果步驟4-5沒有改進最差蛙的位置，則隨機產生一個處於濕地中任何位置的蛙來替代最差的蛙。
不管執行了以上三次跳躍中的任何一次，需重新計算本子群的最優個體Pb和最差個體Pw。
步驟4—7如果iN<LS，則轉到步驟4-3。
步驟4—8如果im<m，則轉到步驟4-2，否則轉到全局搜索過程的步驟5。
演算法停止條件
SFLA通常採用兩種策略來控制演算法的執行時間：
1)在最近的K次全局思想交流過程之後，全局最好解沒有得到明顯的改進；
2)演算法預先定義的函數評價次數已經達到。
3)已有標准測試結果。
無論哪個停止條件得到滿足，演算法都要被強制退出整個循環搜索過程。

『陸』 蛙跳演算法的原理

蛙跳演算法的思想是：在一片濕地中生活著一群青蛙。濕地內離散的分布著許多石頭，青蛙通過尋找不同的石頭進行跳躍去找到食物較多的地方。每隻青蛙個體之間通過文化的交流實現信息的交換。每隻青蛙都具有自己的文化。每隻青蛙的文化被定義為問題的一個解。濕地的整個青蛙群體被分為不同的子群體，每個子群體有著自己的文化，執行局部搜索策略。在子群體中的每個個體有著自己的文化，並且影響著其他個體，也受其他個體的影響，並隨著子群體的進化而進化。當子群體進化到一定階段以後，各個子群體之間再進行思想的交流（全局信息交換）實現子群體間的混合運算，一直到所設置的條件滿足為止。