一種動(dòng)態(tài)分群帶熵權(quán)的粒子群優(yōu)化方法

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

(1. 信陽(yáng)師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院，河南 信陽(yáng) 464000；2. 信陽(yáng)師范學(xué)院 河南省教育大數(shù)據(jù)分析與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河南 信陽(yáng) 464000)

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

1 粒子群算法動(dòng)態(tài)分群及帶熵權(quán)策略

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

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

1.2 粒子群算法帶熵權(quán)策略

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

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

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

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

(3)

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

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

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

(4)

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

(5)

每個(gè)子群在迭代搜索m次時(shí)全局解Aj的信息熵為

(6)

(7)

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

(8)

同樣，本群內(nèi)新的信息熵權(quán)為

(9)

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

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

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

(10)

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

(11)

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

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

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

(12)

2 動(dòng)態(tài)分群帶熵權(quán)的粒子群優(yōu)化方法

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

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

步驟3 計(jì)算所有子群每一個(gè)粒子的適應(yīng)度值．

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

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

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

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

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

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

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

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

步驟2 計(jì)算各個(gè)粒子的適應(yīng)度值．

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

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

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

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

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

3 實(shí)例及分析

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

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

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

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

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

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

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

4 結(jié) 束 語(yǔ)

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