一種基于聚簇的自適應(yīng)改進(jìn)粒子群優(yōu)化算法

張延年， 吳士力， 劉 永

(1. 南京交通職業(yè)技術(shù)學(xué)院 電子信息工程學(xué)院， 南京 211188; 2. 南京理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 南京 211188)

0 引 言

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是一種種群智能優(yōu)化方法，受鳥群啟發(fā)，其核心是通過種群個(gè)體間的協(xié)作和信息交換尋找目標(biāo)問題的最優(yōu)或次優(yōu)解[1]。由于PSO的高效、簡單和健壯性，該方法廣泛應(yīng)用于多目標(biāo)最優(yōu)化、調(diào)度優(yōu)化、人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練和路徑規(guī)化問題的研究中[2]。然而，經(jīng)過廣泛研究，作為進(jìn)化算法，如何在搜索現(xiàn)有空間與開發(fā)新搜索空間上取得均衡是PSO一直面臨的難題。PSO在其搜索初期，種群粒子可以很快移動(dòng)并聚集至較優(yōu)解的周圍。然而，在搜索末期，整個(gè)種群會(huì)在相同點(diǎn)區(qū)域內(nèi)變得密集，粒子易于陷入至局部最優(yōu)點(diǎn)區(qū)域，出現(xiàn)早熟現(xiàn)象。

研究表明[3]，傳統(tǒng)PSO中, 如果慣性權(quán)重w設(shè)置過大, 則PSO類似于全局搜索算法, 種群總是在探索新的區(qū)域，導(dǎo)致了搜索分散，種群不穩(wěn)定，不易收斂；如果w設(shè)置過小，則算法類似于局部搜索算法，種群很快收斂，導(dǎo)致容易陷入局部極值點(diǎn)。vmax則對(duì)粒子尋解的步長具有一定影響，過大過小都不適合粒子移動(dòng)。以此作為突破口學(xué)者們作了很多改進(jìn)工作。文獻(xiàn)[4]中通過模糊控制和隨機(jī)化方法對(duì)粒子迭代過程進(jìn)行了慣性權(quán)重調(diào)整，效果一般。文獻(xiàn)[5]中則引入收斂因子進(jìn)行粒子迭代處理，并動(dòng)態(tài)地進(jìn)行參數(shù)配置防止種群個(gè)體向著非較優(yōu)區(qū)域移動(dòng)，達(dá)到了控制收斂的目的。部分文獻(xiàn)從種群結(jié)構(gòu)整體出發(fā)進(jìn)行優(yōu)化。文獻(xiàn)[6]中設(shè)計(jì)一種動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)控制粒子的移動(dòng)，在初期粒子鄰居區(qū)域內(nèi)粒子數(shù)量較少，在粒子搜索過程中，根據(jù)粒子間距，其他粒子動(dòng)態(tài)加入擴(kuò)展鄰近區(qū)域。該算法改進(jìn)了靜態(tài)結(jié)構(gòu)不變的特點(diǎn)，使得粒子的鄰近空間可以不斷更新，有利于種群的多樣性。文獻(xiàn)[7]中引入聚類思想，以聚類的中心粒子替換傳統(tǒng)PSO中的粒子最優(yōu)解，以全局聚類中心替換全局最優(yōu)粒子，實(shí)現(xiàn)了粒子鄰近區(qū)域的更新優(yōu)化，并證明了聚類方法的有效性，但算法缺乏對(duì)所選中心的優(yōu)化。文獻(xiàn)[8]中設(shè)計(jì)了一種可變結(jié)構(gòu)的動(dòng)態(tài)聚類粒子群算法，使粒子群個(gè)體在不同階段進(jìn)行成簇，改進(jìn)粒子尋優(yōu)搜索性能。文獻(xiàn)[9]中利用小世界網(wǎng)絡(luò)原理優(yōu)化粒子鄰近搜索區(qū)域，避免了種群早熟，提高粒子尋優(yōu)的收斂性。但文獻(xiàn)缺乏對(duì)如何聚類的描述，以及聚類對(duì)算法的影響。

