蛙跳算法

蛙跳算法(SFLA)是一種全新的後啟發式群體進化算法,具有高效的計算性能和優良的全局搜尋能力。 濕地的整個青蛙群體被分為不同的子群體,每個子群體有著自己的文化,執行局部搜尋策略。 對於青蛙群體,具有全局最好適應度的解表示為U

定義

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

特點

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沒有改進最差蛙的位置,則隨機產生一個處於濕地中任何位置的蛙來替代最差的蛙。
步驟4—7如果iN<LS,則轉到步驟4-3。
步驟4—8如果im<m,則轉到步驟4-2,否則轉到全局搜尋過程的步驟5。
算法停止條件
SFLA通常採用兩種策略來控制算法的執行時間:
1)在最近的K次全局思想交流過程之後,全局最好解沒有得到明顯的改進;
2)算法預先定義的函式評價次數已經達到。
3)已有標準測試結果。
無論哪個停止條件得到滿足,算法都要被強制退出整個循環搜尋過程。

相關詞條

熱門詞條

聯絡我們