基于權值分配策略的聚類天牛群優(yōu)化算法

郭曉語， 高 鷹， 李 寧， 周燦基， 嚴基杰

(廣州大學 計算機科學與網絡工程學院， 廣州 510006)

0 引 言

智能優(yōu)化算法是通過模擬某一自然現象或過程而建立起來的元啟發(fā)式算法，與傳統(tǒng)的數學規(guī)劃法相比，其依靠簡單的規(guī)則和隨機性可以實現復雜的多峰極值問題求解。對初始方案的弱依賴性以及不需要提供梯度信息等方面，成功地彌補了傳統(tǒng)優(yōu)化算法的不足，為復雜優(yōu)化問題提供了一種全新的解決方法，眾多文獻都已證明智能優(yōu)化算法在函數尋優(yōu)上的高效性。目前，流行的智能優(yōu)化算法包括：模擬鳥群覓食的粒子群優(yōu)化算法(PSO)[1]、源于螞蟻釋放信息素行為的蟻群優(yōu)化算法(ACO)[2]、受蜂群行為啟發(fā)的人工蜂群算法(ABC)[3]，以及以化學物質的冷卻和結晶為基礎的模擬退火算法(SA)[4]等等。

天牛群優(yōu)化算法(Beetle Swarm Optimization Algorithm，BSO)[5]是2018年由Wang等人提出的一種混合型智能優(yōu)化算法。BSO算法借鑒粒子群優(yōu)化算法的思想，將天牛須搜索算法(Beetle Antennae Search Algorithm，BAS)[6]從單體智能轉變?yōu)槿后w智能，保留了所需調整參數少的優(yōu)點，同時一定程度上改善了BAS算法在多峰函數上尋優(yōu)表現不佳的問題。目前，已有許多BSO算法的應用案例。如：三維路徑規(guī)劃[7]、投資組合[8]、蓄電負荷控制[9]等。盡管BSO算法提出時間不久，但卻吸引了眾多研究人員對其進行改進。其中，胥松奇等[10]為強化天牛左右須的探測行為，提出了量子天牛群算法(QBSO)，使得天牛個體在量子空間和實體空間中同時搜尋食物,以提高算法的收斂能力；Yang等[11]通過在速度更新公式中引入自適應變異因子，提出自適應變異甲蟲群優(yōu)化算法(MBSO)，以防算法過早收斂并提高算法多樣性；王永貴等[12]提出引入變異策略的混沌天牛群搜索算法(CMBSOA)，將混沌映射用于算法種群初始化階段，以達到個體均勻分布的效果，并在位置更新上引入變異因子來增加算法跳出局部最優(yōu)解的概率。

鑒于BSO算法存在收斂過快、精度低且在多峰問題上易陷入局部最優(yōu)解的問題，本文提出了一種基于權值分配策略的聚類天牛群優(yōu)化算法(K-means Clustering Beetle Swarm Optimization Algorithm Based on Weight Distribution Strategy，KMBSO)。算法以加強群體之間的信息交流為目的，利用K-means聚類算法配合輪廓系數法，將種群分為若干子群，并對每個子群中的最優(yōu)個體分配一定權值以代替全局最優(yōu)個體，從而實現對位置更新的聯合決策。仿真實驗結果表明，改進后的算法在給定的單、多峰函數上的表現明顯優(yōu)于BSO算法以及其它對比算法，具備較好的魯棒性，并能有效地應用于優(yōu)化問題。

1 算法原理

1.1 天牛群優(yōu)化算法

在天牛群優(yōu)化算法中，將包含有n只天牛個體的種群在S維中的表現形式描述為X={X1,X2,…,Xn}，第i只天牛在S維空間中的位置用Xi=(Xi1,Xi2,…,XiS)T表示，天牛個體在空間中移動所需的速度變量被表示為Vi=(Vi1,Vi2,…,ViS)T。天牛群優(yōu)化算法引用粒子群優(yōu)化算法的思想，保留種群個體迭代過程中的個體最優(yōu)位置和全局最優(yōu)位置。其中，將Pi=(Pi1,Pi2,…,PiS)T表示為第i只天牛迭代過程中的最優(yōu)位置，將Pg=(Pg1,Pg2,…,PgS)T表示為天牛種群在解空間中迄今搜索到的全局最優(yōu)位置。天牛位置更新可通過式(1)實現：

