融合聚類算法的改進麻雀搜索算法

歐陽城添，朱東林，邱亞嫻

(江西理工大學，江西 贛州 341000)

1 引言

近年來，隨著各種優化問題被提出，對應著優化算法被逐漸開采，意在解決各種工程復雜問題。麻雀搜索算法是在2020年提出來的新型群智能優化算法。該算法受麻雀覓食等行為啟發，在優化問題上較粒子群(Particle Swarm Optimization，PSO)、灰狼算法(Grey Wolf Algorithm，GWO)、遺傳算法(Genetic Algorithm，GA)等傳統的智能優化算法有著明顯的優勢。但其同樣存在陷入局部最優的概率且尋優結果具有較大的隨機性。

對此，許多學者針對麻雀搜索算法的缺陷提出不同的方案改進，并成功地應用在工程問題上。呂鑫[2]等學者提出一種混沌麻雀搜索算法(CSSA)，首先采用基于隨機變量的tent映射初始化種群，使得種群分布均勻，再使用混沌擾動及高斯變異防止算法在尋優過程中出現麻雀個體局部聚集，出現陷入局部最優的現象；最后將改進的算法應用于圖像分割，并取得了良好的效果；毛清華[3]等學者提出了一種融合柯西變異和反向學習的麻雀搜索算法，采用sin混沌初始化種群，再在發現者位置更新公式中移入上一代的全局最優解，同時也引入了自適應權重策略，平衡了局部與全局搜索能力，最后在最優解位置融合柯西變異與反向學習策略，增強算法跳出局部最優的能力，在8個標準測試函數上驗證了此算法的有效性。湯安迪[4]等學者提出了一種基于混沌麻雀搜索算法的航跡規劃方法。首先，該算法采用立方映射初始化種群，并使用反向學習策略保證了種群的均勻性。再采用精英反向學習策略擴大精英反向解的搜索區域，在追隨者位置更新上引入正余弦算法，增加了種群多樣性，最后對警戒線數量進行線性衰減，平衡了算法全局性與局部性搜索。通過15個標準測試函數證明了該算法的優越性，同時在有威脅的情況下進行路徑規劃仿真，與其它優化算法相比，驗證了該算法的實用性。這些改進的算法均有一定的成效，但初始化種群方法依然存有一定的隨機性，不能保證每次迭代之后的分布都是均勻的，在尋優過程中采用的策略具有區域局限性，未能在整個空間內進行全局搜索，這樣依然存在陷入局部最優的概率。

在總結前人的工作上，本文提出融合聚類算法的改進麻雀搜索算法(KDLSSA)，起初利用K-medoids動態更新種群個體位置，保證了種群的均勻性與多樣性，再引入基于重心的反向學習策略，彌補了一般學習策略沒有充分利用種群空間的情況，使發現者具有廣闊的搜索范圍且防止過早的收斂，最后在追隨者引入自適應余弦權重策略保證了算法具有細致且靈活的搜索能力，平衡了算法全局性與局部性搜索。在8個測試函數上驗證了改進算法的有效性及實用性。

2 麻雀搜索算法

在麻雀覓食的過程中，分發現者和追隨者兩個行為策略。發現者一般為種群數量的0.2，是種群個體的引導者，它帶領著其它個體進行食物的尋找，因此發現者具有廣闊的搜索范圍。發現者的位置更新公式如下

(1)

式(1)，h表示當前的迭代次數，M為最大的迭代次數。Xi，j表示當前第i個麻雀在第j維中的位置。α∈[0，1]，且是一個隨機數。R2和ST分別代表預警值和安全值，且R2∈[0，1]、ST∈[0.5，1]。Q是一個正態分布的隨機數。L表示一個元素全為1的1×d的矩陣。當R2

追隨者為了獲取優質食物，緊隨發現者之后，其中部分追隨者會監督發現者及和捕食率較高的發現者爭奪食物，從而提高自身的營養。

追隨者的位置更新描述如下

(2)

式(2)中，Xp是發現者當前所占據的最優位置，Xworst表示當前的最壞位置。A為一個元素僅是1或-1的1×d的矩陣，其中A+=AT(AAT)-1。當i>n/2時，這時當意識到危險時，麻雀種群會做出反捕食行為，其數學表達式如下

(3)

式(3)中，Xbest是當前的全局最優位置。β為控制步長參數，是服從均值為0且方差為1的正態分布的隨機數。K∈[-1，1]是一個隨機數，fi表示當前麻雀個體的適應度值。fg和fw分別當前搜索范圍內最優及最劣適應度值。ε為最小的實數，防止分母出現0的情況。當fi≠fg表示當前的麻雀處在種群的邊界，容易受捕食者的攻擊，需要調整位置。fi=fg時，這表明處于種群內部的麻雀個體意識到了危險，為躲避危險，需要靠近其它麻雀的位置，K代表麻雀移動的方向同時也可以控制移動步長。

