湯安迪, 韓 統(tǒng), 徐登武, 周 歡, 謝 磊

(1. 空軍工程大學(xué)航空工程學(xué)院, 陜西 西安 710038; 2. 空軍工程大學(xué)研究生院, 陜西 西安 710038;3. 中國人民解放軍94855部隊, 浙江 衢州 324000)

0 引 言

隨著社會發(fā)展和科技進(jìn)步,各類實際工程問題的復(fù)雜度越來越高。傳統(tǒng)的基于梯度的數(shù)值優(yōu)化算法在面對問題規(guī)模不斷擴(kuò)大的實際工程優(yōu)化問題時,難以有效求解,而智能優(yōu)化算法不依賴具體問題特征和梯度信息,具有簡單高效的結(jié)構(gòu),受到越來越多學(xué)者的關(guān)注和研究。

智能優(yōu)化算法通常分為3類:受自然進(jìn)化機(jī)制啟發(fā)的進(jìn)化,如遺傳算法(genetic algorithm,GA)、差分進(jìn)化(differential evolution,DE)算法等;基于物理概念建立的算法,如模擬退火(simulated annealing,SA)算法、重力搜索算法(gravity search algorithm,GSA)、核反應(yīng)(nuclear reaction optimization,NRO)算法等;基于群體行為的群智能優(yōu)化算法,如灰狼優(yōu)化(grey wolf optimizer,GWO)算法、人工蜂群(artificial bee colony,ABC)算法、鯨魚優(yōu)化算法(whale optimization algorithm,WOA)等。無免費(fèi)午餐理論表明,沒有任何一種算法能夠較好地解決所有優(yōu)化問題,因此不斷有學(xué)者提出新的智能優(yōu)化算法來求解復(fù)雜的全局優(yōu)化問題。

樽海鞘群算法(salp swarm algorithm,SSA)是Mirjalili等在2017年新提出的基于種群的智能優(yōu)化算法,該算法模擬了樽海鞘群以鏈?zhǔn)降姆椒ㄟM(jìn)行捕食的過程,具有參數(shù)少、結(jié)構(gòu)簡單的優(yōu)點。文獻(xiàn)[10]表明,SSA是一種在尋優(yōu)性能上優(yōu)于粒子群(particle swarm optimization, PSO)算法、GSA、GA和異花授粉算法等新型群智能優(yōu)化算法,因此已被廣泛應(yīng)用于各種實際工程優(yōu)化問題。

然而,同其他群智能優(yōu)化算法類似,也存在迭代后期種群多樣性減少、易于陷入局部最優(yōu)的不足,從而限制了算法的開發(fā)和探索能力。為了進(jìn)一步提高SSA的性能,國內(nèi)外學(xué)者對原始SSA做出了相應(yīng)改進(jìn)。文獻(xiàn)[14]將PSO算法的速度階段公式融入到SSA中,從而避免了算法的早熟收斂。文獻(xiàn)[15]使用一種集合/復(fù)合突變策略,來提高算法的開發(fā)和探索能力。文獻(xiàn)[16]使用混沌映射來控制SSA領(lǐng)導(dǎo)者位置公式中的參數(shù),以此增強(qiáng)算法尋優(yōu)能力。文獻(xiàn)[17]使用正態(tài)云模型對SSA追隨者位置進(jìn)行更新,增強(qiáng)種群多樣性。文獻(xiàn)[18]使用慣性權(quán)重和數(shù)量自適應(yīng)調(diào)整策略,增強(qiáng)算法前期的探索和后期的開發(fā)能力。

為提高原始SSA的尋優(yōu)能力,本文提出了一種使用高斯分布估計策略的SSA(SSA using Gaussian distribution estimation strategy, GDESSA)。首先在領(lǐng)導(dǎo)者位置更新時引入精英池策略,每個領(lǐng)導(dǎo)者在更新位置時隨機(jī)從精英池中選擇食物源,從而增強(qiáng)種群多樣性,避免算法陷入局部最優(yōu);其次對追隨者位置更新公式進(jìn)行修改,引入高斯分布估計策略,通過擬合優(yōu)勢種群信息,更好地引導(dǎo)追隨者進(jìn)化方向,從而提高算法收斂效率,增強(qiáng)算法尋優(yōu)性能。通過求解CEC2017測試函數(shù),并與其他算法進(jìn)行對比,驗證了本文提出的改進(jìn)策略的有效性和改進(jìn)算法的優(yōu)越性。

