融合自適應(yīng)權(quán)重與Levy 飛行的拉丁超立方體海鷗優(yōu)化算法及應(yīng)用

梁靜

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴陽 550025）

0 引言

近年來，隨著群智能優(yōu)化算法的發(fā)展與應(yīng)用，越來越多的優(yōu)化算法也陸續(xù)得以提出，例如蜻蜓算法（Dragonfly algorithm，DA）［1］、蝴蝶優(yōu)化算法（butterfly optimization algorithm，BOA）［2］、灰狼優(yōu)化算法（Grey Wolf Optimization，GWO）［3］、水循環(huán)算法（Water Cycle algorithm，WCA）［4］、樽海鞘算法（Slap swarm algorithm，SSA）［5］、鯨魚優(yōu)化算法（Whale Optimization algorithm，WOA）［6］、黏菌優(yōu)化算法（Slime mould algorithm，SMA）［7］等。這些通過模仿自然界中生物規(guī)律來構(gòu)建不同搜索機制的群智能算法，被廣泛運用到各種優(yōu)化問題中去尋找最優(yōu)解或者次優(yōu)解。

Dhiman 等人［8］受海鷗遷徙行為以及遷徙過程中覓食行為的啟發(fā)，在2019 年提出海鷗優(yōu)化算法（Seagull optimization algorithm，SOA）。在SOA 算法中，海鷗的遷徙行為代表算法的全局搜索能力，覓食行為則代表算法的局部開發(fā)能力。該算法原理簡單，在工業(yè)問題以及分類問題上部署難度低。雖然SOA 算法在一些方面表現(xiàn)優(yōu)異，但是海鷗的群體覓食行為會降低算法的多樣性以及算法搜索能力，此外該算法還存在收斂速度慢，容易陷入局部最優(yōu)等缺陷。針對這些問題，文獻(xiàn)［9］引入記憶功能提高海鷗算法的搜索能力以及規(guī)避局部最優(yōu)的能力。文獻(xiàn)［10］利用混沌初始化、多方向飛行路徑等策略改進(jìn)算法，增加算法的多樣性與尋優(yōu)能力。文獻(xiàn)［11］引入自適應(yīng)t分布變異策略，提高算法跳出局部最優(yōu)的能力。文獻(xiàn)［12］使用Sigmoid函數(shù)與黃金正弦機制引導(dǎo)海鷗完成搜尋以及位置更新，提高算法的收斂速度和精度。

上述改進(jìn)策略對該算法的多樣性、尋優(yōu)精度以及收斂速度等方面均有一定的提升，為了進(jìn)一步提高該算法的性能并檢驗該算法在實際應(yīng)用中的效果，本文提出了融合自適應(yīng)權(quán)重與Levy 飛行的拉丁超立方體海鷗優(yōu)化算法。首先，采用拉丁超立方體抽樣的方法產(chǎn)生海鷗種群的初始位置，使海鷗種群在空間上分布更加均勻、避免碰撞，能夠加快海鷗尋找目標(biāo)的速度；其次，在海鷗遷徙階段引入自適應(yīng)權(quán)重因子，有利于算法在當(dāng)前位置使用精確的搜索策略，加快算法收斂；最后，在海鷗覓食階段使用Levy飛行策略［13］，使個體位置變化更加靈活多樣，提高算法的多樣性與跳出局部最優(yōu)的能力。本文使用23 個基準(zhǔn)測試函數(shù)和圖像分割問題檢驗改進(jìn)算法的效果，并將實驗結(jié)果與原算法以及其它優(yōu)化算法做比較，驗證了ALLSOA 算法的先進(jìn)性。

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

