基于多機制優(yōu)化螺旋飛行特征的烏燕鷗算法

李光泉, 劉欣宇, 王龍飛, 邵鵬

(江西農(nóng)業(yè)大學計算機與信息工程學院, 南昌 330045)

近些年來,各國學者們由于深受自然界動植物的特征行為而倍受啟發(fā),并通過模擬自然界生物的各種覓食行為、攻擊行為和繁殖行為等提出了一系列的群體智能優(yōu)化算法。群智能優(yōu)化算法種類眾多,但因為其結構簡單、易于擴充且效果顯著而深受廣泛學習研究。例如:鯨魚優(yōu)化算法[1](whale optimization algorithm, WOA)、粒子群算法[2](particle swarm optimization, PSO)、樽海鞘群體算法[3](salp swarm algorithm, SSA)、蝴蝶優(yōu)化算法[4](butterfly optimization algorithm, BOA)、灰狼優(yōu)化算法[5](grey wolf optimization, GWO)、海鷗優(yōu)化算法[6](seagull optimization algorithm, SOA)、烏燕鷗優(yōu)化算法[7](sooty tern optimization algorithm, STOA)等。其中,烏燕鷗算法就是近年來一種新興的群智能優(yōu)化算法,其主要是通過特殊的遷徙行為和攻擊行為,實現(xiàn)了算法在全局搜索和局部搜索的主要功能,并因為算法的可操作性強,可實現(xiàn)性高,目前在一些工業(yè)問題和分類問題上均取得了良好效果。然而,也因為算法有限的搜索能力和單一的搜索方式,導致了算法較易陷入局部最優(yōu),并隨著迭代次數(shù)的增加會導致種群多樣性的不斷減小,降低了算法在搜索后期的收斂速度及收斂精度。

為此,針對STOA存在的不足,中外學者們傾向于從算法混合、單策略優(yōu)化、多策略優(yōu)化以及基于實際工程問題優(yōu)化等多角度提出廣泛的改進方法,并在不同的函數(shù)集和實際問題上進行仿真實驗。賈鶴鳴等[8]通過將遺傳算法和烏燕鷗算法進行混合,并通過平均適應度值進行評估,以此加強烏燕鷗算法的局部搜索能力,證明了該算法在數(shù)據(jù)挖掘領域具有廣闊的工程應用前景;肖永江等[9]通過將遺傳算法的變異思想融入烏燕鷗算法中,提出了一種新穎的改進烏燕鷗算法并進行了DG的優(yōu)化配置,大大提高了算法收斂速度和精度;喬夏君等[10]針對傳統(tǒng)PID參數(shù)整定存在的問題,通過引入混沌映射提出了一種混沌烏燕鷗算法(chaos sooty tern optimization algorithm, CSTOA)用以優(yōu)化發(fā)動機參數(shù)自整定PID控制;Soni等[11]通過引入烏燕鷗算法對動態(tài)經(jīng)濟排放調(diào)度問題進行了優(yōu)化和解決。同時,孫珂琪等[12]提出一種混合正余弦算法和Lévy飛行的自適應烏燕鷗算法,并將其應用于解決橋式起重機主梁結構優(yōu)化設計中;雒珊等[13]為解決算法局部最優(yōu)能力和尋優(yōu)能力較低的問題,提出了一種混合Lévy飛行和熱交換混沌烏燕鷗算法,并將算法應用于二級斜齒圓柱齒輪傳動機構可靠性輕量化設計,實現(xiàn)了齒輪傳動機構輕量化設計的目的;而李家?guī)浀萚14]針對行星齒輪箱振動信號的非線性特征明顯、故障特征難以識別的問題,提出了一種基于烏燕鷗算法的故障診斷方法用以提取磨損故障特征頻率;李月英[15]和王國柱等[16]則在此基礎上提出了一種改進的烏燕鷗算法和多策略改進的烏燕鷗算法,有效地解決了移動機器人在復雜環(huán)境中的最優(yōu)路徑規(guī)劃問題和橋式起重機主梁質(zhì)量減重問題。