1 原始SSA

樽海鞘群體在進(jìn)行覓食時通常分為兩個部分:領(lǐng)導(dǎo)者和追隨者。領(lǐng)導(dǎo)者位于鏈的前端,負(fù)責(zé)尋找食物源進(jìn)行引導(dǎo),追隨者則跟隨先前的個體,群體通過相互協(xié)作找到食物源,具體數(shù)學(xué)模型介紹如下。

同其他群智能優(yōu)化算法類似,初始化階段盡可能均勻分布在搜索空間,隨機(jī)初始化位置公式為

(1)=·(-)+

(1)

式中:為服從0到1均勻分布的隨機(jī)向量;和分別表示搜索空間的上下界。

樽海鞘群體根據(jù)適應(yīng)度值由低到高排序(以最小化問題為例),適應(yīng)度值最小個體作為食物源,前一半種群作為領(lǐng)導(dǎo)者,后一半種群作為追隨者,分別進(jìn)行位置更新。領(lǐng)導(dǎo)者位置更新公式描述如下:

(2)

(3)

追隨者根據(jù)鏈?zhǔn)揭?guī)則,順次跟隨移動,其數(shù)學(xué)模型描述如下:

(4)

在對所有個體進(jìn)行位置更新后,會進(jìn)行邊界處理,超出邊界的個體會在搜索空間中隨機(jī)生成,位置更新如下:

(5)

2 改進(jìn)SSA

為了增強(qiáng)領(lǐng)導(dǎo)者的多樣性,在其位置更新公式引入精英池策略,然后使用高斯分布估計策略對追隨者位置更新公式進(jìn)行改進(jìn),充分利用優(yōu)勢種群信息,引導(dǎo)進(jìn)化方向,從而提升算法尋優(yōu)性能。

2.1 精英池策略

領(lǐng)導(dǎo)者在進(jìn)行位置更新時,總是使用當(dāng)前最優(yōu)個體作為食物源,這就導(dǎo)致了如果食物源已陷入局部最優(yōu),那么鏈?zhǔn)揭?guī)則會引導(dǎo)后續(xù)所有個體靠近局部最優(yōu)個體,從而導(dǎo)致算法早熟收斂。為了增強(qiáng)種群多樣性,GWO算法提出了等級制度,將當(dāng)前最優(yōu)的前3個個體算術(shù)平均的位置作為最優(yōu)位置,以此避免使用一個最優(yōu)個體引導(dǎo)帶來的不足。為增強(qiáng)算法的種群個體多樣性,本文提出一種精英池策略,在精英池中存儲當(dāng)前最優(yōu)的前3個個體和領(lǐng)導(dǎo)者群體的加權(quán)平均位置,如圖1所示,3個最優(yōu)個體能幫助領(lǐng)導(dǎo)者進(jìn)行探索,而加權(quán)平均位置代表整個優(yōu)勢種群的進(jìn)化趨勢,有利于算法進(jìn)行開發(fā)。每個領(lǐng)導(dǎo)者在進(jìn)行位置更新時會從精英池隨機(jī)選擇一個個體作為食物源,一定程度上避免了僅有一個食物源導(dǎo)致的陷入局部最優(yōu)的不足。精英池策略描述如下:

(6)

(7)

(8)

圖1 精英池策略示意圖Fig.1 Elite pool strategy diagram

因此,調(diào)整后的領(lǐng)導(dǎo)者位置更新公式如下:

(9)

式中:為精英池中隨機(jī)選擇的個體。

2.2 高斯分布估計策略

對原始SSA追隨者位置公式分析可知,每個追隨者僅依靠自身和種群鏈上相鄰個體信息進(jìn)行位置更新,缺乏和其他個體的信息交流,當(dāng)領(lǐng)導(dǎo)者陷入局部最優(yōu)時,追隨者會由于“鏈?zhǔn)叫?yīng)”,接連陷入局部最優(yōu),這在一定程度導(dǎo)致算法出現(xiàn)早熟收斂。為增強(qiáng)算法的尋優(yōu)能力,本文使用高斯分布估計策略對追隨者位置公式進(jìn)行更新,公式如下:

