基本介紹
- 中文名：蛙跳算法
- 外文名：SFLA
- 類型：全新的啟發式群體進化算法
- 時間：2003年
特點,原理,數學模型,過程,
特點
SFLA由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) （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].
過程
全局搜尋過程
步驟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)已有標準測試結果。
無論哪個停止條件得到滿足，算法都要被強制退出整個循環搜尋過程。