3 改進的麻雀搜索算法

3.1 K-medoids聚類算法

麻雀搜索算法尋優能力較好，但每次尋優結果存在較大的隨機性，依賴于初始化種群的麻雀個體的位置，因此每次得到最優解的穩定性較差。本文采用經典聚類算法K-medoids對種群進行動態分割，將麻雀個體進行分類聚化，在初期階段進行個體分類，減小初期工作的復雜性，加快了信息交流，之后隨著迭代次數變化而變化，提高了種群的多樣性，在一定程度上減小了陷入局部最優的概率。

K-medoids算法是目前運用范圍較廣的聚類方法，具有對數據敏感性強且魯棒性好等優點。與K-means算法相似，兩種算法的差異在于聚類中心數的選取，K-means算法是將當前簇中所有個體的平均值作為聚類中心點，但這點存在不可靠性，若該點不是當前最優點附近會有誤導性，反而增加了無用功，K-medoids算法是直接選取當前簇中的一個個體作為聚類中心點，且要滿足簇中其它所有點到這個個體的距離最短，這樣使得聚類中心點具有代表性。具體K-medoids聚類過程如下：

Step1：從麻雀種群中隨機選擇K個個體作為初始聚類中心點。

Step2：計算其它個體到各個聚類中心的距離，根據距離最小原則，將各麻雀個體劃分到最近的簇內。

Step3：計算每個簇內所有個體的均值，根據距離最小原則，選取離均值點最近的個體作為聚類中心。

Step4：不斷重復step2，直到最大迭代次數進行終止。

3.2 基于重心的反向學習策略

發現者在整個尋優過程中起著引領作用，因此發現者必須有著廣闊且靈活的飛行方式，它的尋優質量直接影響著算法的收斂速度與最優解的質量。在麻雀搜索算法中，發現者有其自身的飛行方式，但在尋優效率及質量上難以保障，一旦陷入局部極值狀態就會限制算法的整體性能。反向學習是評估當前解與反向解加速搜索進程的一種技術。一般的反向學習策略在智能優化算法上取得了較好的效果，但一般的學習策略僅僅在部分空間上進行反向搜索，針對此問題，本文引入基于重心的反向學習策略，彌補了其沒有充分利用整個種群空間的能力，使算法在整個空間內動態變化，加快了個體搜索效率，能夠全面探索整個空間，維持種群多樣性，極大地提升了算法的尋優能力。

定義1重心：設(X1，X2，…，Xn)是D維空間中帶有質量的n個點，那么整體的重心為

(4)

定義2重心方向點：若一個離散均勻的整體的重心為M，則M中某一點Xi的反向點為

(5)

反向點存在于一個具有動態邊界的搜索空間，記為Xi，j∈[aj，bj]動態邊界的表達式為

aj=min(xi，j)，bj=max(xi，j)

(6)

若反向點超出規定邊界時，需按式(7)重新計算反向點

(7)

采用基于重心的反向學習策略拓寬了麻雀個體飛行的區域，提高了種群的工作效率，在復雜函數尋優時具有良好的突變性，擺脫局部極值的吸引。

3.3 自適應余弦慣性權重

追溯者緊跟發現者尋找優質解，這樣導致其具有盲目性且喪失獨立性，智能優化算法循規蹈矩的尋優存在一定局限性，因此采用動態調節的方法進行靈活尋優，本文在追隨者位置更新階段引入自適應余弦權重策略，動態調節當前當前個體對下一代個體尋優的影響，從而提升了追隨者的尋優手段。引入自適應余弦權重的追隨者更新公式如下

(8)

(9)

(10)

上述式中，wmax與wmin分別為最大權重與最小權重；Sstop為停止閾值，本文為常數0.001，用來減小算法在迭代中重復計算w的頻度。

引入自適應余弦函數慣性權重，使得追隨者搜索隨著迭代次數而變化，余弦函數提高了追隨者階段的靈活性，搜索變得更加細致，同時在中期防止陷入局部最優，后期增大了收斂精度。

3.4 改進的麻雀搜索算法流程