(10)

(11)

(12)

式中:為優(yōu)勢種群的加權(quán)協(xié)方差矩陣。如圖2所示,通過利用高斯分布估計策略來調(diào)整搜索方向,從而更好地引導(dǎo)種群進(jìn)化,以此增強(qiáng)算法的開發(fā)能力,同時公式中引入了精英池中隨機(jī)食物源,使得追隨者具有不同的位移均值,這也增加種群多樣性,提高了算法的探索能力。

圖2 修改后的追隨者位置示意圖Fig.2 Modified follower location diagram

為了確保GDESSA收斂,使用優(yōu)勝劣汰機(jī)制來保留優(yōu)勢個體,數(shù)學(xué)模型如下:

(13)

2.3 GDESSA的實現(xiàn)流程

通過使用精英池策略和高斯分布估計策略,對領(lǐng)導(dǎo)者和追隨者位置更新公式進(jìn)行調(diào)整,得到了GDESSA。GDESSA的實現(xiàn)流程如下所示:

設(shè)定種群數(shù)NP、最大迭代次數(shù),維數(shù)、上下邊界和;

根據(jù)式(1)初始化樽海鞘群個體位置,計算適應(yīng)度值;

根據(jù)式(6)、式(7)生成精英池,根據(jù)式(9)更新領(lǐng)導(dǎo)者位置;

根據(jù)式(10)更新追隨者位置;

計算更新后的個體適應(yīng)度值,根據(jù)式(13)生成新的樽海鞘群;

判斷當(dāng)前迭代次數(shù)是否達(dá)到最大,若達(dá)到,結(jié)束迭代;否則返回執(zhí)行步驟3;

輸出最優(yōu)個體適應(yīng)度值及其位置。

GDESSA的偽代碼如算法1所示。

