基于K-means聚類的麻雀搜索算法研究

方旺盛，趙如華，朱東林，王 沖

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

1 引言

麻雀搜索算法是2020年由JiankaiXue和BoShen提出的一種新型的仿生物群智能算法，根據(jù)麻雀覓食并躲避捕食者的行為而受啟發(fā)。由于該算法控制參數(shù)較少，實現(xiàn)簡單易懂，因此可應(yīng)用在微電網(wǎng)多目標(biāo)優(yōu)化、梯級水庫調(diào)度優(yōu)化、無人機邊緣檢測等領(lǐng)域，在解決一些工程問題時具有明顯優(yōu)勢，但該算法和許多群智能算法一樣仍存在極易陷入局部最優(yōu)和提早收斂問題。

針對群智能算法的缺陷，許多學(xué)者進行了深入研究，并取得了一定的成果。其中，張永和陳鋒學(xué)者針對鯨魚優(yōu)化算法(WOA)收斂速度慢、收斂精度低的問題，在提升性能的基礎(chǔ)上保留WOA的簡單性，提出一種改進的WOA，利用分段Logistic混沌映射產(chǎn)生混沌序列對種群位置進行初始化，以維持全局搜索時初始種群的多樣性?？紤]算法的非線性優(yōu)化過程和搜索過程中個體狀態(tài)的差異性，在WOA中引入非線性自適應(yīng)權(quán)重策略，以協(xié)調(diào)全局探索和局部開發(fā)能力。樊曉紅和萬仁霞學(xué)者在針對鳥群算法在尋優(yōu)后期極易陷入局部最優(yōu)和過早收斂的問題，提出一種基于聚合度改進的鳥群算法，通過引進種群相似度和聚集度的概念來描述鳥群在覓食過程的可行性搜索范圍。王曉東，張姣，薛紅學(xué)者為解決傳統(tǒng)K—means算法中因初始聚類中心選擇不恰當(dāng)而導(dǎo)致聚類結(jié)果陷入局部極值的問題，采用蝙蝠算法搜尋K-means算法的初始聚類中心，并將模擬退火的思想和基于排擠的小生境技術(shù)引入到蝙蝠算法中，以克服原始蝙蝠算法存在后期收斂速度慢、搜索力不強等問題麻雀算法通過位置來接近食物。為了解決存在麻雀搜索算法極易陷入局部最優(yōu)和提早收斂問題。本文采取k-means聚類的思想將種群初始聚類分化，結(jié)合麻雀算法較好的尋優(yōu)能力，使收斂速度得到了有效提升。

2 基本麻雀搜索算法

在麻雀覓食的過程中，分為探索者和追隨者，探索者在種群中負(fù)責(zé)尋找食物并為整個麻雀種群提供覓食區(qū)域和方向，而追隨者則是利用探索者指明的區(qū)域和方向來獲取食物。種群中的個體會監(jiān)視群體中其它個體的行為，并且該種群中的攻擊者會與高攝取量的同伴爭奪食物資源，以提高自己的捕食率。此外，當(dāng)麻雀種群受到捕食者的攻擊時會做出反捕食行為。通過仿照麻雀的這一系列行為，仿照麻雀的這些行為構(gòu)造數(shù)學(xué)模型，假設(shè)在維空間中有只麻雀進行種群覓食活動，在時刻第只鳥的位置，={，…，}表示設(shè)計了該算法進行函數(shù)最優(yōu)化求解，具體實現(xiàn)方式如下：

1)具有較好適應(yīng)度值的探索者在搜索過程中會優(yōu)先獲取食物。由于探索者是負(fù)責(zé)為整個麻雀種群尋找食物并為追隨者提供覓食的方向，所以探索者可以獲得比追隨者更大的覓食搜索范圍。對于追隨者在覓食過程中會時刻追隨并監(jiān)視探索者，這些追隨者會做出同探索者爭奪食物或者在探索者周圍覓食的行為。

在每次的迭代過程中，當(dāng)2<時，這表明此時的覓食環(huán)境周圍沒有捕食者，探索者可以執(zhí)行廣泛的搜索操作。此時探索者的位置更新公式為

(1)

其中代表當(dāng)前迭代數(shù)，是一個常數(shù)，表示最大的迭代次數(shù)。表示第個麻雀在第維中的位置信息。∈(0，1)是一個隨機數(shù)。(∈[0，1])和(∈[05，1])分別表示預(yù)警值和安全值。

