王培崇， 尹欣潔， 李麗榮

(1.河北地質(zhì)大學(xué) 信息工程學(xué)院，河北 石家莊 050031；2.河北地質(zhì)大學(xué) 人工智能與機器學(xué)習(xí)研究室，河北 石家莊 050031；3.河北地質(zhì)大學(xué) 藝術(shù)學(xué)院，河北 石家莊 050031)

0 引言

近些年，元啟發(fā)算法[1]發(fā)展迅速，2019年的海鷗優(yōu)化算法(seagull optimization algorithm，SOA)[2]就是元啟發(fā)算法的代表算法之一。該算法通過模擬海鷗種群的協(xié)作飛行和捕食獵物實現(xiàn)對問題的求解，并在多個工程領(lǐng)域內(nèi)得到了成功應(yīng)用。但是，由于該算法缺少嚴格的數(shù)學(xué)理論支持，在解決較高維度的函數(shù)優(yōu)化問題時出現(xiàn)了收斂速度慢、解精度低和容易早熟等問題[3-5]。

針對標準SOA容易早熟、解精度低等問題，毛清華等[6]提出一種融合改進Logistics混沌和正弦、余弦算子的自適應(yīng)t分布海鷗算法，該算法采用改進的Logistics混沌映射機制初始化種群，在種群的搜索階段引入正弦、余弦算子更新個體的位置，并引入非線性收斂因子協(xié)調(diào)算法的局部搜索和全局搜索，加快算法的收斂速度；同時，為了克服算法早熟，對種群內(nèi)最優(yōu)個體所在的位置引入自適應(yīng)t分布變異策略加以擾動。王寧等[7]提出一種黃金正弦引導(dǎo)與Sigmoid連續(xù)化的海鷗優(yōu)化算法，該算法在海鷗遷徙階段，引入Sigmoid函數(shù)的慣性權(quán)重引導(dǎo)海鷗種群的全局搜索；在捕食階段，將置信度低的區(qū)域設(shè)置為搜索禁忌，保證種群一直向置信度高的優(yōu)秀解空間區(qū)域飛行；并且加入黃金正弦機制幫助種群尋找搜索范圍，指引種群的位置更新，提高尋優(yōu)能力。秦維娜等[8]提出一種基于慣性權(quán)重的海鷗優(yōu)化算法，采用非線性遞減的慣性權(quán)重計算附加變量的值來調(diào)整海鷗的位置，通過Levy飛行和隨機指數(shù)值增加海鷗飛行的隨機性，增強算法搜索尋優(yōu)的全局能力，避免算法尋優(yōu)搜索陷入局部最優(yōu)。Che等[9]提出了一種混合鯨魚-海鷗優(yōu)化算法，該算法首先在SOA螺旋式攻擊行為中融入鯨魚優(yōu)化算法的空間收縮策略，以提高SOA的計算精度；其次，在SOA的搜索算子中引入Levy飛行策略，引導(dǎo)算法跳出局部最優(yōu)的約束。上述改進機制在一定程度上改善了算法的性能，但是均沒有考慮種群內(nèi)粒子之間的信息交流問題。

本文提出一種具有學(xué)習(xí)機制的改進海鷗優(yōu)化算法(improved SOA with learning，ISOAL)。該算法在遷移算子中引入基于當(dāng)前粒子和種群均值間差異的學(xué)習(xí)機制，在算法的后期引入精英粒子的反向?qū)W習(xí)(opposition-based learning,OBL)[10-11]，以提升算法性能。

1 標準海鷗優(yōu)化算法

標準海鷗優(yōu)化算法流程如圖1所示。

圖1 標準海鷗優(yōu)化算法流程Figure 1 Flow chart of standard SOA

1.1 遷移算子

(1)

(2)

式中:A=fs-[t·(fs/Tmax)]，fs=2，Tmax為最大迭代次數(shù)；B=2A2·rand(0,1)。

