雷 灝, 趙品彰, 汪東華, 陳柏屹

(1. 江蘇省計(jì)量科學(xué)研究院, 江蘇 南京 210049; 2. 南京航空航天大學(xué)航天學(xué)院, 江蘇 南京 210016)

0 引 言

隨著社會(huì)發(fā)展和科技進(jìn)步,各類工程問(wèn)題的復(fù)雜度越來(lái)越高。在面對(duì)問(wèn)題規(guī)模不斷擴(kuò)大的實(shí)際工程優(yōu)化問(wèn)題時(shí),傳統(tǒng)的基于梯度的數(shù)值優(yōu)化算法難以有效求解。受自然中群體行為啟發(fā)而提出的群智能優(yōu)化算法[1-6]不依賴具體問(wèn)題特征和梯度信息,具有簡(jiǎn)單高效的結(jié)構(gòu),受到越來(lái)越多學(xué)者的關(guān)注和研究[7]。常見(jiàn)的群智能優(yōu)化算法包括灰狼優(yōu)化(grey wolf optimizer, GWO)算法[8-11]、人工蜂群(artificial bee colony, ABC)算法[12-14]、鯨魚優(yōu)化算法(whale optimization algorithm, WOA)[15-22]等。為了進(jìn)一步挖掘群智能算法的性能,不斷有學(xué)者提出新的智能優(yōu)化算法來(lái)求解復(fù)雜的全局優(yōu)化問(wèn)題[23]。

樽海鞘群算法(salp swarm algorithm, SSA)是Mirjalili等[24]在2017年新提出的基于種群的智能優(yōu)化算法,該算法模擬了樽海鞘群以偏序運(yùn)動(dòng)鏈?zhǔn)降姆椒ㄟM(jìn)行捕食的過(guò)程,具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單的優(yōu)點(diǎn)。然而也存在迭代后期種群多樣性減少、易于陷入局部最優(yōu)的不足,從而限制了算法的開(kāi)發(fā)和探索能力。為了進(jìn)一步提高SSA的性能,國(guó)內(nèi)外學(xué)者對(duì)原始SSA做出了相應(yīng)的改進(jìn)。

在算法參數(shù)選擇上,Qais等[25]在基準(zhǔn)SSA的基礎(chǔ)上,采用游走補(bǔ)償隨機(jī)化與跟隨率隨機(jī)化提出了一種加強(qiáng)SSA。改進(jìn)后的算法具有更快的收斂速度,與SSA相比能夠更有效地求解多目標(biāo)函數(shù)。為了增強(qiáng)追隨者位置更新的靈活性,王宗山等人[26]引入了一種非線性遞減慣性權(quán)重來(lái)評(píng)價(jià)前一個(gè)個(gè)體對(duì)當(dāng)前追隨者的影響程度。黃小根等人提出一種多策略驅(qū)動(dòng)的改進(jìn)SSA[27]。在領(lǐng)導(dǎo)者位置更新公式中引入指數(shù)衰減因子,改善算法的全局收斂速度;在跟隨者位置更新公式中引入隨機(jī)慣性權(quán)重算子,以協(xié)調(diào)并增強(qiáng)算法的局部開(kāi)采和全局勘探能力。陳忠云等人選擇Schaffer測(cè)試函數(shù),通過(guò)仿真分析確定漫游步長(zhǎng)中的指數(shù)設(shè)置為2.5為最優(yōu)[28]。

在算法結(jié)構(gòu)上,陳忠云等人引入正弦余弦算法在算法執(zhí)行后期代替SSA的鏈?zhǔn)綑C(jī)制[29]。王宗山等人提出一種基于正交設(shè)計(jì)的折射反向?qū)W習(xí)算法[26],有效增強(qiáng)了算法的全局勘探能力,同時(shí)減少函數(shù)的評(píng)價(jià)次數(shù),改善了算法的整體性能。為了解決部分遮蔽條件下光伏系統(tǒng)最大功率跟蹤問(wèn)題,楊博等人[30]提出一種具有多鏈結(jié)構(gòu)的改進(jìn)SSA。采用多個(gè)樽海鞘鏈同時(shí)進(jìn)行獨(dú)立尋優(yōu),以提高算法全局搜索和局部搜索的能力;同時(shí),通過(guò)群落中所有樽海鞘間的信息交流,重組產(chǎn)生新的樽海鞘鏈,以提高算法的收斂穩(wěn)定性。3個(gè)算例結(jié)果表明所提算法能在部分遮蔽條件下快速、穩(wěn)定地獲取最大光能。