當(dāng)2≥，這表示種群中的一些麻雀已經(jīng)發(fā)現(xiàn)了捕食者，并向種群中其它麻雀發(fā)出了警報，此時所有麻雀都需要迅速飛到其它安全的地方進行覓食。此時探索者的位置更新公式為

(2)

是服從正態(tài)分布的隨機數(shù)。表示一個1×的矩陣，其中該矩陣內(nèi)每個元素全部為1。

2)對于追隨者在覓食過程中會時刻追隨并監(jiān)視探索者，這些追隨者會做出同探索者爭奪食物或者在探索者周圍覓食的行為。

當(dāng)≤2時，此時追隨者在探索者周圍進行覓食的行為，此時追隨者的位置更新描述如下：

(3)

其中，是服從正態(tài)分布的隨機數(shù)，表示種群的維度，則表示當(dāng)前全局最差的位置。

當(dāng)>2時，此時代表著在種群中適應(yīng)度值較低的第個追隨者沒有獲得食物，需要飛往其它地方覓食，以獲得更多的能量。是目前發(fā)現(xiàn)者所占據(jù)的最優(yōu)位置，表示一個1×的矩陣，其中每個元素隨機賦值為1或-1，并且=()。此時追隨者的位置更新描述如下

(4)

3)當(dāng)整個麻雀種群收到捕食者攻擊時，處在種群最外層的麻雀更容易收到捕食者的攻擊，所以種群中的麻雀會不斷的調(diào)整位置來為自己獲得更優(yōu)的位置。與此同時，在種群中心的麻雀也會不斷的去接近與其相鄰的同伴，可以盡量避免它們處在危險區(qū)域。偵察預(yù)警的麻雀一般是占到種群的10到20左右，當(dāng)>表示此時的麻雀正處于種群的邊緣，比較容易受到捕食者的攻擊。其位置更新的數(shù)學(xué)表達式如下

(5)

=時，表示種群中間的麻雀收到了危險的信號，需要做出接近其它麻雀的反捕食行為。其位置更新的數(shù)學(xué)表達式如下

(6)

其中，其中是當(dāng)前的全局最優(yōu)位置。作為步長控制參數(shù)，是服從均值為0，方差為1的正態(tài)分布的隨機數(shù)。∈[-1，1]是一個隨機數(shù)，則是當(dāng)前麻雀個體的適應(yīng)度值。和分別是當(dāng)前全局最佳和最差的適應(yīng)度值。是最小的常數(shù)，以避免分母出現(xiàn)零。

為簡單起見，當(dāng)>表示此時的麻雀正處于種群的邊緣，比較容易受到捕食者的攻擊。當(dāng)=時，表示種群中間的麻雀收到了危險的信號，需要做出接近其它麻雀的反捕食行為。表示麻雀移動的方向同時也是步長控制參數(shù)。

3 K-means原理

K-means算法屬于一種經(jīng)典的無監(jiān)督的聚類算法。對于一個給定的樣本集，根據(jù)樣本之間的距離大小，將該樣本劃分為個簇，使得每個簇里的點盡量緊密的連在一起，并且讓每個簇之間的間隔盡量大。

如果用數(shù)據(jù)表達式表示樣本集={，…，}，k-means算法就是針對聚類劃分={，，…，}最小化平方誤差

(7)

步驟一：在數(shù)據(jù)集中隨機選擇聚類個數(shù)，生成個聚類初始中心；

步驟二：計算任意一個樣本點到個聚類中心的距離，根據(jù)遠(yuǎn)近聚類；

步驟三：利用均值等方法更新聚類中心，迭代聚類；

步驟四：若聚類中心變動很小(滿足收斂要求)或者達到迭代次數(shù)，則認(rèn)為達到穩(wěn)定狀態(tài)，迭代結(jié)束，對不同的聚類塊和聚類中心選擇不同的顏色標(biāo)注。

以此看出，K-means算法實現(xiàn)起來比較簡單且聚類效果也不錯，算法的可解釋度較強主要需要調(diào)節(jié)的參數(shù)僅僅是簇數(shù)K。但是該算法仍存在可改進的部分，對于K值的選取不好把握，最終結(jié)果和選的初始值有關(guān)，容易陷入局部最優(yōu)。

4 基于k-means的麻雀搜索算法