(1)

其中，t表示當前迭代次數，s表示S維解空間中的第s維。Vis和ξis分別表示第i只天牛在第s維空間中的移動速度和位置增量，算法主要通過更新兩者的值，來控制天牛個體在解空間中搜尋最優(yōu)解；α表示設置的權重系數，取自[0,1]中的一個常數。

天牛個體移動速度V的計算采用粒子群中的速度更新策略，具體表示為：

(2)

(3)

c0=d1+1.2cos(πt)/Max_iter

(4)

c1=d2-1.2cos(πt)/Max_iter

(5)

其中，ω稱為慣性因子，調整其值可以改變算法全局尋優(yōu)和局部尋優(yōu)能力的比重；c0和c1為加速因子，前者稱為個體學習因子，后者稱為社會學習因子；r0、r1為兩個單位隨機變量；Max_iter表示設定的算法最大迭代次數。

天牛個體的移動依賴于天牛須搜索算法所提供的位置增量ξ，具體表示為：

(6)

(7)

δt+1=ηδt

(8)

dt=δt/c

(9)

η=δmin(δmax/δmin)1/(1+10t/Max_iter)

(10)

1.2 K-means聚類算法

聚類算法起源于分類學，其主要作用是將相似的樣本自動歸類。在眾多的聚類方法中，常見的方法有K-means聚類[13]、Hierarchical聚類[14]、基于密度的噪聲應用空間聚類[15]以及使用高斯混合模型的期望最大化聚類[16]等。其中，K-means聚類算法因其簡潔和高效率，成為使用最廣泛、最著名的聚類算法。

對于n個處于m維空間的個體，K-means聚類算法可以將這n個個體依據相似性分別聚集到指定的k個簇中。在確定了k個初始化聚類中心點后，依據式(11)的歐氏距離公式，將每個個體依次分配到最近的簇中：

(11)

其中，Xi表示第i個個體(1≤i≤n);Cj表示第j個簇中心點(1≤j≤k)；Xit和Cjt分別表示對應個體與中心點在第t維上的屬性值(1≤t≤m)。

每進行一次聚類操作后，則更新每個簇的中心點，而后按照式(11)中的規(guī)則繼續(xù)操作，直到前后兩次的聚類中心點的每個維度差值不超過給定值。更新中心點的方式為計算各個簇中個體在每個維度上的均值，具體的計算方式表示為

(12)

其中，Sj表示第j個個體簇；|Sj|表示該簇中的個體數；Yi表示第i個個體(1≤i≤|Sj|)。

1.3 輪廓系數法

K-means聚類算法作為無監(jiān)督學習方法的一種，可以很好地對樣本進行分類，但是對于簇的個數卻較難確定。針對于此，常用解決方法有：手肘法[17]、輪廓系數法[18]、Calinski criterion法[19]以及Gap Statistic法[20]等。本文使用輪廓系數法作為確定種群最優(yōu)聚類數的方法。

在確定了聚類個數為k的前提下，輪廓系數可以作為衡量個體在簇內不相似度和簇間不相似度的指標。通過對不同聚類個數所對應的種群輪廓系數值進行比較，可以確定最優(yōu)的聚類個數。具體的計算公式如下：

(13)

(14)

其中，a(i)表示第i個個體與簇內其它個體間的平均距離；b(i)表示第i(1≤i≤n)個個體與其它簇中個體的平均距離的集合取最小值；n為種群個體數量。Tk(1≤k≤n)表示當聚類個數為k時，種群中個體的輪廓系數平均值，Tk的值在[-1,1]中，其值越趨近于1則表示分類的情況越好。

2 改進天牛群優(yōu)化算法

與許多智能優(yōu)化算法一樣，BSO算法以當前全局最優(yōu)個體作為個體移動的主要導向，但忽略搜尋過程中得到的局部最優(yōu)解這一有用信息。本節(jié)針對該種情況，提出以下具體改進策略。

2.1 確定天牛子群

為確定最佳聚類子群數，需要計算在不同聚類數下的種群輪廓系數值，其中得到的最大輪廓系數值所代表的聚類個數便是最佳聚類數。這需要循環(huán)計算n次的種群輪廓系數值，其計算過程如下：

