一種新型的樽海鞘群算法及其應(yīng)用*

謝 聰，鄭洪清

(1.廣西大學(xué)行健文理學(xué)院，廣西 南寧 530005；2.廣西外國語學(xué)院信息工程學(xué)院，廣西 南寧 530222)

1 引言

近年來，隨著群智能算法的發(fā)展和應(yīng)用，一系列新的算法被提出，如蜻蜓算法DA(Dragonfly Algorithm)[1]、水循環(huán)算法WCA(Water Cycle Algorithm)[2]、布谷鳥搜索CS(Cuckoo Search)算法[3]、灰狼優(yōu)化GWO(Grey Wolf Optimizer)算法[4]、Jaya算法[5]和鯨魚優(yōu)化算法WOA(Whale Optimization Algorithm)[6]等。2017年，Mirjalili等[7]提出樽海鞘群算法SSA(Salp Swarm Algorithm)，它與其他群智能算法一樣存在后期收斂速度慢和易陷入局部最優(yōu)等缺陷。一些學(xué)者對其進(jìn)行了改進(jìn)，文獻(xiàn)[8,9]通過Tent混沌序列生成初始種群并對最優(yōu)個(gè)體采用精英質(zhì)心拉伸機(jī)制，在食物源位置上引入瘋狂算子，并且在追隨者位置更新公式中引入自適應(yīng)慣性權(quán)重來增強(qiáng)全局搜索能力；文獻(xiàn)[10]分別在領(lǐng)導(dǎo)者階段和跟隨者階段添加衰減因子和動(dòng)態(tài)學(xué)習(xí)策略來提高算法的全局搜索能力；文獻(xiàn)[11]在領(lǐng)導(dǎo)者位置引入上一代樽海鞘群位置并加入了慣性權(quán)重策略，提高了算法的尋優(yōu)精度和穩(wěn)定性；文獻(xiàn)[12]將PSO(Particle Swarm Optimization)算法的隨機(jī)慣性權(quán)重引入SSA的追隨者位置更新公式中，其次用差分進(jìn)化 DE(Differential Evolution)算法的變異操作替代SSA的領(lǐng)導(dǎo)者位置更新操作來提高收斂速度和計(jì)算精度；文獻(xiàn)[13]通過引入天體運(yùn)動(dòng)更新機(jī)制來提高算法的收斂速度和計(jì)算精度。上述算法雖然在一定程度上提高了算法性能，但仍有提升的空間。

針對以上問題，本文提出一種新型的樽海鞘群算法NSSA(a Novel Salp Swarm Algorithm)，借鑒灰狼優(yōu)化算法追隨α狼的思想，在SSA的追隨者位置更新公式中引入GWO算法的追隨機(jī)制，通過23個(gè)基準(zhǔn)函數(shù)和2個(gè)圖像匹配問題對算法性能進(jìn)行評測，驗(yàn)證了NSSA的有效性。

2 樽海鞘群算法

樽海鞘群算法是Mirjalili等根據(jù)海洋中的樽海鞘的覓食行為而提出的一種群智能算法，其依靠領(lǐng)導(dǎo)者和追隨者的位置更新來完成問題優(yōu)化。領(lǐng)導(dǎo)者的位置更新公式如式(1)所示：

(1)

c1=2e-(4*l/lmax)2

(2)

追隨者的位置更新利用式 (3)進(jìn)行(牛頓運(yùn)動(dòng)定律)：

(3)

其中,t是時(shí)間，a是加速度，v0是初始速度，a=(vfinal-v0)/t,v=(x-x0)/t，追隨者的位置更新公式如式(4)所示：

(4)

3 新型樽海鞘群算法

在基本樽海鞘群算法中，追隨者的新位置為當(dāng)前追隨者與上一個(gè)追隨者位置的平均值，在迭代過程中形成鏈?zhǔn)浇Y(jié)構(gòu)，最終追隨至領(lǐng)導(dǎo)者位置，這一追隨方式是造成算法收斂速度慢和計(jì)算精度差的主要原因。針對基本樽海鞘群算法存在的不足，本文借鑒灰狼算法的ω狼追隨α狼的思想替換樽海鞘的追隨方式。因此，追隨者的位置更新公式如式(5)所示：

(5)

A1=2*a/r1-a

(6)

a=2-2*l/lmax

(7)

C1=2*r2

(8)

其中，r1,r2∈[0,1]為隨機(jī)數(shù)，其他符號含義與式(1)～式(3)相同。

新型樽海鞘群算法步驟如算法1所示：

算法1新型樽海鞘群算法

步驟1設(shè)置種群規(guī)模、初始迭代值、最大迭代次數(shù)和問題邊界等參數(shù)。

步驟2在邊界范圍內(nèi)隨機(jī)初始化樽海鞘種群，求出領(lǐng)導(dǎo)者位置和相應(yīng)值。

步驟3判斷是否達(dá)到最大迭代次數(shù)，如果是，輸出領(lǐng)導(dǎo)者和相應(yīng)值，結(jié)束算法，否則進(jìn)入步驟4。

