基于核模糊聚類的動態(tài)多子群協(xié)作骨干粒子群優(yōu)化

楊國鋒，戴家才，劉向君,2，吳曉龍，田延妮

(1.西南石油大學(xué) 地球科學(xué)與技術(shù)學(xué)院，成都 610500； 2.油氣藏地質(zhì)及開發(fā)工程國家重點實驗室(西南石油大學(xué))，成都 610500)

0 引言

經(jīng)典的粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是由Kennedy等[1]受鳥類覓食行為的啟發(fā)而提出的一種群體智能算法，具有形式簡單、易于實現(xiàn)的優(yōu)勢，但PSO算法的性能與收斂情況受算法參數(shù)的影響[2]。為優(yōu)化算法的性能與結(jié)構(gòu)，2003年Kennedy[3]在PSO算法的基礎(chǔ)上，通過分析粒子的飛行軌跡，提出了一種無參數(shù)的骨干粒子群優(yōu)化(BareBones Particle Swarm Optimization, BBPSO)算法。和經(jīng)典PSO算法相比，BBPSO算法取消了速度項，從而省略了加速系數(shù)與速度閾值等參數(shù)。算法以服從高斯分布的隨機采樣來更新粒子的位置，因此BBPSO算法結(jié)構(gòu)更為簡便，性能更為高效，具有自組織、自適應(yīng)的特點[4]。目前PSO算法、BBPSO算法已廣泛應(yīng)用于解決各類工程中的優(yōu)化問題[5-6]。盡管如此，PSO算法與BBPSO算法在處理復(fù)雜多峰函數(shù)優(yōu)化問題時仍然存在易陷入局部最優(yōu)、收斂速度低等不足。針對基本算法所存在的不足，現(xiàn)階段，研究人員從多方面對PSO算法與BBPSO算法進行了改進。

由于算法在迭代初期粒子會快速聚集，導(dǎo)致種群多樣性迅速降低，從而喪失探索能力，這使得算法易陷入局部最優(yōu)；因此設(shè)法保證粒子在迭代中的多樣性是增強算法探索能力、防止算法早熟的有效手段。Wang[7]采用反向?qū)W習的策略通過計算解空間內(nèi)粒子的對立粒子來增加種群的多樣性，提高了算法的性能。 Krohling等[8]利用高斯分布或者柯西分布產(chǎn)生的擾動來使算法跳出局部最優(yōu)。 Liu等[9]采用動態(tài)自學(xué)習策略對算法進行了改進，提高了進化過程中的多樣性，平衡了算法開發(fā)與探索能力。張芳芳等[10]利用混沌擾動來進行全局極值點的選擇并提出了自適應(yīng)跳離算子來彌補種群多樣性的缺失。張震等[11]利用剪枝策略來提高BBPSO算法的多樣性。 除此之外，也有學(xué)者從拓撲結(jié)構(gòu)的角度對算法進行了改進，研究了環(huán)形拓撲、馮諾依曼拓撲等不同的拓撲結(jié)構(gòu)對算法性能的影響[12]。還有一些學(xué)者將粒子群算法與其他智能算法相結(jié)合，以彌補算法的不足[13]。

在提高算法搜索效率與收斂速度方面，一些學(xué)者研究發(fā)現(xiàn)利用多種群協(xié)作是一種有效方法：劉衍民等[14]利用K-均值聚類將粒子劃分為若干子群，實現(xiàn)了多子群協(xié)同搜索；謝紅俠等[15]利用個體最優(yōu)值作為子群種子，以子群種子為基礎(chǔ)構(gòu)建多個子群實現(xiàn)了多種群粒子群算法；Chen[16]以環(huán)狀拓撲結(jié)構(gòu)構(gòu)建多個粒子子集，并以子集內(nèi)粒子位置的平均值作為高斯分布的均值，位置平均值與全局最優(yōu)粒子位置的偏差作為高斯分布的標準差實現(xiàn)了BBPSO算法的多種群協(xié)作搜索模式；申元霞等[17]利用并行的主群與從群之間的協(xié)作學(xué)習來協(xié)調(diào)算法的探索能力與開發(fā)能力。

