混合多策略改進(jìn)的樽海鞘群算法及其應(yīng)用

張家瑋，李 琳+，張奇志

(1.西安石油大學(xué) 電子工程學(xué)院，陜西 西安 710065；2.西安石油大學(xué) 陜西省油氣井重點(diǎn)測控實(shí)驗(yàn)室，陜西 西安 710065)

0 引 言

近年來，源于自然現(xiàn)象的群智能優(yōu)化算法迅速發(fā)展[1]，如海鷗算法(seagull optimization algorithm，SOA)[2]、麻雀搜索算法(sparrow search algorithm，SSA)[3]和黏菌算法(slime mound algorithm，SMA)[4]。這些群智能算法具有靈活性、無梯度機(jī)制、簡單性和避免局部最優(yōu)等優(yōu)點(diǎn)。樽海鞘群優(yōu)化算法(salp swarm algorithm，SSA)由Mirjalili等提出[5]，SSA算法模擬了樽海鞘的生活習(xí)性和捕食習(xí)性，其數(shù)學(xué)模型可分為兩組：一組為領(lǐng)導(dǎo)者，另一組為跟隨者。領(lǐng)導(dǎo)者是樽海鞘鏈中的第一個(gè)樽海鞘，在這條鏈中其余樽海鞘為跟隨者。在算法尋優(yōu)中，領(lǐng)導(dǎo)者帶領(lǐng)種群尋找最優(yōu)食物，而跟隨者則跟隨最近的樽海鞘，由于樽海鞘之間的相互作用，樽海鞘不會輕易傾向一個(gè)局部可行的解，很大程度地避免局部最優(yōu)，其尋優(yōu)精度和收斂性能的效果比傳統(tǒng)遺傳算法、粒子群算法、灰狼算法更好[6]。此外，其結(jié)構(gòu)簡單和控制參數(shù)少使得它正在成為算法領(lǐng)域的熱門研究[7]，引來許多學(xué)者研究并將其應(yīng)用于不同領(lǐng)域，如訓(xùn)練多層感知器[8]、電力系統(tǒng)調(diào)度優(yōu)化[9]和能源管理策略優(yōu)化[10]等。這些都反映了SSA算法在某些領(lǐng)域的突出性能，驗(yàn)證該方法的高靈活性和可靠性。

1 相關(guān)工作

雖然SSA算法在很多領(lǐng)域都表現(xiàn)出了出色的性能，但它存在收斂速度慢、局部最優(yōu)停滯等缺點(diǎn)。多年來，研究人員提出了許多改進(jìn)的SSA算法，以獲取更好的性能。文獻(xiàn)[11]中通過改進(jìn)混沌Tent映射機(jī)制對種群化初始化，同時(shí)加入動態(tài)學(xué)習(xí)使算法跳出局部最優(yōu)，提升其尋優(yōu)能力。文獻(xiàn)[12]引入衰減因子和動態(tài)學(xué)習(xí)機(jī)制分別對領(lǐng)導(dǎo)者和追隨者的位置更新進(jìn)行優(yōu)化，有效提升局部開發(fā)和全局搜索能力。

這些改進(jìn)在一定程度上提高了SSA算法尋優(yōu)能力，但仍存在計(jì)算精度低和局部最優(yōu)停滯等缺陷。本文提出一種混合多策略的改進(jìn)樽海鞘群算法(improved slap swarm algorithm with hybrid multi-strategy，ISSA)。在前期利用佳點(diǎn)集策略生成初始化種群，增強(qiáng)種群空間分布的均勻性，減少種群隨機(jī)性的影響；將反向?qū)W習(xí)和自適應(yīng)t分布融入到領(lǐng)導(dǎo)者的位置更新中，使得領(lǐng)導(dǎo)者擺脫以往的限制，不僅在迭代前期具有更大的全局搜索空間，而且在后期具有更好的局部開發(fā)能力；在種群位置更新的最后階段引入精英反向?qū)W習(xí)策略，選取適應(yīng)度較優(yōu)的個(gè)體來參與算法的下一次迭代，種群由精英個(gè)體引導(dǎo)，更有可能地找到全局最優(yōu)解。將ISSA算法與其它算法在測試函數(shù)上對比性能以驗(yàn)證ISSA算法的優(yōu)勢，并采用Wilcoxon秩和檢驗(yàn)評價(jià)算法之間的差異性。