步驟4首先執(zhí)行式(2)，然后對每一個(gè)樽海鞘執(zhí)行式(1)；再執(zhí)行式(5)～式(8)。

步驟5對種群中每一個(gè)樽海鞘進(jìn)行越界處理，求出領(lǐng)導(dǎo)者位置和相應(yīng)值并判斷此時(shí)樽海鞘的值是否優(yōu)于之前領(lǐng)導(dǎo)者值，如果是則用較優(yōu)值替換較差值。

步驟6迭代次數(shù)加1，進(jìn)入步驟3。

4 圖像匹配

基于灰度圖像匹配的數(shù)學(xué)描述：給定2幅灰度圖像S和T的大小分別為m1×n1和m2×n2,S和T分別表示原圖像和目標(biāo)圖像，T(m,n)表示目標(biāo)圖像上坐標(biāo)(m,n)處的像素。令m2≤m1,n2≤n1，以S為原圖像，T為目標(biāo)圖像，所求解的問題就是在S中搜索T的最優(yōu)位置，采用歸一化積的最大相似度作為目標(biāo)函數(shù)如式(9)所示：

(9)

其中,1≤i≤m1-m2+1,1≤j≤n1-n2+1。

算法2利用新型樽海鞘群算法求解圖像匹配

步驟1設(shè)置種群規(guī)模、初始迭代值、最大迭代次數(shù)和問題邊界等參數(shù)，導(dǎo)入圖像數(shù)據(jù)。

步驟2在邊界范圍內(nèi)隨機(jī)初始化樽海鞘種群，利用式(9)求出領(lǐng)導(dǎo)者位置和相應(yīng)值。

步驟3判斷是否達(dá)到最大迭代次數(shù)，如果是，輸出領(lǐng)導(dǎo)者和相應(yīng)值，結(jié)束算法，否則進(jìn)入步驟4。

步驟4首先執(zhí)行式(2)，然后對每一個(gè)樽海鞘執(zhí)行式(1)；再執(zhí)行式(5)～式(8)。

步驟5對種群中每一個(gè)樽海鞘進(jìn)行越界處理，利用式(9)求出領(lǐng)導(dǎo)者位置和相應(yīng)值，并判斷此時(shí)樽海鞘的值是否優(yōu)于之前領(lǐng)導(dǎo)者值，如果是則用較優(yōu)值替換較差值。

步驟6迭代次數(shù)加1，進(jìn)入步驟3。

5 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證NSSA的性能和圖像匹配的效果，分別進(jìn)行實(shí)驗(yàn)1和實(shí)驗(yàn)2。實(shí)驗(yàn)1采用23個(gè)基準(zhǔn)函數(shù)，并與其他算法進(jìn)行性能比較；實(shí)驗(yàn)2采用2個(gè)圖像匹配案例，并與其他算法進(jìn)行性能比較。所有實(shí)驗(yàn)均運(yùn)行在處理器為Intel Celeron(R)雙核CPU T3200,2.90 GHz、內(nèi)存為4 GB的Windows PC機(jī)上，以Matlab R2010a編寫代碼。

5.1 實(shí)驗(yàn)1

用NSSA來求解全局優(yōu)化問題，并與LECUSSA(LEvy flight-based Conditional Updating Salp Swarm Algorithm)[14]、SSA、WCA、CS、GWO和Jaya算法進(jìn)行性能比較。所有算法的種群規(guī)模為30，最大迭代次數(shù)為500，23個(gè)基準(zhǔn)函數(shù)如表1所示，其中Dim,Range和fmin分別表示維度、取值范圍和理論最小值；f1～f7為單峰值函數(shù)；f8～f23為多峰值函數(shù)。

Table 1 Benchmark functions

7種算法求解23個(gè)基準(zhǔn)函數(shù)的結(jié)果如表2所示，每種算法獨(dú)立運(yùn)行30次，結(jié)果均為30次實(shí)驗(yàn)結(jié)果的平均值和標(biāo)準(zhǔn)差，加粗字體表示與其他算法比較時(shí)求解的最小值和標(biāo)準(zhǔn)差。從表2可知，對函數(shù)f6、f15和f20而言，NSSA求解的最優(yōu)值比WCA、LECUSSA和CS算法求解的效果稍差。對其余20個(gè)函數(shù)中的5個(gè)函數(shù)：函數(shù)f14，NSSA求解效果與CS算法的一致；函數(shù)f16和f18，NSSA求解效果與LECUSSA、SSA、WCA和CS算法的一致；函數(shù)f17和f19，NSSA求解效果與SSA、WCA和CS算法的一致。對其他15個(gè)函數(shù)，NSSA求解效果均優(yōu)于其他算法，尤其是對函數(shù)f3、f8、f9、f11、f21、f22和f23而言，NSSA求解的最優(yōu)值均達(dá)到了理論最優(yōu)值，而未達(dá)到理論最優(yōu)值的結(jié)果也比其他算法的求解精度提高了幾到幾百個(gè)數(shù)量級。另外，從標(biāo)準(zhǔn)差可知，NSSA算法的魯棒性亦優(yōu)于其他算法。

