融合自適應權重與Levy 飛行的拉丁超立方體海鷗優化算法及應用

梁靜

（貴州大學 大數據與信息工程學院，貴陽 550025）

0 引言

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

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

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

1 海鷗優化算法

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

1.1 遷徙

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

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

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

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

其中，Ms（t）表示最佳位置方向；Pbs（t）表示海鷗的最優位置；rd是［0，1］內的隨機數。

在海鷗確定最佳位置方向后，就會向該方向移動，到達最佳位置。數學公式具體如下：

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

1.2 覓食

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

其中，r表示螺旋半徑；[0，2π] 是 [0，2π] 內的隨機數；u為常數。

因此，海鷗覓食行為的數學描述為：

其中，Ps（t）表示海鷗當前攻擊的位置；Ds（t -1）表示海鷗上一時刻的位置；Pbs（t -1）表示海鷗上一時刻的最優位置。

2 融合自適應權重與Levy 飛行的拉丁超立方體海鷗優化算法

2.1 拉丁超立方體初始化

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

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

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

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

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

Step 4A的每行對應一個超立方體，每個超立方體產生一個樣本。

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

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

2.2 自適應權重因子

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

針對該問題，本文在海鷗算法的群體行為中加入自適應權重因子。在更新最佳位置方向時，使用自適應權重因子代替海鷗算法中的隨機數。自適應權重因子的數學表達式為：

在海鷗算法的位置更新中引入自適應權重因子的個體位置更新公式為：

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

2.3 Levy 飛行

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

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

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

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

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

2.4 ALLSOA 算法步驟

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

2.5 時間復雜度計算

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

SOA 算法的時間復雜度的組成部分是：隨機初始化參數O（1），計算適應度O（N），迭代計算最優值O（NT），則SOA算法的時間復雜度為：

其中，N為種群大小，T為迭代次數。

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

其中，N為種群大小，T為迭代次數。

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

3 圖像分割

本文使用不同的智能算法對K-means 聚類算法［14］進行優化，并使用各算法的最優解完成圖像分割任務。

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

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

使用智能算法優化K-means 聚類算法進行圖像分割的步驟為：

Step 1加載圖像，將圖像像素點轉化為樣本數據。

Step 2初始化簇心。

Step 3使用智能算法優化K-means 聚類算法，更新簇心坐標，計算樣本數據與簇心的距離，取距離最小簇心的類作為該樣本的類別。

Step 4計算更新后的簇心坐標與當前簇心坐標的差距，若大于規定閾值，重復Step3，反之結束。

4 仿真實驗與結果分析

4.1 實驗環境與參數設置

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

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

4.2 算法性能對比實驗

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

由表2 可知，ALLSOA 求解函數f1、f2、f7、f8、f15、f19的最優值時，比其它優化算法差一點。但是對于函數f8，ALLSOA 求解的最優值精度雖差，但是標準差更小，算法更加穩定。對于函數f15和f19，ALLSOA求解的最優值與其它算法相差甚微，只是標準差稍大。

表2 測試結果Tab.2 Test results

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

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

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

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

4.3 圖像分割對比實驗

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

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

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

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

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

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

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

表3 算法運行結果Tab.3 Running results of the algorithms

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

5 結束語

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

未來的研究方向是進一步提升海鷗算法的收斂精度，并應用于更多的工程問題當中。