2 樽海鞘群算法

樽海鞘群優(yōu)化算法與其它基于群體的智能優(yōu)化算法相似。首先，隨機(jī)初始化種群，樽海鞘的位置被定義在N維搜索空間中，樽海鞘群X可以表述一個(gè)N×D維矩陣，如式(1)所示。F在搜索空間中被設(shè)定為目標(biāo)向量或者食物源，領(lǐng)導(dǎo)者位置的每次更新都是朝著食物源，更新公式如式(2)所示

(1)

(2)

(3)

式中：l是當(dāng)前迭代次數(shù)，Lmax是定義的最大迭代次數(shù)，追隨者的運(yùn)動是由領(lǐng)導(dǎo)者引導(dǎo)，追隨者位置更新公式如下所示

(4)

3 改進(jìn)樽海鞘群算法

3.1 基于佳點(diǎn)集的種群初始化

任何一種元啟發(fā)式算法都是為了在全局優(yōu)化過程中找到收斂性和多樣性之間的平衡而設(shè)計(jì)，這種權(quán)衡對于成功執(zhí)行優(yōu)化算法至關(guān)重要[13]。一般來說，良好的多樣性表示種群對探索整個(gè)搜索空間具有很強(qiáng)的優(yōu)勢。標(biāo)準(zhǔn)SSA算法的種群初始化主要依靠隨機(jī)方式生成，而隨機(jī)初始化會造成種群在搜索空間的非均勻分布。因此，本文結(jié)合均勻設(shè)計(jì)思想，引入佳點(diǎn)集策略來改進(jìn)SSA算法。佳點(diǎn)集理論由華羅庚先生提出[14]，利用佳點(diǎn)集策略生成初始化群體，可得到以下公式

(5)

式中：d表示變量的維數(shù)，p是滿足p≥2d+3的最小素?cái)?shù)。假設(shè)N為群體規(guī)模，第i個(gè)樽海鞘可由下式產(chǎn)生

(6)

式中：{γji} 表示γji的小數(shù)部分。ubj，lbj分別是搜索范圍的上下限。

3.2 領(lǐng)導(dǎo)者更新機(jī)制變化

SSA算法中，所有領(lǐng)導(dǎo)者向食物源靠近，受食物源牽引的領(lǐng)導(dǎo)者可以加快算法的收斂速度。但由式(2)可知，其搜索范圍太窄，導(dǎo)致領(lǐng)導(dǎo)者對搜索空間的勘探不充分，造成搜索精度不足。

反向?qū)W習(xí)(opposition-based learning，OBL)是由Tizhoo提出[15]，反向?qū)W習(xí)是一種旨在提高元啟發(fā)式算法性能的機(jī)器智能策略，它是在當(dāng)前個(gè)體中間找到一個(gè)更有效的解，求得反向解，計(jì)算它們的適應(yīng)度值，選擇最優(yōu)解進(jìn)行下一次迭代。本文受反向?qū)W習(xí)的啟發(fā)，將反向?qū)W習(xí)的思想融入到領(lǐng)導(dǎo)者的更新機(jī)制，在搜索最優(yōu)值的過程中，使得算法擁有更好的全局開發(fā)能力和局部開發(fā)能力。融入反向?qū)W習(xí)的領(lǐng)導(dǎo)者位置更新公式如下所示

(7)

3.3 自適應(yīng)t分布權(quán)重

SSA算法主要依靠領(lǐng)導(dǎo)者進(jìn)行覓食尋優(yōu)，領(lǐng)導(dǎo)者的移動主要受參數(shù)c1控制，因此，c1是影響整個(gè)算法尋優(yōu)能力的重要指標(biāo)。隨迭代次數(shù)的增加，c1是[0，2]之間遞減的非線性函數(shù)，在迭代前期，算法具有較大的全局搜索空間；但在迭代后期，算法的局部開發(fā)能力減弱，導(dǎo)致算法的精度不高。受文獻(xiàn)[16]啟發(fā)，本文引入t分布用來替換c1參數(shù)，在概率學(xué)中，t分布又稱學(xué)生分布。t分布曲線的形狀與自由度n有關(guān)，與標(biāo)準(zhǔn)正態(tài)分布相比，自由度越小，曲線越平坦。如果曲線中間較低，那么曲線兩邊的尾部較高。自由度n越大，t分布越接近正態(tài)分布?？挛鞣植己透咚狗植际莟分布邊界處的兩個(gè)特殊情況分布，3個(gè)函數(shù)分布如圖1所示。