Table 2 Optimization results on benchmark functions

圖1～圖4給出了NSSA與其他6種算法在部分基準(zhǔn)函數(shù)上的平均適應(yīng)度曲線，從圖1和圖2可知，雖然NSSA初值收斂速度不是最快，但中后期進(jìn)化明顯(由于線條重疊難以分辨，但從表1的函數(shù)值可知)；從圖3～圖4可知，在初期和中后期NSSA收斂速度均為最快。

Figure 1 Average optimization curve on f1圖1 f1函數(shù)上的平均優(yōu)化曲線

Figure 2 Average optimization curve on f2圖2 f2函數(shù)上的平均優(yōu)化曲線

Figure 3 Average optimization curve on f14 圖3 f14函數(shù)上的平均優(yōu)化曲線

Figure 4 Average optimization curve on f21 圖4 f21函數(shù)上的平均優(yōu)化曲線

5.2 實(shí)驗(yàn)2

將NSSA應(yīng)用于圖像匹配，并與其他4種算法進(jìn)行比較，所有算法種群規(guī)模為30，最大迭代次數(shù)為100。

首先驗(yàn)證NSSA在無噪聲環(huán)境中的有效性，以分辨率為512×512的Lena圖像為原圖像，取該圖坐標(biāo)(220，220)為左上角，截取分辨率為100×100的子圖作為目標(biāo)圖像，理想適應(yīng)度值為1。

原圖像和目標(biāo)圖像分別如圖5a和圖5b所示，利用NSSA進(jìn)行圖像匹配的結(jié)果如圖5c所示，圖中的黑色框線表示匹配到的實(shí)驗(yàn)結(jié)果。

Figure 5 Result of matching Lena image with NSSA 圖5 NSSA匹配Lena圖像的結(jié)果

為了展示NSSA的有效性，將其迭代次數(shù)與平均適應(yīng)度值關(guān)系的仿真結(jié)果與其他算法比較，如圖6所示。由圖6可知，NSSA在30次迭代過程中，大約在30代左右達(dá)到理論最優(yōu)值1，而此時(shí)其他算法平均適應(yīng)度值均未達(dá)到最優(yōu)。另外，30次實(shí)驗(yàn)的平均運(yùn)行時(shí)間(平均運(yùn)行時(shí)間為達(dá)到理論值1所需時(shí)間，即為匹配成功的時(shí)間)及匹配率如表3所示。由表3可知，本文NSSA的平均運(yùn)行時(shí)間僅為0.093 s，匹配率為100%，可見NSSA的匹配速度和匹配精度遠(yuǎn)優(yōu)于其他算法。

Figure 6 Comparison of average convergence curve of 6 algorithms圖6 6種算法平均收斂曲線比較

Table 3 Comparison results of each algorithm on Lena

再驗(yàn)證NSSA在有噪聲環(huán)境中的有效性，選取分辨率為512×512的Couple圖像進(jìn)行測試，取該圖坐標(biāo)(123,131)為左上角，截取分辨率為100×100的子圖作為目標(biāo)圖像，理想適應(yīng)度值為1。給原圖像和目標(biāo)圖像添加均值為0、方差為0.05的高斯噪聲，分別如圖7a和圖7b所示，利用NSSA進(jìn)行圖像匹配的結(jié)果如圖7c所示，圖中的黑色框線表示匹配到的實(shí)驗(yàn)結(jié)果。另外，30次實(shí)驗(yàn)的平均運(yùn)行時(shí)間(平均運(yùn)行時(shí)間為達(dá)到最大迭代次數(shù)所需時(shí)間，因?yàn)榇藭r(shí)無法達(dá)到理論最優(yōu)值1)及匹配率如表4所示。由表4可知，在高斯噪聲下的Couple圖像，NSSA的匹配成功率依然最高，為93.33%，且耗時(shí)在0.45 s左右。雖然所有的算法都能成功匹配，但目標(biāo)函數(shù)值均不能達(dá)到理論最優(yōu)值1。綜上所述，所有的實(shí)驗(yàn)均表明了NSSA具有更好的收斂速度、匹配精度和魯棒性。

Figure 7 Result of matching Couple image with NSSA 圖7 NSSA匹配Couple上圖像的結(jié)果

Table 4 Comparison results of each algorithm on Couple

6 結(jié)束語

本文針對基本樽海鞘群算法在后期收斂速度慢和易陷入局部最優(yōu)等缺陷，分析了樽海鞘的追隨領(lǐng)導(dǎo)者方式是造成其缺陷的主要原因，借鑒灰狼優(yōu)化算法中ω狼追隨頭狼的思想替換樽海鞘追隨領(lǐng)導(dǎo)者的方式，提出一種新型的樽海鞘群算法NSSA。通過23個(gè)基準(zhǔn)函數(shù)和無噪聲及有噪聲圖像匹配的仿真實(shí)驗(yàn)表明，所提算法具有更好的收斂速度、計(jì)算精度和魯棒性。