本文提出的融合聚類算法的改進麻雀搜索算法，首先采用K-medoids初始化種群，動態分布每個麻雀個體的位置，提高了算法的種群多樣性，再引入基于重心的反向學習策略，使得發現者的位置搜索具有廣闊性，充分利用到了整個給定空間，在一定程度上防止了算法陷入局部最優，再提出了一種自適應余弦慣性權重，使得追隨者個體具有靈活性，改善了其具有盲目性的缺陷，前期增大了算法的收斂速度，后期提高了其搜連精度。多種策略的引入使得算法在尋優能力上具有較好的靈活性，平衡了算法全局性搜索能力與局部性搜索，找到可靠解。具體算法流程如下：

1)初始化參數。設置種群規模、迭代次數及初始聚類中心數K。

2)根據聚類算法K更新化麻雀個體的位置。

3)計算適應度函數。得出最小及最大適應度值。

4)從部分麻雀個體中選擇發現者，并按式(5)～(7)更新發現者的為位置。

5) 根據式(8)更新追隨者的位置。

6)根據式(3)更新意思到危險的麻雀位置。

7)判斷是否達到迭代次數，是則進行下一步，否則跳轉步驟2)

8)算法結束，輸出最優值及對應位置。

4 實驗結果與分析

4.1 參數及環境設置

本文選取個標準測試函數對改進的麻雀搜索算法進行對比實驗，將PSO，GWO，SSA，CSSA，KSSA算法加入本實驗進行試驗對照，CSSA算法式來自文獻[5]，KSSA算法采用K-means動態更新種群，且其它策略與KDLSSA算法不變，種群數量為50，迭代次數為200，K設定為5。在SSA及其變體中，發現者及偵察者的比例均為0.2，其它算法的通用參數保持一致，標準測試函數如表1，采用8個不同類型函數來驗證改進算法的可行性，前四個函數為單峰函數，中間三個函數為復雜多峰函數，最后一個為易陷入局部最優的固定維度函數。為了使實驗效果更具說服力，將各算法獨立運行30次，統計各自的最優值、平均值及標準差。三個指標用來衡量各算法的穩定性及尋優能力。各算法運行結果如表2。

表1 測試函數表

表2 各算法性能測試表

從表2來看，KDSSA較其它優化算法具有顯著的尋優能力。在單峰函數上，KDLSSA存在較好的收斂精度，特別在F1與F3函數中，KDLSSA算法可以直接找到最優值，在多峰函數上，KDLSSA存有較好的抗局部極值吸引能力，在尋優效果上有著明顯的改善，在F5與F6函數中，KSSA也同樣有著較好的收斂能力，但其穩定性較差，在F8函數上中，各算法都能找到最優值，但各算法穩定性較差，KDLSSA的標準差值最小，具有較高的穩定性。綜上所述，多種策略的引入使得算法在尋優效率上有者明顯的提升，且擺脫了原算法尋優機制的束縛，找到質量更高的解。

4.2 收斂性分析

為了更好地描述各算法在各函數中的尋優軌跡，畫出各算法的平均收斂曲線如圖1所示。

圖1 各算法平均收斂曲線

如圖1內容可看出，KDLSSA算法具有較好的收斂效果，在F1-F3及F6函數中，KDLSSA與KSSA的收斂精度差異不大，但KDLSSA收斂速度較快，在其它函數中，KDLSSA與其它改進的麻雀搜索算法的尋優差異不大，但有較快的收斂效果。綜上所述，K-medoids聚類算法的引入較K-means算法具有較好的尋優推動能力，在基于重心的反向學習策略與自適應余弦權重的引入下，使得算法在廣闊的空間內執行廣泛而細致的搜索，提高了算法的收斂能力，同時也在尋優效率上得到顯著的提升。

5 結束語

在目前眾多改進的麻雀搜索算法依然存在陷入局部最優且收斂速度較慢的基礎上，本文提出融合聚類算法的改進麻雀搜索算法，該算法初期采用K-medoids聚類算法對麻雀種群進行動態更新，防止過早收斂且加快了初期尋優效率，其次在發現者階段引入基于重心的反向學習策略，擺脫了一般反向學習策略僅在有限的空間內進行搜索的弊端，提高了算法的全局性搜索，最后在追隨者階段引入自適應余弦權重策略，使得追隨者擺脫自身的盲目性搜索，且搜索變得廣泛而細致，平衡了局部與全局性搜索。通過8個不同類型的標準測試函數，證明了改進的麻雀搜索算法KDLSSA比其它算法的優化能力更佳，在尋優效率上也更勝一籌。但在高維復雜情況下，KDLSSA算法僅在收斂速度上比較顯著，而收斂精度上沒有得到顯著的提升。在后期，如何使得算法在復雜函數下平衡收斂速度與收斂精度是往后研究的重點。