本文以種群分布結(jié)構(gòu)和自適應(yīng)性為基礎(chǔ)，采用聚簇方法對(duì)整個(gè)種群進(jìn)行動(dòng)態(tài)劃分，形成多個(gè)聚簇，每個(gè)聚簇根據(jù)得到搜索解與整個(gè)種群的最優(yōu)解比較，根據(jù)比較結(jié)果對(duì)聚簇成員粒子進(jìn)行自適應(yīng)參數(shù)調(diào)整。聚簇劃分在每次迭代時(shí)自發(fā)進(jìn)行，每個(gè)聚簇粒子數(shù)量不同，以降低了陷入局部極值的可能性，且聚簇間粒子可以移動(dòng)，增加粒子信息交換，提高搜索效率。而通過自適應(yīng)參數(shù)調(diào)整，不僅可以消除算法對(duì)參數(shù)設(shè)置的依賴，而且可以賦予每個(gè)簇不同的搜索能力，進(jìn)一步增強(qiáng)簇的差異性和多樣性。與此同時(shí)，這種參數(shù)的自適應(yīng)性調(diào)整，可以進(jìn)一步提高進(jìn)化優(yōu)良粒子簇的局部尋優(yōu)能力，從而使算法的搜索精度和效率都有很大提高。

1 算法設(shè)計(jì)

1.1 粒子聚簇

類似于社會(huì)中的群體結(jié)構(gòu)，種群中的單個(gè)粒子個(gè)體主要通過學(xué)習(xí)鄰近區(qū)域內(nèi)的其他優(yōu)秀粒子來改進(jìn)自身行為[10]。基于該思想，HPSOC算法設(shè)計(jì)基于聚簇的方法將種群粒子進(jìn)行動(dòng)態(tài)劃分，具有相似特征的粒子劃分為一個(gè)聚簇。聚簇方法改進(jìn)了傳統(tǒng)聚簇的簇內(nèi)粒子數(shù)量固定的不足，具有動(dòng)態(tài)連續(xù)性。且在粒子狀態(tài)更新后聚族過程將重新啟動(dòng)，進(jìn)而形成簇內(nèi)粒子數(shù)量不同，大小非均勻的簇結(jié)構(gòu)。粒子可在簇間移動(dòng)和信息交換，增強(qiáng)了群體振動(dòng)性。選擇K-均值方法對(duì)粒子群進(jìn)行聚簇[12]。

(1) 定義1 選擇K個(gè)粒子作為中心(p1,p2,…,pK)，定義不同粒子間的距離為：

(1)

(2) 定義2 聚簇的目標(biāo)函數(shù)定義為：

(2)

式中：Ck表示粒子的聚簇k。

HPSOC算法的粒子聚簇過程為：

① 步驟1 首先，隨機(jī)從種群中選擇K個(gè)粒子(p1,p2,…,pK)，每個(gè)粒子視為一個(gè)聚簇的中心。② 步驟2 計(jì)算其他粒子與聚簇中心的距離dis(xj,xk)，根據(jù)距離最小的原則(式(2))，將剩余粒子分配至距離中心最近的聚簇內(nèi)。③ 步驟3 對(duì)于每個(gè)聚簇，選擇聚簇內(nèi)粒子位置的平均值作為新的聚簇中心。④ 步驟4 如果達(dá)到終止條件，則輸出結(jié)果；否則，返回步驟2繼續(xù)執(zhí)行。

粒子聚簇形成后，評(píng)估粒子適應(yīng)度，選擇最優(yōu)個(gè)體作為聚簇內(nèi)的最優(yōu)解。多個(gè)聚簇之間的關(guān)聯(lián)性，通過Ring-結(jié)構(gòu)進(jìn)行聚簇間的信息交換方法。在Ring-結(jié)構(gòu)中，每個(gè)聚簇與其鄰居的兩個(gè)聚簇相連，每個(gè)聚簇內(nèi)的粒子可依據(jù)該結(jié)構(gòu)與其他粒子進(jìn)行信息交換，令聚簇j至目前為止搜索到的最優(yōu)解為Cbj，粒子i的鄰居最優(yōu)解為nbesti=(nbi1,nbi2,…,nbiD)，其中粒子i屬于聚簇j，此時(shí)比較Cbj-1,Cbj與Cbj+1的大小，選擇3者間的最優(yōu)解作為粒子i的鄰居nbest。由于gbest 和nbesti對(duì)粒子的學(xué)習(xí)能力均擁有重要影響，因此，HPSOC算法建立了粒子速度的更新模式：