算法 1 GDESSA算法初始化 種群數(shù)NP、最大迭代次數(shù)tmax、維數(shù)D、上下邊界lb和ub、生成初始種群X(1);計算樽海鞘群個體適應(yīng)度值f(Xi(t));While (t

3 仿真實驗和結(jié)果分析

為全面驗證GDESSA算法的優(yōu)越性能,本文使用IEEE CEC2017單目標(biāo)測試函數(shù)對算法進(jìn)行性能測試。CEC2017測試集包括28個測試函數(shù),其中F1屬于單峰測試函數(shù),用于檢驗算法的收斂精度;F2～F8屬于多峰測試函數(shù),主要用于測試算法跳出局部最優(yōu)的能力;F9～F18和F18～F28分別為混合函數(shù)和合成函數(shù),這兩類函數(shù)組成復(fù)雜,可用于測試算法解決現(xiàn)實世界復(fù)雜優(yōu)化問題。為保證公平,所有算法NP=500,=30,=600。所有算法獨立運(yùn)行51次記錄實驗結(jié)果。仿真實驗環(huán)境為AMD R7 4800U(1.80 GHz)處理器和16GB內(nèi)存,程序在Matlab 2016b平臺上運(yùn)行。

3.1 GDESSA改進(jìn)策略比較分析

為驗證本文所提改進(jìn)策略的有效性,將只使用精英池策略的SSA-1、只使用高斯分布估計策略的SSA-2和GDESSA以及基本SSA進(jìn)行對比,仿真結(jié)果如表1所示。其中誤差均值用于評估算法的優(yōu)化性能,計算耗時則表示各算法求解測試函數(shù)的時間成本,同時根據(jù)誤差均值和計算耗時分別進(jìn)行排名,最優(yōu)值加粗顯示,最后一欄為各算法的平均排名。

表1 不同改進(jìn)策略對比結(jié)果

從表1可以得知,具有完整改進(jìn)策略的GDESSA在尋優(yōu)精度上排名第一,在計算耗時上則排名第二,而基本SSA則在尋優(yōu)精度上排名最后,僅在計算耗時上優(yōu)于僅使用精英池策略的SSA-1。具體分析來說,對于單峰測試函數(shù)F1,可以得知SSA優(yōu)于SSA-1,這是由于引入精英池策略,使得領(lǐng)導(dǎo)者在進(jìn)行位置更新時不再只使用全局最優(yōu)個體,而是從精英池隨機(jī)選擇,這主要提高了種群多樣性,增強(qiáng)算法探索能力,但在一定程度上會削弱算法在單峰測試函數(shù)上的開發(fā)能力。對于多峰測試函數(shù)F2～F8,SSA僅在F2優(yōu)于SSA-1,在其余多峰測試函數(shù)中均表現(xiàn)較差,而使用高斯分布估計策略的SSA-2和GDESSA則排在前兩位,這說明追隨者位置使用優(yōu)勢群體信息進(jìn)行更新,避免了只使用鏈?zhǔn)较噜弬€體帶來的不足,通過擬合優(yōu)勢群體進(jìn)化方向,更好地引導(dǎo)追隨者進(jìn)行追隨,同時精英池策略能夠增強(qiáng)算法種群多樣性,避免算法陷入局部最優(yōu)。對于混合和合成函數(shù)F11～F28,SSA僅在F20和F23分別排在第二和第三,而在整體上表現(xiàn)仍不及SSA-1、SSA-2和GDESSA。在4個算法中,GDESSA均值平均排名為1.25,剩余排序分別為SSA-2、SSA-1和SSA,這說明了改進(jìn)策略在提升算法尋優(yōu)性能上的顯著作用,融合所有改進(jìn)策略的GDESSA尋優(yōu)性能最佳。另一方面,分析得知,使用精英池策略的SSA-1計算耗時平均排名為4,這說明生成精英池和選擇精英池過程增加了計算成本,這從GDESSA計算耗時高于SSA-2也可以看出,僅使用高斯分布估計策略的SSA-2在所有算法中耗時均最少,而包含所有改進(jìn)策略的GDESSA耗時均多于SSA-2,但兩者差異不大,使用精英池策略帶來的計算成本增加,給GDESSA帶來的提高也是明顯的,由“無免費(fèi)午餐理論”可知,因性能提高帶來的計算成本增加是可以接受的,所以本文提出的GDESSA能夠顯著提升SSA性能。為直觀顯示各算法在測試函數(shù)中的表現(xiàn),根據(jù)表1中的排名分別繪制雷達(dá)圖,如圖3所示,圖中連接曲線所圍面積越小,表明該算法性能越好。從圖中可以得知,GDESSA在均值雷達(dá)圖中所圍面積最小,而在耗時雷達(dá)圖上所圍面積大于SSA-2。

圖3 均值與耗時排名雷達(dá)圖Fig.3 Mean and elapsed time ranking radar chart

3.2 GDESSA與其他算法比較分析

為進(jìn)一步驗證GDESSA的優(yōu)越性,選取3種改進(jìn)群智能優(yōu)化算法(混合螢火蟲和粒子群優(yōu)化(hybrid firefly and particle swarm optimization, HFPSO)、混合高斯分布估計策略的灰狼優(yōu)化算法(a modified GWO integrated with the Gaussian estimation of distribution strategy, GEDGWO)、病毒群搜索(virus colony search, VCS))和3種最新的群智能優(yōu)化算法(海洋捕食者算法(marine predators algorithm, MPA)、黏液霉算法(llime mould algorithm, SMA)、哈里斯鷹優(yōu)化(Harris hawks optimization, HHO)算法)同GDESSA進(jìn)行比較。HFPSO是一種混合螢火蟲算法的改進(jìn)粒子群算法。GEDGWO是一種融合了分布估計算法的GWO算法變體。VCS是一種結(jié)合DE和CMA-ES的融合算法。這3種改進(jìn)算法均在各自文獻(xiàn)證明了其具有較好的性能。而MPA、SMA和HHO均是近年來最新提出的表現(xiàn)較好的群智能優(yōu)化算法,已被運(yùn)用在不同的學(xué)科和工程領(lǐng)域。因此,使用這些算法進(jìn)行對比能夠驗證本文提出算法是否在性能上有提升。為保證公平,各算法參數(shù)設(shè)置參考原文獻(xiàn),如表2所示。將所有算法獨立運(yùn)行51次,記錄均值和標(biāo)準(zhǔn)差,實驗結(jié)果如表3所示。