前人研究證實了通過提高種群的多樣性，可有效提高算法的探索能力，防止算法過早收斂，利用多子群協(xié)作學(xué)習可有效地提高算法的搜索效率與收斂速度。本文在前人研究的基礎(chǔ)上，針對BBPSO算法在優(yōu)化問題中易早熟、精度低、收斂速度低等問題，提出了一種基于核模糊聚類的動態(tài)多子群協(xié)作骨干粒子群優(yōu)化(dynamic Multi-Subgroup collaboration Barebones Particle Swarm Optimization based on Kernel Fuzzy Clustering, KFC-MSBPSO)算法。該算法利用核模糊聚類將主群分割為多個子群，令多個子群協(xié)同搜索，提高了算法搜索效率，同時為了協(xié)調(diào)算法的探索能力，提高粒子利用率，本文通過動態(tài)變異策略以子群冗余粒子為基礎(chǔ)重新構(gòu)建主群，提高粒子的多樣性，防止算法早熟。為提高算法穩(wěn)定性，加強粒子間信息交流，利用粒子吸收策略與子群合并策略實現(xiàn)子群與主群的動態(tài)重組，以子群與主群中的最優(yōu)粒子為基礎(chǔ)實現(xiàn)子群重建。上述策略對算法的性能有較大改善。

1 粒子群與骨干粒子群算法理論

經(jīng)典粒子群算法中的每一個粒子均為優(yōu)化問題的一個潛在解，并采用位置、速度和適應(yīng)度3個屬性來描述粒子的特性，算法中粒子速度與位置的更新公式如式(1)、式(2)所示：

vij(t+1)=ωvij(t)+c1r1(pij(t)-xij(t))+c2r2(gj(t)-

xij(t))

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

其中：t為迭代次數(shù)，vi為粒子i的速度向量；xi為粒子i的位置向量；pi為粒子i的歷史最優(yōu)位置；g為全局最優(yōu)位置；下標j表示向量第j維的屬性值；參數(shù)ω為慣性權(quán)重因子，用于協(xié)調(diào)全局搜索能力與局部搜索能力。參數(shù)r1、r2為[0,1]間均勻分布的隨機數(shù)，參數(shù)c1、c2稱為加速系數(shù)，用于控制社會認知與個體認知對速度的影響。粒子在解空間內(nèi)利用式(1)、(2)追蹤個體最優(yōu)位置與全局最優(yōu)位置來更新自身的位置，并通過不斷迭代來找尋最優(yōu)解。

骨干粒子群算法與經(jīng)典粒子群算法的差別在于取消了速度項，而采用以高斯分布進行隨機采樣的方式實現(xiàn)粒子位置的更新，其中高斯分布的均值為粒子的個體最優(yōu)位置與全局最優(yōu)位置的中心，標準差為粒子個體最優(yōu)位置與全局最優(yōu)位置的偏差，位置更新模型可表示為式(3)：

(3)

其中ξ為標準正態(tài)分布隨機數(shù)N(0,1)。在迭代初期由于個體最優(yōu)位置與全局最優(yōu)位置差距較大，因此高斯分布具有較大的標準差，此時算法探索能力較強，迭代后期，標準差逐漸趨近于0，算法將主要集中在對全局最優(yōu)的開發(fā)上。

2 KFC-MSBPSO算法

2.1 基于核模糊聚類的主群劃分

采用核模糊聚類方法進行主群劃分的原理是利用特征映射將粒子的位置向量映射到高維特征空間，從而發(fā)現(xiàn)粒子間的線性模式，使解空間中的粒子更為可分。核模糊聚類有效地解決了聚類樣本高維度與非線性的問題[18]，因此在處理高維粒子的主群劃分問題時，核模糊聚類有更好的適用性。具體聚類原理可參考文獻[18]。