圖1 高斯分布、柯西分布和t分布的概率密度曲線

從圖1中可以看出，t分布的兩端形狀長而平坦，接近0的過程相對平緩。速度和峰值均介于柯西分布和高斯分布之間，使得t分布吸取了柯西分布和高斯分布的優(yōu)點(diǎn)。因此，在領(lǐng)導(dǎo)者位置更新公式中引入t分布突變，利用t分布突變的擾動能力提高全局優(yōu)化的能力。具體公式如下所示

(8)

式中：t(iter) 表示具有迭代次數(shù)itert的t分布，將迭代次數(shù)iter視為參數(shù)自由度。

3.4 精英反向?qū)W習(xí)機(jī)制

精英反向?qū)W習(xí)(elite opposition-based learning，EOBL)是OBL的改進(jìn)版本，EBOL定義請見文獻(xiàn)[17]。利用EBOL策略可以擴(kuò)大算法的搜索范圍，提升算法的尋優(yōu)性能，并且EBOL已經(jīng)成功應(yīng)于改進(jìn)其它群體智能算法[18]。

本文利用EOBL策略來提高SSA算法的全局搜索能力。設(shè)每輪迭代更新后的樽海鞘都是精英個(gè)體，精英個(gè)體公式如下所示

(9)

其反向解公式如下所示

(10)

如果反向解超越邊界，則利用隨機(jī)生成將其重置，重置公式如下所示

(11)

計(jì)算精英樽海鞘和反向精英樽海鞘的適應(yīng)度，保留適應(yīng)度更優(yōu)的前N個(gè)樽海鞘，將其作為新的樽海鞘種群參與下一次更新迭代。

3.5 算法步驟

ISSA算法的具體執(zhí)行步驟如下：

步驟1 設(shè)置種群規(guī)模N和迭代次數(shù)Lmax等初始變量。

步驟2 利用3.1節(jié)的佳點(diǎn)集策略生成初始種群。

步驟3 計(jì)算每個(gè)個(gè)體的適應(yīng)度值，選擇最優(yōu)的個(gè)體作為食物源位置。

步驟4 根據(jù)式(8)更新領(lǐng)導(dǎo)者的位置，式(4)更新跟隨者的位置。

步驟5 計(jì)算個(gè)體的動態(tài)邊界，根據(jù)式(10)生成反向解并添加到種群中。

步驟6 從融合的種群中保留適應(yīng)度更優(yōu)的前N個(gè)樽海鞘，將其作為新的樽海鞘種群參與下一次迭代，并將最佳位置設(shè)為食物源。

步驟7 判斷條件，若符合，則得到結(jié)果；否則，跳到步驟4。

ISSA算法的流程如圖2所示。

圖2 ISSA算法的流程

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

為驗(yàn)證ISSA算法的有效性，將ISSA算法與標(biāo)準(zhǔn)樽海鞘群算法(SSA)和標(biāo)準(zhǔn)海鷗算法(SOA)對比性能；同時(shí)為了突出ISSA算法的競爭優(yōu)勢，選取3種改進(jìn)SSA算法，即基于衰減因子和動態(tài)學(xué)習(xí)的改進(jìn)樽海鞘群算法(SSA based on reduction factor and dynamic learning，RDSSA[12])、基于混沌映射動態(tài)慣性權(quán)重的改進(jìn)樽海鞘群算法(SSA based on chaotic map and dynamic inertia weight，I-SSA[19])和基于高斯分布估計(jì)策略的改進(jìn)樽海鞘群算法(SSA based on Gaussian distribution estimation strategy，CDESSA[20])，進(jìn)行對比研究。它們的具體參數(shù)設(shè)置見表1。

表1 算法實(shí)驗(yàn)參數(shù)設(shè)置

4.2 測試函數(shù)及測試環(huán)境

