基于指數(shù)慣性權(quán)重和自適應(yīng)變異的樽海鞘算法

蔡藝君，賀興時(shí)，楊新社

(1.西安工程大學(xué) 理學(xué)院，陜西 西安 710048；2.密德薩斯大學(xué) 科學(xué)與技術(shù)學(xué)院，英國(guó) 倫敦 NW4 4BT)

0 引 言

在經(jīng)濟(jì)社會(huì)和自然科學(xué)等領(lǐng)域中都存在復(fù)雜優(yōu)化問(wèn)題，而傳統(tǒng)的優(yōu)化方法如牛頓法、共軛梯度法等在解決這些問(wèn)題時(shí)存在一定局限性。為此，科研工作者通過(guò)模擬生物群體行為設(shè)計(jì)了大量群智能算法[1],如粒子群算法[2]、蟻群算法[3]、蝙蝠算法[4]、布谷鳥(niǎo)算法[5]等。這類算法在過(guò)去的二三十年里得到了迅速發(fā)展，并且已經(jīng)在數(shù)據(jù)挖掘、工程技術(shù)、能源、網(wǎng)絡(luò)、經(jīng)濟(jì)、醫(yī)學(xué)等多個(gè)領(lǐng)域得到了廣泛應(yīng)用。

樽海鞘是一種類似水母的海洋生物，它們通常首尾相連形成樽海鞘鏈在海洋中移動(dòng)和覓食。受此啟發(fā)，MIRJALILI等提出了樽海鞘算法(salp swarm algorithm，SSA)[6]。相比于其他群智能算法，該算法具有模型簡(jiǎn)單、參數(shù)少、易實(shí)現(xiàn)等優(yōu)點(diǎn)，自提出以來(lái)受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，目前已被成功應(yīng)用在特征選擇[7]、圖像處理[8]、混合動(dòng)力系統(tǒng)[9]、目標(biāo)分類[10]等領(lǐng)域中。

雖然SSA對(duì)大多數(shù)優(yōu)化問(wèn)題具有很強(qiáng)的求解能力，但在解高維復(fù)雜函數(shù)優(yōu)化問(wèn)題時(shí)存在收斂速度慢、尋優(yōu)精度低、易陷入局部最優(yōu)的缺點(diǎn)。為此，許多科研工作者針對(duì)該算法的不足做了相應(yīng)改進(jìn)。文獻(xiàn)[11]提出一種基于混沌的SSA，利用混沌映射產(chǎn)生的混沌數(shù)代替原有的隨機(jī)數(shù)，在一定程度上解決了算法易陷入局部最優(yōu)、收斂速度慢的缺點(diǎn)，并將其應(yīng)用于特征選擇問(wèn)題；文獻(xiàn)[12]提出了一種增強(qiáng)型的SSA，并將其應(yīng)用于變速風(fēng)力發(fā)電機(jī)；文獻(xiàn)[13]在SSA領(lǐng)導(dǎo)者位置更新公式中引入萊維飛行策略，提升了算法的全局搜索能力和收斂速度；文獻(xiàn)[14]提出一種帶交叉算子的二進(jìn)制，以SSA增強(qiáng)算法的全局搜索能力；文獻(xiàn)[15]提出一種集成隨機(jī)慣性權(quán)重和差分變異操作的SSA，提高了算法收斂速度和精度。

上述改進(jìn)的SSA在不同方面、不同程度上彌補(bǔ)了該算法的缺點(diǎn)，但是從實(shí)驗(yàn)結(jié)果看，改進(jìn)算法的收斂速度、精度、搜索能力和穩(wěn)定性等仍有待提高。因此，為了使SSA具有更高的收斂精度，更快的收斂速度以及更好的全局和局部搜索能力，本文提出一種基于指數(shù)慣性權(quán)重和自適應(yīng)t分布變異的改進(jìn)樽海鞘算法(improved salp swarm algorithm, ISSA)。

1 樽海鞘算法

在樽海鞘算法中，樽海鞘鏈由位于鏈前端的領(lǐng)導(dǎo)者及其跟隨者組成。該算法流程[16]如下：

(1)

2) 根據(jù)目標(biāo)函數(shù)計(jì)算N個(gè)樽海鞘個(gè)體的適應(yīng)度值。

3) 選定食物源的位置。對(duì)樽海鞘的適應(yīng)度值排序，最優(yōu)適應(yīng)度值對(duì)應(yīng)的樽海鞘位置即為食物源的位置。

4) 選定領(lǐng)導(dǎo)者和跟隨者。選定食物位置后，群體中剩余N-1個(gè)樽海鞘，按照樽海鞘個(gè)體的排序，將排在前端的樽海鞘視為領(lǐng)導(dǎo)者，其余樽海鞘視為跟隨者。

