劉道華，胡秀云，趙巖松，崔玉爽

(1. 信陽師范學院 計算機與信息技術學院，河南 信陽 464000；2. 信陽師范學院 河南省教育大數(shù)據(jù)分析與應用重點實驗室，河南 信陽 464000)

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是一種群體智能的隨機優(yōu)化算法，由于其具有控制參數(shù)少、收斂速度快和尋優(yōu)效果好等優(yōu)點，廣泛應用于復雜多峰優(yōu)化問題的求解．為了增強粒子群算法的全局搜索能力，許多學者采用了各種改進策略以提高粒子群優(yōu)化算法的求解性能．在眾多的改進算法中，基本上均是從參數(shù)優(yōu)化、解的鄰域選擇、種群劃分以及算法混合上進行改進．在參數(shù)優(yōu)化改進上，如文獻[1]發(fā)現(xiàn)當慣性權重隨迭代次數(shù)線性遞減時算法尋優(yōu)效果較好．文獻[2]設計了一種基于離散度大小的動態(tài)調整粒子群參數(shù)的優(yōu)化方法．在解的鄰域選擇上，文獻[3]利用個體粒子間“充分信任”的信息，提出了一種粒子群優(yōu)化算法鄰域結構的選擇方法．文獻[4]利用粒子的衰退機理，提出了一種動態(tài)調整全局最優(yōu)型鄰域結構的方法，以增強粒子尋優(yōu)時最優(yōu)解的多樣性．在種群劃分上，文獻[5]采用主-從群混合進化的粒子群算法優(yōu)化規(guī)則參數(shù)，建立了一種基于雙啟動標準的限制供水解析規(guī)則，以此提高算法的求解精度和收斂速度．文獻[6]提出了一種基于分類的自適應粒子群優(yōu)化算法．在算法混合上，文獻[7]針對目前粒子群優(yōu)化算法在多零點低旁瓣約束的陣列天線方向圖綜合中早熟收斂、易陷入局部極值的問題，融合混沌優(yōu)化算法和粒子群優(yōu)化算法的優(yōu)點，提出了一種新的混合優(yōu)化算法．文獻[8]提出了一種混合小生境粒子群優(yōu)化算法，以求解復雜多峰優(yōu)化問題．總之，這些改進策略均提高了粒子群算法的求解性能．但既采用分群劃分的改進策略，同時又使用參數(shù)調整的策略，這樣的文獻還很少見．基于此，筆者將粒子群依據(jù)k的均值聚類劃分成若干個子群，同時以子群為中心，更改子群算法的參數(shù)，將子群粒子優(yōu)化過程中的熵信息融入到子群慣性權重參數(shù)ω的調整上，通過經(jīng)典的Benchmark典型測試函數(shù)進行驗證，并同其他優(yōu)化方法進行求解對比得出，這種動態(tài)分群帶熵權的粒子群優(yōu)化方法具有收斂速度快、解的精度高，尤其在對復雜的多峰病態(tài)函數(shù)求解時，既能獲得函數(shù)的所有峰值解，又能提高解的精度．

1 粒子群算法動態(tài)分群及帶熵權策略

1.1 粒子群算法動態(tài)分群策略

傳統(tǒng)的粒子群算法基本上均為一個群體，這種方法用于求解復雜多峰函數(shù)時，很難找全所有峰值解，尤其對于復雜局部近似峰值解時，該方法更難找全局部峰值解．為了獲得復雜多峰函數(shù)所有峰值解以及所有局部峰值解，采用多子群且先粗搜索后精搜索的方式進行求解．在粗搜索的過程中，先將初始化后的隨機粒子或是優(yōu)化迭代一步后的粒子采用k均值聚類的方式構建k個子群體，每個子群體依據(jù)自身子種群對原問題進行優(yōu)化迭代的每一次，均將執(zhí)行一次k均值聚類重新分群，從而實現(xiàn)粒子群動態(tài)分群策略．

1.2 粒子群算法帶熵權策略

在傳統(tǒng)的PSO算法中，設搜索空間的維數(shù)為D，粒子群個體規(guī)模為s，則第i個粒子的當前位置狀態(tài)xi= (x1，x2，…，xD)T，當前速度vi= (v1，v2，…，vD)T，當前搜索到最優(yōu)位置pi= (pi,1，pi,2，…，pi,D)T，i=1，2，…，s．設整個種群搜索到最優(yōu)位置時對應粒子下標為g，則PSO中各粒子的速度位置更新方程為

其中，t為當前迭代次數(shù)，t=1，2，…，maxgen;d表示維度，d=1，2，…，D;c1和c2分別為個體認知因子和社會認知因子，但在一般情況下，c1=c2= 2;r1和r2為隨機數(shù)，獨立服從區(qū)間(0，1)上均勻分布;ω為慣性權重[9]．