海鷗優(yōu)化算法是通過模擬海鷗2 個最重要的特征：遷徙和覓食而提出的算法。海鷗是群居生活動物，在季節(jié)更替時，海鷗會進(jìn)行遷徙活動。遷徙時海鷗會保證自己的位置與其它海鷗的位置不同，避免發(fā)生碰撞。海鷗是雜食動物，在覓食時會以螺旋形的運動形態(tài)攻擊其它候鳥。海鷗的遷徙行為與覓食行為可以用以下數(shù)學(xué)模型來表示。

1.1 遷徙

在該過程中，算法模擬海鷗從當(dāng)前位置移動到下一個位置。在移動過程中，海鷗會滿足3 個條件：避免碰撞，最佳位置方向，靠近最佳位置。

為了避免碰撞，算法通過添加變量A來計算海鷗的新位置。對此可表示：

其中，Cs（t）表示不與其它海鷗發(fā)生碰撞的新位置；Ps（t）表示海鷗當(dāng)前的位置；t表示當(dāng)前迭代數(shù)；fc表示控制A的頻率，取值為2；Maxiteration表示最大迭代次數(shù)。

滿足避免碰撞的條件之后，海鷗會向最佳位置方向運動。研究推出的數(shù)學(xué)公式可寫為：

其中，Ms（t）表示最佳位置方向；Pbs（t）表示海鷗的最優(yōu)位置；rd是［0，1］內(nèi)的隨機數(shù)。

在海鷗確定最佳位置方向后，就會向該方向移動，到達(dá)最佳位置。數(shù)學(xué)公式具體如下：

其中，Ds（t）表示海鷗的最佳位置。

1.2 覓食

海鷗在覓食過程中會以螺旋形運動狀態(tài)攻擊獵物，因此海鷗在x、y、z平面中的數(shù)學(xué)模型如下：

其中，r表示螺旋半徑；[0，2π] 是 [0，2π] 內(nèi)的隨機數(shù)；u為常數(shù)。

因此，海鷗覓食行為的數(shù)學(xué)描述為：

其中，Ps（t）表示海鷗當(dāng)前攻擊的位置；Ds（t -1）表示海鷗上一時刻的位置；Pbs（t -1）表示海鷗上一時刻的最優(yōu)位置。

2 融合自適應(yīng)權(quán)重與Levy 飛行的拉丁超立方體海鷗優(yōu)化算法

2.1 拉丁超立方體初始化

海鷗算法的初始化方法是在規(guī)定界限內(nèi)隨機生成海鷗的位置，這種初始化方法很容易導(dǎo)致海鷗個體在空間中分布不均，進(jìn)而影響算法的尋優(yōu)精度。為解決該問題，本文采用拉丁超立方體抽樣的方法初始化種群。

拉丁超立方體抽樣的關(guān)鍵是將輸入概率分布進(jìn)行分層，在每一層中抽取一個樣本。這樣可以保證海鷗初始位置的分布更加均勻，避免早熟。拉丁超立方體抽樣的步驟如下：

Step 1確定抽樣規(guī)模H，即海鷗種群規(guī)模。

Step 2將每個海鷗位置變量di的定義域區(qū)間劃分為H個相等的小區(qū)間，即：

Step 3生成H × n的矩陣A，其中每列均為數(shù)列1，2，…，H的隨機排序。

Step 4A的每行對應(yīng)一個超立方體，每個超立方體產(chǎn)生一個樣本。

初始化位置分布如圖1 所示。由圖1（a）可知，隨機初始化位置在上半部比較密集，下半部比較稀疏；圖1（b）中位置分布則比較均勻。因此可以得出，使用超立方體初始化種群相較于隨機初始化種群位置分布更為均勻，更有利于算法尋優(yōu)。

圖1 初始化位置分布圖Fig.1 Map of initializing the location

2.2 自適應(yīng)權(quán)重因子