上述研究不僅在一定程度上平衡、增強了烏燕鷗算法在全局尋優(yōu)和局部尋優(yōu)的能力,而且對于算法的收斂速度及收斂精度也有了本質(zhì)的提升。然而,由于SOTA自身獨特的尋優(yōu)方式,導致算法仍然存在著“全局強,局部弱”的顯著優(yōu)缺點。為了能在更大程度上提高算法的局部搜索能力和收斂速度,現(xiàn)提出一種融合混沌映射、自適應慣性權重與高斯變異的多機制烏燕鷗優(yōu)化算法(GT-STOA)。首先,通過采用Tent混沌映射對種群進行初始化;其次,引入自適應慣性權重優(yōu)化機制,增強算法的局部搜索能力,并在此基礎上引入高斯變異機制,此為提升算法跳出局部極值的能力。由此可見,基于多機制協(xié)同優(yōu)化的GT-STOA不僅增強了種群的多樣性,而且提升了算法在全局搜索和局部搜索的能力,從而使之具備更強的尋優(yōu)能力和算法魯棒性。

1 烏燕鷗優(yōu)化算法

1.1 烏燕鷗遷徙行為

(1)避免碰撞:為了防止烏燕鷗群體間產(chǎn)生相互碰撞,附加變量SA將會用于計算新的搜索代理位置,以避免相鄰烏燕鷗個體之間的碰撞,并計算產(chǎn)生烏燕鷗的新位置:

(1)

(2)

z=0,1,…,Maxiterations

(3)

式中:Cf為一個線性調(diào)整SA的控制變量,它的值從Cf線性減小至0;z為當前迭代次數(shù);Maxiterations為最大迭代次數(shù)。

(2)聚集:烏燕鷗個體在遷徙過程中避免相互碰撞后,群體之間會朝著最佳個體所在的位置方向進行移動。

(4)

CB=0.5Rand

(5)

(3)更新:最終,烏燕鷗可以根據(jù)最佳個體所在的位置方向更新其軌跡和最終位置。

(6)

1.2 烏燕鷗攻擊行為

攻擊行為是烏燕鷗種群重要的特征行為之一,在遷徙的途中,它們可以依靠自身重量和羽翼改變它們的速度、高度和攻擊角度等。當烏燕鷗群體攻擊獵物時,它們便會在空中產(chǎn)生特定的螺旋行為。具體表現(xiàn)形式如下。

x′=Rsini

(7)

y′=Rcosi

(8)

z′=Ri

(9)

R=uekv

(10)

(11)

2 烏燕鷗算法的優(yōu)化設計

2.1 混沌初始化機制

烏燕鷗種群的初始位置對于烏燕鷗最優(yōu)位置的移動搜索會存在較大的影響和一定的約束,在STOA算法中就初始位置的更新方式而言主要是通過在搜索空間中隨機生成位置序列而產(chǎn)生的。隨機初始化所得的確定位置,雖然在一定程度上保證了初始位置的隨機性,但是就種群的多樣性而言同樣帶來了極大的不確定性,也無法保證個體位置的均勻分布,從而導致種群多樣性和尋優(yōu)速度的降低。

通過學者們的不斷嘗試和復現(xiàn),并結合混沌映射的遍歷性特征和隨機性特征,王賀琦等[17]將Tent映射用于了優(yōu)化改進人工蜂群算法,毛清華等[18]則融合改進Tent混沌方法優(yōu)化了灰狼算法等。以此為鑒,本文研究將引入Tent混沌映射機制優(yōu)化烏燕鷗種群初始化過程,具體映射函數(shù)表達式為

(12)

式(12)中:t為映射次數(shù),t=0,1,2…;xt為第t次所得的映射函數(shù)值;γ為混沌參數(shù),在本文中設為定值2。

假設在二維搜索空間中,設定種群數(shù)量為200,將隨機種群初始化后的位置分布同引入混沌映射后的種群初始化位置分布圖進行直觀比對。由圖1(a)可以發(fā)現(xiàn),隨機初始化種群所得的遍歷位置分布散亂,隨機性較大。反觀圖1(b),在引入Tent映射優(yōu)化初始種群位置后所呈現(xiàn)出的分布趨勢是較為均勻的,由此直觀地反映出Tent映射初始化種群具有一定的優(yōu)化效果。

圖1 種群初始化位置分布示意圖

2.2 自適應慣性權重優(yōu)化機制