從式(1)和式(2)可以看出，傳統(tǒng)粒子群算法的關鍵參數(shù)分別為慣性權重參數(shù)ω、加速因子參數(shù)c1及c2．許多學者都提出ω的值應該在算法搜索迭代過程中線性下降，ω可表示為

ω=ωmax-(ωmax-ωmin)g/G，

(3)

其中，g是算法的當前迭代次數(shù)，G是最大迭代次數(shù)，ωmax和ωmin一般設為0.9和0.4．

這種傳統(tǒng)的慣性權重參數(shù)調整方法不能很好地獲得其他粒子熵信息．基于此，在任一子群進行粗搜索時就充分利用其他子群的熵信息，因此，對于式(1)中的ω將采用如下操作方式獲得．

假定通過k均方聚類獲得k個聚類中心，則設子群數(shù)為k個，當然每個子群所包含的粒子數(shù)可能不相等．在每個子群經(jīng)過m次迭代后，每個子群獲得的優(yōu)化解設為Aj，其中j∈ (1，2，…，m)，則k個子群經(jīng)過m次迭代后所構建的最優(yōu)解矩陣D為

(4)

全局最優(yōu)解D歸一化后，得

(5)

每個子群在迭代搜索m次時全局解Aj的信息熵為

(6)

(7)

由于式(1)中的r1和r2為隨機數(shù)，且獨立服從區(qū)間(0，1)上均勻分布，則該參數(shù)不能充分利用本群內其他粒子的信息熵．基于此，將參數(shù)r2附加上自身群內不同粒子間迭代搜索的熵信息，此時自身群n個粒子經(jīng)過m次迭代時獲得的優(yōu)化解設為Aj，其中j∈ (1，2，…，m)，則n個粒子經(jīng)過m次迭代后所構建的最優(yōu)解矩陣D為

(8)

同樣，本群內新的信息熵權為

(9)

同樣，采用式(5)及式(6)計算Ej所用的Aij將依據(jù)式(8)計算得出．

相應地，將式(1)更改為

vi，d(t+1)=ω′vi，d(t)+c1r[pi，d(t)-xi，d(t)]+c2[ω″pg，d(t)-xi，d(t)] ．

(10)

在精搜索過程中，不存在其他子群的熵信息，仍采用k個子群構建k個粒子，每個粒子的初始位置以當前群獲得的最優(yōu)解為初始設置，進行PSO精搜索．在精搜索過程中，依據(jù)每一子群搜索到最優(yōu)解時那一粒子的最終信息構成新粒子群的初始信息，即此時群體有k個粒子．式(10)中不存在其他子群的熵信息，此時的ω′將以式(1)中的ω代替，而Aj為k個粒子經(jīng)過m次迭代時的最優(yōu)值．則該群內全局優(yōu)化解將附加的信息熵權為

(11)

同樣，此時采用式(5)及式(6)計算Ej所用的Aij將依據(jù)式(8)計算得出．

相應地，將式(1)更改為

vi，d(t+1)=ωvi，d(t)+c1r[pi，d(t)-xi，d(t)]+c2[ω?pg，d(t)-xi，d(t)] ．

(12)

2 動態(tài)分群帶熵權的粒子群優(yōu)化方法

動態(tài)分群帶熵權的粒子群優(yōu)化方法先進行粗搜索，以獲得復雜多峰最優(yōu)解或近似最優(yōu)解，并將該最優(yōu)解作為精搜索的初始信息．該方法粗搜索的具體步驟如下:

步驟1 初始化．依據(jù)被優(yōu)化多峰函數(shù)的難易程度選擇初始群體的規(guī)模s，最大迭代次數(shù)maxgen，迭代次數(shù)計數(shù)器t為0、ωmax和ωmin，初始化粒子群，即隨機設定各粒子的初始位置x和初始速度v．

步驟3 計算所有子群每一個粒子的適應度值．

步驟4 比較所有子群每個粒子的適應度值和它自身經(jīng)歷過的最好位置pi，d的適應度值，如果優(yōu)于先前最優(yōu)值，則用此時適應度值替換原pi，d值．

步驟5 尋找當前所有群所有粒子的最優(yōu)位置適應度值pd．

步驟6 比較所有子群每個粒子的適應度值和該子群體經(jīng)歷過的最好位置pg，d的適應度值，如果優(yōu)于先前最優(yōu)值pd，則用此時適應度值替換原pg，d值．

步驟7 分別計算式(2)，式(4)～式(10)，調整各子群各粒子的速度及位置．

步驟8 迭代計數(shù)器t=t+1．

步驟9 判斷是否達到最大迭代次數(shù)，如滿足，則退出循環(huán)；否則，轉步驟2．

該方法精搜索的具體步驟如下:

步驟1 將粗搜索各子群獲得最優(yōu)位置及速度的粒子作為精搜索粒子群的初始條件(粒子個數(shù)與原子群個數(shù)相同)，重新設置最大迭代次數(shù)，迭代次數(shù)計數(shù)器t=0．

步驟2 計算各個粒子的適應度值．