在標(biāo)準(zhǔn)的海鷗算法中，海鷗的位置更新公式主要是由海鷗當(dāng)前位置、最佳方向與隨機參數(shù)組成。隨機參數(shù)的大小對算法的搜索能力、尋優(yōu)能力都有著較大的影響。因為當(dāng)該參數(shù)越大時，海鷗位置更新的步長越大，算法對全局搜索的能力越強；當(dāng)這個參數(shù)越小時，海鷗位置更新的步長越小，算法對局部的搜索能力越強。但是海鷗算法中該參數(shù)是隨機生成的，這將導(dǎo)致該算法在計算海鷗個體位置時盲目性較高，無法很好地分配算法在初期與末期的搜索能力。

針對該問題，本文在海鷗算法的群體行為中加入自適應(yīng)權(quán)重因子。在更新最佳位置方向時，使用自適應(yīng)權(quán)重因子代替海鷗算法中的隨機數(shù)。自適應(yīng)權(quán)重因子的數(shù)學(xué)表達(dá)式為：

在海鷗算法的位置更新中引入自適應(yīng)權(quán)重因子的個體位置更新公式為：

算法迭代開始時，自適應(yīng)權(quán)重因子最大，海鷗個體位置更新步長最大，代表算法此時的全局搜索能力最強。此后，自適應(yīng)權(quán)重因子隨著時間的增大而減小，海鷗個體位置更新步長逐漸減小，代表算法的局部搜索能力逐漸加強。

2.3 Levy 飛行

Levy 飛行模擬自然界中動物覓食的游走過程，并且服從萊維分布，是一種短距離搜索與長距離行走相間的飛行方式。這種飛行機制由法國數(shù)學(xué)家萊維提出，可以用來緩解海鷗算法早熟的問題以及增加算法的多樣性。Levy 飛行的數(shù)學(xué)表達(dá)式為：

其中，0＜φ≤2；D、G～N（0，υ）；Γ（x）是Gamma 函數(shù)；α表示步長；φ＝2／3。

使用Levy 飛行后的海鷗位置更新部分的公式更新為：

其中，rand為［0，1］之間的隨機數(shù)。

改進(jìn)后的位置更新公式，可以使海鷗的位置變化更加靈活，不僅增強算法的尋優(yōu)能力，還減少算法出現(xiàn)局部最優(yōu)的現(xiàn)象。

2.4 ALLSOA 算法步驟

結(jié)合上述改進(jìn)方法，本文研發(fā)的ALLSOA 算法偽代碼的設(shè)計表述見如下。begin設(shè)置初始參數(shù)：種群規(guī)模N，超參數(shù)fc，最大迭代次數(shù)Maxiteration獲取測試函數(shù)F的邊界與維度信息拉丁超立方體初始化種群，計算種群每個搜索代理的適應(yīng)度

2.5 時間復(fù)雜度計算

算法復(fù)雜度是算法運算速度的一種體現(xiàn)，也可以反映出算法的效率。在改進(jìn)算法時算法的時間復(fù)雜度如果變大，將會增加算法的運行時間，降低算法效率。在此，本文比較SOA 算法與ALLSOA 算法的時間復(fù)雜度。

SOA 算法的時間復(fù)雜度的組成部分是：隨機初始化參數(shù)O（1），計算適應(yīng)度O（N），迭代計算最優(yōu)值O（NT），則SOA算法的時間復(fù)雜度為：

其中，N為種群大小，T為迭代次數(shù)。

ALLSOA 算法的時間復(fù)雜度的組成部分是：拉丁超立方體初始化參數(shù)O（NT），計算適應(yīng)度O（N），迭代計算最優(yōu)值O（NT），自適應(yīng)權(quán)重因子O（NT），Levy 飛行O（NT），故ALLSOA 的時間復(fù)雜度如式（19）所示：

其中，N為種群大小，T為迭代次數(shù)。

綜上，本文改進(jìn)后的算法ALLSOA 時間復(fù)雜度與原算法相比未見增加，故ALLSOA 算法的改進(jìn)部分并未影響到算法的計算效率。

3 圖像分割

