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

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

0 引 言

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

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

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

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

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

1 原始SSA

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

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

(1)=·(-)+

(1)

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

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

(2)

(3)

追隨者根據(jù)鏈式規(guī)則,順次跟隨移動,其數(shù)學模型描述如下:

(4)

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

(5)

2 改進SSA

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

2.1 精英池策略

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

(6)

(7)

(8)

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

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

(9)

式中:為精英池中隨機選擇的個體。

2.2 高斯分布估計策略

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

(10)

(11)

(12)

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

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

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

(13)

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 GDESSA改進策略比較分析

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

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

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

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

3.2 GDESSA與其他算法比較分析

為進一步驗證GDESSA的優(yōu)越性,選取3種改進群智能優(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進行比較。HFPSO是一種混合螢火蟲算法的改進粒子群算法。GEDGWO是一種融合了分布估計算法的GWO算法變體。VCS是一種結(jié)合DE和CMA-ES的融合算法。這3種改進算法均在各自文獻證明了其具有較好的性能。而MPA、SMA和HHO均是近年來最新提出的表現(xiàn)較好的群智能優(yōu)化算法,已被運用在不同的學科和工程領域。因此,使用這些算法進行對比能夠驗證本文提出算法是否在性能上有提升。為保證公平,各算法參數(shù)設置參考原文獻,如表2所示。將所有算法獨立運行51次,記錄均值和標準差,實驗結(jié)果如表3所示。

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

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

續(xù)表3

由表3可知,GDESSA在單峰測試函數(shù)F1上表現(xiàn)最好,表明了GDESSA在求解病態(tài)函數(shù)的優(yōu)勢,再一次驗證了改進策略能有效提高算法的開發(fā)能力。對于多峰測試函數(shù)F2～F8,GDESSA在其中5個函數(shù)上(F3～F7)取得了更好的解,這表明改進策略能夠很好地增強種群多樣性,避免局部最優(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é)果。總體來說,GDESSA在28個測試函數(shù)中的16個測試函數(shù)上排名第一,并在8個測試函數(shù)中排名第二,表明了本文提出的改進策略能很好地提升算法的開發(fā)和探索能力。

為分析改進算法所求解的分布特性,根據(jù)各算法獨立求解測試函數(shù)51次的結(jié)果繪制箱式圖,如圖4所示。對于每種算法,每個框的中心標記表示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

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

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

文獻[25-26]表明僅根據(jù)平均值比較算法性能是不充分的,為了避免測試中的偶然性,本文使用Wilcoxon符號秩檢驗來驗證改進算法與對比算法是否在統(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)計學上驗證了改進算法的出色性能。

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

續(xù)表4

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

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

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

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