5) 更新樽海鞘領(lǐng)導(dǎo)者的位置。

(2)

c1=2exp(-(4l/L)2)

(3)

式中:l為當(dāng)前迭代次數(shù);L為最大迭代次數(shù)。

6) 更新跟隨者的位置。

(4)

7) 計(jì)算更新后的個(gè)體的適應(yīng)度。將更新后每個(gè)樽海鞘個(gè)體的適應(yīng)度值與當(dāng)前食物的適應(yīng)度值進(jìn)行比較，若更新后樽海鞘的適應(yīng)度值優(yōu)于食物，則以適應(yīng)度值更優(yōu)的樽海鞘位置作為新的食物源位置。

8) 判斷是否滿足終止條件。若是，則輸出結(jié)果;否則,轉(zhuǎn)到4)繼續(xù)迭代。

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

2.1 跟隨者位置更新公式改進(jìn)

原算法中跟隨者根據(jù)自己的歷史位置和前一個(gè)個(gè)體的歷史位置更新自己的位置，所以會(huì)出現(xiàn)盲目跟從和易陷入局部最優(yōu)的問(wèn)題。為了增強(qiáng)對(duì)局部搜索能力的開(kāi)拓，改善樽海鞘盲目跟從問(wèn)題，將上一代前一個(gè)體的位置由上一代最優(yōu)位置(即食物源的位置)代替，促使追隨者們向最優(yōu)位置移動(dòng)以達(dá)到更好的尋優(yōu)目的。改進(jìn)后的跟隨者位置更新公式定義如下：

(5)

2.2 指數(shù)遞減慣性權(quán)重

平衡種群的全局和局部搜索能力在一定程度上會(huì)影響算法的尋優(yōu)性能,而慣性權(quán)重策略可以提升算法的搜索能力，平衡局部搜索和全局搜索之間的關(guān)系。在粒子群優(yōu)化算法中，文獻(xiàn)[17]提出慣性權(quán)重能克服算法陷入局部最優(yōu)，加快收斂速度。并指出如果慣性權(quán)重較大，粒子具有較強(qiáng)的全局搜索能力，但搜索能力較差效率低；反之，慣性權(quán)重小，粒子具有較強(qiáng)的局部搜索能力，但容易陷入局部最優(yōu)?；谝陨嫌^點(diǎn)，文獻(xiàn)[18]進(jìn)一步提出線性遞減的慣性權(quán)重有效地平衡全局和局部搜索，使得粒子早期具有很強(qiáng)的全局搜索能力，后期具有較強(qiáng)的局部搜索能力，能搜索到相對(duì)精確的結(jié)果。受此啟發(fā)，本文在改進(jìn)后的跟隨者位置更新公式中引入指數(shù)遞減慣性權(quán)重w(l)。w(l)的更新公式及加入權(quán)重后追隨者位置更新公式如下：

(6)

(7)

式中:wmax和wmin分別表示權(quán)重因子w(l)的最大值和最小值，分別取0.8和0.2;l為當(dāng)前迭代次數(shù)，L為最大迭代次數(shù)。在初始迭代階段，權(quán)重因子較大，搜索范圍也大，保證了全局搜索能力;隨著迭代次數(shù)增加，權(quán)重因子逐漸減小，搜索范圍也減小，使局部搜索能力逐漸增強(qiáng)，搜索結(jié)果也越來(lái)越精確。同時(shí)，隨機(jī)擾動(dòng)項(xiàng)rand(·)wmin增加了多種可能性，使權(quán)重因子更靈活，防止算法陷入局部極值而出現(xiàn)迭代停滯的可能。

2.3 自適應(yīng)t分布變異

在樽海鞘個(gè)體位置更新后引入自適應(yīng)t分布變異策略，對(duì)更新后的位置進(jìn)行擾動(dòng)，增加種群多樣性，避免陷入局部最優(yōu)。設(shè)置自適應(yīng)因子α[19]控制變異程度的大小，定義如下：

(8)

式中:L為最大迭代次數(shù);α的值在1到0間遞減，隨迭代次數(shù)的增加控制變異的程度由大到小。自適應(yīng)t分布變異策略具體如下：

(9)

2.4 ISSA算法流程

1) 隨機(jī)初始化N×d大小的種群。

2) 根據(jù)目標(biāo)函數(shù)計(jì)算N個(gè)樽海鞘的適應(yīng)度值。

3) 選定食物源的位置。對(duì)樽海鞘的適應(yīng)度值排序，最優(yōu)適應(yīng)度值對(duì)應(yīng)的樽海鞘位置即為食物源的位置。