烏燕鷗優(yōu)化算法中的慣性權值是衡量算法收斂速度和尋優(yōu)結果的一個重要指標。當慣性權重取值較大時,算法會因為大權值的存在而表現(xiàn)出顯著的全局搜索能力,而當慣性權重取值較小時,算法則更會表現(xiàn)出卓越的局部搜索能力。由此,歸于烏燕鷗算法的迭代過程。因為變量SA在尋優(yōu)過程中充當著慣性權重的重要作用,所以本文研究將針對變量SA進行自適應權重優(yōu)化。通過迭代次數(shù)的遞增適當?shù)貙嘀颠M行自適應縮小,用以增強算法的局部搜索能力,平衡算法在全局搜索和局部搜索的性能。綜上,具體的優(yōu)化模型如下。

(13)

(14)

2.3 高斯變異優(yōu)化機制

烏燕鷗優(yōu)化算法由于小步長搜索特性的存在而表現(xiàn)出了顯著的全局搜索能力而被廣泛應用于實際問題的優(yōu)化解決中,但同時也是因為減小了搜索步長給算法的局部搜索帶來了一定的負影響。不僅如此,在STOA的迭代執(zhí)行過程中,種群內(nèi)烏燕鷗位置的多樣性會伴隨著迭代次數(shù)的不斷遞增而大幅下降,由此削弱了算法精細搜索的能力,使得算法過早的陷入局部最優(yōu),降低了算法尋優(yōu)性能。

鑒于此,所受李文超等[19]將高斯變異算子作為自花授粉更新公式,葉坤濤等[20]通過高斯變異擾動更新種群蜘蛛最優(yōu)位置為啟發(fā),并綜于烏燕鷗算法的小步長搜索機理,本文研究在烏燕鷗種群完成遷徙攻擊搜索后針對種群內(nèi)的最優(yōu)個體位置Posbest通過高斯變異機制執(zhí)行優(yōu)化更新,具體機制模型為

Posbest=Posbest[0.1+kGaussian(0,1)]

(15)

式(15)中:Posbest為烏燕鷗的最優(yōu)個體位置;k為在區(qū)間[0,1]中的隨機數(shù);Gaussian(0,1)為服從均值為0、方差為1的高斯分布。

2.4 GT-STOA算法流程及描述

GT-STOA算法是一種由多機制優(yōu)化后的群智能算法,其本質(zhì)是通過模擬烏燕鷗種群的遷徙行為和攻擊行為進行數(shù)學模型復現(xiàn),以達到定位搜索和快速尋優(yōu)的效果。

針對傳統(tǒng)烏燕鷗算法存在的不足,通過融合混沌映射,自適應慣性權重和高斯變異擾動展開了多機制輔助優(yōu)化。主要包括在種群初始化位置的更新,慣性變量權值的自適應性擾動以及在最優(yōu)個體位置的更新上進行針對性優(yōu)化,幫助算法豐富了種群多樣性,提升了收斂速率和提高了尋優(yōu)精度等。綜上所述,GT-STOA算法的整體執(zhí)行過程如下。

步驟1初始化烏燕鷗種群{xi|i=1,2,…,N},初始化參數(shù)SA、CB和Maxiterations,并由式(12)混沌映射函數(shù)更新種群初始化位置。

步驟2計算烏燕鷗個體的適應度值Pst(x),尋找適應度值最優(yōu)所屬烏燕鷗的所處位置Pbst(x),記錄此時最優(yōu)解Xbest。

步驟3由式(13)和式(14)計算自適應權重值,通過自適應權重的結果更新烏燕鷗個體的位置。

步驟4由式(1)、式(4)、式(6)計算烏燕鷗個體的運行軌跡和最終位置。

步驟5由式(7)～式(11)計算烏燕鷗最終的螺旋飛行位置Pst(x+1)。

步驟6更新計算目標函數(shù)適應度值,保留最優(yōu)烏燕鷗個體位置。

步驟7由式(15)通過高斯變異對最優(yōu)烏燕鷗個體位置進行擾動更新,選擇保留兩者中適應度值更好的解,并更新最優(yōu)解Xbest。

步驟8判斷結束條件,如果已滿足結束條件,則準備結束程序,輸出所得結果,否則跳轉步驟2。

步驟9程序執(zhí)行結束,輸出最優(yōu)位置及最優(yōu)解Xbest。