表2 算法參數(shù)設(shè)置

表3 CEC2017 30D測試中7種算法的結(jié)果統(tǒng)計

續(xù)表3

由表3可知,GDESSA在單峰測試函數(shù)F1上表現(xiàn)最好,表明了GDESSA在求解病態(tài)函數(shù)的優(yōu)勢,再一次驗證了改進(jìn)策略能有效提高算法的開發(fā)能力。對于多峰測試函數(shù)F2～F8,GDESSA在其中5個函數(shù)上(F3～F7)取得了更好的解,這表明改進(jìn)策略能夠很好地增強(qiáng)種群多樣性,避免局部最優(yōu)。HFPSO在F2上排名第一,MPA則在F8上取得了最好的成績。對于混合和合成函數(shù)F9～F28,各個算法各有優(yōu)劣。GDESSA在其中10個測試函數(shù)(F10,F11,F13～F18,F21,F22)上排名第一,并且在7個測試函數(shù)(F9、F12、F19、F24、F26～F28)中排名第二,GEDGWO在6個測試函數(shù)(F9,F12,F20,F26～F28)上取得令人滿意的結(jié)果,MPA則在F19和F24中表現(xiàn)最佳,HFPSO和VCS分別在F25和F23上獲得最好的結(jié)果?？傮w來說,GDESSA在28個測試函數(shù)中的16個測試函數(shù)上排名第一,并在8個測試函數(shù)中排名第二,表明了本文提出的改進(jìn)策略能很好地提升算法的開發(fā)和探索能力。

為分析改進(jìn)算法所求解的分布特性,根據(jù)各算法獨立求解測試函數(shù)51次的結(jié)果繪制箱式圖,如圖4所示。對于每種算法,每個框的中心標(biāo)記表示51次求解函數(shù)結(jié)果的中位數(shù),框的底部和頂部邊緣表示一等分點和三等分點,符號“+”表示不在箱子內(nèi)的壞值。受篇幅所限,本文僅列出其中10個測試函數(shù)(F1、F3、F5、F10、F14、F16、F18、F21、F22、F28)的箱式圖。通過比較箱式圖的中位數(shù)和壞值,可以得知,GDESSA中位數(shù)更小,表明GDESSA解的質(zhì)量更優(yōu);而壞值較少,則說明GDESSA所得解的分布更加集中,有著更好的穩(wěn)定性。

圖4 部分測試函數(shù)箱式圖Fig.4 Part of the test function box diagram

收斂速度和收斂精度也是衡量算法性能的重要指標(biāo),圖5展示了7種算法求解CEC2017測試集的平均誤差收斂曲線圖。受篇幅所限,本文選取10個測試函數(shù)(F1、F4、F5、F10、F14、F16、F18、F21、F22、F28)的均值收斂曲線圖進(jìn)行分析。在F4、F7、F11、F28上,GDESSA有著更快的收斂速度和收斂精度;而在F1、F9、F14和F22上,雖然GDESSA在迭代前期收斂較慢,這是由于引入精英池策略,導(dǎo)致在前期沒有總是以最優(yōu)個體引導(dǎo),從而在前期收斂較慢,但GEDSSA在迭代后期收斂速度加快且精度更高,這也使精英池策略增加了種群多樣性,避免了局部最優(yōu),同時高斯分布估計策略使得追隨者能更好地向優(yōu)勢方向進(jìn)化,增強(qiáng)了算法的后期開發(fā)能力;GEDSSA在F26上排名第二,仍優(yōu)于5種對比算法。因此，本文提出的改進(jìn)策略能夠有效提升算法收斂性能。

圖5 部分測試函數(shù)收斂曲線圖Fig.5 Part of the test function convergence curves