4) 選定領(lǐng)導(dǎo)者和跟隨者。選定食物位置后，群體中剩余N-1個(gè)樽海鞘，按照樽海鞘個(gè)體的排序，將排在前端的樽海鞘視為領(lǐng)導(dǎo)者，其余樽海鞘視為跟隨者。

5) 按照式(2)和式(7)更新領(lǐng)導(dǎo)者和跟隨者的位置。

6) 通過(guò)設(shè)置的概率cr與隨機(jī)數(shù)rand(·)進(jìn)行比較：如果rand(·)

7) 組合舊種群和從變異中獲得的新種群，計(jì)算每個(gè)樽海鞘個(gè)體的適應(yīng)度值,并與當(dāng)前食物的適應(yīng)度值進(jìn)行比較。若更新后樽海鞘的適應(yīng)度值優(yōu)于食物，則以適應(yīng)度值更優(yōu)的樽海鞘位置作為新的食物的位置。

8) 判斷是否滿足終止條件。若是，則輸出結(jié)果；否則，轉(zhuǎn)到4)繼續(xù)迭代。

3 仿真實(shí)驗(yàn)

為了證明ISSA的尋優(yōu)性能，選取了8個(gè)不同難度的函數(shù)，分別測(cè)試改進(jìn)算法(ISSA)的收斂精度、收斂速度，同時(shí)與帶衰減因子的樽海鞘算法(RSSA)[20]、基本樽海鞘算法(SSA)、基本蝙蝠算法(BA)、基本花授粉算法(FPA)等4種算法進(jìn)行比較，驗(yàn)證ISSA收斂速度和精度的優(yōu)劣。

3.1 測(cè)試函數(shù)

選取了表1所示的最優(yōu)值均為0的8個(gè)測(cè)試函數(shù)。f1(x)～f6(x)為高維函數(shù)，f7(x)～f8(x)為二維函數(shù)。其中高維多峰函數(shù)f1(x)～f3(x)有較多局部極值點(diǎn)，主要用于測(cè)試算法跳出局部最優(yōu)的能力；高維單峰函數(shù)f4(x)～f6(x)只有一個(gè)全局最小值，主要為了測(cè)試算法的收斂性能。

表 1 測(cè)試函數(shù)

3.2 測(cè)試環(huán)境及算法參數(shù)

實(shí)驗(yàn)環(huán)境為：CPU為i5-5257U 2.70 GHz，運(yùn)行內(nèi)存4 GB，操作系統(tǒng)Windows10，編程環(huán)境Matlab R2019a。設(shè)置ISSA算法的變異概率為0.5，BA算法聲波頻度為0.5, FPA算法的轉(zhuǎn)換概率為0.8。

3.3 求解精度比較

表2～9是5種算法對(duì)于不同測(cè)試函數(shù)f1(x)～f8(x)的求解精度對(duì)比。分別在相同的測(cè)試環(huán)境下運(yùn)行了30次，種群大小均為30，最大迭代次數(shù)為1 000。

表 2 f1(x)函數(shù)仿真結(jié)果

表 3 f2(x)函數(shù)仿真結(jié)果

表 4 f3(x)函數(shù)仿真結(jié)果

表 5 f4(x)函數(shù)仿真結(jié)果

表 6 f5(x)函數(shù)仿真結(jié)果

表 7 f6(x)函數(shù)仿真結(jié)果

表 8 f7(x)函數(shù)仿真結(jié)果

表 9 f8(x)函數(shù)仿真結(jié)果

表2～7是5種算法對(duì)高維測(cè)試函數(shù)f1(x)～f6(x)的方差、最優(yōu)值、平均值和最差值仿真結(jié)果；表8～9是5種算法對(duì)低維(維數(shù)為2)測(cè)試函數(shù)f7(x)及f8(x)的方差、最優(yōu)值、平均值和最差值仿真結(jié)果。f1(x)～f3(x)為多峰函數(shù)。由表2～4可知，除f1(x) 外，ISSA在不同維度下均表現(xiàn)出良好的尋優(yōu)能力，而其他算法都無(wú)法求得全局最優(yōu)解。f4(x)～f6(x)為單峰函數(shù)，在定義域內(nèi)只有一個(gè)極值點(diǎn)。從表5～7可以看出，ISSA也仍能取到全局最優(yōu)解，表現(xiàn)出良好的尋優(yōu)性能?？梢?jiàn)，不論是單峰函數(shù)還是復(fù)雜多峰函數(shù)，ISSA均取到了全局最優(yōu)值，并且隨著維度的增加，仍能保持得出最優(yōu)結(jié)果，而其他4個(gè)算法在迭代后期都陷入了局部最優(yōu)，并隨著維度的提高，求解精度逐漸下降。對(duì)于f1(x)，ISSA雖然陷入了局部最優(yōu)8.882×10-16，但相較于其他4個(gè)算法仍提高了收斂精度，并隨著維度的提高，其他4個(gè)算法求解精度都在明顯下降時(shí)，ISSA仍能表現(xiàn)出良好的穩(wěn)定性。對(duì)于低維函數(shù)，由表8和9可以看出，ISSA仍能收斂到全局最優(yōu)，表明ISSA在低維測(cè)試函數(shù)條件下仍然具有良好性能。