GT-STOA的算法偽代碼如下。

GT-STOA偽代碼Begin初始化參數(shù),種群規(guī)模N,測試函數(shù)F,最大迭代次數(shù)Maxiterations;按式(12)Tent初始化種群,計算個體適應度值,尋找種群最優(yōu)位置Pbst(x);While t < Maxiterations do for i = 1 to N do 按式(13)和式(14)計算自適應權重值,并由此更新種群個體的位置; end for for i = 1 to N do 按式(15)對最優(yōu)個體位置進行擾動更新; end forend WhileEnd

2.5 時間復雜度分析

算法的時間復雜度對評判算法的性能有著至關重要的作用。為此,計算STOA算法在優(yōu)化后的時間復雜度。

當對于種群大小為N、維度為D的啟發(fā)式算法 STOA而言,其所得的時間復雜度為O(ND)。而對于多機制優(yōu)化后的GT-STOA而言:Tent映射初始化參數(shù)所需時間的為ND,自適應慣性權重優(yōu)化個體位置所需的時間為ND,高斯變異擾動最優(yōu)個體位置所需的時間也為ND。綜上,GT-STOA整體的時間花費為

ND+ND+ND=3ND

(16)

由此可見,本文GT-STOA算法的時間復雜度為O(3ND),通過對照算法STOA的時間復雜度O(ND)發(fā)現(xiàn)二者的時間復雜度并沒有顯著性差異,故本文的多策略優(yōu)化并不會對算法效率造成負面影響。

3 實驗仿真與結果分析

3.1 實驗環(huán)境及參數(shù)設置

本次實驗的測試環(huán)境為64 位 Windows 10 操作系統(tǒng),實驗軟件由MATLAB R2018b負責執(zhí)行算法運算。

同時,為了充分證明GT-STOA算法的可行性和準確性,也為保證算法執(zhí)行結果的相對公平性,在本文的仿真實驗中將統(tǒng)一算法的測試方法與測試數(shù)據(jù)。其中,種群數(shù)量設定為30,最大迭代次數(shù)為500,并且為了防止算法執(zhí)行過程的隨機性影響,所有實驗均獨立運行30次,記錄實驗結果的平均值、最優(yōu)值和標準差。

3.2 測試函數(shù)

為了驗證GT-STOA的優(yōu)化效果,選用12個基于不同特征的基準測試函數(shù)進行仿真實驗。其中,F1～F7是單峰測試函數(shù),F8～F11是多峰測試函數(shù),F12則是固定維度的多峰測試函數(shù),測試函數(shù)的具體信息如下:F1為Sphere函數(shù), F2為Schwefel 2.22函數(shù), F3為Schwefel 1.2函數(shù), F4為Schwefel 2.21函數(shù), F5為Rosenbrock函數(shù), F6為Quartic函數(shù),F7為Sum Squares函數(shù),F8為Rastrigin函數(shù),F9為Ackley函數(shù),F10為Griewank函數(shù),F11為Alpine函數(shù),F12為Foxholes函數(shù)。

3.3 仿真結果分析

為驗證GT-STOA算法的尋優(yōu)性能,選取PSO作為經(jīng)典智能優(yōu)化算法的代表。同時,為了衡量GT-STOA在新型領域及相關研究領域的尋優(yōu)效果,選取多策略海鷗優(yōu)化算法[21](multi-mechanism seagull optimization algorithm, GEN-SOA)、非洲野狗算法[22](design optimization algorithm, DOA)、CSTOA、GWO、SSA、BOA、SOA和STOA 9種對照算法進行對比實驗。

從實驗直觀性角度出發(fā),將GT-STOA同所有對照算法一起,取F1～F12測試函數(shù)的最優(yōu)值,平均值和標準差如表1中統(tǒng)計所示。同時,根據(jù)各算法的尋優(yōu)結果將繪制部分測試函數(shù)的收斂曲線圖用于收斂性分析,如圖2所示。

表1 10種不同算法的實驗對比

圖2 對比算法收斂圖

3.3.1 算法精度分析

