謝 聰,鄭洪清
(1.廣西大學(xué)行健文理學(xué)院,廣西 南寧 530005;2.廣西外國語學(xué)院信息工程學(xué)院,廣西 南寧 530222)
近年來,隨著群智能算法的發(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的有效性。
樽海鞘群算法是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)
在基本樽海鞘群算法中,追隨者的新位置為當(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。
基于灰度圖像匹配的數(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。
為了驗(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編寫代碼。
用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)化曲線
將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
本文針對基本樽海鞘群算法在后期收斂速度慢和易陷入局部最優(yōu)等缺陷,分析了樽海鞘的追隨領(lǐng)導(dǎo)者方式是造成其缺陷的主要原因,借鑒灰狼優(yōu)化算法中ω狼追隨頭狼的思想替換樽海鞘追隨領(lǐng)導(dǎo)者的方式,提出一種新型的樽海鞘群算法NSSA。通過23個(gè)基準(zhǔn)函數(shù)和無噪聲及有噪聲圖像匹配的仿真實(shí)驗(yàn)表明,所提算法具有更好的收斂速度、計(jì)算精度和魯棒性。