文獻(xiàn)[25-26]表明僅根據(jù)平均值比較算法性能是不充分的,為了避免測試中的偶然性,本文使用Wilcoxon符號秩檢驗來驗證改進(jìn)算法與對比算法是否在統(tǒng)計上存在顯著差異。表4列出了在α=0.05的情況下,每種算法和GDESSA的Wilcoxon符號秩檢驗的結(jié)果。在表4中,“+”表示GDESSA的優(yōu)化結(jié)果優(yōu)于比較算法,“-”表示結(jié)果較差,“=”表示結(jié)果相似,符號“R+”是一個正等級值,表示GDESSA比對比算法更好的程度,“R-”表示相反的結(jié)果。從表4可以看出,GDESSA在26個測試函數(shù)上表現(xiàn)優(yōu)于HFPSO,在16個測試函數(shù)上優(yōu)于GEDGWO,在23個測試函數(shù)上優(yōu)于VCS,在19個測試函數(shù)上優(yōu)于MPA,在所有測試函數(shù)中優(yōu)于SMA,在27個測試函數(shù)中優(yōu)于HHO。綜上,GDESSA至少在28個測試函數(shù)中的16個優(yōu)于所有對比算法,這在統(tǒng)計學(xué)上驗證了改進(jìn)算法的出色性能。

表4 Wilcoxon 符號秩檢驗結(jié)果(α=0.05)

續(xù)表4

此外,為了檢測多個算法之間的差別與排名,本文采用了另外一種非參數(shù)多重比較方法:Friedman檢驗。在Friedman檢驗中,越低的排名代表著其擁有越好的性能。Friedman測試主要從均值、標(biāo)準(zhǔn)差與耗時3個方面進(jìn)行比較。如表5所示,3個方面的Friedman測試顯著概率明顯小于0.05,因此假設(shè)被拒絕,7個比較的算法性能是有顯著的差別。在均值與方差方面,GDESSA表現(xiàn)為最好;在耗時方面,GDESSA表現(xiàn)排名第四,劣于3種混合算法。

表5 在均值、標(biāo)準(zhǔn)差和耗時3個方面的Friedman測試結(jié)果

為了進(jìn)一步測試差異發(fā)生情況,采用Iman-Davenport測試。Iman-Davenport測試是根據(jù)自由度的F分布進(jìn)行的:

(14)

式中：和代表比較算法個數(shù)與測試函數(shù)的個數(shù)。在本文中,=7和=28。根據(jù)式(14),可以得到Iman-Davenport測試結(jié)果如表5所示。為了發(fā)現(xiàn)所有算法的差異,使用基于Nemenyi測試的臨界差異(critical difference,CD)。CD的計算如下:

(15)

圖6 基于Nemenyi測試的算法比較Fig.6 Comparison of algorithms based on the Nemenyi test

4 結(jié) 論

本文針對基本SSA存在的不足,提出了GDESSA,首先將領(lǐng)導(dǎo)者食物源選擇從最優(yōu)個體改為從精英池中隨機(jī)選擇,避免最優(yōu)個體陷入局部最優(yōu)導(dǎo)致的早熟收斂,增強(qiáng)種群多樣性;其次調(diào)整追隨者位置更新公式,將鏈?zhǔn)礁乱?guī)則改為依靠優(yōu)勢群體、個體和精英池個體來調(diào)整位置,既結(jié)合了優(yōu)勢種群進(jìn)化方向,又保留部分個體信息,還參考精英池個體信息,提高了算法的開發(fā)和探索能力。使用CEC2017測試函數(shù)對改進(jìn)策略和算法尋優(yōu)性能進(jìn)行測試,并通過數(shù)值分析、收斂性分析、穩(wěn)定性分析、Wilcoxon檢驗、Friedman檢驗和Iman-Davenport檢驗評估算法性能。實驗結(jié)果表明,改進(jìn)策略能有效增強(qiáng)種群多樣性、提高算法的收斂速度和收斂精度、穩(wěn)定地獲得較優(yōu)解,并在整體上性能優(yōu)于對比算法。在后續(xù)研究中,考慮將改進(jìn)后的SSA應(yīng)用到無人機(jī)航跡規(guī)劃和任務(wù)分配問題中,以進(jìn)一步驗證算法求解現(xiàn)實世界復(fù)雜優(yōu)化問題的能力。