與基于梯度近似的群智能算法不同(比如粒子群優(yōu)化(particle swarm optimization, PSO)算法、GWO、WOA等),SSA采用偏序主從運(yùn)動(dòng)鏈的形式,通過(guò)領(lǐng)導(dǎo)者在當(dāng)前全局最優(yōu)解處的隨機(jī)游走實(shí)現(xiàn)對(duì)設(shè)計(jì)空間的探索,以偏序?qū)W習(xí)的機(jī)制形成運(yùn)動(dòng)鏈的慣性,進(jìn)而提高領(lǐng)導(dǎo)者隨機(jī)游走的遍歷性,隨著迭代過(guò)程的推進(jìn),領(lǐng)導(dǎo)者隨機(jī)游走的強(qiáng)度逐漸衰減,完成算法收斂。根據(jù)以上討論,SSA的改進(jìn)大致可以歸為三類:領(lǐng)導(dǎo)者選擇機(jī)制的改進(jìn)[31]、隨機(jī)游走機(jī)制的改進(jìn)[25,32]以及偏序跟隨率的改進(jìn)[25-26,28-29]?，F(xiàn)有文獻(xiàn)通過(guò)改進(jìn)學(xué)習(xí)機(jī)制有效改善了算法的性能,但是對(duì)于算法性能提升的原因缺乏原理性的解釋,無(wú)法在改進(jìn)算法的同時(shí)保證算法的穩(wěn)定性和收斂性。

從收斂性分析的角度出發(fā),本文首先建立了SSA的動(dòng)力學(xué)模型,并且從控制系統(tǒng)穩(wěn)定性的角度推導(dǎo)了算法穩(wěn)定的條件以及SSA收斂到全局最優(yōu)點(diǎn)的條件。基于建立的動(dòng)力學(xué)模型,對(duì)改進(jìn)策略進(jìn)行了總結(jié),通過(guò)引入異質(zhì)定常跟隨率和多鏈結(jié)構(gòu),本文還提出了新的多鏈異質(zhì)SSA,仿真結(jié)果表明改進(jìn)算法的探索性和多樣性有所改善。通過(guò)求解CEC2017測(cè)試函數(shù),并與其他算法進(jìn)行對(duì)比,驗(yàn)證了本文提出的改進(jìn)策略的有效性和改進(jìn)算法的優(yōu)越性。

1 SSA動(dòng)力學(xué)建模

受啟發(fā)于海洋中樽海鞘的群體游動(dòng)特性,Mirjalili等[24]提出了SSA。該算法采用偏序運(yùn)動(dòng)鏈的形式更新個(gè)體在設(shè)計(jì)空間中的位置,其中位于偏序位置首位的個(gè)體稱為領(lǐng)導(dǎo)者,其他的個(gè)體均稱為跟隨者,該算法通過(guò)領(lǐng)導(dǎo)者的隨機(jī)游走實(shí)現(xiàn)對(duì)設(shè)計(jì)空間的探索,利用偏序跟隨者的延時(shí)運(yùn)動(dòng)發(fā)現(xiàn)更優(yōu)位置,在算法執(zhí)行后期,通過(guò)收縮領(lǐng)導(dǎo)者隨機(jī)游走的范圍,確保算法在全局最優(yōu)解處收斂。

1.1 SSA的基本形式

在基準(zhǔn)SSA中,定義第1個(gè)個(gè)體為領(lǐng)導(dǎo)者,其位置更新算法滿足:

(1)

(2)

式中:T表示算法迭代最大次數(shù);r2表示服從(0,1)均勻分布的隨機(jī)變量。

領(lǐng)導(dǎo)者的位置更新機(jī)理可以理解為在全局最優(yōu)點(diǎn)處的隨機(jī)游走,游走尺度由控制參數(shù)c確定。算法中跟隨者的更新機(jī)理表示為自身位置與前序位置的平均位置:

(3)

式中:i= 1,2,…,N,N表示種群規(guī)模?；鶞?zhǔn)SSA由式(1)和式(3)組成,分別對(duì)領(lǐng)導(dǎo)者與跟隨者的位置進(jìn)行更新。

考慮到設(shè)計(jì)空間中各維數(shù)之間無(wú)相互影響,則可以將一個(gè)D維的離散系統(tǒng)轉(zhuǎn)化為D個(gè)1維的離散系統(tǒng),且各系統(tǒng)之間的穩(wěn)定性具有一致性。因此,本文后續(xù)僅針對(duì)1維的離散系統(tǒng)進(jìn)行討論。

1.2 SSA的動(dòng)力學(xué)模型

樽海鞘群基準(zhǔn)算法的動(dòng)力學(xué)模型可以通過(guò)構(gòu)建群狀態(tài)的差分方程實(shí)現(xiàn),將式(1)中等號(hào)的右半部分可以表示為隨機(jī)變量cr,j的形式:

