改進(jìn)的樽海鞘群算法及在焊接梁問題中的應(yīng)用

王彥軍，王秋萍，王曉峰

(西安理工大學(xué) 理學(xué)院，陜西西安710054)

群體智能(SI)技術(shù)是受自然啟發(fā)的元啟發(fā)式算法，是現(xiàn)在最為流行的尋優(yōu)算法，在諸多領(lǐng)域中得到了成功應(yīng)用。Mirjalili等模擬自然界中樽海鞘的群體行為，于2017年提出樽海鞘群算法(Salp Swarm Algorithm，SSA)，該算法只有一個主要控制參數(shù)，因此算法結(jié)構(gòu)較為簡單，易于實現(xiàn)，且研究結(jié)果表明該算法的尋優(yōu)性能優(yōu)于飛蛾火焰算法(MFO)、灰狼優(yōu)化算法(GWO)和人工蜂群算法(ABC)等[1]。因此，SSA算法在科學(xué)和工程等領(lǐng)域中有著廣泛應(yīng)用。

然而，與其他群智能算法類似，SSA算法也存在求解精度低、易陷入局部最優(yōu)等缺陷。國內(nèi)外學(xué)者針對這些缺陷提出了一系列改進(jìn)。

Sayed[2]等提出一種基于混沌理論的SSA算法以解決SSA算法易陷入局部最優(yōu)、收斂速度慢的缺點。

Ibrahim等[3]利用粒子群算法(PSO)的全局收斂性，提出一種基于SSA和PSO的混合優(yōu)化算法以平衡算法的勘探和開發(fā)能力。

Faris等[4]使用交叉算子來代替平均算子，提出了一種帶交叉的二進(jìn)制SSA算法以增強算法的全局探索。

王夢秋等[5]分析了SSA算法，發(fā)現(xiàn)追隨者位置更新方程具有一定的盲目性，在一定程度上限制了算法的搜索能力，提出了一種改進(jìn)的SSA算法并將其應(yīng)用于PMSM參數(shù)辨識。

為進(jìn)一步提高基本SSA算法的求解精度和收斂速度，本文提出了一種改進(jìn)樽海鞘群算法(Improved Salp Swarm Algorithm,ISSA)。該算法首先采用精英反向?qū)W習(xí)策略，有效地平衡算法的勘探和開發(fā)能力。然后，為增大搜索范圍，提高算法求解精度，引入一種差分策略來更新追隨者位置。最后，對食物位置進(jìn)行Gauss變異，以避免算法陷入局部最優(yōu)。對10個標(biāo)準(zhǔn)測試函數(shù)和一個經(jīng)典工程問題的實驗結(jié)果表明,本文所提出的ISSA算法具有較好的搜索性能。

1 樽海鞘群算法

1.1 樽海鞘群算法

樽海鞘屬于海樽科，有著透明的圓柱形身體，是一種與水母非常相似的海洋生物。在海洋中，樽海鞘有一種被稱為樽海鞘鏈的群體行為，有關(guān)學(xué)者認(rèn)為這種行為是為了幫助它們快速覓食和躲避天敵?；谶@一行為，Mirjalili等建立了樽海鞘鏈數(shù)學(xué)模型，并在優(yōu)化問題中測試了該模型的有效性。

SSA算法首先將種群分成兩部分，即領(lǐng)導(dǎo)者和追隨者。領(lǐng)導(dǎo)者引導(dǎo)群體，追隨者相互追隨。與其他基于種群的算法類似，樽海鞘的位置是在n維搜索空間中定義的，其中n表示給定問題的維數(shù)。因此，所有樽海鞘的位置都存儲在一個N×n二維矩陣x中(N是種群規(guī)模)。

假設(shè)在搜索空間中有一個叫做F的食物源作為種群的搜索目標(biāo)。

領(lǐng)導(dǎo)者根據(jù)下式更新位置：

(1)

(2)

式中：t是當(dāng)前迭代次數(shù)；T是最大的迭代次數(shù)。

使用下式更新追隨者位置：

(3)

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

本文選取一半的樽海鞘個體作為領(lǐng)導(dǎo)者，其余個體作為追隨者。領(lǐng)導(dǎo)者(j≤N/2)按式(4)更新之后，執(zhí)行精英反向?qū)W習(xí)策略。

(4)

采用差分策略更新追隨者位置，對食物位置進(jìn)行Gauss變異使其跳出局部最優(yōu)。

1.2.1精英反向?qū)W習(xí)策略

由于反向?qū)W習(xí)策略[6]通過同時對當(dāng)前候選解和反向候選解進(jìn)行評估，可以提供更多的機會找到更接近全局最優(yōu)的候選解。因此反向?qū)W習(xí)策略在群智能優(yōu)化算法中有效地提高了算法的搜索性能。

