蛙跳演算法

出自 MBA智库百科(https://wiki.mbalib.com/)

　　蛙跳演算法是一種全新的啟髮式群體進化演算法，具有高效的計算性能和優良的全局搜索能力。對混合蛙跳演算法的基本原理進行了闡述，針對演算法局部更新策略引起的更新操作前後個體空間位置變化較大，降低收斂速度這一問題，提出了一種基於閾值選擇策略的改進蛙跳演算法。通過不滿足閾值條件的個體分量不予更新的策略，減小了個體空間差異，從而改善了演算法的性能。數值實驗證明瞭該改進演算法的有效性，並對改進演算法的閾值參數進行了率定。

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

　　蛙跳原理是由Eusuff和Lansey為解決組合優化問題於2003年最先提出。作為一種新型的仿生物學智能優化演算法，SFLA 結合了基於模因（meme）進化的模因演演算法（MA，memeticalgorithm）和基於群體行為的粒子群演算法（PSO,particle swarm optimization）2 種群智能優化演算法的優點。該演算法具有概念簡單，調整的參數少，計算速度快，全局搜索尋優能力強，易於實現的特點。混合蛙跳演算法主要應用於解決多目標優化問題，例如水資源分配、橋墩維修、車間作業流程安排等工程實際應用問題。

　　演算法參數

　　與其他優化演算法一樣，SFLA亦具有一些必要的計算參數，包括F：蛙群的數量；m：族群的數量；n：族群中青蛙的數量；Smax：最大允許跳動步長；Px：全局最好解；Pb：局部最好解；Pw：局部最差解；q：子族群中青蛙的數量；LS：局部元進化次數以及SF：全局思想交流次數等。

　　更新策略

　　對於青蛙群體，具有全局最好適應度的解表示為U g；對於每一個子族群，具有最好適應度的解表示為UB，最差適應度的解表示為UW。首先對每個子族群進行局部搜索，即對子族群中最差適應度的青蛙個體進行更新操作，更新策略為

　　青蛙更新距離 Ds=rand（）*(Pb-Pw)

　　更新後的青蛙 newDw=oldPw+Ds（-Dmax≦Ds≦Dmax）

　　其中， Ds 表示青蛙個體的調整矢量， Dmax表示青蛙個體允許改變的最大步長。如設Uw=[1 3 5 4 2]，UB=[2 1 5 3 4],允許改變的最大步長Dmax =3，若rand=0.5，則:

　　Uq=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]。