但利用聚類算法來進行主群劃分時，算法對初始聚類中心較為敏感，選取不同的初始聚類中心往往會造成不同的聚類結(jié)果[19]。為保證算法的穩(wěn)定性，且應(yīng)使每個子群內(nèi)存在潛在的最優(yōu)解，需要對初始聚類中心進行甄選。因此本文首先采用如下方法確定解空間內(nèi)的潛在最優(yōu)解：對初始化之后的主群粒子施加一個隨機擾動，并計算擾動前與擾動后粒子的適應(yīng)度，以較優(yōu)點為pij，較差點為xij按式(4)迭代更新pij與xij的值。由于式(4)中不存在全局最優(yōu)信息，因此各粒子最終會收斂于初始位置附近的局部最優(yōu)位置。這些局部最優(yōu)粒子被記錄并作為候選聚類中心。判斷某粒子已經(jīng)收斂于局部最優(yōu)的判據(jù)為經(jīng)過T次迭代后粒子的pij沒有發(fā)生變化。

(4)

本文選取的候選聚類中心數(shù)量為子群數(shù)目的2倍。之后本文提出動態(tài)閾值策略用于在候選聚類中心集合內(nèi)選取初始聚類中心，該策略既能保證聚類中心粒子的適應(yīng)性也能保證彼此之間的差異性。具體步驟如下所示：

步驟1 將記錄的候選聚類中心適應(yīng)性進行排序，其中最優(yōu)的一個粒子為第一個初始聚類中心。

步驟2 設(shè)定距離閾值D，并計算其他所有候選聚類中心距第一個初始聚類中心的距離，記錄所有距離大于D的候選聚類中心，將其中適應(yīng)性最好的粒子選為第二個初始聚類中心。

步驟3 計算剩余候選聚類中心到已有初始聚類中心的距離，并找到距已有初始聚類中心距離均大于D的粒子，選出其中適應(yīng)性最好的粒子為第三個初始聚類中心。

步驟4 若不存在這樣的粒子則令D=0.9D，通過降低閾值，找到滿足條件的粒子。循環(huán)迭代直到找到N個初始聚類中心。

步驟5 利用選出的N個初始聚類中心進行核模糊聚類實現(xiàn)主群粒子的劃分。

2.2 動態(tài)變異策略

將主群劃分為多個子群后，各子群中的粒子將按常規(guī)骨干粒子群的尋優(yōu)方式進行尋優(yōu)，如式(3)所示。雖然子群對所處范圍內(nèi)的開發(fā)能力較強，但同時也喪失了一定的探索能力，為了彌補算法探索能力的不足，本文采用動態(tài)變異策略，利用子群內(nèi)的冗余粒子進行變異操作重新構(gòu)建主群，提高整體粒子的多樣性從而提高全局的探索能力。

本文提出的變異策略首先根據(jù)子群內(nèi)的粒子數(shù)通過輪盤賭的方式選擇發(fā)生變異的子群，子群Sk被選擇的概率與該子群內(nèi)所具有的粒子數(shù)成正比，如式(5)所示：

(5)

在確定進行變異操作的子群Sk之后，算法將根據(jù)該子群的收斂情況確定變異概率，子群越收斂則變異概率越大，反之變異概率越小。本文依據(jù)按文獻[20]給出的歸一化方差來評價子群的收斂情況，如式(6)所示：

(6)

其中：fi為粒子i的適應(yīng)度，favg為子群平均適應(yīng)度，m為子群粒子數(shù)，f為歸一化因子，由式(7)確定：

(7)

受經(jīng)典PSO算法非線性慣性權(quán)重的啟發(fā)，本文引入非線性動態(tài)變異因子。在計算出子群的歸一化方差值之后按式(8)計算該子群的變異概率：

(8)

其中：c為調(diào)節(jié)系數(shù)，是大于0的正數(shù)。當方差接近1時子群變異概率很小，且在方差降低初期變異概率增長較緩；當方差接近0時，變異概率隨方差降低增長較快，方差為0時變異概率增至最大，其值為0.5。

一旦確定子群Sk的粒子進行變異操作，則將子群Sk內(nèi)粒子適應(yīng)性進行排序，將適應(yīng)性最低的粒子從子群內(nèi)移除，重新初始化該粒子位置，并將該粒子計入主群S；同時，為了防止子群因不斷變異最終被破壞，引入子群保護閾值H，即當子群內(nèi)粒子數(shù)減少到H時，該子群被選擇進行變異的概率設(shè)置為0。保護閾值保證了子群的穩(wěn)定性，防止已學(xué)習的信息丟失。

