基于層級交流機制的混合蛙跳算法

張文康，李佳玲

(1.江蘇大學附屬醫院 信息科，江蘇 鎮江 212001；2.江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013)

0 引 言

混合蛙跳算法(SFLA)[1-2]是一種新型的群智能優化算法，它具有結構簡單、易于實現、全局搜索能力強的特點，因此被廣泛應用。但是，SFLA算法[3-11]和其他的群智能優化算法一樣，在進化后期多樣性降低，收斂速度慢，易于陷入局部最優。因此，國內外眾多學者對其進行了大量的研究與改進。呂立霞等[12-13]將混沌優化策略加到SFLA中，提高了算法的收斂速度和精度。王俊等[14]在SFLA的基礎上加入了討論機制，并且根據迭代次數動態改變，增強了后期的種群多樣性，減少了其陷入局部最優的概率。王娜等[15]前期根據差分進化的思想利用種群中的其他個體有用信息來更新最差個體；后期則利用最好個體來進行交叉變異，同時通過外部歸檔集來保留種群的多樣性，這在一定程度上提高了算法的尋優能力。李俊等[16]則是將SFLA和多種群粒子群算法的優勢互補，在多種群粒子群尋優的基礎上，將各個子群中的最優粒子組合后運用蛙跳思想進行更新，這在一定程度上改善了算法的整體尋優性能。戴月明等[17]將子群中的平均個體引入到最差個體的更新中，另外讓子群中的較差個體向鄰近子群中的最優個體學習，再在全局迭代過程中采取精英群自學習機制。

以上算法雖然對SFLA有一定的改進，但并沒有考慮到SFLA子群中的那些非最差個體和非最優個體的尋優能力。本文提出了一種基于層級交流機制的SFLA。對子群中非最差個體和非最優個體進行層級交流學習，使得各個子群在局部搜索時也能進行全局的信息交流，提高了解的精度。為保障算法后期的搜索能力，用子群中最差個體的自旋來代替原本的第3次隨機跳躍。最后，通過仿真測試表明了新算法的有效性。

1 混合蛙跳算法

SFLA模擬的是青蛙按族群劃分所進行的覓食行為，主要基于組內最差青蛙的三級跳躍的局部搜索能力以及全局混合重排的全局搜索能力。其基本思想是：在搜索空間內隨機初始化F個點(青蛙)作為初始時候的種群。根據目標函數計算每個青蛙所對應的目標函數值后，按照目標函數值將青蛙從優到劣降序排列；然后將青蛙分配到m個子群，其分配規則是這樣的，排在第1個的青蛙進入第1個子群，排在第2個的青蛙進入第2個子群，排在第3個的青蛙進入第3個子群，以此類推，第m個青蛙進入第m個子群，第m+1個青蛙進入第1個子群，第m+2個青蛙進入第2個子群，直到所有的青蛙分配完畢。

初始化及分配完畢之后進入局部搜索狀態，混合蛙跳算法的局部搜索發生在每個子群之中。首先找到子群內的最優位置Pb以及最差位置Pw。對Pw進行第1次跳躍是根據下式而來的：

式中:i表示第i個子群;Di是移動步長，rand()表示[0,1]之間的隨機數;Dmax表示最大的移動步長。如果得到的新的Pwnew個體優于原來的Pw，則用Pwnew來替換Pw，否則進行第2次跳躍，第2次跳躍是用全局最優個體Pg來代替公式中的Pb，再代入式(1)、(2)重新產生新的個體，如果這次產生的新個體優于Pw，則替換Pw；否則進行第3次跳躍，隨機生成1個新個體來替換Pw。重復以上的操作直到所有子群均完成更新。

當所有子群完成其局部搜索后，將所有的青蛙重新混合后，再次按照目標函數值從優到劣進行排序，然后劃分子群，對每個子群再進行局部搜索，直到滿足相應的結束條件(達到相應的迭代次數或者相應的精度)。

2 改進的混合蛙跳算法

2.1 層級交流機制

SFLA主要是依據對子群中最差的個體進行3次跳躍來進行局部搜索。每次迭代對子群內其他個體沒有任何操作，這會明顯降低算法整體的收斂速度。對此，受差分進化思想以及多維學習思想啟發而來，本文提出一種層級交流機制，對組內的非最優個體和非最差個體進行更新操作。具體為：在每組的迭代時，排在第2至倒數第2的個體的每一維度都有機會(以概率的形式)向排在其他子群的同一位置的個體學習。更新的概率如下：

p=0.8(k/subnum)

(3)

式中：k為該個體所在的列；subnum為每組的總數。對于每個個體而言，如果產生的隨機數小于概率p，則用下式來更新；否則，不更新。

Xnew,h=Xnew,h+rand()·(frog1,h-frog2,h)

(4)

式中：frog1和frog2是從對應的列隨機選出的2個個體；h代表個體的維度。