當(dāng)前粒子與最優(yōu)粒子之間的相對距離為

(3)

1.2 捕食算子

海鷗采用一種螺旋式飛行的方式對獵物進行攻擊，在三維空間的運動為

(4)

式中：r為海鷗在螺旋飛行時的半徑；θ∈[0,2π]為隨機角度；u、v為常數(shù)。

當(dāng)前粒子的捕食算子為

Xi(t+1)=Di(t)·gxgygz+Xb(t)。

(5)

綜上，算法迭代過程中的當(dāng)前粒子軌跡為

Xi(t+1)=|(A-B)·Xi(t)+B·Xb(t)|·

gxgygz+Xb(t)。

(6)

2 具有學(xué)習(xí)機制的海鷗優(yōu)化算法

由式(6)可知，海鷗優(yōu)化算法的迭代過程僅有2個參數(shù)。其中參數(shù)A為線性變化，在一定程度上提升了算法的收斂速度，但對于解空間為多峰的復(fù)雜優(yōu)化問題，算法容易忽略部分解空間。此外，該算法沒有考慮種群內(nèi)部非最優(yōu)粒子之間的信息交流和互動行為，而自然界中的生命群體均會存在內(nèi)部信息的溝通和學(xué)習(xí)行為，這種學(xué)習(xí)行為在很大程度上可以主導(dǎo)種群的演化方向?；诖耍疚膶囊韵聨讉€方面對算法進行改進。

2.1 基于學(xué)習(xí)機制的遷移算子

記Xm(t)為當(dāng)前種群全部粒子的平均狀態(tài)值，則式(1)的空間搜索機制更新為

(7)

式中：α為(0,1)的隨機數(shù)；Xm(t)-Xi(t)表示當(dāng)前粒子向種群均值學(xué)習(xí)，這樣可以在算法早期有效擴大搜索范圍，避免過早的收斂。

2.2 參數(shù)A的改進

標準SOA中的參數(shù)A受fs的制約，從2線性遞減到0，收斂速度較快。但是，大多數(shù)優(yōu)化問題的解空間為非線性，線性參數(shù)并不適合對空間進行有效搜索，容易忽略部分空間。因此將參數(shù)A調(diào)整為非線性以保證粒子對解空間的非線性搜索，見式(8)：

(8)

式中：betarand(·)為能產(chǎn)生beta分布的隨機數(shù)生成器。

圖2 參數(shù)A和A′隨迭代次數(shù)的變化曲線Figure 2 Curves of A and A′ with the number of iterations

2.3 精英反向?qū)W習(xí)

群體智能算法中，適應(yīng)度優(yōu)的精英粒子必然包含了更多的引導(dǎo)種群向全局最優(yōu)收斂的有益信息。令精英粒子執(zhí)行反向?qū)W習(xí)，既能加快算法的收斂速度，也加強了算法的局部探索能力。

定義2基于反向解的優(yōu)化。設(shè)待優(yōu)化問題為最小問題，適應(yīng)度函數(shù)為f(X)，若存在某個可行解X，其反向解為X′，若f(X′)

算法1OBL算法。

輸入：個體Xi(t)，下限a，上限b,最大迭代次數(shù)Itermax；

輸出：最優(yōu)個體Xi(t)；

Step 1 設(shè)置迭代次數(shù)為m=0；

“對對，就是那個乾隆皇帝的‘乾隆’，這‘乾隆通寶’，就是他在位時鑄造的貨幣，不過因為款式面值，發(fā)行地各有不同，流傳下來的‘乾隆通寶’也是各有差異?！崩腺Z看向少的那一堆。孟導(dǎo)順著老賈的目光看過去，果然發(fā)現(xiàn)那一小堆錢上正面基本都有“乾隆通寶”的銘文，不過反面朝上的則銘有許多自己不認識的符號。即使認真看了看，也分不出是哪國文字。

Step 2 生成一般化系數(shù)k∈[0,1]，依據(jù)定義1生成反向解X′t(m)，并保存；