麻雀搜索算法雖較其它群體優(yōu)化算法有較好的全局搜索能力，但在局部搜索性能上還是較差，因其種群內(nèi)部分工較為復(fù)雜，導(dǎo)致迭代次數(shù)增加，且無意義的次數(shù)也在增加。k-means聚類算法在局部有較好的開采能力，適用于局部局部尋優(yōu)且計算簡單。兩者結(jié)合優(yōu)勢互補，在一定的程度上加快收斂，提升尋優(yōu)能力。在種群初始化時，群內(nèi)個體交流繁多，使得誤差增大，將種群進行K-means聚類，分類之后同屬于一類的群體之間先進行信息交互，且不受其它群體干擾，增大群體之間的容錯率，之后再進行信息匯總；同時有效躲避攻擊者的抓捕，從而提高個體的捕食率，增強尋優(yōu)能力和加大收斂速度，具體實現(xiàn)流程如下：

1)初始化種群位置、數(shù)量以及迭代次數(shù)，包括種群規(guī)模N，探索者個數(shù)p，偵察預(yù)警的麻雀個數(shù)s，目標(biāo)函數(shù)的維度D，最大迭代次數(shù)T。

2)通過引用3節(jié)中的k-means算法確定聚類中心數(shù)K，將種群聚類分化(注：聚類中心數(shù)K不宜過大，否者個體之間的距離較遠(yuǎn)，信息難以交互，呈現(xiàn)負(fù)效果，K隨種群數(shù)量增大而增大)。

“完成黨的十九大提出的目標(biāo)任務(wù)，必須充分發(fā)揮工人階級主力軍作用?！?0月29日，習(xí)近平總書記在同中華全國總工會新一屆領(lǐng)導(dǎo)班子成員集體談話并發(fā)表重要講話時指出，我國廣大職工要牢牢把握為實現(xiàn)中國夢而奮斗的時代主題，把自身前途命運同國家和民族前途命運緊緊聯(lián)系在一起，把個人夢同中國夢緊密聯(lián)系在一起，把實現(xiàn)黨和國家確立的發(fā)展目標(biāo)變成自己的自覺行動，愛崗敬業(yè)、爭創(chuàng)一流，以不懈奮斗書寫新時代華章，共同創(chuàng)造幸福生活和美好未來。

3)計算每只麻雀的適應(yīng)度fi，選出當(dāng)前最優(yōu)適應(yīng)度fb和其所對應(yīng)的位置Xb，以及當(dāng)前最劣適應(yīng)度fw和其對應(yīng)的位置Xw。

4)選取適應(yīng)度優(yōu)的前p個麻雀作為探索者，剩余的作為追隨者者，當(dāng)R2n/2時，根據(jù)式(4)更新追隨者的位置。

5)從麻雀種群中隨機選取s只麻雀進行偵察預(yù)警，當(dāng)fi>fg時，根據(jù)式(5)更新其位置，當(dāng)fi=fg時，根據(jù)式(6)更新其位置。

6)判斷是否達到迭代次數(shù)或者求解精度。否，則回到4)步。是，則進行下一步。

7)輸出最佳尋優(yōu)結(jié)果。

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

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

算法在Window1064bit系統(tǒng)上運行，內(nèi)存為8GB。算法的種群規(guī)模為20、迭代次數(shù)為1000次，聚類中心數(shù)K=5，采用MATLAB R2018b進行仿真。

5.2 基準(zhǔn)測試函數(shù)

本文選擇了10個典型的基準(zhǔn)測試函數(shù)如表一所示進行仿真來進行評估KSSA的尋優(yōu)能力。10個基準(zhǔn)測試函數(shù)分為2組，前5個是固定維度30來優(yōu)化測試，且單峰函數(shù)與多峰函數(shù)各一半，后5個是不同維度的維優(yōu)化測試，這樣不僅可以用來驗證算法的收斂速度和收斂精度，也可以用來驗證算法的全局尋優(yōu)能力和局部最優(yōu)規(guī)避能力。

表1 基準(zhǔn)函數(shù)

在實驗時，保證4種智能算法種群搜索個體的數(shù)目Num和迭代最大次數(shù)Num均保持一致，各組實驗均分別獨立進行30次實驗，并取30次實驗最優(yōu)目標(biāo)值的平均值(ave)、標(biāo)準(zhǔn)方差(std)、最大值(max)、最小值(min)等4項指標(biāo)作為性能評價依據(jù)，實驗統(tǒng)計結(jié)果見表2。

表2 基準(zhǔn)函數(shù)優(yōu)化結(jié)果比較