(3)

該過程后，新的種群結(jié)構(gòu)在Ring-結(jié)構(gòu)下在不同聚簇間得以重新動(dòng)態(tài)建立，每個(gè)粒子將基于previous best、neighborhood best、global best信息更新其位置。

1.2 粒子自適應(yīng)調(diào)整

顯然地，通過以上的聚簇方法得到的粒子聚簇?fù)碛胁煌慕Y(jié)構(gòu)，包含的粒子數(shù)量也不相同。同時(shí)，由于粒子能力的不同，聚簇的搜索能力也是各不相同的，表現(xiàn)為與最優(yōu)粒子的平均距離是各不相同的。因此，可以基于這種平均距離的不同將所有聚簇進(jìn)行搜索能力等級(jí)的劃分。

定義3令粒子聚簇i為Ci，|Ci|表示聚簇i中粒子數(shù)量，fji表示粒子j在聚簇i中的適應(yīng)度，則聚簇i的平均適應(yīng)度為

種群的平均適應(yīng)度則為

N為種群大小。

由于搜索過程中每個(gè)粒子處于不同的位置，個(gè)體表現(xiàn)出不同的特征和能力。適應(yīng)度是區(qū)別這種不同的最佳手段。處于不同階段的粒子在搜索空間中需要增加在該階段所需要的能力，例如：若粒子處于較差的位置，則需要較快脫離較差區(qū)域，加速搜索其他空間區(qū)域；若粒子已經(jīng)處于較優(yōu)的位置，則需要進(jìn)一步探索所在區(qū)域，以尋找更優(yōu)解。HPSOC算法基于粒子聚簇改進(jìn)粒子的搜索能力，聚簇后的簇內(nèi)粒子擁有不同的優(yōu)劣點(diǎn)，導(dǎo)致其得到的聚簇的平均適應(yīng)度也是不同的。HPSOC算法根據(jù)這種差異通過調(diào)整每個(gè)個(gè)體的慣性權(quán)重來評(píng)估聚簇。

假設(shè)以最小化適應(yīng)度值為目標(biāo)，其比較結(jié)果有以下兩種情形：

情形1AFCj≥AFS。表明該聚簇子種群處于較優(yōu)位置，離最優(yōu)解較近。此時(shí)應(yīng)該減少該聚簇內(nèi)粒子的搜索步長，以增強(qiáng)其局部搜索能力。此時(shí)可調(diào)整減少慣性權(quán)重w。

情形2AFCj

根據(jù)以上分析，粒子自適應(yīng)調(diào)整方式具體為：

2 HPSOC算法流程與收斂性分析

HPSOC算法由兩部分組成：① 利用K-均值方法對(duì)粒子群進(jìn)行聚簇，以形成多個(gè)不同的子種群，同時(shí)，不同聚簇間的信息交換通過Ring-拓?fù)浣Y(jié)構(gòu)執(zhí)行。② 進(jìn)行參數(shù)自適應(yīng)調(diào)整，目標(biāo)是根據(jù)不同聚簇的狀態(tài)調(diào)整粒子的搜索行為。具體步驟為：

步驟1隨機(jī)設(shè)置xi和vi，計(jì)算每個(gè)粒子個(gè)體的fj，初始化wmax和wi，隨機(jī)選擇K個(gè)粒子作為聚簇的中心；

步驟2利用K-均值聚簇方法對(duì)種群進(jìn)行子劃分，得到子種群Clusterj,j∈(1,2,…,K) (K為聚簇?cái)?shù)量)；

步驟3設(shè)置至當(dāng)前為止所找到的粒子i(i∈(1,2,…, |Cj|) )的最優(yōu)位置pbesti為聚簇j的最優(yōu)位置Cbj;

步驟4在Ring-拓?fù)湎逻x擇聚簇中的最優(yōu)位置作為每個(gè)粒子的nbesti;