基準(zhǔn)函數(shù)測試是衡量智能算法性能的常用方法，本文選取的8個(gè)基準(zhǔn)測試函數(shù)來展示所改進(jìn)算法的優(yōu)越性能，F(xiàn)1～F4是單峰函數(shù)，這類測試函數(shù)只存在一個(gè)最優(yōu)解。這類型的搜索空間適用于測試收斂速度和搜索的能力。F5～F8是多峰值的基準(zhǔn)函數(shù)，多峰值的基準(zhǔn)函數(shù)存在局部最優(yōu)值，這使得它們適合于對比算法的局部最優(yōu)回避和全局探索行為。它們的具體信息分別見表2和表3。

表2 單峰基準(zhǔn)測試函數(shù)

表3 多峰基準(zhǔn)測試函數(shù)

本文的實(shí)驗(yàn)環(huán)境是基于Intel(R)Core i5處理器以及4 G內(nèi)存的計(jì)算機(jī)，仿真軟件是MatlabR2016b。所有測試的初始條件均相同：種群規(guī)模N=60，迭代次數(shù)Lmax=1000。每種算法在函數(shù)中獨(dú)立運(yùn)行30次，其結(jié)果取最優(yōu)值、平均值和標(biāo)準(zhǔn)差，如表4所示。

表4 測試函數(shù)結(jié)果

4.3 實(shí)驗(yàn)結(jié)果及分析

由表4可以看出，在單峰基準(zhǔn)函數(shù)F1～F4的測試結(jié)果中，ISSA算法都取得了較好的效果，ISSA算法的3個(gè)指標(biāo)相比其它算法都具有顯著的優(yōu)勢。如在函數(shù)F1的測試結(jié)果中，標(biāo)準(zhǔn)SSA算法和改進(jìn)算法中結(jié)果較好的I_SSA算法的平均值分別為8.97E-09和3.02E-74，而ISSA算法的平均值達(dá)到了9.7695E-244，相較I-SSA算法提高近150個(gè)數(shù)量級，較SSA算法更是提高近230個(gè)數(shù)量級，其結(jié)果表明本文提出的改進(jìn)策略能有效提高SSA算法的收斂精度。

由表4可知，在多峰基準(zhǔn)函數(shù)的測試結(jié)果中，ISSA算法在函數(shù)F5和F7上都達(dá)到理論最優(yōu)值，均值和標(biāo)準(zhǔn)差的值都是0，ISSA算法在函數(shù)F6的結(jié)果比RDSSA算法和I_SSA算法的效果略差，但在函數(shù)F8的結(jié)果上強(qiáng)于其它改進(jìn)算法?？偟膩碚fISSA算法在多峰基準(zhǔn)函數(shù)上表現(xiàn)出較好的結(jié)果，驗(yàn)證其具有良好的避免局部最優(yōu)的能力。

綜上所述，在求解單峰和多峰基準(zhǔn)函數(shù)過程中，ISSA算法相對其它5種算法具有更好的尋優(yōu)效果。為了更好地體現(xiàn)算法的尋優(yōu)性能，本文給出6種算法在8個(gè)基準(zhǔn)函數(shù)的收斂曲線圖，分別如圖3和圖4所示。

圖3 單峰函數(shù)上的收斂曲線

圖4 多峰函數(shù)上的收斂曲線

由圖3和圖4的收斂曲線可以直觀地看出，SSA算法在尋優(yōu)迭代過程中，收斂曲線很難向下探索并且探索的速度較為緩慢，并且在求解每個(gè)函數(shù)的過程中都出現(xiàn)停滯，只是它們的程度不同，表明SSA算法容易陷入了局部最優(yōu)。由圖3(a)～圖3(d)所示單峰函數(shù)的收斂曲線看出，ISSA算法的收斂曲線呈直線型快速向下探索，由此可以驗(yàn)證本文改進(jìn)SSA算法在收斂速度上有較為明顯的改善；由圖4(a)～圖4(d)所示多峰函數(shù)的收斂曲線可知，ISSA算法的收斂曲線下降速度較快且曲線存在拐點(diǎn)，驗(yàn)證提出的改進(jìn)方法能明顯提高其全局搜索能力和局部勘探能力，有效地避免陷入局部最優(yōu)的情況。由于I-SSA算法在函數(shù)F5和F7上迅速收斂到最優(yōu)值，因此圖中沒有I-SSA算法的收斂曲線。