(4)

定義離散系統(tǒng)的狀態(tài)量為種群中所有個(gè)體第j維的取值:

Xj(k)=[x1,j(k),x2,j(k),…,xN,j(k)]T

則式(4)可以轉(zhuǎn)化為N階離散系統(tǒng)動(dòng)力學(xué)的差分方程形式:

(5)

式(5)可以表示為矩陣形式:

Xj(k+1)=AXj(k)+Bbg,j(k)+Dcr,j(k)

(6)

式中:狀態(tài)量Xj(k)的第一維表示領(lǐng)導(dǎo)者j維位置,其余維表示跟隨者j維的位置;矩陣A為N維方陣,矩陣A、B、C決定了種群j維位置的更新方式。

由于基準(zhǔn)SSA的算法模型可以轉(zhuǎn)化為離散系統(tǒng)的差分方程組(6)的形式,則可以通過(guò)分析離散動(dòng)力學(xué)模型(5)獲得SSA的穩(wěn)定性和收斂性,如果系統(tǒng)的狀態(tài)空間模型(6)穩(wěn)定收斂,則多次迭代后狀態(tài)量收斂到唯一解,即種群j維的位置收斂到唯一值。式(6)中,系統(tǒng)的控制輸入可以視為全局最優(yōu)位置bg,j,而算法中的領(lǐng)導(dǎo)者隨機(jī)游走行為等價(jià)為動(dòng)力學(xué)系統(tǒng)的隨機(jī)擾動(dòng)。

與基于近似梯度的PSO算法、GWO算法等不同,SSA一般具有偏序運(yùn)動(dòng)鏈的特征?？紤]到SSA的變種,可以進(jìn)一步將SSA泛化表示為具有參量的形式為

Xj(k+1)=A(a,b)Xj(k)+B(c)bg,j(k)+D(d)

(7)

式中:

式中:a= {ai},b= {bi},i=2,3,…,n。將式(7)轉(zhuǎn)化為常規(guī)形式:

(8)

式中:c表示領(lǐng)導(dǎo)者對(duì)全局最優(yōu)解的學(xué)習(xí)因子;d表示領(lǐng)導(dǎo)者在全局最優(yōu)解處的隨機(jī)游走;bi表示跟隨者i自身的慣性因子;ai表示跟隨者i對(duì)于前序?qū)ο蟮膶W(xué)習(xí)因子,在基準(zhǔn)算法中,各參數(shù)具有如下定義:ai=bi=1/2,c=1,d(k)=cr,j(k)。

2 SSA穩(wěn)定性分析

2.1 穩(wěn)定性分析

差分系統(tǒng)的穩(wěn)定性由狀態(tài)矩陣的極點(diǎn)分布確定,當(dāng)系統(tǒng)的極點(diǎn)分布在z平面的單位圓之內(nèi)系統(tǒng)穩(wěn)定。根據(jù)離散系統(tǒng)的穩(wěn)定性理論可知,系統(tǒng)具有全局漸進(jìn)穩(wěn)定性。

定理 1SSA收斂性定理?？紤]具有與式(8)相同算法結(jié)構(gòu)的SSA。當(dāng)|bi|<1,i=2,3,…,n時(shí),算法收斂。

證明算法結(jié)構(gòu)式(8)與離散系統(tǒng)(7)等價(jià),即算法(8)的收斂性與離散系統(tǒng)(7)的穩(wěn)定性一致。離散系統(tǒng)(7)的穩(wěn)定性由系統(tǒng)狀態(tài)矩陣A(a,b)確定。根據(jù)矩陣論計(jì)算得到狀態(tài)矩陣A(a,b)的極點(diǎn)為

zi={0,b2,b3,…,bn}

當(dāng)|bi|<1,i=2,3,…,n時(shí),根據(jù)離散系統(tǒng)穩(wěn)定性原理,系統(tǒng)具有N-1個(gè)位于z平面單位圓內(nèi)且在實(shí)軸上的極點(diǎn),因此離散系統(tǒng)(6)穩(wěn)定,即算法收斂。

證畢

2.2 終值平衡點(diǎn)分析

考慮迭代次數(shù)很大的情況下,以全局最優(yōu)點(diǎn)作為驅(qū)動(dòng)量,當(dāng)系統(tǒng)滿足穩(wěn)定性條件時(shí),系統(tǒng)收斂到一個(gè)平衡點(diǎn)。該平衡點(diǎn)與全局最優(yōu)點(diǎn)之間的關(guān)系由如下定理確定。

定理 2SSA終值定理。當(dāng)算法收斂的前提下,當(dāng)k→∞,全局最優(yōu)量bg,j恒定,且擾動(dòng)d(k)→0時(shí),算法最終狀態(tài)收斂于平衡點(diǎn):

