張延年， 吳士力， 劉 永

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

0 引 言

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

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

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

1 算法設(shè)計

1.1 粒子聚簇

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

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

(1)

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

(2)

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

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

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

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

(3)

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

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

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

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

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

N為種群大小。

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

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

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

情形2AFCj

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

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

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

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

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

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

步驟4在Ring-拓撲下選擇聚簇中的最優(yōu)位置作為每個粒子的nbesti;

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

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

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

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

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

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

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

(6)

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

(7)

c1rand()c2rand()/2

則

(8)

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

(9)

(10)

則當

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

3 實驗分析

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

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

表1 函數(shù)聲明

實驗1種群分布。

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

(a) PSO的種群分布

(b) KPSO的種群分布

(c) HPSOC的種群分布

圖1 種群分布

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

(a) f1(b) f2

(c) f3(d) f4

(e) f5(f) f6

圖2 收斂性性能

實驗2收斂性。

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

實驗3適應(yīng)度統(tǒng)計分析。

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

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

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

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

實驗4HPSOC的敏感度分析。

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

表3 算法敏感度

4 結(jié) 語

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

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