本文使用不同的智能算法對K-means 聚類算法［14］進(jìn)行優(yōu)化，并使用各算法的最優(yōu)解完成圖像分割任務(wù)。

K-means 聚類算法的主要思想是將給定的樣本集，按照樣本個體之間的距離大小將樣本劃分為規(guī)定的簇數(shù)，令簇內(nèi)的點盡量連接緊密，簇間距離盡量遠(yuǎn)。根據(jù)聚類中心分簇的度量方式為平方差：

其中，x（i）為樣本點；a（i）是與x（i）最相似的類別；yj為聚類中心。

使用智能算法優(yōu)化K-means 聚類算法進(jìn)行圖像分割的步驟為：

Step 1加載圖像，將圖像像素點轉(zhuǎn)化為樣本數(shù)據(jù)。

Step 2初始化簇心。

Step 3使用智能算法優(yōu)化K-means 聚類算法，更新簇心坐標(biāo)，計算樣本數(shù)據(jù)與簇心的距離，取距離最小簇心的類作為該樣本的類別。

Step 4計算更新后的簇心坐標(biāo)與當(dāng)前簇心坐標(biāo)的差距，若大于規(guī)定閾值，重復(fù)Step3，反之結(jié)束。

4 仿真實驗與結(jié)果分析

4.1 實驗環(huán)境與參數(shù)設(shè)置

本文實驗運行環(huán)境為：64 位Windows10 操作系統(tǒng)，Intel Corei5-7300HQ 的處理器，Matlab R2020b的仿真軟件。

為驗證ALLSOA 算法的性能與圖像分割效果，分別進(jìn)行了2 種實驗。實驗1 使用23 個基準(zhǔn)函數(shù)檢驗ALLSOA 的算法性能并與其它算法做比較；實驗2 使用圖像分割案例驗證ALLSOA 的先進(jìn)性，并與其它算法做比較。23 個基準(zhǔn)函數(shù)見表1，前7 個函數(shù)為單峰值函數(shù)，其余為多峰值函數(shù)。

4.2 算法性能對比實驗

為了檢驗本文算法的性能，本文選擇了不同的智能優(yōu)化算法：鯨魚優(yōu)化算法（WOA）、樽海鞘優(yōu)化算法（SSA）、標(biāo)準(zhǔn)海鷗優(yōu)化算法（SOA）以及改進(jìn)算法（ALLSOA）進(jìn)行對比實驗。為了提高實驗的準(zhǔn)確性，對每個智能優(yōu)化算法進(jìn)行30 次獨立實驗后，取實驗結(jié)果的平均值與標(biāo)準(zhǔn)差進(jìn)行對比。本次實驗設(shè)置參數(shù)為：種群規(guī)模N＝30，最大迭代次數(shù)T＝1 000。實驗結(jié)果見表2，加粗字體表示4 種算法求解的最優(yōu)解。

由表2 可知，ALLSOA 求解函數(shù)f1、f2、f7、f8、f15、f19的最優(yōu)值時，比其它優(yōu)化算法差一點。但是對于函數(shù)f8，ALLSOA 求解的最優(yōu)值精度雖差，但是標(biāo)準(zhǔn)差更小，算法更加穩(wěn)定。對于函數(shù)f15和f19，ALLSOA求解的最優(yōu)值與其它算法相差甚微，只是標(biāo)準(zhǔn)差稍大。

表2 測試結(jié)果Tab.2 Test results

對于單峰值函數(shù)f3～f6，ALLSOA 算法的尋優(yōu)能力明顯高于WOA、SSA 與SOA 算法，收斂精度更高。對于多峰值函數(shù)f9～f14，雖然只有函數(shù)f9和f11被ALLSOA 算法找到了最優(yōu)值，但是ALLSOA 算法求解得到值均為4 個算法中的最優(yōu)解，且明顯優(yōu)于SOA 算法求解值。例如f12函數(shù)，ALLSOA 算法的解比SOA 算法的解相差6 個數(shù)量級。對于函數(shù)f18，雖然4 個算法均找到了最優(yōu)值，但是ALLSOA 算法的標(biāo)準(zhǔn)差最小。對于函數(shù)f20～f23，ALLSOA 在尋優(yōu)精度與標(biāo)準(zhǔn)差均小于其它3 種算法，與SOA 算法相比有著大幅提升。