(9)

證明考慮系統(tǒng)差分動(dòng)力學(xué)模型(7),若系統(tǒng)擾動(dòng)為0時(shí),則系統(tǒng)收斂,且滿足:

Xj(k+1)=Xj(k)=Xj(∞)

(10)

將式(10)代入式(7)可以推導(dǎo)得到:

Xj(∞)=(I-A)-1Bbg,j

(11)

將式(11)推導(dǎo)展開(kāi)即可得到式(9)。

證畢

推論 1SSA全局最優(yōu)收斂條件。考慮到具有偏序運(yùn)動(dòng)鏈的算法結(jié)構(gòu)(8),需要滿足如下4個(gè)條件才能確保系統(tǒng)收斂到最優(yōu)點(diǎn):

(ⅰ) ?k>Tc,|bi(k)|<1,i=2,3,…,n

由于系統(tǒng)收斂,根據(jù)定理1可以得到條件(ⅰ),表示存在迭代次數(shù)Tc,當(dāng)?shù)螖?shù)k大于Tc時(shí),動(dòng)力學(xué)系統(tǒng)的慣性因子bi的模值要小于1;要求系統(tǒng)收斂到全局最優(yōu)點(diǎn),根據(jù)定理2以得到條件(ⅱ)～條件(ⅳ)。

3 基于動(dòng)力學(xué)模型的算法改進(jìn)

根據(jù)SSA的動(dòng)力學(xué)模型可以從以下幾個(gè)方面對(duì)算法進(jìn)行改進(jìn):根據(jù)系統(tǒng)狀態(tài)矩陣A的定義可以建立鏈運(yùn)動(dòng)的跟隨律;根據(jù)系統(tǒng)的控制矩陣B的定義可以建立鏈?zhǔn)讓?duì)驅(qū)動(dòng)量的學(xué)習(xí)機(jī)制;根據(jù)系統(tǒng)的驅(qū)動(dòng)量u的定義可以建立系統(tǒng)的驅(qū)動(dòng)機(jī)制;根據(jù)系統(tǒng)擾動(dòng)量d的定義可以建立系統(tǒng)的游走機(jī)制。關(guān)于SSA動(dòng)力學(xué)差分方程中各參數(shù)與因式的物理解釋可參考圖1。

圖1 跟隨律基于動(dòng)力學(xué)分析的代數(shù)解釋Fig.1 Algebraic interpretation of the following law based on dynamic interpreter

通過(guò)動(dòng)力學(xué)分析可知,學(xué)習(xí)律在一定程度上影響了算法的收斂性和搜索性,但是影響程度有限。從代數(shù)解析的角度分析,學(xué)習(xí)律過(guò)程的變化對(duì)于算法本身的收斂性沒(méi)有影響,只需要保證當(dāng)?shù)螖?shù)增加時(shí),學(xué)習(xí)率趨近于1即可。從幾何的角度分析,學(xué)習(xí)律的變化影響的是領(lǐng)導(dǎo)者學(xué)習(xí)中心的變化,其決定了領(lǐng)導(dǎo)者當(dāng)前迭代周期的游走中心,在一定程度上提高了系統(tǒng)搜索性。

此外,游走機(jī)制也可以通過(guò)增加系統(tǒng)的隨機(jī)性來(lái)提高算法的搜索性,比如通過(guò)萊維飛行模式[33]、高斯變異[34]、混沌模型[35]等方式進(jìn)行游走。本文具體討論跟隨律和驅(qū)動(dòng)機(jī)制的改進(jìn)思路。

3.1 跟隨律改進(jìn)

算法模型的跟隨律指的是個(gè)體自身的慣性因子bi與偏序?qū)W習(xí)因子ai隨迭代次數(shù)的變化規(guī)律。根據(jù)定理1可知,系統(tǒng)的收斂性僅與慣性因子bi有關(guān)。因此,根據(jù)收斂速率與系統(tǒng)極點(diǎn)的關(guān)系,可以直接確定系統(tǒng)收斂速率。

系統(tǒng)狀態(tài)收斂速率的差異在一定程度上表征了算法對(duì)過(guò)程狀態(tài)的遍歷能力。在基準(zhǔn)SSA中,慣性因子為常數(shù)0.5,種群中所有個(gè)體具有相同的收斂速率。因此,從提高算法遍歷能力的角度出發(fā),可以設(shè)計(jì)不同收斂速率的跟隨率。

