一種基于聚簇的自適應改進粒子群優化算法

張延年， 吳士力， 劉 永

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

0 引 言

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

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

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

1 算法設計

1.1 粒子聚簇

類似于社會中的群體結構，種群中的單個粒子個體主要通過學習鄰近區域內的其他優秀粒子來改進自身行為[10]。基于該思想，HPSOC算法設計基于聚簇的方法將種群粒子進行動態劃分，具有相似特征的粒子劃分為一個聚簇。聚簇方法改進了傳統聚簇的簇內粒子數量固定的不足，具有動態連續性。且在粒子狀態更新后聚族過程將重新啟動，進而形成簇內粒子數量不同，大小非均勻的簇結構。粒子可在簇間移動和信息交換，增強了群體振動性。選擇K-均值方法對粒子群進行聚簇[12]。

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

(1)

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

(2)

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

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

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

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

(3)

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

1.2 粒子自適應調整

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

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

種群的平均適應度則為

N為種群大小。

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

假設以最小化適應度值為目標，其比較結果有以下兩種情形：

情形1AFCj≥AFS。表明該聚簇子種群處于較優位置，離最優解較近。此時應該減少該聚簇內粒子的搜索步長，以增強其局部搜索能力。此時可調整減少慣性權重w。

情形2AFCj

根據以上分析，粒子自適應調整方式具體為：

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

HPSOC算法由兩部分組成：① 利用K-均值方法對粒子群進行聚簇，以形成多個不同的子種群，同時，不同聚簇間的信息交換通過Ring-拓撲結構執行。② 進行參數自適應調整，目標是根據不同聚簇的狀態調整粒子的搜索行為。具體步驟為：

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

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

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

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

步驟5計算每個粒子的適應度，選擇gbest;

步驟6如果滿足終止條件，則輸出結果；否則，轉至步驟7執行；

步驟7根據式(4)調整wi和vmaxi；

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

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

定理1HPSOC算法具有穩定的收斂性。

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

(6)

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

(7)

c1rand()c2rand()/2

則

(8)

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

(9)

(10)

則當

時，系統是漸進穩定的，即表明HPSOC算法是穩定且收斂的。

3 實驗分析

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

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

表1 函數聲明

實驗1種群分布。

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

(a) PSO的種群分布

(b) KPSO的種群分布

(c) HPSOC的種群分布

圖1 種群分布

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

(a) f1(b) f2

(c) f3(d) f4

(e) f5(f) f6

圖2 收斂性性能

實驗2收斂性。

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

實驗3適應度統計分析。

本部分通過統計分析的方法分析適應度的最小值min、最大值max、平均最優值Mean Best和標準差值St.Dev。最大迭代次數設置為400，實驗結果如表2所示。

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

表2 搜索能力的統計分析

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

實驗4HPSOC的敏感度分析。

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

表3 算法敏感度

4 結 語

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

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