步驟5計(jì)算每個(gè)粒子的適應(yīng)度，選擇gbest;

步驟6如果滿足終止條件，則輸出結(jié)果；否則，轉(zhuǎn)至步驟7執(zhí)行；

步驟7根據(jù)式(4)調(diào)整wi和vmaxi；

步驟8根據(jù)式(3)更新每個(gè)粒子的xi和vi；

步驟9計(jì)算每個(gè)聚簇Clusterj的位置均值，選擇均值位置作為新的聚簇中心，并返回步驟2執(zhí)行。

定理1HPSOC算法具有穩(wěn)定的收斂性。

證明：重寫式(1)和式(4)為：

(6)

令c1rand()+c2rand()=α，則

(7)

c1rand()c2rand()/2

則

(8)

以上等式表示一個(gè)離散時(shí)間的系統(tǒng)方程，其穩(wěn)定的充分必要條件是矩陣A的特征值的模小于1。矩陣A的特征值為：

(9)

(10)

則當(dāng)

時(shí)，系統(tǒng)是漸進(jìn)穩(wěn)定的，即表明HPSOC算法是穩(wěn)定且收斂的。

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

為了評(píng)估HPSOC算法的性能，在Matlab中進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)在相同參數(shù)情況下同時(shí)實(shí)現(xiàn)了PSO、KPSO(K-means Particle Swarm Optimization)[7]和HPSOC 3種算法。并選擇6種最具代表性的基準(zhǔn)函數(shù)進(jìn)行粒子群優(yōu)化性能的測試，包括：Sphere函數(shù)f1、Quadric函數(shù)f2、Rosenbrock函數(shù)f3、Rastrigin函數(shù)f4、Griewank函數(shù)f5以及Rotated Quadric函數(shù)f6(6種基準(zhǔn)測試函數(shù)中，f3、f4、f5和f6是多峰函數(shù)，其他為單峰函數(shù))：

表1給出了基準(zhǔn)函數(shù)的相關(guān)聲明，相關(guān)參數(shù)設(shè)置為：種群規(guī)模N=30，初始速度vmax=30，學(xué)習(xí)因子c1=c2=1.5 for PSO,c1=c2=0.5 for others，慣性權(quán)重wmax=0.9,wmin=0.4，聚簇?cái)?shù)量K=5，最大速度vf=30。

表1 函數(shù)聲明

實(shí)驗(yàn)1種群分布。

種群分布一定程度上可以反映種群的多樣性。筆者記錄了在迭代次數(shù)為50、100和200時(shí)所有粒子的位置信息(見圖1)。

(a) PSO的種群分布

(b) KPSO的種群分布

(c) HPSOC的種群分布

圖1 種群分布

由于多峰函數(shù)在此項(xiàng)指標(biāo)上更具代表性，圖2給出了多峰函數(shù)的實(shí)驗(yàn)結(jié)果。對(duì)于PSO，種群始終處于較分散的狀態(tài)。尤其在后面的階段中，一些粒子很容易陷入至某些局部極值點(diǎn)的區(qū)域內(nèi)。比較PSO，KPSO具有更好的全局收斂性，同時(shí)，在后期的階段中，KPSO中的大部分粒子可能進(jìn)入全局最優(yōu)點(diǎn)的區(qū)域中。HPSOC中的粒子明顯具有比PSO更好的聚集，并且HPSOC不會(huì)陷入局部最優(yōu)點(diǎn)區(qū)域從而導(dǎo)致早熟。而比較KPSO，HPSOC則擁有更快的收斂速度。

(a) f1(b) f2

(c) f3(d) f4

(e) f5(f) f6

圖2 收斂性性能

實(shí)驗(yàn)2收斂性。

由圖2可知，在相同初始值的條件下，HPSOC在收斂速度和收斂精確度上均優(yōu)于PSO和KPSO。KPSO通過利用聚簇得到了比PSO更高的解能力，其收斂速度也更快。而HPSOC則通過自適應(yīng)調(diào)整克服了KPSO的缺點(diǎn)，降低了對(duì)初始參數(shù)的依賴性，這可以提高算法的局部搜索和全局搜索能力。