由表2統(tǒng)計結(jié)果可知，KSSA算法在、、在精度和收斂要略高于其它算法，盡管最優(yōu)值和接近，但穩(wěn)定性和全局性要比SSA好，且F、F4、F8測試函數(shù)上，KSSA表現(xiàn)突出的尋優(yōu)性能，這充分說明加快了種群的個體之間信息交流使得尋優(yōu)速度和精度大大提升。、、在尋優(yōu)效果上并不顯著，但不會低于SSA，這說明SSA算法在此函數(shù)上尋優(yōu)效果已接近峰值。

5.3 算法收斂分析

F-F的收斂如圖1所示。為了使實驗結(jié)果更加可觀，可以選擇對目標(biāo)函數(shù)值進行l(wèi)og變換。

從單峰函數(shù)的收斂圖可以看出，基于K-means的麻雀搜索算法KSSA在收斂速度上明顯快于其它算法，同時KSSA算法的收斂速度相比于其它算法也有著較大的優(yōu)勢。

當(dāng)測試函數(shù)為單峰時，K-means算法的精準(zhǔn)快速尋得最優(yōu)值的效果較好。當(dāng)測試函數(shù)為多峰以及變維度多峰函數(shù)時，引入K-means策略能有效地防止算法陷入局部最優(yōu)，能夠更穩(wěn)定地尋找全局最優(yōu)值。同時，由F和F可以看出，基于K-means的麻雀搜索算法KSSA在單峰函數(shù)的收斂速度更快。

圖1 F1一F10的收斂

根據(jù)11個測試函數(shù)的實驗結(jié)果進行綜合比較，從ave指標(biāo)來看改進之后的KSSA算法無論是在收斂速度和收斂精度還是對高維單/多峰基準(zhǔn)測試函數(shù)均表現(xiàn)較強的平均尋優(yōu)性能都明顯強于其它3種算法，同時KSSA算法還具有在最優(yōu)目標(biāo)尋找過程中具有較高的算法平穩(wěn)性或較小的波動差異性，有利于解決實際生活中的尋找最優(yōu)值問題。KSSA算法在30次統(tǒng)計結(jié)果中仍尋得較好的min目標(biāo)值，展現(xiàn)出KSSA算法較強的局部極值規(guī)避性與良好的全局尋優(yōu)能力，在一定程度上有利于減少實際優(yōu)化應(yīng)用中的潛在風(fēng)險與損失等。

6 基于KSSA的SVM參數(shù)優(yōu)化

6.1 SVM原理及相關(guān)參數(shù)

SVM(SupportVectorMachine)的主要思想是估計一個模型，在這個模型中，應(yīng)該找出能夠分離數(shù)據(jù)的最佳超平面。如果訓(xùn)練數(shù)據(jù)可以達到完美的可分性，則可以使用硬裕度最優(yōu)。在這種情況下，選擇超平面決策邊界，使超平面到最近的訓(xùn)練數(shù)據(jù)點的距離最大。在非線性分類的情況下，超平面仍然是邊界，不同的是，超平面在特征空間而不是原始輸入中。SVM的決策邊界是對訓(xùn)練數(shù)據(jù)求解的最大邊距超平面?；驹砣缦拢杭僭O(shè)有一組訓(xùn)練樣本，其中，是n維文本向量，是分類標(biāo)簽，用來表示的所屬類別。在二元線性分類中，分類標(biāo)簽有兩個值，1和-1。SVM 先通過一個分類超平面分割兩個不同類別的樣本，盡可能的使不同種類間的間隔最大以獲得最優(yōu)的分類效果。將其用于不等式約束條件下的二次規(guī)劃求解

(8)

式中，為懲罰函數(shù)；為松弛變量。針對不等式約束條件下求解困難的問題，引進Lagrange乘子，則得出如下的對偶形式

(9)

在非線性的情況下，引入核函數(shù)映射

(，)=(()，())

將式轉(zhuǎn)化為

(10)

由式推導(dǎo)，得到?jīng)Q策函數(shù)如下

(11)

式中，為基本符號函數(shù)；(，)為和函數(shù)；由二次規(guī)劃確定；為訓(xùn)練樣本數(shù)；為閾值，其大小由訓(xùn)練樣本確定。

當(dāng)今幾種比較常用的核函數(shù)表達形式有柯西核函數(shù)、多項式核函數(shù)、徑向基核函數(shù)、線性核函數(shù)等。因徑向基核函數(shù)(RBF)有較強的學(xué)習(xí)能力且泛化能力優(yōu)越，在多種情況下具有良好的適應(yīng)性，所以應(yīng)用比較廣泛，本文同樣采取RBF，具體表達式如下：