根據(jù)SSA機(jī)理可知,領(lǐng)導(dǎo)者承擔(dān)了領(lǐng)域探索的角色,其前后迭代步長(zhǎng)變化的隨機(jī)性最大。跟隨者的探索步長(zhǎng)的大小可以視為對(duì)領(lǐng)導(dǎo)者探索區(qū)域的二次探索。若跟隨者慣性因子越小,則迭代步長(zhǎng)越大,收斂性越強(qiáng)。因此,可以根據(jù)跟隨偏序集為每一個(gè)個(gè)體指定不同的慣性因子:前序個(gè)體慣性因子較小,以較快速度收斂于跟隨者,確保對(duì)未知區(qū)域的快速探索;后序個(gè)體慣性因子較大,收斂性較慢,使得整個(gè)樽海鞘群的運(yùn)動(dòng)鏈具有“拖尾”效應(yīng),確保群體在領(lǐng)導(dǎo)者的探索包絡(luò)內(nèi)具有更細(xì)致的探索能力。

(12)

式中:bmin,bmax表示慣性因子變化范圍,其中bmax<1,bmin>0。

此外,為了確保算法具有全局最優(yōu)的收斂條件,根據(jù)推論1中的條件(ⅱ)可知,在滿足式(12)的基礎(chǔ)上,需要對(duì)偏序?qū)W習(xí)因子ai進(jìn)行約束,才能確保算法滿足全局最優(yōu)的收斂性,ai表達(dá)式為

ai=1-bi,i=2,3,…,n

(13)

圖2中給出了幾何解釋,其中空心圓表示當(dāng)前個(gè)體位置,實(shí)心圓表示算法迭代后的更新位置,黃色五角星表示當(dāng)前的全局最優(yōu)解,黃色的圓圈表示當(dāng)前迭代中算法所獲得的全局最優(yōu)位置。越接近于領(lǐng)導(dǎo)者的個(gè)體對(duì)前序位置跟蹤的越快,從而強(qiáng)化了領(lǐng)導(dǎo)者游走的探索效果。

圖2 跟隨律基于動(dòng)力學(xué)分析的幾何解釋Fig.2 Geometric interpretation of heterogeneous following law

3.2 驅(qū)動(dòng)機(jī)制改進(jìn)

SSA一般采用單鏈形式,即驅(qū)動(dòng)量為迭代過(guò)程中所獲得的全局最優(yōu)解。根據(jù)動(dòng)力學(xué)形式可知在搜索過(guò)程中可以通過(guò)調(diào)整驅(qū)動(dòng)量,即學(xué)習(xí)對(duì)象來(lái)提高算法的搜索性。一般算法中學(xué)習(xí)對(duì)象可以是全局最優(yōu)解、全局次優(yōu)解、個(gè)體歷史最優(yōu)解、隨機(jī)對(duì)象等。

因此,可以通過(guò)構(gòu)建多運(yùn)動(dòng)鏈結(jié)構(gòu),同時(shí)指定多個(gè)學(xué)習(xí)對(duì)象提高算法的多樣性。從算法結(jié)構(gòu)上將種群個(gè)體分為確定的若干個(gè)子鏈,每一個(gè)子鏈確定偏序運(yùn)動(dòng)。

首先,將種群中的個(gè)體進(jìn)行編號(hào),種群規(guī)模為N,定義運(yùn)動(dòng)鏈的總數(shù)為Mc,則各個(gè)運(yùn)動(dòng)鏈中個(gè)體的數(shù)目為

第m個(gè)運(yùn)動(dòng)鏈中領(lǐng)導(dǎo)者及后續(xù)跟隨者對(duì)應(yīng)的編號(hào)為

式中:i=1表示領(lǐng)導(dǎo)者;i=2,3,…,Nm表示跟隨者。

在將種群劃分多鏈的基礎(chǔ)上,驅(qū)動(dòng)機(jī)制改進(jìn)的核心在于對(duì)于每一個(gè)子鏈指定不同的學(xué)習(xí)對(duì)象。可以采用隨機(jī)化個(gè)體或者偏序最優(yōu)解。本文中采用的改進(jìn)機(jī)制為偏序最優(yōu)解,即每一個(gè)子鏈的領(lǐng)導(dǎo)者的學(xué)習(xí)中心分別指定為排序后的最優(yōu)解位置。

以具有3個(gè)運(yùn)動(dòng)鏈的算法結(jié)構(gòu)為例,則3個(gè)領(lǐng)導(dǎo)者的更新機(jī)理為

(14)

式中:上標(biāo)1、2、3表示子鏈序號(hào);br1=bg;br2表示僅次于bg的位置;br3次之。

3.3 基于動(dòng)力學(xué)行為的算法改進(jìn)

在基準(zhǔn)SSA的基礎(chǔ)上,采用以上兩種改進(jìn)策略,提出了多鏈異質(zhì)SSA(multi-chain heterogeneous SSA, MHSSA)。