4.4 Wilcoxon秩和檢驗(yàn)

僅僅是平均值和標(biāo)準(zhǔn)差不足以體現(xiàn)算法之間的差異，為了驗(yàn)證ISSA算法與其它5種算法在求解復(fù)雜優(yōu)化問題時(shí)是否存在顯著差異，采用Wilcoxon秩和檢驗(yàn)比較兩種算法的性能測試特征。Wilcoxon秩和檢驗(yàn)是一種非參數(shù)零假設(shè)檢驗(yàn)統(tǒng)計(jì)方法，用于評價(jià)算法的公平性和魯棒性[21]。表5列出獨(dú)立運(yùn)行30次后的Wilcoxon秩和檢驗(yàn)結(jié)果的p值，其中N/A表示不適用。

表5 Wilcoxon秩和檢驗(yàn)p值

由表5可以看出，ISSA算法的p值大部分小于0.05，說明ISSA算法的性能與其它算法相比具有較強(qiáng)的競爭能力，驗(yàn)證該算法在不同函數(shù)優(yōu)化問題上的優(yōu)勢。綜上所述，ISSA算法與其它5種算法有顯著不同，其結(jié)果具有統(tǒng)計(jì)學(xué)意義，表明ISSA算法的性能不是偶然的。

4.5 ISSA算法在拉伸/壓縮彈簧設(shè)計(jì)問題中的應(yīng)用

為了進(jìn)一步驗(yàn)證ISSA算法的性能，將ISSA算法應(yīng)用到拉伸/壓縮彈簧設(shè)計(jì)的工程優(yōu)化問題，該問題的設(shè)計(jì)模型如圖5所示。該問題通過考慮最小擾度、剪切應(yīng)力和喘振頻率等約束來最小化彈簧的質(zhì)量。這個(gè)模型有3個(gè)連續(xù)優(yōu)化變量，分別是導(dǎo)線直徑d、線圈直徑D和有源線圈個(gè)數(shù)N，其數(shù)學(xué)模型如下所示。

圖5 拉伸/壓縮彈簧問題的設(shè)計(jì)

假設(shè)

(12)

(13)

0.05≤x1≤2，0.25≤x2≤1.3，2≤x3≤15

(14)

6種算法對拉伸/壓縮彈簧設(shè)計(jì)問題的優(yōu)化結(jié)果見表6。

表6 彈簧設(shè)計(jì)問題的優(yōu)化結(jié)果

從表6可以看出，在彈簧設(shè)計(jì)的問題上，ISSA算法的優(yōu)化結(jié)果要優(yōu)于其它算法。

5 結(jié)束語

為提高標(biāo)準(zhǔn)SSA算法的搜索效率、收斂精度和穩(wěn)定性。本文在標(biāo)準(zhǔn)SSA算法的基礎(chǔ)上，提出一種融合佳點(diǎn)集策略、反向?qū)W習(xí)、自適應(yīng)t分布和精英反向?qū)W習(xí)的改進(jìn)樽海鞘群算法(ISSA)。ISSA算法采用佳點(diǎn)集策略生成初始化種群，具有更強(qiáng)大的搜索能力；通過將反向?qū)W習(xí)和自適應(yīng)t分布融入領(lǐng)導(dǎo)者位置更新中，既利用領(lǐng)導(dǎo)者和跟隨者的位置優(yōu)勢，又利用t分布的優(yōu)勢，使得種群盡可能地尋找最優(yōu)解；加入精英反向?qū)W習(xí)，篩選出更好的種群參與下一次迭代。在8個(gè)基準(zhǔn)函數(shù)上測試了ISSA算法的有效性，其仿真結(jié)果說明該算法在求解尋優(yōu)的能力優(yōu)于其它算法，同時(shí)Wilcoxon秩和檢驗(yàn)的結(jié)果表明ISSA算法相比SSA算法及其它算法存在顯著差異。在一些實(shí)際的工程優(yōu)化問題中，ISSA算法也表現(xiàn)出較好的效果。下一步會將ISSA算法應(yīng)用到更多的工程優(yōu)化問題中，并且嘗試不同的改進(jìn)策略，獲得更優(yōu)的結(jié)果。