綜上，實驗結(jié)果表明ALLSOA 算法相比較其它算法有著較好的尋優(yōu)能力以及收斂精度，但是在某些函數(shù)上的表現(xiàn)并不比其它算法要更好，這也表示海鷗算法還有進(jìn)一步改進(jìn)的空間。

圖2 給出了ALLSOA 與其它3 種優(yōu)化算法在求解基準(zhǔn)函數(shù)最優(yōu)值時，隨著迭代次數(shù)的增長，其適應(yīng)值的變化曲線。從圖2 中可以看出，ALLSOA 算法在尋優(yōu)精度與收斂速度上均優(yōu)于其它算法。

圖2 算法收斂曲線圖Fig.2 Convergence curve of the algorithms

4.3 圖像分割對比實驗

將ALLSOA 算法應(yīng)用到圖像分割中，并與其它2 種算法做對比，實驗參數(shù)設(shè)置為：種群規(guī)模N＝30，最大迭代次數(shù)T＝50，簇心數(shù)Z＝3。

原圖與分割后的圖像如圖3 所示。從圖3 中可以明顯看出，ALLSOA 算法的分割效果最好，圖片中人物與景物的紋理最清晰，最能反映現(xiàn)實景象。

圖3 原圖與分割圖Fig.3 Original image and split images

為了進(jìn)一步驗證ALLSOA 算法在圖像分割中的性能，本文繪制3 種算法在分割過程中的收斂曲線如圖4 所示。

從圖4 中可以看出，ALLSOA 算法的尋優(yōu)能力與精度均高于其它算法，在迭代第10 次左右時接近收斂，且尋優(yōu)精度最高。另外，3 種算法的平均運行時間、最佳適應(yīng)度與初始聚類中心見表3。

圖4 WOA、SOA 與ALLSOA 收斂曲線Fig.4 Convergence curves of WOA，SOA and ALLSOA

由表3 得出，ALLSOA 適應(yīng)度值最低，雖然比WOA 慢0.06 s，但是ALLSOA 解出的最佳適應(yīng)度比WOA 低159.387，且聚類中心中沒有零值，聚類效果更好。

表3 算法運行結(jié)果Tab.3 Running results of the algorithms

綜合前文研究可知，通過基準(zhǔn)函數(shù)測試與圖像分割測試，均可以證明本文提出的ALLSOA 算法的性能對比其它算法有著較好的提升，具有更好的收斂速度和尋優(yōu)精度。

5 結(jié)束語

本文針對海鷗優(yōu)化算法（SOA）的各項不足，提出了融合自適應(yīng)權(quán)重與Levy 飛行的拉丁超立方體海鷗優(yōu)化算法（ALLSOA）。首先，在初始化時利用拉丁超立方體抽樣方法讓海鷗分布更加均勻，使海鷗更加容易找到最優(yōu)目標(biāo)；其次，在海鷗位置更新時引入自適應(yīng)權(quán)重因子，更好地控制算法的全局尋優(yōu)與局部搜索能力；最后，在海鷗的覓食階段使用Levy飛行策略，增加海鷗位置的靈動性，提升算法跳出局部最優(yōu)的能力。通過23 個基準(zhǔn)函數(shù)和圖像分割的仿真實驗結(jié)果表明，本文提出的算法具有更好的穩(wěn)定性、尋優(yōu)能力與收斂精度。

未來的研究方向是進(jìn)一步提升海鷗算法的收斂精度，并應(yīng)用于更多的工程問題當(dāng)中。