主群S內(nèi)粒子的位置更新將舍棄全局信息，以變異前后適應(yīng)性較好的位置為pij，較差位置為xij，按式(4)進行迭代并更新pij與xij。由于主群粒子不會被全局最優(yōu)點吸引，因此具有較強的探索能力，可彌補子群探索能力的不足。

2.3 粒子吸收策略與子群合并策略

雖然主群S內(nèi)的粒子在搜索時不會被全局最優(yōu)位置吸引，但卻有可能運動到某子群Sk的搜索范圍內(nèi)。針對此類情況，本文利用粒子吸收策略使子群Sk吸收該粒子。粒子吸收策略可以實現(xiàn)子群與主群間的信息交流，攜帶主群信息的粒子被子群吸收可以提高子群的多樣性，更好地引導(dǎo)子群搜索[21]。粒子吸收策略還可以改變子群的收斂性與粒子數(shù)，從而決定子群發(fā)生變異概率，實現(xiàn)各個子群的動態(tài)重組。本文采用文獻[21]所提出的粒子吸收策略判據(jù)，如式(9)所示：

if ‖S.xi-Sk.g‖≤Sk.R

then

Sk=Sk∪{S.xi}

S=S〗{S.xi}|

(9)

其中:Sk.g為子群k內(nèi)的最優(yōu)粒子，Sk.xi為主群粒子xi，Sk.R為子群k的半徑，其值為：

Sk.R=max{‖Sk.xi-Sk.g‖}

(10)

此外，子群與子群之間同樣會出現(xiàn)相互重疊的情況，該情況下兩個子群將收斂于同一個最優(yōu)位置，此時若兩個子群依舊各自迭代則會降低算法運行效率，且不利于子群跳出局部最優(yōu)。因此當兩個子群重疊時需要將兩個子群進行合并以改變?nèi)簝?nèi)粒子數(shù)目與結(jié)構(gòu)，提高被選擇進行變異操作的概率，幫助子群跳出局部最優(yōu)。文獻[21]同樣提出了子群合并策略的判據(jù)，如式(11)所示:

(11)

即當兩個子群S1、S2內(nèi)的最優(yōu)粒子間的距離小于兩個子群半徑之和時，將兩個子群合并。然而此判據(jù)存在一定缺陷：若兩子群的最優(yōu)位置距離較小，但各自半徑較大時則可能丟失全局最優(yōu)點，在一維問題中該情況如圖1所示。

圖1 易引發(fā)子群過早合并的情況

圖1中子群S1與子群S2均未收斂于全局最優(yōu)點，子群S1中的最優(yōu)點適應(yīng)性優(yōu)于子群S2，但子群S2離全局最優(yōu)點更近，此時雖然符合式(11)的合并判據(jù)，但若進行合并會導(dǎo)致子群S2向子群S1方向移動，從而陷入局部最優(yōu)。

產(chǎn)生此類問題的原因是由于子群尚未收斂就進行合并，導(dǎo)致子群對所在區(qū)域并未搜索完畢。本文提出的子群合并策略同時考慮兩子群最優(yōu)位置間的距離與子群各自的收斂情況，改進的子群合并判據(jù)如式(12)所示：

(12)

2.4 子群重建策略

