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

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

0 引言

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

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

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

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

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

經(jīng)典粒子群算法中的每一個(gè)粒子均為優(yōu)化問題的一個(gè)潛在解，并采用位置、速度和適應(yīng)度3個(gè)屬性來描述粒子的特性，算法中粒子速度與位置的更新公式如式(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)位置；下標(biāo)j表示向量第j維的屬性值；參數(shù)ω為慣性權(quán)重因子，用于協(xié)調(diào)全局搜索能力與局部搜索能力。參數(shù)r1、r2為[0,1]間均勻分布的隨機(jī)數(shù)，參數(shù)c1、c2稱為加速系數(shù)，用于控制社會(huì)認(rèn)知與個(gè)體認(rèn)知對(duì)速度的影響。粒子在解空間內(nèi)利用式(1)、(2)追蹤個(gè)體最優(yōu)位置與全局最優(yōu)位置來更新自身的位置，并通過不斷迭代來找尋最優(yōu)解。

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

(3)

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

2 KFC-MSBPSO算法

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

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

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

(4)

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

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

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

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

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

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

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

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

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

(5)

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

(6)

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

(7)

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

(8)

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

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

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

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

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

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

(11)

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

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

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

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

(12)

2.4 子群重建策略

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

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

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

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

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

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

2.5 KFC-MSBPSO算法流程

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

算法1 KFC-MSBPSO算法。

初始化n維主群粒子S.xm，設(shè)置子群個(gè)數(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

運(yùn)用動(dòng)態(tài)閾值策略從集合v中選取N個(gè)聚類中心

核模糊聚類劃分子群

Repeat

For 每個(gè)子群Sk與主群SDo

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

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

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

Sk=Sk∪xm

S=S〗xm

Endif

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

更新子群半徑Sk.R

計(jì)算子群Sk被選擇概率Pchoose

利用式(8)計(jì)算子群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ù)值實(shí)驗(yàn)及分析

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

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

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

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

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

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

3.2 實(shí)驗(yàn)分析

3.2.1 算法性能對(duì)比

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

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

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

3.2.2 算法收斂性對(duì)比分析

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

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

由圖3可以得出以下結(jié)論：第一，在低維解空間內(nèi)(Dim=5，Dim=30)，各算法收斂速度接近。這是由于維度較低時(shí)對(duì)算法性能要求較低，算法能夠較快地收斂于全局最優(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)的方式可以提高算法整體的運(yùn)行效率，因此相對(duì)于全局搜索模式，協(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 算法時(shí)間開銷對(duì)比分析

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

[15] 謝紅俠,馬曉偉,陳曉曉,等.基于多種群的改進(jìn)粒子群算法多模態(tài)優(yōu)化[J].計(jì)算機(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é)報(bào),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] 盛萬(wàn)興,季宇,吳鳴,等.基于改進(jìn)模糊C均值聚類算法的區(qū)域集中式光伏發(fā)電系統(tǒng)動(dò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ò)碳酸鹽巖流體識(shí)別方法研究[J].地球物理學(xué)報(bào),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.