針對實驗的單峰測試函數(shù)F1～F4而言,GT-STOA和GEN-SOA均在算法執(zhí)行結果中找到了理論最優(yōu)值,并且GT-STOA相對于其他對照算法而言也實現(xiàn)了精度數(shù)值最優(yōu)的結果,并在F7、F8、F10和F12函數(shù)也都尋及理論最優(yōu)值。對于單峰測試函數(shù)F5,SOA與GEN-SOA算法在最終的尋優(yōu)結果的精度上取得了較好的效果,而STOA則相對來說尋優(yōu)效果較弱。對于測試函數(shù)F6,GT-STOA通過自適應慣性權重的優(yōu)化表現(xiàn)出了最優(yōu)的尋優(yōu)結果,而CSTOA則僅次于此,在數(shù)值精度上平均高出近2個數(shù)量級左右。然而對于多峰測試函數(shù)F8～F11,就F8可以發(fā)現(xiàn),GT-STOA與5個算法同樣在函數(shù)值上找到了理論最優(yōu)值。對于F9而言,GT-STOA與GEN-SOA和DOA所能尋及的最優(yōu)值相同,但同樣是所有對照算法中的最優(yōu),并且得益于算法的多機制輔助優(yōu)化,幫助它們所得的標準差均為0,提升了算法在尋優(yōu)過程的穩(wěn)定性,而GWO,BOA等則緊隨其后。對于測試函數(shù)F10,在最終結果上GT-STOA、GEN-SOA、GWO、DOA和CSTOA均找到了理論最優(yōu)值,并且GT-STOA、GEN-SOA和DOA在平均值和算法穩(wěn)定性指標上的表現(xiàn)也十分出色。針對測試函數(shù)F11中GT-STOA與GEN-SOA在結果中找到了理論最優(yōu)。而在F12函數(shù)中,雖然SSA表現(xiàn)出了較全面的尋優(yōu)能力,但總體而言,GT-STOA的尋優(yōu)能力依舊出色。

3.3.2 算法收斂性分析

結合收斂圖2和表1可以發(fā)現(xiàn),針對測試函數(shù)F1～F12而言,GT-STOA、GEN-SOA和DOA 3種算法的全局最優(yōu)值均以相對較高的速率進行收斂下降,并且算法在全局勘測和局部尋優(yōu)的協(xié)調(diào)能力中有著顯著的優(yōu)越性,實例表現(xiàn)在測試函數(shù)F5和F6等在后期依舊能夠通過有力的局部搜索找到最優(yōu)值。其中,對于測試函數(shù)F1、F3和F10,GT-STOA均在250以內(nèi)便收斂到了全局最優(yōu)值,并且表現(xiàn)出了收斂速度最快,收斂精度最小的顯著效果。而在測試函數(shù)F8和F10中所表現(xiàn)出的收斂性最強,在50代后便收斂到了算法最優(yōu)值也是全局最優(yōu)值。展現(xiàn)了GT-STOA算法穩(wěn)定且顯著的全局尋優(yōu)能力。

3.4 高維函數(shù)的實驗分析

綜合上述各算法的精度分析及收斂性分析發(fā)現(xiàn),GT-STOA在低維度尋優(yōu)過程中有著顯著性效果?；诖?為充分驗證算法在高維度條件下所顯現(xiàn)的尋優(yōu)能力,對6個測試函數(shù)在100維情況下進行仿真實驗,比較GT-STOA與各類代表性算法在高維情況下的尋優(yōu)能力。算法的實驗參數(shù)與3.1節(jié)一致,實驗結果如表2所示。

表2 高維函數(shù)對比

由表2的實驗結果可知,當測試函數(shù)的維度提升至100維時,GT-STOA針對不同類型的單峰函數(shù)和多峰函數(shù)依舊能在不同的對照算法中表現(xiàn)出更優(yōu)的尋優(yōu)能力。在測試函數(shù)F2、F4、F10和F11中GT-STOA也找到了函數(shù)的理論最優(yōu)值,并且對于實驗結果的均值和標準差而言,也展現(xiàn)出了算法在高維情況下顯著的穩(wěn)定性。由上述分析可知,GT-STOA在處理高維優(yōu)化問題方面也具有一定的競爭優(yōu)勢。

3.5 非參數(shù)統(tǒng)計檢驗