利用多子群協(xié)作尋優(yōu)可以使算法具有較高的搜索效率，但子群Sk內(nèi)的粒子總是追蹤子群內(nèi)的最優(yōu)點，若子群內(nèi)的最優(yōu)點處于局部最優(yōu)而非全局最優(yōu)，則會引導(dǎo)整個子群陷入局部最優(yōu)，這不利于提高算法整體的尋優(yōu)能力。而且由于主群S內(nèi)粒子位置的更新僅依靠個體信息，因此一旦主群粒子收斂于自身最優(yōu)，則會停止更新，無法將探索到信息及時傳遞給子群，所以每隔一定的迭代次數(shù)需要重組子群，幫助子群跳出局部最優(yōu)。文獻[14]通過數(shù)值實驗的方式確定了子群重構(gòu)的間隔代數(shù)，但固定的重組間隔代數(shù)并不一定利于子群的搜索，而且有可能會提高算法的復(fù)雜度，降低運行效率。最佳策略應(yīng)根據(jù)當前算法的搜索情況來決定是否進行子群重建：若搜索到的全局最優(yōu)解仍在更新，則說明算法仍處于有效的搜索階段，此時不應(yīng)進行子群重建；反之，若主群粒子因探索到了新的全局最優(yōu)位置而自身收斂，此時則應(yīng)及時進行子群重建，將主群探索到信息傳遞給子群。因此，本文結(jié)合主群粒子，改進了子群重建策略。具體步驟如下：

步驟1 判斷并記錄所有子群的最優(yōu)粒子與收斂于自身最優(yōu)的主群粒子。

步驟2 比較所有子群最優(yōu)解適應(yīng)性與主群收斂粒子的適應(yīng)性。

步驟3 若主群收斂粒子的適應(yīng)性劣于所有子群最優(yōu)解適應(yīng)性，為防止主群粒子停止更新，讓該粒子以當前全局最優(yōu)解為pij，以該粒子歷史最優(yōu)解為xij按式(4)迭代。若主群收斂粒子的適應(yīng)性優(yōu)于某子群內(nèi)最優(yōu)粒子適應(yīng)性，則將主群收斂粒子與各子群的最優(yōu)粒子按適應(yīng)性進行排序，以前N個粒子為聚類中心，重新聚類劃分子群。

步驟4 設(shè)置最大間隔代數(shù)I，若全局最優(yōu)粒子適應(yīng)性經(jīng)過I次迭代未發(fā)生變化，則以適應(yīng)性較好的前N個粒子為聚類中心，采用核模糊聚類重新劃分子群。

根據(jù)主要步驟繪制的子群重建策略流程如圖2所示。

2.5 KFC-MSBPSO算法流程

綜上所述，本文提出的KFC-MSBPSO算法偽代碼如下所示：

算法1 KFC-MSBPSO算法。

初始化n維主群粒子S.xm，設(shè)置子群個數(shù)N

Repeat

采用式(4)訓(xùn)練主群粒子S.xm

更新主群粒子S.xm適應(yīng)性

IfS.xm適應(yīng)性經(jīng)過T次迭代未發(fā)生變化

候選聚類中心集合v=v∪S.xm

Endif

Untilv.size=2N

運用動態(tài)閾值策略從集合v中選取N個聚類中心

核模糊聚類劃分子群

Repeat

For 每個子群Sk與主群SDo

Sk粒子采用式(3)進行位置更新

S粒子采用式(4)進行位置更新

If 主群S粒子xm滿足吸收策略式(9)

Sk=Sk∪xm

S=S〗xm

Endif

更新粒子適應(yīng)性

更新子群半徑Sk.R

計算子群Sk被選擇概率Pchoose

利用式(8)計算子群Sk變異概率Pmutation

Ifrand

記錄子群Sk中最差粒子Sk.xworst

重新初始化Sk.xworst

主群S=S∪Sk.xworst

子群Sk=Sk〗Sk.xworst

Endif

Endif

If 子群S1與子群S2滿足子群合并策略式(12)

S1=S1∪S2

S2=?

Endif

If 滿足子群重構(gòu)條件

使用核模糊聚類重新劃分子群

Endif

Endfor

Until 迭代終止

圖2 子群合并策略流程

3 數(shù)值實驗及分析

3.1 測試函數(shù)與參數(shù)設(shè)置

為驗證KFC-MSBPSO算法的尋優(yōu)能力，本章采用6個廣泛應(yīng)用的標準測試函數(shù)對KFC-MSBPSO算法進行測試，標準測試函數(shù)的名稱、表達式、解空間范圍以及理論最優(yōu)解如表1所示。其中：函數(shù)Sphere(F1)、Rosenbrock(F2)為單峰函數(shù)，函數(shù)Griewank(F3)、Ackley(F4)、Step(F5)、Rastrigin(F6)為多峰函數(shù)。