Step 3 迭代次數(shù)沒有滿足結(jié)束條件，則m=m+1,轉(zhuǎn)至Step 2；

Step 4 在Xi(t)和所產(chǎn)生的全部反向解中選擇最優(yōu)的個體替換Xi(t)并輸出，算法結(jié)束。

2.4 算法描述

算法2具有學(xué)習(xí)機制的海鷗優(yōu)化算法ISOAL。

輸入：種群規(guī)模N，最大迭代次數(shù)等參數(shù)；

輸出：最優(yōu)粒子Xb(t)。

Step 1 在解空間內(nèi)隨機初始化種群POP；

Step 2 計算粒子的適應(yīng)度值選擇最優(yōu)粒子Xb(t)；

Step 3 以式(7)、(8)替換式(1)，執(zhí)行遷移算子；

Step 4 執(zhí)行捕食算子；

Step 5 精英粒子變化幅度小于0.01，則執(zhí)行反向?qū)W習(xí)；

Step 6 算法不滿足終止條件，則轉(zhuǎn)至Step 2；

Step 7 輸出最優(yōu)粒子Xb(t)，算法結(jié)束。

設(shè)算子最大迭代次數(shù)為Tmax,種群規(guī)模為N，分析上述算法可知，主要操作集中于Step 3～6，則時間復(fù)雜度為O(Tmax·N)。

3 實驗及結(jié)果分析

3.1 無約束函數(shù)測試

為了驗證所提算法的性能，應(yīng)用MATLAB 2019編程實現(xiàn)上述算法，實驗環(huán)境為聯(lián)想筆記本(intel i7，16 GB)。選擇10個CEC2017標準測試函數(shù)來測試算法的性能，列于表1中，以近年來最新算法HPSO-TS[12]、V-DVGA[13]、DADE[14]和CMA-ES[15]作為對比算法。ISOAL的種群規(guī)模設(shè)置為30，問題維度為50，算法的迭代次數(shù)為3 000。所有算法均獨立運行30次，以消除偶然因素的影響，取解均值和方差進行對比，如表2所示。

表1 CEC2017測試函數(shù)Table 1 CEC2017 functions

表2列出了SOA、HPSO-TS、V-DVGA、DADE、CMA-ES與本文算法在CEC2017的10個函數(shù)上的解均值和方差。由表2可知，在單峰函數(shù)f1、f2、f3上，本文算法ISOAL的解均值和方差均最小。多峰函數(shù)f4、f6的解空間并不復(fù)雜，考驗的是算法跳出局部最優(yōu)約束的能力，從實驗結(jié)果看，ISOAL在解均值和方差上比CMA-ES算法略差，但是仍然優(yōu)于其他算法。多峰函數(shù)中的f5、f7、f8的解空間較復(fù)雜，存在多個局部最優(yōu)極值點，因此，對應(yīng)算法不僅需要有擺脫局部極值約束的能力，而且還要有一定的勘探新解的能力。在f5函數(shù)上，HPSO-TS、V-DVGA和ISOAL的解均值精度相差不大，ISOAL的方差優(yōu)于其他幾個算法，表現(xiàn)出較好的穩(wěn)定性。在f7、f8函數(shù)上，ISOAL的解均值和方差均最小，穩(wěn)定性良好。在函數(shù)f9上，ISOAL的解均值和方差均略高于DADE算法，但也在同一個數(shù)量級上，優(yōu)于其他算法。函數(shù)f10是一個多峰函數(shù)且局部最優(yōu)值數(shù)量眾多，ISOAL同樣表現(xiàn)出色，解均值和方差均最小，優(yōu)于其他對比算法。

圖3為V-DVGA、HPSO-TS、ISOAL和SOA算法在f1、f2、f3、f4、f5和f6上的收斂曲線。

圖3 算法收斂曲線對比Figure 3 Comparison of algorithm convergence curve