為避免上述所得的算法結果會出現(xiàn)片面性且無法進行統(tǒng)一定性分析等問題,同時為了更好地驗證上述結論,如表3所示,本文介紹了非參數(shù)統(tǒng)計學中的Wilcoxon檢驗[23]和Friedman檢驗[24]的統(tǒng)計結果。

表3 統(tǒng)計檢驗結果

在Wilcoxon統(tǒng)計檢驗中,若顯著性水平P<0.05,則表示算法對于對比算法具有顯著性優(yōu)勢。而在Friedman統(tǒng)計檢驗中,將根據(jù)排名值進行排序,排名值越低則算法排名順序越高。綜上所述,在本文算法性能排名第一的是GT-STOA;同時,結合P值可知GT-STOA較9種對比算法而言具有顯著的優(yōu)勢。

3.6 壓力容器優(yōu)化問題

為實際驗證GT-STOA的優(yōu)化效果,在前期算法取得出色收斂效果和尋優(yōu)能力的前提下,采用壓力容器優(yōu)化設計問題對GT-STOA進行實例驗證。其中種群規(guī)模設定為30,最大迭代次數(shù)設為1 000。

壓力容器優(yōu)化設計問題[25]是使一個圓柱形容器的材料、成型和焊接總成本最小化,該問題也同樣具有4個主要優(yōu)化變量,包括殼體厚度Ts(x1)、頂部厚度Th(x2)、內(nèi)半徑R(x3)、忽略頂部的圓柱形截面長度L(x4)。其中,壓力容器的約束條件為以壓力容器優(yōu)化設計問題為例,通過應用GT-STOA與SOA、STOA和GEN-SOA算法進行收斂性分析,收斂曲線圖如圖3所示。同時,就GT-STOA與STOA于壓力容器設計問題進行精度分析,其中所得最優(yōu)解的變量取值與30次獨立實驗所得的平均精度如表4所示。

表4 壓力容器檢驗結果

圖3 壓力容器優(yōu)化問題

(17)

由此可見,GT-STOA不僅在上述分析的算法準確性和收斂速度上有明顯的優(yōu)勢,而且在壓力容器工程優(yōu)化問題上也優(yōu)于同型算法,擁有更出色的收斂與尋優(yōu)能力,并較傳統(tǒng)STOA算法的優(yōu)化精度提升了42.54%。

4 結論

針對烏燕鷗優(yōu)化算法(STOA)求解精度較低、種群多樣性較弱,并且容易陷入局部最優(yōu)的缺點,提出了一種融合混沌映射、自適應慣性權重與高斯變異的多機制烏燕鷗優(yōu)化算法(GT-STOA)。其中,本文研究的創(chuàng)新點和主要貢獻在于通過混沌映射函數(shù)的遍歷性特征和隨機性特征對種群初始位置進行多樣性調(diào)整,增加了種群多樣性,予以解決了由于種群多樣性不足導致尋優(yōu)效率低下的缺陷;并且基于自適應慣性權重和高斯變異優(yōu)化機制對最優(yōu)種群個體位置進行擾動,不僅增強了算法的穩(wěn)定性,還能幫助算法跳出局部最優(yōu),提高算法在局部搜索過程的尋優(yōu)精度和收斂速度。

與此同時,為驗證GT-STOA算法的優(yōu)越性和穩(wěn)定性,在12個基于不同特征的基準測試函數(shù)上,分別對GT-STOA、GEN-SOA、BOA、SSA、GWO、PSO、DOA、STOA、SOA和CSTOA進行仿真實驗對比。由實驗數(shù)據(jù)可知,GT-STOA在9個測試函數(shù)上均找到理論最優(yōu)值,尋及理論最優(yōu)率為75%。并且在非參數(shù)統(tǒng)計檢驗中Friedman排名值為2.13位居第一,展現(xiàn)出了算法顯著的優(yōu)勢。不僅如此,還通過引入了壓力容器優(yōu)化設計問題對GT-STOA算法進行了實例驗證,據(jù)實驗結果表明GT-STOA較傳統(tǒng)STOA算法在優(yōu)化精度上提升了42.54%。

未來,將進一步對STOA攻擊尋優(yōu)的方式進行深入的研究與分析,并努力將優(yōu)化后的GT-STOA與實際工程應用問題相結合,投入在離散優(yōu)化問題的改進與應用中,提升GT-STOA算法的實際應用價值。