步驟1初始聚類個數k=1；

步驟2k=k+1；通過式(11)進行聚類操作，并通過式(12)重新確定每個簇的中心點，重復本步驟直至達到設定的迭代次數；

步驟3通過式(13)計算每個天牛個體的輪廓系數，并通過式(14)計算得到所有天牛的輪廓系數均值，即天牛種群的總輪廓系數值；

步驟4重復執(zhí)行n次步驟2、3的操作，比較各次得到的種群輪廓系數值以確定最佳聚類個數k及其對應的種群分類情況。

2.2 權值分配

在得到天牛群體的最佳分類方案后，選擇各簇中的最優(yōu)適應度個體作為簇代表。為分配不同簇代表對種群個體移動的影響權值，本文以其適應度值大小為指標進行權值分配。適應度值越小權值越大，相反適應度值越大則權值越小。依照適應度值可能出現的全為正、全為負和有正有負3種情況進行分類討論，采用不同的計算方式以加快算法收斂，具體如式(15)所示：

(15)

其中，集合K包含有k個不同的簇代表；xj表示K中的第j個個體；f(xj)為其適應度值(1≤j≤k)；ymax表示集合K中所有個體的最大適應度值；W(xj)為該簇代表xj所對應分配的權值大小。此外，為避免出現f(xj)為0而導致權值不能計算的情況，將使用最小浮點數精度eps=2.22e-16進行替代。

2.3 多子群融合

如式(1)所示，BSO算法主要通過更新速度V和位置增量ξ的值來控制天牛個體在解空間中的移動，而其中天牛個體兩須的位置同樣會受到速度V的影響，從而間接影響位置增量。

本文將使用Q={Q1,Q2,…,Qk}來表示不同的簇代表，在保持個體學習部分不變的情況下，使用Q代替全局最優(yōu)個體，并通過加權的方式更新社會學習部分，在更改速度公式的同時也間接地改變位置增量。具體的改進方法如下：

(16)

通過對天牛群進行聚類操作可以優(yōu)化天牛速度更新模塊的社會學習部分，增強天牛個體之間的信息交流，使得算法迭代過程中得到的局部信息得以充分的利用，從而達到增強尋優(yōu)能力的作用。在BSO算法中，社會學習部分只受到全局最優(yōu)個體的影響，而改進后的KMBSO算法在該部分將受到k個子群的最優(yōu)個體的影響，因此前者為后者在k=1時的特例。

2.4 KMBSO算法

通過上述對算法改進的描述，KMBSO算法的具體實現步驟如下：

步驟1種群初始化。隨機產生一個天牛種群G={X1,X2,…,Xn}，設定速度V、慣性權重ω和天牛移動步長δ等變量的范圍值，以及最大迭代次數Max_iter和權重α等常量的值；

步驟2對V、ω、δ等自適應變量進行更新，隨后使用K-means聚類算法配合輪廓系數法對天牛種群進行分類，并得到分類后的子群集合S={S1,S2,…,Sk}；

步驟3在每個子群Sj中挑選出適應度值最優(yōu)的簇代表Qj=(Qj1,Qj2,…,QjS)T，并依據Qj對應適應度值，通過式(15)計算得到應分配的權重值Wj；

步驟4確定每個天牛個體迄今搜索到的最優(yōu)位置P={P1,P2,…,Pn}。利用步驟3得到的權值Wj配合Qj帶入式(16)中，計算得到新的速度更新量V={V1,V2,…,Vn}；

步驟5依據速度更新量Vi以及天牛左右兩須的位置對位置增量ξ={ξ1,ξ2,…,ξn}進行更新，并通過式(1)對兩者進行加權處理，以此獲得新一代的天牛種群；

步驟6對比前后兩代天牛種群的適應度值，更新天牛個體最優(yōu)位置以及全局最優(yōu)位置；

步驟7判斷算法是否達到初始設定的最大迭代次數。若未達到，轉步驟2重新進行聚類操作；否則結束迭代過程，輸出全局最優(yōu)位置，即全局最優(yōu)解。

3 仿真實驗及結果分析