然而，反向?qū)W習(xí)策略并不能適用于所有類型的優(yōu)化問題。例如，在求解多峰函數(shù)問題時，變換后的候選對象可能會偏離全局最優(yōu)。為了避免這種情況的發(fā)生，汪慎文等[7]在一般反向?qū)W習(xí)的基礎(chǔ)上引入精英個體的良好信息，提出了精英反向?qū)W習(xí)策略，并給出了關(guān)于精英反向?qū)W習(xí)策略在群智能優(yōu)化算法中具有全局收斂性的證明。

實驗結(jié)果表明，精英反向?qū)W習(xí)策略具有更優(yōu)良的性能[7]。

(5)

式中，λ是[0,1]區(qū)間服從均勻分布的隨機數(shù)，ai(t)、bi(t)表達(dá)式為：

在文獻(xiàn)[7]中,作者對精英反向?qū)W習(xí)策略進(jìn)行了分析。精英反向?qū)W習(xí)策略在反向解與當(dāng)前解中選出優(yōu)秀個體進(jìn)入下一代群體中以增強種群的多樣性,降低算法陷入局部最優(yōu)的概率。如果算法能收斂到全局最優(yōu)解，則精英個體所構(gòu)成的搜索區(qū)間必將收斂到最優(yōu)解所在的區(qū)域。因此，在精英個體所構(gòu)成的搜索區(qū)間上產(chǎn)生反向解，引導(dǎo)搜索過程向最優(yōu)解逼近，從而提高算法的收斂速度。從而，精英反向?qū)W習(xí)策略可以較好地平衡算法的勘探和開發(fā)能力。

反向?qū)W習(xí)策略可以增加種群多樣性[8]。因此，本文利用領(lǐng)導(dǎo)者個體的搜索信息，在領(lǐng)導(dǎo)者個體所構(gòu)成的搜索空間上產(chǎn)生反向解。

對反向解和當(dāng)前解，采用貪心保留策略，選出更加優(yōu)秀的個體進(jìn)入下一代以增加種群多樣性，可以更好地避免算法陷入局部最優(yōu)，且提高算法的收斂速度。

1.2.2差分策略

在基本SSA算法中，由式(3)可以看出，第j個樽海鞘的位置更新只與自身和跟隨的第j-1個樽海鞘的位置信息有關(guān)。這種在單向接收第j-1個樽海鞘的位置信息后立即更新位置，在一定程度上限制了算法搜索效果。

針對算法的這種缺陷，我們將引入第j-2個樽海鞘的位置信息，來引導(dǎo)追隨者個體增大搜索范圍，避免算法陷入局部最優(yōu)，改善算法的搜索效果和提高算法的求解精度。

(6)

1.2.3Gauss變異策略

在樽海鞘群算法中，所有個體都直接或間接地向種群當(dāng)前最好個體(食物)學(xué)習(xí)，在迭代后期種群多樣性的丟失是不可避免的。一旦最好個體陷入局部最優(yōu)，則易導(dǎo)致群體出現(xiàn)搜索停滯，算法出現(xiàn)早熟收斂現(xiàn)象。

受文獻(xiàn)[10]啟發(fā)，本文將對食物進(jìn)行Gauss變異操作，以提高跳出局部最優(yōu)的能力。而另一方面，我們將對變異結(jié)果采取貪心保留策略，以保證算法有較好的全局收斂性。

在優(yōu)化過程中，如果當(dāng)前最好個體(食物)的適應(yīng)度值連續(xù)smax次迭代沒有得到改善(smax設(shè)置為10)，則對食物執(zhí)行Gauss變異，具體為：

F′i=Fi(1+λξ)

(7)

式中：ξ是服從標(biāo)準(zhǔn)正態(tài)分布的隨機變量，λ=0.5。對Gauss變異的結(jié)果F′采用貪心保留策略，即：

(8)

式中：fit(x)為x的適應(yīng)值。

1.2.4算法偽代碼

綜上所述，ISSA算法偽代碼為如下。

初始化參數(shù)，種群規(guī)模N，維數(shù)n，最大迭代次數(shù)T，在初始解空間中隨機初始化樽海鞘群的位置，進(jìn)行適應(yīng)度評估，排序，記錄當(dāng)前最好個體位置F。

while(t

利用式(2)更新r1

forj= 1 toNdo

ifj≤N/2

利用式(4)更新領(lǐng)導(dǎo)者個體

利用式(5)執(zhí)行精英反向?qū)W習(xí)策略

else

利用式(6)更新追隨者個體

endif

根據(jù)變量的上下界對種群個體進(jìn)行修正

適應(yīng)度評估，更新食物位置

ifs==smax