首先,設(shè)置運(yùn)動(dòng)鏈的個(gè)數(shù),將種群中的個(gè)體按照運(yùn)動(dòng)鏈的從屬關(guān)系進(jìn)行分類,并在同一個(gè)運(yùn)動(dòng)鏈中以固定排序的形式建立偏序運(yùn)動(dòng)鏈。各運(yùn)動(dòng)鏈中,異質(zhì)慣性因子根據(jù)偏序集定義為

b=linspace(bmin,bmax,Nl-1)

(15)

式中:bmin=0.1,bmax=0.9,運(yùn)動(dòng)鏈排序越靠前的個(gè)體慣性因子越小;Nl表示第l個(gè)子鏈的個(gè)體總數(shù)。

以上改進(jìn)措施均在算法初始化的時(shí)候完成,后續(xù)算法執(zhí)行過(guò)程中與基準(zhǔn)SSA的流程相似,且計(jì)算量相當(dāng),未增加算法對(duì)算力的負(fù)荷。算法的執(zhí)行流程如下。

步驟 1初始化:定義種群規(guī)模N,運(yùn)動(dòng)鏈個(gè)數(shù)Mc,偏序結(jié)構(gòu),根據(jù)式(15)定義各個(gè)個(gè)體的跟隨率;

步驟 2適應(yīng)度計(jì)算:根據(jù)種群位置計(jì)算適應(yīng)度;

步驟 3更新最優(yōu)序列:根據(jù)當(dāng)前適應(yīng)度對(duì)個(gè)體進(jìn)行排序,并更新最優(yōu)序列;

步驟 4迭代終止條件判斷:判斷是否滿足終止條件。如果滿足,則輸出當(dāng)前最優(yōu)序列中的首項(xiàng)作為全局最優(yōu)解;否則執(zhí)行步驟5;

步驟 5多鏈領(lǐng)導(dǎo)者選擇:選擇當(dāng)前最優(yōu)序列中前Mc個(gè)個(gè)體位置分別作為不同運(yùn)動(dòng)鏈的驅(qū)動(dòng)量;

步驟 6位置更新:根據(jù)式(7),更新種群位置信息,并跳轉(zhuǎn)至步驟1。

算法流程圖如圖3所示,其中本文所提出的改進(jìn)流程以粗體凸顯。

圖3 MHSSA的流程圖Fig.3 Flowchart of MHSSA

4 仿真與驗(yàn)證

4.1 測(cè)試函數(shù)及仿真設(shè)置

本文的仿真對(duì)象選擇CEC14中定義的16個(gè)簡(jiǎn)單函數(shù)(3個(gè)單谷函數(shù)、13個(gè)多谷函數(shù)),6個(gè)混合函數(shù)與8個(gè)組合函數(shù)共30個(gè)函數(shù)組成仿真測(cè)試集。單谷函數(shù)用于檢驗(yàn)算法的收斂精度,多谷函數(shù)用于測(cè)試算法跳出局部最優(yōu)的能力,混合函數(shù)和組合函數(shù)組成復(fù)雜,可用于測(cè)試算法解決現(xiàn)實(shí)世界復(fù)雜優(yōu)化問(wèn)題。其中,設(shè)計(jì)空間的搜索范圍定義為[-100,100]D,其中D表示設(shè)計(jì)變量x的維數(shù)。

在每次的仿真測(cè)試過(guò)程中,需要對(duì)全局最優(yōu)解進(jìn)行隨機(jī)化處理:全局最優(yōu)隨機(jī)偏移與設(shè)計(jì)空間的隨機(jī)扭轉(zhuǎn)。令o表示偏移后的全局最優(yōu)解,在[-80,80]D范圍內(nèi)隨機(jī)指定。令M表示為旋轉(zhuǎn)矩陣,對(duì)所有的函數(shù)與基函數(shù)均進(jìn)行設(shè)計(jì)空間的旋轉(zhuǎn)。

本文中優(yōu)化問(wèn)題考慮的維數(shù)為D=30,種群規(guī)模設(shè)置為

單個(gè)問(wèn)題仿真的次數(shù)為51次,考慮到算力的約束限制,本文中約定最大迭代次數(shù)為