為驗證改進策略的有效性，實驗選取了4種不同的算法與改進后的算法進行比較。其中包括BSO算法、自適應粒子群優(yōu)化算法(Adaptive Particle Swarm Optimization algorithm, APSO)、正弦余弦算法(Sine Cosine Algorithm, SCA)以及樽海鞘群優(yōu)化算法(Salp Swarm Algorithm, SSA)。各算法在不同維度的測試函數中運行，并對所得實驗結果進行Wilcoxon符號秩檢驗。

實驗測試環(huán)境為：Inter(R) Core(TM) i5-4210M CPU @ 2.60 GHz，8 G運行內存，Windows 7 操作系統(tǒng)，MATLAB R2018a。

3.1 測試函數

依照多樣性的原則，本文選取15個國際基準測試函數對算法進行性能檢驗，函數詳情見表1。其中，f1～f5為單峰測試函數，用于測試算法的局部開發(fā)能力；f6～f10為多峰測試函數，側重于測試算法的全局探索能力以及跳出局部最優(yōu)解的能力；f10～f15為定維多峰測試函數，用于測試算法在低維復雜函數中的表現情況；D表示搜索空間的維度。

表1 標準測試函數

3.2 參數設定及結果分析

在實驗參數的設定上，KMBSO算法與BSO算法、APSO算法保持一致。其中，對于天牛移動步長δ和左右兩須距離d的影響因子η和c，設定δmin=0.2，δmax=0.9，η=0.95，c=2；對于權重系數α，設定α=0.4；對于慣性權重和加速因子，設定ωmin=0.4，ωmax=0.9，d1=1.3，d2=2。

為充分了解算法的尋優(yōu)過程，實驗設定種群規(guī)模為300，運行代數為1 000，搜索空間的維度分別取5維、10維和30維。所有算法在不同類型的測試函數上獨立執(zhí)行30次，實驗數值結果見表2～表4。

表2 5種算法在單峰測試函數上的表現

表3 5種算法在多峰測試函數上的表現

表4 5種算法在定維多峰測試函數上的表現

在定量分析方面，實驗結果的對比采用3個指標分別是：重復多次實驗后得到結果的平均值、標準差以及不同算法結果間以顯著性水平α=0.05為前提的Wilcoxon符號秩檢驗。其中，平均值可以衡量算法在求解問題上得到結果的質量好壞，平均值越小，結果越好；標準差可以衡量算法穩(wěn)定性，表現出結果在平均值附近的震蕩程度，標準差越小，算法越穩(wěn)定。符號秩檢驗用于判斷兩組數據之間是否存在顯著性差異，在表中使用“+”、“=”和“-”分別表示KMBSO算法的表現優(yōu)于、相當和劣于其它算法。表中使用加粗的方式來表示5種算法在這兩個對比指標中的最優(yōu)數值結果，并在表尾處給出了檢驗結果的初步數量統(tǒng)計。

在表2的單峰測試函數問題中，KMBSO算法在函數f4和f5中的表現優(yōu)于其它算法，平均值和標準差上都擁有較高的尋優(yōu)精度。但由于單峰函數本身只存在一個因函數值持續(xù)下降導致的極值點，所以不需要使用聚類策略，只利用全局最優(yōu)點作為移動導向也有機會搜索到一個較好的結果(如：BSO與APSO算法在f1和f2上得到的最小值結果)，但當問題維度提高時，KMBSO算法的性能便明顯優(yōu)于兩者。此外，從符號秩檢驗的結果也可以看出，KMBSO算法的局部開發(fā)能力明顯優(yōu)于其它算法，特別是與SCA算法和SSA算法的比較，皆為11個顯著優(yōu)勝。

在表3的多峰測試函數問題中，因為迭代次數和種群數量足夠大，不同的算法在一些測試函數的求解中會出現相同的結果(如：5維下的f6、f9和f10函數)。KMBSO算法的尋優(yōu)性能相較于未改進前的BSO算法仍有提升，檢驗結果為8個顯著優(yōu)勝，4個無顯著差異，3個顯著劣解；相較于APSO算法和SSA算法，檢驗結果表現出顯著的優(yōu)勢；對于SCA算法，兩者的性能表現相當，檢驗結果為6個顯著優(yōu)勝，3個無顯著差異，6個顯著劣解。

在表4中的定維多峰測試函數下，KMBSO算法表現良好，與其它算法的數值檢驗結果皆未出現顯著劣解，且尋優(yōu)表現優(yōu)于SCA算法。