(s為食物適應(yīng)值連續(xù)沒有改善的次數(shù))

用式(7)～(8)對食物執(zhí)行Gauss變異

endif

endfor

t=t+1

endwhile

returnF

接下來計算ISSA算法的時間復(fù)雜度。

1) 分析算法迭代一次所需要的基本操作。

2) 更新領(lǐng)導(dǎo)者位置，追隨者位置和基于變量的上下界修正樽海鞘個體的位置的復(fù)雜度是O(Nn)；

3) 計算適應(yīng)度值和更新食物位置的復(fù)雜度是O(2N)；

4) 對食物進(jìn)行Gauss變異操作是O(kn)，其中k是變異的次數(shù)；

5) 進(jìn)行精英反向?qū)W習(xí)策略的復(fù)雜度是O(Nn/2)。

則算法迭代一次的復(fù)雜度是:

O(Nn) +O(2N)+O(kn)+O(Nn/2)=O(CNn)

因此該算法的整體復(fù)雜度是O(CNnT)，其中N是種群規(guī)模，n是維數(shù)，T是最大迭代次數(shù)，C是常數(shù)。

2 仿真實驗

2.1 參數(shù)設(shè)置和結(jié)果分析

利用一組經(jīng)典的基準(zhǔn)函數(shù)，包括10個不同的函數(shù)(單峰和多峰函數(shù))，來評價該算法的優(yōu)化性能。基準(zhǔn)函數(shù)的定義及其細(xì)節(jié)見表1。

表1 標(biāo)準(zhǔn)測試函數(shù)Tab.1 Benchmark test functions

為體現(xiàn)本文所提算法的有效性，我們將引入樽海鞘群算法[1]、粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)[11-12]、飛蛾撲火優(yōu)化算法(Moth-Flame Optimization，MFO)[13]以及混沌樽海鞘群算法(Chaotic Salp Swarm Algorithm，CSSA)[2]做對比實驗。

為體現(xiàn)實驗的公平性，我們將設(shè)置相同的實驗參數(shù)：種群規(guī)模為30，最大迭代次數(shù)為500，測試函數(shù)的維數(shù)均設(shè)置為30，領(lǐng)導(dǎo)者個數(shù)設(shè)置為N/2，smax設(shè)置為10。

五種算法在每個測試函數(shù)上均獨立運行30次，并記錄下平均值、標(biāo)準(zhǔn)差、最好值、最差值，實驗結(jié)果見表2。最好的結(jié)果以粗體顯示。

由表2可以得出，ISSA算法的求解精度在以上基準(zhǔn)函數(shù)上都優(yōu)于幾種對比算法，尤其在函數(shù)F3、F7和F9上顯著提高了求解精度，此外，ISSA算法的標(biāo)準(zhǔn)差值相對比較小，這說明該算法具有較強的魯棒性。在函數(shù)F8上CSSA算法的求解精度較低于SSA算法。雖然CSSA算法的尋優(yōu)性能得到了一定的改善，但是效果不是很明顯。在函數(shù)F5上，ISSA算法的最好值沒有明顯地提升，但是，方差、均值、最差值都在一定的程度上有了較大提高。這說明該算法較好地平衡了局部開發(fā)和全局勘探能力。

由圖1可以很直觀地看到，在函數(shù)F5上，雖然ISSA算法、SSA算法和PSO算法求解精度相差不大，但是ISSA算法具有更快的收斂速度。在函數(shù)F7上可以看出，ISSA算法在迭代200次之后收斂到理論最優(yōu)值，明顯優(yōu)于其他幾種對比算法。

因此，本文所提出的ISSA算法與對比算法相比，該算法具有較好的尋優(yōu)性能。

表2 5種算法對10個測試函數(shù)的尋優(yōu)結(jié)果比較Tab.2 Comparison of optimization results of 11 test functions by 5 algorithms

圖1 測試函數(shù)收斂曲線圖Fig.1 Convergence curves of test functions

2.2 改進(jìn)策略的有效性分析

為分析三種改進(jìn)策略的有效性，我們將繼續(xù)使用上述標(biāo)準(zhǔn)測試函數(shù)進(jìn)行實驗。將僅采用Gauss變異策略的改進(jìn)SSA算法記為GSSA算法，將僅采用差分策略的改進(jìn)SSA算法記為DESSA算法，將僅采用精英反向?qū)W習(xí)策略的改進(jìn)SSA算法記為OSSA算法。

為體現(xiàn)實驗的公平性，GSSA算法、DESSA算法、OSSA算法、ISSA算法、SSA算法均采用相同的初始化、相同的參數(shù)設(shè)置，種群規(guī)模為30，最大迭代次數(shù)為500，維數(shù)為30。5種算法在部分測試函數(shù)上的收斂曲線圖見圖2。