實(shí)驗(yàn)3適應(yīng)度統(tǒng)計(jì)分析。

本部分通過統(tǒng)計(jì)分析的方法分析適應(yīng)度的最小值min、最大值max、平均最優(yōu)值Mean Best和標(biāo)準(zhǔn)差值St.Dev。最大迭代次數(shù)設(shè)置為400，實(shí)驗(yàn)結(jié)果如表2所示。

由于單峰函數(shù)中可行區(qū)域中僅存在一個(gè)全局極值點(diǎn)，且越接近極值點(diǎn)其變化越輕微，因此更加適合于測試算法的搜索速度。由表2可知，HPSOC和KPSO的結(jié)果精確性明顯高于PSO，這表明聚簇方法對(duì)于個(gè)體多樣性和保持迭代進(jìn)化是有效可行的。比較KPSO，HPSOC的效果更好。在相同的配置下，min、max和Mean Best的統(tǒng)計(jì)值更接近于全局最優(yōu)。這表明通過自適應(yīng)調(diào)整策略，種群個(gè)體能夠增強(qiáng)搜索能力，在gbest和nbest的影響下，粒子可以選擇更合適的方向進(jìn)化。

表2 搜索能力的統(tǒng)計(jì)分析

在多峰函數(shù)中，HPSOC也擁有優(yōu)于KPSO和PSO的性能。HPSOC和KPSO擁有比PSO更加接近的全局最小值，這表明聚簇可以改進(jìn)粒子擺脫局部極值點(diǎn)的能力。同時(shí)，多峰函數(shù)的測試結(jié)果還表明聚簇可以避免種群過早成熟，通過根據(jù)不同階段的自適應(yīng)參數(shù)調(diào)整使個(gè)體擁有了更好的學(xué)習(xí)能力，提升了種群的搜索能力。

實(shí)驗(yàn)4HPSOC的敏感度分析。

本節(jié)的目標(biāo)是觀察wmax對(duì)HPSOC算法性能的影響，結(jié)果如表3所示。實(shí)驗(yàn)中以0.1為步長，wmax取值范圍為[0.6, 0.9]，最大迭代次數(shù)為200，每個(gè)基準(zhǔn)函數(shù)運(yùn)行30次。對(duì)于單峰函數(shù)，在不同的wmax取值下，最差解處于10-43～10-59之間，其精度滿足預(yù)設(shè)要求。最優(yōu)解達(dá)到10-68的數(shù)量級(jí)。而從平均解和標(biāo)準(zhǔn)方差可以看出，算法得到的解處于較優(yōu)的等級(jí)，且波動(dòng)幅度很小。對(duì)于多峰函數(shù)，其精度也滿足需求，其統(tǒng)計(jì)結(jié)果也其他函數(shù)是相似的。綜合以上統(tǒng)計(jì)結(jié)果分析，不同的初始參數(shù)設(shè)置對(duì)算法性能并無重大影響，這證明HPSOC算法對(duì)于參數(shù)wmax的取值具有較好的魯棒性，對(duì)初始參數(shù)值無明顯敏感度。

表3 算法敏感度

4 結(jié) 語

提出了一種具有動(dòng)態(tài)聚簇功能的自適應(yīng)粒子群優(yōu)化算法。算法利用k-均值聚簇方法將種群動(dòng)態(tài)劃分為包含不同粒子數(shù)量的異構(gòu)聚簇，利用Ring結(jié)構(gòu)進(jìn)行不同聚簇間的信息交換。并設(shè)計(jì)了新的聚簇搜索階段發(fā)現(xiàn)方法，使得每個(gè)粒子可以根據(jù)其聚簇搜索階段，動(dòng)態(tài)自適應(yīng)地調(diào)整粒子參數(shù)，進(jìn)而使得每個(gè)聚簇可以獲得與其階段相匹配的自我搜索能力。通過6種基準(zhǔn)函數(shù)的測試，結(jié)果證明所提算法不僅能夠有效避免種群陷入局部極值點(diǎn)，而且收斂性更好。

——摘自《國家中長期教育改革和發(fā)展規(guī)劃綱要(2010-2020年)》