在算法從探索階段轉向開發(fā)階段時，KMBSO算法能夠不斷地跳出局部最優(yōu)，得益于利用多個極值點共同進行決策，并不失側重地依據適應度值分配權值。因此，會相應延長算法的全局搜索過程，有利于對解空間進行充分的探索，同時在開發(fā)階段能夠將種群個體導向更優(yōu)的位置。例如：定維多峰函數f15，全局共有5個局部極小值點，其縱深較大，若算法只利用搜索到的全局最優(yōu)點作為導向，很容易出現過早收斂以及陷入局部最優(yōu)的情況，從而導致得到的實驗結果較差。

表5對5種算法在不同維度下的檢驗結果進行了統(tǒng)計。可以看出，KMBSO算法在絕大多數測試函數中的表現均優(yōu)于其它對比算法，特別是在5維和10維空間中，整體表現優(yōu)于BSO算法，這表明改進策略是可行有效的；但當維度升至30維時，KMBSO算法與SCA算法、SSA算法的表現相當。

表5 5種算法在不同維度上的Wilcoxon符號秩檢驗統(tǒng)計

在定性分析方面，圖1中給出了不同的測試函數在給定維度下的算法數值結果收斂曲線對比結果，可以直觀地了解到不同算法在迭代過程中的收斂情況。

圖1 5種算法的收斂曲線對比

從圖1(a)～圖1(e)可知，KMBSO算法在對應的單峰函數中的收斂速度相較于BSO和APSO算法稍慢一點，但卻具有遠優(yōu)于BSO和APSO算法的收斂精度。在圖1(d)中，KMBSO算法收斂卻最快，迭代未到400次就得到最優(yōu)值0。而APSO和BSO算法會出現早熟現象，主要原因是搜索過程中全局最優(yōu)個體對其它個體的強吸引力，同時缺少必要的變異手段，導致種群個體過早聚集；SCA和SSA算法在多個函數的收斂過程中出現速度慢，精度低的現象，這表明兩者的局部開發(fā)能力較弱。

從圖1(f)～圖1(o)可知，5種算法的收斂過程主要集中在前中期，多數圖中BSO和APSO算法的收斂同樣早于KMBSO算法，但當其陷入局部最優(yōu)時，KMBSO算法依舊可以跳出并找到更優(yōu)的解。其中，KMBSO算法收斂的速度較慢也是因為聚類策略在幫助算法不斷地跳出局部最優(yōu)。SCA和SSA算法的圖像多處呈階梯型，表明其同樣具備跳出局部最優(yōu)的能力，其中SCA算法出現較早收斂的現象，而SSA算法在迭代后期仍未收斂，呈現出可持續(xù)開發(fā)的能力。

綜上所述，APSO算法結構簡單，但易出現早熟的現象，在30維的空間中往往易陷入局部最優(yōu)；BSO算法的性能優(yōu)于APSO算法，特別是在低維空間中，但仍存在前期收斂過快和中期全局尋優(yōu)能力較弱的問題；KMBSO算法收斂較慢，但尋優(yōu)性能強于兩者，具備不斷跳出局部最優(yōu)的能力，且在5維和10維下能達到相較于SCA算法更高的數值精度；SSA算法收斂速度較慢，局部開發(fā)能力有待提升，但在30維空間中的表現較好。

4 結束語

針對天牛群優(yōu)化算法存在的不足，本文提出了一種新的基于聚類的天牛群優(yōu)化算法，將聚類的思想融合到天牛種群中。通過將一個基礎種群分為若干子群，使用多個子群中的最優(yōu)個體代替全局最優(yōu)個體，從而擴展局部極值在社會學習部分的影響范圍。其次，本文提出了一種新的權值分配策略，該策略在利用群體智能求解極值問題上，可對影響群體移動的關鍵個體，按其對應的適應度值進行相應的權值分配。仿真實驗結果表明，改進策略有利于算法跳出局部極值，并能夠提高算法的尋優(yōu)精度及穩(wěn)定性，在單、多峰函數中的表現說明其具備較好的魯棒性。

此外，在研究的過程中發(fā)現，使用其他的聚類算法進行種群分類時，在一些基準函數中的表現會優(yōu)于使用K-means聚類算法。因此在接下來的工作中，將對這一方面開展進一步的探究。