圖2 測試函數(shù)收斂曲線圖Fig.2 Test convergence curves of test function

由圖2可以清晰地看出，DESSA算法的收斂效果最為接近ISSA算法，現(xiàn)在我們有較充分的理由說明在標(biāo)準(zhǔn)SSA算法中，追隨者的位置更新缺乏一定的指導(dǎo)信息，嚴(yán)重影響了算法的尋優(yōu)性能；與SSA算法相比，除了在函數(shù)F1和F5上，GSSA算法和OSSA算法的尋優(yōu)效果基本上沒什么改善，在絕大多數(shù)測試函數(shù)上，都具有較高的求解精度和收斂速度。這說明了標(biāo)準(zhǔn)的SSA算法容易陷入局部最優(yōu)、收斂速度較慢等，本文所采用的改進(jìn)策略在一定程度上改善了這種缺陷，提高了算法的尋優(yōu)性能。

3 ISSA在焊接梁問題中的應(yīng)用

利用經(jīng)典工程問題(焊接梁設(shè)計問題)來評價該算法解決實際問題的性能。為體現(xiàn)該算法的有效性，將引入文獻(xiàn)[15-16]做對比實驗。

3.1 焊接梁優(yōu)化問題的數(shù)學(xué)模型

焊接梁問題是一個典型的數(shù)學(xué)規(guī)劃問題，該問題可以描述為：在滿足剪應(yīng)力τ、梁的彎曲應(yīng)力σ、桿上彎曲載荷Pc、梁端撓度δ和邊界條件等約束條件下，尋找最優(yōu)的設(shè)計變量h、l、t和b，使得制造焊接梁的費用最小。四個設(shè)計變量的含義可參照圖3中焊接梁設(shè)計圖。

圖3 焊接梁設(shè)計圖Fig.3 Welded beam design

該設(shè)計問題的數(shù)學(xué)模型如下：

x=[x1,x2,x3,x4]=[h,l,t,b]

minf(x)=1.1047x12x2+0.04811x3x4(14.0+x2)

g7(x)=0.10471x12+

0.04811x3x4(14.0+x2)-5.0≤0

0.1≤x1,x4≤2

0.1≤x2,x3≤10

式中各變量表示為：

(10)

式中：P=6 000，L=14,E=30×106,G=12×106。

3.2 焊接梁優(yōu)化問題求解

罰函數(shù)方法是迄今為止處理約束的最常見和最簡單的方法，通過對目標(biāo)函數(shù)加(或減)懲罰項，將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題[14]。因此本文將采用罰函數(shù)方法來求解該問題，目標(biāo)函數(shù)對應(yīng)的罰函數(shù)為：

(11)

式中：bi=max{0,gi(x)}，1≤i≤7；ki>0為罰函數(shù)系數(shù)。

為保證實驗的公平性，本文的參數(shù)設(shè)置與文獻(xiàn)[15-16]相同。對該問題進(jìn)行30次獨立運行，并提供統(tǒng)計結(jié)果，包括最好值、平均值和最劣值，得到的結(jié)果如下。

表3顯示了ISSA算法和文獻(xiàn)中的兩種算法解焊接梁問題的最優(yōu)解的比較，結(jié)果表明ISSA算法具有更好搜索性能。

表4顯示了本文算法與文獻(xiàn)中的算法30次獨立運行的結(jié)果，實驗表明，本文算法與文獻(xiàn)中的算法相比，有較高的求解精度。

表3 不同算法解焊接梁問題的最優(yōu)解Tab.3 Optimal solution of welded beam problem by different algorithms

表4 不同算法求焊接梁問題f(x)的統(tǒng)計數(shù)據(jù)Tab.4 Statistical data of welded beam problem solved by different algorithms

4 結(jié) 語

本文在基本SSA算法的基礎(chǔ)上提出了一種ISSA算法，在該算法中引入精英反向?qū)W習(xí)策略以更好地平衡算法的勘探和開發(fā)能力；為增大追隨者搜索范圍，引入差分策略來更新追隨者位置；最后，在搜索過程中對食物位置進(jìn)行Gauss變異以提高跳出局部最優(yōu)的能力，為算法進(jìn)行全局搜索奠定基礎(chǔ)。通過10個經(jīng)典的無約束基準(zhǔn)函數(shù)，對ISSA算法的性能進(jìn)行了評價。實驗結(jié)果表明，ISSA算法的性能優(yōu)于文獻(xiàn)中其他算法。選取了1個工程優(yōu)化問題，驗證了ISSA算法在解決實際約束工程問題中的性能。未來的研究重點應(yīng)該是將ISSA算法擴展到解決多目標(biāo)無約束優(yōu)化和約束優(yōu)化問題以及其他實際應(yīng)用中。