由圖3可知，在函數(shù)f1、f2、f3和f4上，ISOAL初始種群的最優(yōu)適應(yīng)度就已經(jīng)優(yōu)于其他算法，并且經(jīng)過非常少的迭代次數(shù)就迅速收斂，收斂速度明顯優(yōu)于其他算法。在函數(shù)f1上，HPSO-TS搜索到的最小適應(yīng)度值為0.224 5，ISOAL搜索到的最小適應(yīng)度值為0.191 2，相比下降14.83%。在函數(shù)f3上，HPSO-TS搜索到的最小適應(yīng)度值為0.165 7，ISOAL搜索到的最小適應(yīng)度值為0.154 7，相比下降6.63%。在函數(shù)f5上，HPSO-TS與ISOAL搜索到的最小適應(yīng)度值相差不大。在函數(shù)f6上，HPSO-TS搜索到的最小適應(yīng)度值為0.363 3，ISOAL搜索到的最小適應(yīng)度值為0.342 7，相比下降5.67%。在函數(shù)f2上，ISOAL算法和其他算法的收斂曲線在迭代初期交叉在一起，但是ISOAL算法在經(jīng)過較少的迭代之后，能夠迅速收斂到最優(yōu)解周圍，并開始進行勘探操作。結(jié)果表明，ISOAL所獲得最終解的精度優(yōu)于其他算法。

3.2 約束函數(shù)測試

針對工程中常見的張力彈簧問題[16]進行測試實驗，以檢測本文算法在約束問題上的性能。實驗?zāi)繕耸窃跐M足撓度、剪應(yīng)力和振動頻率等約束條件下，獲得最小質(zhì)量的彈簧。其變量分別為彈簧的線圈直徑W(x1)、彈簧的平均直徑D(x2)、彈簧的有效線圈數(shù)L(x3)。該問題的目標函數(shù)(總代價)和約束函數(shù)分別為

(9)

(10)

式中：0.05≤x1≤2.00； 0.25≤x2≤1.30； 2.0≤x3≤15.0。

表3列出了對比算法在該問題上的求解結(jié)果，對比算法的數(shù)據(jù)取自文獻[16]。由表3可知，ISOAL在僅有8 000次的評價次數(shù)內(nèi)，獲得的總代價比SOA降低了3.5%，彈簧的線圈直徑和平均直徑分別下降了5.7%和3.5%。

表3 算法在張力彈簧問題上的結(jié)果對比Table 3 Result comparison of design of tension/compression springs

表4為對比算法約束條件函數(shù)值。上述實驗結(jié)果表明，ISOAL能夠比較好地解決約束優(yōu)化問題，且具有良好的性能。

表4 彈簧設(shè)計問題的約束函數(shù)值對比Table 4 Comparison of constrained function values in design of tension/compression springs

4 結(jié)論

為了解決標準SOA算法內(nèi)部粒子之間缺少交流的問題，本文提出了一種具有學(xué)習(xí)機制的海鷗優(yōu)化算法ISOAL。該算法引入了基于粒子狀態(tài)差異的學(xué)習(xí)機制，使當(dāng)前粒子先向種群內(nèi)粒子的均值狀態(tài)學(xué)習(xí)，再搜索非沖突位置，執(zhí)行位置遷移，并將原參數(shù)A由線性遞減修改為非線性自適應(yīng)遞減方式，增強種群對解空間的全局搜索能力。為了提升算法的解精度，在后期引入精英反向?qū)W習(xí)，通過該機制加強對精英個體所在空間的勘探。在CEC2017和張力彈簧上的測試實驗表明，ISOAL不僅具有較快的收斂速度，還具有較好的解精度和魯棒性。

海鷗優(yōu)化算法出現(xiàn)時間較短，相應(yīng)的研究成果較少，下一步應(yīng)該加強對其收斂性能的研究。借鑒其他算法以改善SOA的性能，探索新的應(yīng)用領(lǐng)域也是未來主要的研究方向。