表1 標準測試函數(shù)

算法整體采用Matlab編制，仿真實驗硬件環(huán)境為：Intel Core i7-6500U 2.60 GHz。操作系統(tǒng)為64位，內(nèi)存為8 GB。軟件運行環(huán)境為Window 7操作系統(tǒng)，Matlab版本為2016a。

KFC-MSBPSO算法的主要參數(shù)設(shè)置為：子群個數(shù)N設(shè)為4，動態(tài)閾值D設(shè)為粒子間最大歐氏距離的1/2，方差判定閾值σm設(shè)為0.25，變異概率調(diào)節(jié)系數(shù)c設(shè)為5，子群保護閾值H設(shè)置為子群原有粒子數(shù)的2/3。

子群重建策略中最大間隔代數(shù)I設(shè)為100。將KFC-MSBPSO算法的尋優(yōu)結(jié)果與傳統(tǒng)的BBPSO算法[3]及其改進形式BBExp[3]、反向骨干粒子群優(yōu)化(Opposition-Based Barebones Particle Swarm Optimization, OBBPSO)算法[7]、協(xié)作骨干粒子群優(yōu)化(Cooperative Barebones Particle Swarm Optimization, CBPSO)算法[16]的尋優(yōu)結(jié)果進行比較，對比算法的參數(shù)按照相關(guān)文獻設(shè)置，其中OBBPSO算法反向?qū)W習概率P0等于0.5，CBPSO算法子集內(nèi)粒子數(shù)為5。為保證對比實驗的公平性，所有算法使用相同的實驗參數(shù)：種群規(guī)模為50，函數(shù)評價次數(shù)為1×104，對每個目標函數(shù)算法運行次數(shù)為30次,同時為了研究維度對算法性能的影響，將目標函數(shù)解向量設(shè)置為5、30、100三種維度。

3.2 實驗分析

3.2.1 算法性能對比

本文采用算法對測試函數(shù)多次運行結(jié)果的平均值與標準差來反映算法的性能。表2中列出了5種算法在F1～F6函數(shù)中尋優(yōu)結(jié)果的平均值與標準差，其中最佳均值采用下劃線標出。在實驗中若算法尋優(yōu)結(jié)果與理論解之間的差距小于10-15則認為測試結(jié)果準確度達到要求。經(jīng)統(tǒng)計可得KFC-MSBPSO算法的尋優(yōu)準確率與其他4種算法的尋優(yōu)準確率相比至少提高了11.1%。此外由表2可以看出，在低維解空間(Dim=5，30)內(nèi)各算法的性能差異較小，運行得到的最優(yōu)解均具有較高的精度，其中KFC-MSBPSO算法在5維解空間中的Sphere函數(shù)(F1)、Griewank函數(shù)(F3)、Step函數(shù)(F5)以及30維解空間中的Griewank函數(shù)(F3)的尋優(yōu)精度與準確率均達到100%。這也說明KFC-MSBPSO算法在低維問題中具有較好的性能。

當維數(shù)升高時(Dim=100)，KFC-MSBPSO算法在F2、F3、F4、F5、F6測試函數(shù)下的尋優(yōu)結(jié)果具有最高的精度，而其他幾種算法均不同程度地陷入了局部最優(yōu)。這是由于在低維解空間中，目標函數(shù)內(nèi)局部極值點相對較少，這使得優(yōu)化算法能夠較為容易地跳出局部最優(yōu)，而隨著維度的增加解空間內(nèi)的局部極值點呈指數(shù)形式增加，這時算法能否及時跳出局部最優(yōu)點則直接決定了算法的尋優(yōu)精度，反映出算法的性能。KFC-MSBPSO算法利用多子群協(xié)作的方式可以有效防止所有粒子被局部最優(yōu)點吸引。而動態(tài)變異與子群重組則幫助算法及時跳出局部最優(yōu)點，并加強了粒子間的信息共享，因此在高維解空間內(nèi)，KFC-MSBPSO算法的尋優(yōu)結(jié)果同樣具有較高的精度。

表2 五種算法優(yōu)化結(jié)果平均精度與方差