3.4 算法收斂性比較

圖1是8個(gè)函數(shù)的速度收斂曲線圖，直觀地反映出5種算法的收斂速度和精度。其中，圖1(a)～(f)是高維單峰和多峰函數(shù)(維數(shù)為10)的速度收斂圖，從圖1(g)～(h)是低維函數(shù)(維數(shù)為2)的速度收斂圖。從圖1可以看出：ISSA表現(xiàn)出了優(yōu)越的性能，在收斂速度上優(yōu)于SSA、FPA、BA和RSSA。對(duì)于每個(gè)測(cè)試函數(shù)，ISSA在100代之內(nèi)均可以收斂到全局最優(yōu)，而其他算法則需要迭代更多次才能收斂，甚至不能收斂到全局最優(yōu)值。對(duì)比這5種算法的收斂曲線，無(wú)論是高維、低維還是單峰、多峰函數(shù)，ISSA都具有更好的尋優(yōu)能力和更快的收斂速度。

(a) f1(x)

(b) f2(x)

(c) f3(x)

(d) f4(x)

(e) f5(x)

(f) f6(x)

(g) f7(x)

(h) f8(x)圖 1 測(cè)試函數(shù)收斂曲線Fig.1 Convergence curve of test functions

4 工程應(yīng)用

4.1 管柱設(shè)計(jì)問(wèn)題

該問(wèn)題求解在約束條件g1和g2下的管柱直徑d及厚度t，使管柱成本最小，表示為

minf=9.8dt+2d

式中：2 cm≤d≤14 cm，0.2 cm≤t≤0.8 cm；管柱負(fù)載p=2 500 N；管柱材料應(yīng)力σy=500 N/cm2；彈性模量E=0.85×106N/cm2；管柱高度L=250 cm。ISSA對(duì)管柱設(shè)計(jì)問(wèn)題的求解結(jié)果，與文獻(xiàn)[21]和文獻(xiàn)[22]對(duì)該問(wèn)題的求解結(jié)果對(duì)比，如表10所示。

表 10 管柱設(shè)計(jì)問(wèn)題最佳方案結(jié)果對(duì)比

從表10可以看出,ISSA在計(jì)算管柱設(shè)計(jì)問(wèn)題時(shí)能得到較優(yōu)結(jié)果。

4.2 三桿平面桁架問(wèn)題

該問(wèn)題求解在約束條件g1、g2和g3下,三桿的橫截面積x1、x2和x3并使其體積最小，其中x1=x3，表示為

式中：橫截面0≤x1≤1 cm2，0≤x2≤1 cm2；三桿長(zhǎng)度均為l=100 cm；節(jié)點(diǎn)處受力p=2 kN；桿的應(yīng)力度σ=2 kN/cm2。

ISSA對(duì)三桿平面桁架問(wèn)題的求解結(jié)果與文獻(xiàn)[23]中Park、Yang和Ray對(duì)該問(wèn)題的求解結(jié)果對(duì)比,如表11所示。

表 11 三桿平面桁架問(wèn)題最佳方案結(jié)果對(duì)比

從表11可以看出，ISSA在計(jì)算三桿平面桁架問(wèn)題時(shí)也能得到較優(yōu)結(jié)果。

5 結(jié) 語(yǔ)

本文針對(duì)樽海鞘算法的不足進(jìn)行了改進(jìn)。通過(guò)最優(yōu)位置替換個(gè)體位置，改進(jìn)了跟隨者位置更新公式，提升了算法尋優(yōu)能力；為了增強(qiáng)算法的全局搜索和局部搜索能力，將指數(shù)遞減慣性權(quán)重加入到改進(jìn)后的跟隨者位置更新公式中，提升了收斂精度；引入自適應(yīng)t分布變異，避免算法陷入局部最優(yōu)，加快了其收斂速度。通過(guò)仿真實(shí)驗(yàn)對(duì)比并在工程設(shè)計(jì)問(wèn)題中應(yīng)用，驗(yàn)證了改進(jìn)算法與其他算法相比的優(yōu)越性。下一步將研究改進(jìn)算法在組合優(yōu)化問(wèn)題中的應(yīng)用。