仿真研究的算法主體為采用異質(zhì)跟隨及多鏈驅(qū)動(dòng)改進(jìn)的MHSSA,仿真對(duì)比以基準(zhǔn)SSA、僅采用異質(zhì)跟隨率改進(jìn)的異質(zhì)SSA(heterogeneous, HSSA)、僅采用多鏈驅(qū)動(dòng)改進(jìn)的多鏈SSA(multi-chain SSA, MSSA)進(jìn)行縱向?qū)Ρ?同時(shí)采用公開(kāi)文獻(xiàn)中其他的SSA改進(jìn)算法進(jìn)行橫向?qū)Ρ?包括多子群的共生非均勻高斯變異SSA(multi-subpopulation based symbiosis and non-uniform Gaussian mutation SSA, MSNSSA)和基于正交設(shè)計(jì)的折射反向?qū)W習(xí)SSA(orthogonal opposition-based SSA, OOSSA)。為了說(shuō)明SSA的適用范圍,對(duì)比了PSO算法和GWO算法。

4.2 仿真結(jié)果

表1列出了30個(gè)測(cè)試函數(shù)下不同算法的統(tǒng)計(jì)學(xué)特征平均排名,Med、Var、Min、Max分別表示51次運(yùn)行結(jié)果的中位數(shù)、標(biāo)準(zhǔn)差、最小值和最大值,包括本文提出的MHSSA在內(nèi)的所有算法都能夠收斂。

表1 算法統(tǒng)計(jì)學(xué)特征平均排名比較Table 1 Comparison of average rank for statistical characteristics of algorithms

從表1中可以看出本文提出的MHSSA在中位數(shù)、標(biāo)準(zhǔn)差、最小值、最大值上均名列第1,表明改進(jìn)后的算法在尋優(yōu)能力上有更好的表現(xiàn),由于各算法在標(biāo)準(zhǔn)差上的差異不顯著,不考慮標(biāo)準(zhǔn)差排名,MSSA在中位數(shù)、最大值、最小值上均排名第2,其余算法在中位數(shù)、標(biāo)準(zhǔn)差、最大值、最小值上的表現(xiàn)各有千秋。

為了避免算法對(duì)比中隨機(jī)性所造成的性能差異,本文用p值檢驗(yàn)來(lái)進(jìn)行顯著性驗(yàn)證,對(duì)比MHSSA與其他各個(gè)算法的差異性。顯著性水平設(shè)置為0.05。驗(yàn)證結(jié)果如表2所示,其中,S表示MHSSA算法具有顯著性差異,NS表示沒(méi)有顯著性差異;“+”表示MHSSA算法優(yōu)于對(duì)比算法,“-”表示MHSSA次于對(duì)比算法。

表2 算法性能差異顯著性比較Table 2 Significance testing of algorithms

從表2可以看出MHSSA在28個(gè)測(cè)試函數(shù)上顯著優(yōu)于SSA,在28個(gè)測(cè)試函數(shù)上顯著優(yōu)于HSSA,在12個(gè)測(cè)試函數(shù)上顯著優(yōu)于MSSA,在29個(gè)測(cè)試函數(shù)上顯著優(yōu)于MSNSSA,在20個(gè)測(cè)試函數(shù)上顯著優(yōu)于OOSSA,在24個(gè)測(cè)試函數(shù)上顯著優(yōu)于PSO,在19個(gè)測(cè)試函數(shù)上顯著優(yōu)于GWO。

為了更直觀地表示算法性能差異顯著性比較結(jié)果,圖4對(duì)比較結(jié)果進(jìn)行了統(tǒng)計(jì),其中綠色部分表示MHSSA顯著優(yōu)于對(duì)比算法,白色部分表示對(duì)比結(jié)果不顯著,無(wú)法排除結(jié)果是由于偶然性導(dǎo)致,藍(lán)色部分表示MHSSA顯著次于所對(duì)比的算法。

圖4 MHSSA與其他算法的顯著性對(duì)比Fig.4 Significance comparison between MHSSA and other algorithms

從圖4中可以直觀地看出,MHSSA與SSA和MSNSSA相比,在所有測(cè)試集函數(shù)中均有明顯改善。整體而言,異質(zhì)跟隨率與多鏈驅(qū)動(dòng)機(jī)制的結(jié)合要更優(yōu)于采用單一改進(jìn)機(jī)制的算法。此外,MHSSA在6個(gè)測(cè)試函數(shù)的結(jié)果中顯著次于OOSSA。進(jìn)一步分析可以發(fā)現(xiàn),這些函數(shù)均具有周期性振蕩小幅衰減的函數(shù)?？梢哉J(rèn)為針對(duì)這類型函數(shù)OOSSA有明顯的優(yōu)勢(shì),雖然本文改進(jìn)的算法在以上6個(gè)函數(shù)上未收斂到最優(yōu)解,但是距最優(yōu)解的距離與其他算法相比更小。

根據(jù)圖4中顯著性分析結(jié)果,分別選擇MSSA、OOSSA、PSO與GWO對(duì)比在不同測(cè)試函數(shù)優(yōu)化結(jié)果中中位數(shù)的排名情況,如圖5～圖8所示。