3.2.2 算法收斂性對比分析

為了比較不同算法的收斂性，繪制了BBPSO、BBEXP、OBBPSO、CBBPSO以及KFC-MSBPSO 5種算法對測試函數(shù)F1～F6在5維，30維，100維解空間內(nèi)的迭代曲線，如圖3所示。

圖3 測試函數(shù)迭代曲線

由圖3可以得出以下結(jié)論：第一，在低維解空間內(nèi)(Dim=5，Dim=30)，各算法收斂速度接近。這是由于維度較低時對算法性能要求較低，算法能夠較快地收斂于全局最優(yōu)解。第二，在高維解空間內(nèi)(Dim=100)，KFC-MSBPSO算法和其他算法相比具有更高的收斂速度，尤其是100維解空間內(nèi)的Ackley函數(shù)(F4),Step函數(shù)(F5)以及Rastrigin函數(shù)(F6),KFC-MSBPSO算法表現(xiàn)出了良好的收斂特性。這是由于通過劃分子群，令多子群協(xié)作尋優(yōu)的方式可以提高算法整體的運行效率，因此相對于全局搜索模式，協(xié)同搜索的收斂速度更快。第三，在高維解空間內(nèi)除KFC-MSBPSO算法之外的其他算法均出現(xiàn)了早熟現(xiàn)象，未收斂于全局最優(yōu)適應(yīng)性便停止更新。而KFC-MSBPSO算法則可以利用所提出的策略幫助算法跳出局部最優(yōu)，有效避免算法過早收斂而出現(xiàn)早熟現(xiàn)象，保證了尋優(yōu)結(jié)果的精度。

3.2.3 算法時間開銷對比分析

由于KFC-MSBPSO算法引入了核模糊聚類算法與一系列優(yōu)化策略，因此有必要探討這些改進是否造成了算法運行時間的明顯增加。利用Matlab的tic，toc命令測試了五種算法在100維解空間內(nèi)迭代1×104次的時間，每種函數(shù)的平均運行時間如表3所示，同時計算了每種算法在六種測試函數(shù)中進行迭代的平均時間?？梢钥闯鯧FC-MSBPSO算法的平均運行時間排名第3，高于BBPSO算法與CBPSO算法，低于BBEXP算法與OBBPSO算法。這是由于KFC-MSBPSO算法內(nèi)包含多次聚類操作，從而增加了迭代時的計算量，此外子群粒子的變異，吸收以及子群重組均需一定的計算時間，因此造成了算法運行時間的增加。BBEXP在運行時需對解向量的每一維作出判定，這使得高維度下的尋優(yōu)具有較大的時間開銷。OBBPSO算法在運行時需同時計算種群內(nèi)粒子的反向粒子，這相當于變相增加了粒子數(shù)目，導(dǎo)致了運行時間的增加。整體來說，KFC-MSBPSO算法與BBPSO算法的運行時間相比處于同一數(shù)量級上，這也說明引入的改進策略沒有對算法的運行時間造成較大的影響。

3.2.4 算法相關(guān)算子分析

本文所提算法主要包含多子群協(xié)同尋優(yōu)、動態(tài)變異以及子群重建策略，因此需要對這幾種策略對算法的影響以及對尋優(yōu)效果的貢獻度予以分析。選取單峰函數(shù)Rosenbrock(F2)、多峰函數(shù)Ackley(F4)與Rastrigrin(F6)在100維下的尋優(yōu)效果進行分析，結(jié)果如表4所示。

由表4可以看出，當沒有采用多子群協(xié)同策略時，算法的收斂精度明顯減低，這是因為多子群搜索可以防止全部粒子被一個局部最優(yōu)點吸引，在一定程度上防止算法整體陷入局部最優(yōu)，此外由圖3的收斂曲線也可以看出多子群協(xié)同尋優(yōu)的方式與單一種群的尋優(yōu)方式(BBPSO、BBEXP)相比具有更快的收斂速度。當算法不采用動態(tài)變異策略時，其平均收斂精度同樣有所降低，這是由于動態(tài)變異策略可以提高子群的多樣性，并實現(xiàn)各子群的動態(tài)重組，借助變異操作使算法可以跳出局部最優(yōu)。由表4還可以看出子群重建策略也有利于算法精度的提高，這是由于子群重建可以在各個子群間傳遞全局最優(yōu)信息，提高了子群間的信息交流，同時防止主群粒子的搜索出現(xiàn)停滯。因此相比無重建的多子群策略，具有子群重建策略的算法其尋優(yōu)能力更強，且具有更高的尋優(yōu)精度。