(12)

SVM中C的作用為控制模型復(fù)雜度及模型逼近誤差的折衷，C越大對數(shù)據(jù)的擬合程度越高，但泛化能力降低。參數(shù)g為核函數(shù)的寬度參數(shù)，控制了函數(shù)的徑向作用范圍。當(dāng)g越大，投影空間復(fù)雜度越小，數(shù)據(jù)的線性可分的程度也越??；反之，當(dāng)g越小，投影空間的復(fù)雜度越大，甚至趨向于無窮，雖然能將樣本數(shù)據(jù)映射為高維線性可分，但是會導(dǎo)致嚴(yán)重的過擬合問題。因此，SVM優(yōu)化的效果主要取決于這兩個參數(shù)的選擇，采用較好的優(yōu)化算法進行參數(shù)選擇，才能更好地發(fā)揮SVM的分類性能。

6.2 案例數(shù)據(jù)

本文采用是UCI數(shù)據(jù)庫中的wine數(shù)據(jù)，該數(shù)據(jù)來源于在同一區(qū)域內(nèi)三種不同葡萄酒的化學(xué)成分。數(shù)據(jù)包含178個均含有13個特征分量的樣本，且每個樣本的類別標(biāo)簽均已標(biāo)注。隨機選取這178個樣本中的89個樣本作為測試集，剩下的89個樣本作為訓(xùn)練集，先用訓(xùn)練集對優(yōu)化的SVM進行訓(xùn)練得到分類模型，再用測試集得到的分類模型對測試集的數(shù)據(jù)進行類別標(biāo)簽預(yù)測。

圖2 wine數(shù)據(jù)的box可視化圖

圖3 樣本

6.3 實現(xiàn)結(jié)果

KSSA算法的實驗參數(shù)與上面一致，圖4為最好分類下的預(yù)測情況圖。

圖4 最好分類下的預(yù)測情況圖

通過實驗得到的結(jié)果可以看出有一個標(biāo)簽沒有成功分類，因此預(yù)測概率為98.8674%。為了進一步證明其有效性，本次將遺傳算法(GA)，粒子群算法(PSO)及基本麻雀搜索算法優(yōu)化SVM模型進行對比實驗，實驗參數(shù)一致，各算法獨立運行十次，計算平均準(zhǔn)確率，最優(yōu)準(zhǔn)確率及最差準(zhǔn)確率，三個指標(biāo)可以有效的看出各算法優(yōu)化SVM參數(shù)的穩(wěn)定性及優(yōu)良性。

表3 各算法優(yōu)化情況表

從表中可以看出，KSSA-SVM模型在三個指標(biāo)上最優(yōu)，SSA-SVM模型預(yù)測精度沒有達到最優(yōu)，但穩(wěn)定性僅此于KSSA-SVM模型，PSO-SVM模型雖能達到98.8674%的預(yù)測效果，但預(yù)測結(jié)果不穩(wěn)定，最差達到了57.3034%，GA-SVM在各項指標(biāo)上都處于最低地位，預(yù)測精度不夠且穩(wěn)定性差。

7 結(jié)論

1) 通過將最新提出的麻雀搜索算法與K-means聚類算法融合，提出一種KSSA算法，即將K-means算法良好的聚類分化特性及麻雀搜索算法較好的尋優(yōu)能力相結(jié)合，使得種群內(nèi)部工作交流效率高，擺脫種群隨機復(fù)雜的工作交流，提高算法的尋優(yōu)效率和優(yōu)化性能，準(zhǔn)確且迅速的尋求最優(yōu)值?；鶞?zhǔn)測試函數(shù)實驗表明改進算法提高了尋優(yōu)精度及尋優(yōu)速度，并使算法后期能有效地跳出局部最優(yōu)，提高了麻雀群體的搜索能力，突出改進策略的有效性和可行性。

2) 將改進后的KSSA算法優(yōu)化SVM參數(shù)得到KSSA-SVM，通過各類算法優(yōu)化對比，可以看出KSSA-SVM模型具有較好的穩(wěn)定性，且預(yù)測精度較高，這充分說明KSSA尋優(yōu)性能較好。

3) 文中從更新種群的角度改善了麻雀搜索算法的尋優(yōu)性能，但改進算法只能在低維空間展現(xiàn)較好的尋優(yōu)效果，對高維還是個重點研究方向，今后在高維以及疾病診斷中有著較大的研究前景。