圖5 CEC14測(cè)試函數(shù)集MHSSA與MSSA的中位數(shù)排名對(duì)比Fig.5 Median rank of MSSA and MHSSA for CEC14 testsuite

從圖5中可以看出,MHSSA由于新增了異質(zhì)跟隨律這一機(jī)制,在多谷類型的優(yōu)化問(wèn)題中顯著提高優(yōu)化性能;從圖6中可以看出,多數(shù)情況下MHSSA的優(yōu)化結(jié)果是優(yōu)于OOSSA的,但是對(duì)于次優(yōu)解分布密集且目標(biāo)函數(shù)具有周期性振蕩小幅衰減的情況下,OOSSA具有較好的表現(xiàn);從圖7和圖8中可以看出,相較于PSO和GWO,本文提出的MHSSA在多數(shù)情況下也具有較好的性能表現(xiàn),對(duì)于設(shè)計(jì)變量空間未經(jīng)過(guò)旋轉(zhuǎn)隨機(jī)化的測(cè)試函數(shù),比如F08和F10,PSO的優(yōu)化結(jié)果更優(yōu)。

圖6 CEC14測(cè)試函數(shù)集MHSSA與OOSSA中位數(shù)排名對(duì)比Fig.6 Median rank of MSSA and OOSSA for CEC14 testsuite

圖7 CEC14測(cè)試函數(shù)集MHSSA與PSO中位數(shù)排名對(duì)比Fig.7 Median rank of MSSA and PSO for CEC14 testsuite

圖8 CEC14測(cè)試函數(shù)集MHSSA與GWO中位數(shù)排名對(duì)比Fig.8 Median rank of MSSA and GWO for CEC14 testsuite

為進(jìn)一步說(shuō)明不同算法在典型測(cè)試函數(shù)上的性能的優(yōu)劣,根據(jù)各算法獨(dú)立求解測(cè)試函數(shù)51次的結(jié)果繪制箱式圖,選擇了算法具有顯著對(duì)比差異的部分函數(shù),以多峰函數(shù)、混合函數(shù)和組合函數(shù)為分組依據(jù),如圖9～圖12所示。

圖9 多峰測(cè)試函數(shù)各算法優(yōu)化結(jié)果對(duì)比Fig.9 Optimization results comparison of algorithms for multimodal test functions

圖10 組合測(cè)試函數(shù)各算法優(yōu)化結(jié)果對(duì)比Fig.10 Optimization results comparison of algorithms for combined test functions

圖11 多峰測(cè)試函數(shù)F12最優(yōu)值中位數(shù)收斂曲線對(duì)比Fig.11 Median convergence trajectory comparison of optimal value for multimodal test functions F12

圖12 組合測(cè)試函數(shù)F24最優(yōu)值中位數(shù)收斂曲線對(duì)比Fig.12 Median convergence trajectory comparison of optimal value for combined test functions F24

其中A1表示SSA;A2表示HSSA;A3表示MSSA;A4表示MSNSSA;A5表示OOSSA;A6表示PSO;A7表示GWO;A8表示MHSSA。對(duì)比性能最優(yōu)算法以黃色標(biāo)識(shí)。

5 結(jié) 論

本文以SSA為研究對(duì)象,從動(dòng)力學(xué)的角度出發(fā),將算法更新機(jī)理解構(gòu)為離散動(dòng)力學(xué)方程,提出了算法穩(wěn)定性的充分條件。根據(jù)SSA的動(dòng)力學(xué)解釋模型,歸納總結(jié)了該算法的四類改進(jìn)措施:跟隨律改進(jìn)、學(xué)習(xí)律改進(jìn)、驅(qū)動(dòng)機(jī)制改進(jìn)與游走機(jī)制改進(jìn)?；赟SA收斂性條件,從跟隨律與驅(qū)動(dòng)機(jī)制兩個(gè)方面提出了異質(zhì)定常跟隨律與多鏈驅(qū)動(dòng)的算法改進(jìn)措施。通過(guò)優(yōu)化算法測(cè)試集的仿真結(jié)果,分別驗(yàn)證了兩種改進(jìn)的有效性,在不增加算法算力負(fù)荷的情況下,顯著改善了SSA的算法性能。仿真對(duì)比表明,改進(jìn)措施對(duì)測(cè)試集中絕大多數(shù)函數(shù)的優(yōu)化結(jié)果均有顯著改善;對(duì)于次優(yōu)解分布密集且目標(biāo)函數(shù)具有周期性振蕩小幅衰減的情況,比如Rastrigin函數(shù),采用正交策略可以獲得更優(yōu)的情況。