表3 5種算法100維解空間內(nèi)運行時間比較 s

表4 KFC-MSBPSO算法主要策略對尋優(yōu)效果影響

4 結(jié)語

本文提出了一種改進骨干粒子群算法——KFC-MSBPSO，該算法主要改進包括：1)利用動態(tài)閾值策略確定初始聚類中心，并利用核模糊聚類劃分子群，通過多子群協(xié)作尋優(yōu)的方式提高算法搜索效率。2)提出動態(tài)變異策略，根據(jù)子群粒子數(shù)與收斂情況自動調(diào)節(jié)子群變異概率，利用主群粒子提高算法探索能力。3)利用主群粒子吸收策略提高子群多樣性并改變子群結(jié)構(gòu)；改進了子群合并策略提高其適用性。4)改進了子群重建策略，根據(jù)最優(yōu)解的搜索情況與主群粒子的收斂情況確定子群重建的間隔代數(shù)。通過與其他算法進行比較，實驗結(jié)果表明，無論在低維還是高維解空間內(nèi)KFC-MSBPSO算法均具有較好的尋優(yōu)效果，其收斂速度與尋優(yōu)精度有了顯著提高，這說明改進策略具有較好的效果。

[15] 謝紅俠,馬曉偉,陳曉曉,等.基于多種群的改進粒子群算法多模態(tài)優(yōu)化[J].計算機應(yīng)用,2016,36(9):2516-2520.(XIE H X, MA X W, CHEN X X, et al. Enhanced multi-species-based particle swarm optimization for multi-modal function [J]. Journal of Computer Applications, 2016, 36(9): 2516-2520.)

[16] CHEN C H. Cooperative bare bone particle swarm optimization [C]// ICISCE 2012: Proceedings of the 2012 IET International Conference on Information Science and Control Engineering. Stevenage, UK: IET, 2012: 2.27-2.27.

[17] 申元霞,曾傳華,王喜鳳,等.并行協(xié)作骨干粒子群優(yōu)化算法[J].電子學(xué)報,2016,44(7):1643-1648.(SHEN Y X, ZENG C H, WANG X F, et al. A parallel-cooperative bare-bone particle swarm optimization algorithm [J]. Acta Electronica Sinica, 2016, 44(7): 1643-1648.)

[18] GIROLAMI M. Mercer kernel-based clustering in feature space [J]. IEEE Transactions on Neural Networks, 2002, 13(3): 780-784.

[19] 盛萬興,季宇,吳鳴,等.基于改進模糊C均值聚類算法的區(qū)域集中式光伏發(fā)電系統(tǒng)動態(tài)分群建模[J].電網(wǎng)技術(shù),2017,41(10):3284-3291.(SHENG W X, JI Y, WU M, et al. Dynamic clustering modeling of regional centralized photovoltaic power plant based on improved fuzzy C-means clustering algorithm [J]. Power System Technology, 2017, 41(10): 3284-3291.)

[20] 劉立峰,孫贊東,韓劍發(fā),等.量子粒子群模糊神經(jīng)網(wǎng)絡(luò)碳酸鹽巖流體識別方法研究[J].地球物理學(xué)報,2014,57(3):991-1000.(LIU L F, SUN Z D, HAN J F, et al. A carbonate fluid identification method based on quantum particle swarm fuzzy neural network[J]. Chinese Journal of Geophysics, 2014, 57(3): 991-1000.)

[21] BRITS R, ENGELBRECHT A P, van den BERGH F. A niching particle swarm optimizer [EB/OL]. [2018- 02- 05]. http://pdfs.semanticscholar.org/7cd3/4dce1b828e41e6f0a1485ac1ce1860228499.pdf.