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

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

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

1 引言

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

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

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

2 麻雀搜索算法

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

(1)

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

追隨者為了獲取優(yōu)質(zhì)食物，緊隨發(fā)現(xiàn)者之后，其中部分追隨者會監(jiān)督發(fā)現(xiàn)者及和捕食率較高的發(fā)現(xiàn)者爭奪食物，從而提高自身的營養(yǎng)。

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

(2)

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

(3)

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

3 改進的麻雀搜索算法

3.1 K-medoids聚類算法

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

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

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

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

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

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

3.2 基于重心的反向?qū)W習策略

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

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

(4)

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

(5)

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

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

(6)

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

(7)

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

3.3 自適應余弦慣性權(quán)重

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

(8)

(9)

(10)

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

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

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

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

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

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

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

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

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

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

7)判斷是否達到迭代次數(shù)，是則進行下一步，否則跳轉(zhuǎn)步驟2)

8)算法結(jié)束，輸出最優(yōu)值及對應位置。

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

4.1 參數(shù)及環(huán)境設置

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

表1 測試函數(shù)表

表2 各算法性能測試表

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

4.2 收斂性分析

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

圖1 各算法平均收斂曲線

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

5 結(jié)束語

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