步驟3 比較每一個粒子適應度值和它自身經(jīng)歷過的最好位置pi，d的適應度值，如果優(yōu)于先前最優(yōu)值，則用此時適應度值替換原pi，d值．

步驟4 比較每一個粒子適應度值和該群體經(jīng)歷過的最好位置pg，d的適應度值，如果優(yōu)于先前最優(yōu)值，則用此時適應度值替換原pg，d值．

步驟5 分別計算式(2)～式(6)，式(11)～式(12)，調整各粒子的速度及位置．

步驟6 迭代計數(shù)器t=t+1．

步驟7 判斷是否達到最大迭代次數(shù)，如滿足，則退出循環(huán)；否則，轉步驟2．

3 實例及分析

為了驗證該優(yōu)化方法求解復雜函數(shù)的有效性，以如下4個代表性的Benchmark測試函數(shù)為例:

4個函數(shù)在三維坐標下的圖像如圖1所示．

圖1 4個測試函數(shù)的函數(shù)圖像

基于上述4個代表性的不同種類型的測試函數(shù)，用文中方法與傳統(tǒng)的PSO方法、文獻[9]所提多策略粒子群優(yōu)化(Multi-strategy Particle Swarm Optimization，MPSO)方法進行算法性能比較．

在實驗過程中，采用Intel(R) Core(TM) i3-2120 CPU，@ 3.30 GHz，并在MATLAB R2008a編程環(huán)境下進行求解驗證．每個測試函數(shù)維數(shù)D固定設置為10，每個函數(shù)采用每種方法獨立運行50次，統(tǒng)計每個函數(shù)的最優(yōu)值、平均值、標準差以及平均迭代數(shù)(若沒找到最優(yōu)解則將其視為最大迭代次數(shù))．對于傳統(tǒng)的PSO方法，其算法參數(shù)設置: 個體規(guī)模s= 30，最大迭代數(shù)G= 1 000，個體認知因子和社會認知因子c1=c2=2，慣性權重ωmax和ωmin分別為0.9和0.4．對于MPSO方法，其算法參數(shù)設置：維數(shù)D= 30，種群大小ps= 20，最大速度vmax= 0.1xmax，加速系數(shù)c1=c2=2．對于文中方法，其算法參數(shù)設置: 個體規(guī)模s= 100，最大迭代數(shù) maxgen= 1 000，個體認知因子和社會認知因子c1=c2=2，式(12)中慣性權重ωmax和ωmin分別為0.9和0.4．實驗結果如表1所示．

從表1中數(shù)據(jù)對比可知，文中方法的平均迭代數(shù)遠少于傳統(tǒng)PSO方法和MPSO方法的，這充分體現(xiàn)文中方法具有較高的優(yōu)化效率．而文中方法的最優(yōu)值、平均值以及標準差也優(yōu)于其他兩種方法對應的指標，表明文中方法具有較強的求解穩(wěn)定性．由于4個函數(shù)的理論值均為零，在實驗中，尤其對于復雜多峰函數(shù)f3及f4具有大量局部極值點，由于文中方法利用了其他熵權信息，而且在精搜索過程中，許多局部極值點在粗搜索過程中就事先找到，從而提高了整個算法的搜索效率．總之，文中方法是一種綜合性能較好的粒子群優(yōu)化算法．

圖2～圖5給出了4個函數(shù)3種方法的優(yōu)化曲線對比圖．從圖2～圖5中可以看出，在對4個典型函數(shù)的優(yōu)化求解過程中，只有對于f3函數(shù)，文中方法優(yōu)化迭代次數(shù)略高于其他兩種方法，但獲得解的精度遠高于其余兩種方法．對于f1、f2以及f4函數(shù)，文中方法獲得優(yōu)化解的精度均高于其他兩種方法的，而且在獲得所求函數(shù)的最優(yōu)解時，所用優(yōu)化迭代次數(shù)遠少于其他兩種方法．同時算法從一開始就能及早地達到問題的最優(yōu)解，而且達到最優(yōu)解后，算法一直處于收斂狀態(tài)，不存在振蕩現(xiàn)象，體現(xiàn)出該方法具有穩(wěn)定的求解性能．

4 結 束 語

采用k均值聚類方法獲得子群的分類個數(shù)，并且在所有粒子優(yōu)化迭代每一次后重新執(zhí)行k均值聚類分群，從而實現(xiàn)動態(tài)分群策略．充分利用其他子群的熵信息，以構建不同子群的熵權，從而提高了整個算法的收斂效率．利用子群粗搜索獲得的信息作為精搜索粒子群初始信息，從而充分利用了先前子群獲得的最優(yōu)解信息，使得該方法極易獲得復雜多峰函數(shù)的局部極值點；同時，這種方法也極易獲得復雜多峰函數(shù)的所有全局不同最優(yōu)解．這種動態(tài)分群帶熵權策略也為其他群智能方法的改進提供了很好的借鑒．