對于更新概率而言，如果要被更新的個體排在子群的前排，那么它本身的值就越接近最優值，那它被更新的概率就越小。然后計算選出的新個體的Xnew的目標函數值，若優于原來的，則替換。其偽代碼如下所示：

在子群中：

Forn=2:subnum-1

Forh=1∶1∶D

If rand()

Xnew=Xn+rand()*(frog1-frog2);

Xnew1(1,h)=Xnew(1,h);

else

Xnew1(1,h)=Xn(1,h);

End

End

If func(Xnew1)

Xn=Xnew1;

End

End

2.2 最差個體自旋機制

在SFLA的局部搜索中，若更新最差個體第2次跳躍不成功，就會進入第3次跳躍模式，即隨機初始化一個新的個體來替換最差個體。然而，這種操作并沒有讓最差個體的原有信息保留到下一次迭代，這會造成算法后期尋優速度變慢，多樣性降低。因此，為了充分利用最差個體的原有信息，提出用下式來替換SFLA中的第3次跳躍，讓最差個體進行自旋操作。

Pwnew,h=ch*Pwnew,h+Pwnew,h

(5)

式中：Ch為自旋參數。

2.3 改進后的算法流程

綜上所述，基于層級交流機制的SFLA(IICSFLA)的流程圖如圖1所示，具體算法步驟如下。

圖1 IICSFLA流程圖

步驟1初始化F個青蛙，每個青蛙的維度是D，子群個數為m，子群內的個體總數為subnum，因此F=m·subnum，子群內的迭代次數為sub_iter_max,整體迭代次數為iter_max。

步驟2根據目標函數計算每個青蛙的目標函數值，并依據目標函數值從優到劣排序，根據之前提到的分配規則，將F個青蛙分配到m個子群中。

步驟3進行局部搜索，局部搜索分為兩部分同時進行：

(1)對每個子群中最差個體進行更新，首先使用式(1)、(2)進行第1次跳躍，若得出的新個體優于最差個體，則替換；否則，用全局最優位置去替換式(1)中的子群中的全局最優位置，代入式(1)中得出新的個體，若新個體優于最差個體，則替換；否則，根據式(5)產生1個新個體去替換最差個體。

(2)對于每個子群中的排在第2至倒數第2的個體而言，對于這種個體的每1維隨機產生1個數，若小于式(3),則選取該列的其他子群中的兩個對應的個體，利用式(4)產生該維度上的新值；若產生的隨機數大于式(3)，則該維度上的值不發生改變。最后，根據自然界中優勝劣汰的規則，若產生的新個體優于原有個體，則替換；否則，不做替換。

步驟4若當前子群迭代次數小于子群最大迭代次數，則返回步驟3；否則，繼續執行。

步驟5將所有子群中的青蛙重新混合，重復步驟2～4直至達到終止條件。

3 仿真實驗及其分析

為驗證所提出算法的性能，將本文算法IICSFLA與SFLA，Dmsfla[5]等改進算法進行對比。本文以6個常用的benchmark函數作為測試基準函數，這幾個測試函數的全局最優解都是0，具體情況如表1所示。實驗過程采用的是Matlab 2017b編程，在Intel(R)Core(TM)i7-5500U 中，Win10操作系統下進行大量實驗仿真對比。其參數設置如下：整體迭代次數為400，組內迭代次數為10，總共有100個青蛙，分為10組進行實驗。

表1 Benchmark 函數

表2為3種算法在10維情況下，獨立運行100次的結果比較，表3為3種算法在30維的情況下，獨立運行100次的結果比較。由表2、3可得，IICSFLA的尋優能力比SFLA以及DMSFLA要強。前3個測試函數是單峰測試函數，在相同的迭代次數下，IICSFLA最優，其次是DMSFLA，最后才是SFLA。后面3個是多峰測試函數，IICSFLA也能在取得較優的結果，尤其在f4測試函數上能夠取得全局最優值。

圖3，圖4分別為IICSFLA、SFLA和DMSFLA在10維和30維下的收斂曲線圖。從圖中可以看出，對于大多數測試函數，IICSFLA的收斂速度都要比其他兩個快，在測試函數f4中，IICSFLA能夠快速地收斂到全局最優位置。

表2 3種算法在10維下的性能比較

表3 3種算法在30維下的性能比較

(a)f1

(b)f2

(c)f3

(d)f4

(e)f5

(f)f6

4 結 語

本文針對SFLA求解精度不高，易于陷入局部最優的缺點，提出了一種基于層級交流的混合蛙跳算法。該算法讓子群內不參與迭代更新的個體進行縱向學習，增強了各個子群中的個體的信息共享，有利于尋找更優解。同時，用最差個體自旋機制來替換原本的第3次隨機跳躍，保障了算法后期的搜索能力以及尋優速度，減少了其陷入局部最優的概率。實驗結果也表明了所提出的算法的有效性。之后的研究想把改進的算法運用到實際的工程中，如對NP問題的求解，優化分類器等等。

(a)f1

(b)f2

(c)f3

(d)f4

(e)f5

(f)f6