基于種群分區(qū)的多策略綜合粒子群優(yōu)化算法

李冰曉，萬睿之，朱永杰，趙新超

(北京郵電大學(xué) 理學(xué)院，北京 100876)

粒子群優(yōu)化算法[1]是由KENNEDY和EBERHART于1995年提出的一種全局優(yōu)化算法.它源于對鳥群覓食行為的模擬.自提出以來，粒子群優(yōu)化算法以其參數(shù)少、概念簡單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)引起眾多研究者關(guān)注，并在數(shù)據(jù)聚類[2]、圖像處理[3]、特征選擇[4]、電力系統(tǒng)[5]、人工神經(jīng)網(wǎng)絡(luò)[6]等實(shí)際問題中得到了廣泛應(yīng)用.

然而，粒子群算法容易早熟收斂，算法后期多樣性不足等問題限制了它的性能.為改善上述問題，眾多學(xué)者做了大量的研究工作，主要分為四個(gè)方面：參數(shù)調(diào)整[7]、拓?fù)浣Y(jié)構(gòu)改善[8]、改進(jìn)學(xué)習(xí)策略[9]和與其他算法相結(jié)合.文獻(xiàn)[10]提出了CLPSO，算法中的粒子以一定概率向其他粒子的歷史最佳經(jīng)驗(yàn)學(xué)習(xí)，極大地增加了種群多樣性；文獻(xiàn)[11]提出了一種簡化而高效的粒子群優(yōu)化算法,算法中對粒子的學(xué)習(xí)樣本以一定概率施加均勻擾動(dòng)，能夠有效改善算法陷入局部極值，增大找到最優(yōu)解的概率；文獻(xiàn)[12]提出了一種基于擾動(dòng)全局最優(yōu)概念的新粒子更新策略的擾動(dòng)粒子群優(yōu)化算法(pPSA)，以解決粒子群中的早熟收斂和多樣性保持問題；文獻(xiàn)[13]提出了一種新的多階段擾動(dòng)差分進(jìn)化算法(MPDE)，采用方向性差異信息策略和多參數(shù)自適應(yīng)實(shí)現(xiàn)了一種新的變異策略“多階段擾動(dòng)”；文獻(xiàn)[14]提出一種基于分段優(yōu)勢學(xué)習(xí)的SLPSO算法，算法中的整個(gè)種群被分為精英子群與普通子群，普通子群中粒子分段向精英種群中的粒子進(jìn)行學(xué)習(xí)，使得算法能夠充分利用精英粒子的信息，避免了早熟收斂；文獻(xiàn)[15]將差分變異操作與SLPSO算法相結(jié)合提出了差分變異與新型社會(huì)學(xué)習(xí)粒子群優(yōu)化算法(DSPSO)；文獻(xiàn)[16]在SLPSO算法的啟發(fā)下提出了帶有混合變異策略的多種群協(xié)作粒子群優(yōu)化算法(MPCPSO); 文獻(xiàn)[17-21]都采用了多種群的策略對各個(gè)子群進(jìn)行不同的進(jìn)化策略，研究結(jié)果表明多種群的多策略進(jìn)化是改善粒子群算法性能的一個(gè)有效研究方向.

目前對粒子群算法的研究使得算法性能得到了不同程度的提高，多種群操作以及不同擾動(dòng)策略的引進(jìn)有效改善了粒子群算法收斂精度不高的問題.然而，在很多問題上粒子群陷入局部最優(yōu)以及早熟收斂的問題還沒有得到很好的解決. 針對此現(xiàn)狀，本文提出一種基于種群分區(qū)的多策略綜合學(xué)習(xí)粒子群優(yōu)化算法(MSPSO).在每次迭代中，利用一種新的競爭機(jī)制將種群分為兩個(gè)子群：潛力子群與普通子群，對這兩個(gè)子群采取不同的學(xué)習(xí)策略.在潛力子群中，粒子的進(jìn)化除慣性部分外，還向該子群中隨機(jī)選取的某粒子的歷史最佳經(jīng)驗(yàn)學(xué)習(xí)，這種學(xué)習(xí)策略能夠在充分利用優(yōu)秀粒子精英信息的同時(shí)保持種群多樣性.在普通子群中，設(shè)置了兩種學(xué)習(xí)策略.算法前期，粒子向潛力子群中隨機(jī)選取的某粒子的歷史最佳經(jīng)驗(yàn)學(xué)習(xí)；算法后期，則以一定概率直接向全局最優(yōu)經(jīng)驗(yàn)學(xué)習(xí).這種進(jìn)化方式既保持了兩個(gè)子群的協(xié)同進(jìn)化和種群多樣性，又加快了收斂速度.實(shí)驗(yàn)結(jié)果表明，所提算法具有較快的收斂速度，并且能夠有效防止陷入局部極值，獲得極有競爭力的解.

1 相關(guān)工作

1.1 標(biāo)準(zhǔn)PSO算法

PSO算法首先隨機(jī)初始化一群粒子，然后通過飛行速度和位置的逐步更新迭代找到最優(yōu)解.在每一次迭代中，粒子通過跟蹤個(gè)體發(fā)現(xiàn)的最好極值和群體發(fā)現(xiàn)的全局極值更新自己的飛行速度和位置.假設(shè)在D維搜索空間中，有N個(gè)粒子組成一個(gè)群體，t時(shí)刻粒子i由位置向量(xi1,xi2,…,xiD)和速度向量(vi1,vi2,…,viD)表示.在優(yōu)化過程中，下一代種群中個(gè)體的速度和位置向量由如下公式更新，

Vij(t+1)=ωVij(t)+c1r1(Pij(t)-Xij(t))+c2r2(Pgj(t)-Xij(t)),

Xij(t+1)=Xij(t)+Vij(t+1).

(1)

其中i=1,2,…,N,j=1,2,…,D,N為群體規(guī)模，w為慣性權(quán)重，r1,r2為(0,1)區(qū)間均勻分布的隨機(jī)數(shù)，c1,c2為加速系數(shù).Pij(t)為粒子i的歷史最佳位置的第j維分量，Pgj(t)為整個(gè)種群的歷史最佳位置的第j維分量，t為當(dāng)前迭代次數(shù).

1.2 CLPSO算法

與標(biāo)準(zhǔn)PSO算法不同的是，CLPSO算法中的粒子以概率(1-pc)向個(gè)人歷史最佳經(jīng)驗(yàn)學(xué)習(xí)，以概率pc向由競爭機(jī)制選擇出的其他粒子的歷史最佳經(jīng)驗(yàn)學(xué)習(xí).粒子更新過程由如下公式產(chǎn)生：Vij(t+1)=ωVij(t)+cr(Pfi(j)(t)-Xij(t)),其中w為慣性權(quán)重,r為(0,1)區(qū)間內(nèi)的隨機(jī)數(shù),c為加速系數(shù)，fi(j)為由CLS構(gòu)建的學(xué)習(xí)樣本的索引.下面是CLPSO構(gòu)建學(xué)習(xí)樣本的過程.

對于粒子i的每一維度j：[1]產(chǎn)生隨機(jī)數(shù)p,p∈(0,1);[2]若p≤pc，粒子向由競爭機(jī)制選擇出的其他粒子的歷史最佳經(jīng)驗(yàn)學(xué)習(xí)；[3]若p>pc，粒子向其個(gè)體歷史最佳經(jīng)驗(yàn)學(xué)習(xí).

與標(biāo)準(zhǔn)PSO算法相比，粒子可以向不同的粒子歷史最佳個(gè)體學(xué)習(xí)，有效保證了種群多樣性，提供了大范圍而有潛力的搜索區(qū)域.

1.3 Nmp3PSO算法

文獻(xiàn)[22]提出一種基于非均勻變異和多階段擾動(dòng)的粒子群優(yōu)化算法(Nmp3PSO).該算法在執(zhí)行的不同階段利用對當(dāng)前最優(yōu)解施加大小不同的鄰域擾動(dòng)操作，并且引入非均勻變異運(yùn)算適應(yīng)性調(diào)整解向量的搜索步長，具體操作如下.

1.3.1非均勻變異算子

假設(shè)對粒子xi={xi1,xi2,…,xin}T的第d個(gè)分量執(zhí)行變異運(yùn)算，而xid的下界和上界分別記為LB和UB，則變異后的分量：

1.3.2最優(yōu)粒子擾動(dòng)策略及粒子更新

對全局最優(yōu)粒子gbest依據(jù)方差可調(diào)的正態(tài)隨機(jī)分布進(jìn)行擾動(dòng)得到新的最優(yōu)粒子pgbest，然后選定的待更新粒子向pgbest學(xué)習(xí)，速度更新公式為：

其中σ1>σ2>σ3表示正態(tài)擾動(dòng)幅度的半徑參數(shù)；α1,α2是半徑變化的控制參數(shù)，且α1<α2；t是當(dāng)前函數(shù)值計(jì)算次數(shù)，T是最大函數(shù)值計(jì)算次數(shù).

算法性能分析表明，Nmp3PSO能夠較好兼顧群體優(yōu)化算法的多樣性和精英學(xué)習(xí)強(qiáng)度之間的平衡問題.

1.4 其他群體智能算法

文獻(xiàn)[23]提出了一種自適應(yīng)差分進(jìn)化算法(SaDE)，算法中的試驗(yàn)向量生成策略及其相關(guān)的控制參數(shù)通過學(xué)習(xí)它們以前生成的潛力解的經(jīng)驗(yàn)而逐漸實(shí)現(xiàn)自適應(yīng)，從而自適應(yīng)地確定更合適的進(jìn)化策略及參數(shù)設(shè)置來匹配搜索過程的不同階段.實(shí)驗(yàn)結(jié)果與傳統(tǒng)DE[24]以及幾個(gè)先進(jìn)的參數(shù)自適應(yīng)DE變體相比,SaDE能夠獲得更高質(zhì)量的解、更小的標(biāo)準(zhǔn)差以及更高的成功率.

文獻(xiàn)[25]提出了一種遺傳算法的變體(GL25)，算法在交叉操作之前執(zhí)行了3個(gè)過程.首先是雌性和雄性的分化過程，它決定了種群中可能成為雌性或雄性父母的個(gè)體；然后采用兩種不同的選擇機(jī)制從每個(gè)群體中選擇雌雄親本；最后討論了最適合的進(jìn)化模型的選擇以及從這些親本選擇機(jī)制中獲益.實(shí)驗(yàn)表明這3個(gè)過程可以增強(qiáng)以父代為中心的交叉算子的操作性能.

2 多策略綜合學(xué)習(xí)粒子群優(yōu)化算法(MSPSO)

2.1 研究動(dòng)機(jī)

對粒子群體中不同適應(yīng)值的粒子信息如何個(gè)性化的進(jìn)行開發(fā)和利用是本文最初的出發(fā)點(diǎn)，逐步具體化為如何設(shè)置一種新的競爭規(guī)則將整個(gè)種群劃分成不同的子群，對攜帶精英信息較多的子群如何在加強(qiáng)精英搜索的基礎(chǔ)上引進(jìn)較多的群體多樣性，對攜帶差異化信息較多的群體如何在擴(kuò)大全局搜索的基礎(chǔ)上適當(dāng)加速算法的收斂，同時(shí)保證整個(gè)種群及多個(gè)子群能夠保持協(xié)同進(jìn)化來平衡算法的全局搜索能力和局部開發(fā)能力.

2.2 MSPSO算法

首先設(shè)計(jì)合理的競爭機(jī)制將整個(gè)種群分為兩個(gè)子群，對這兩個(gè)子群進(jìn)行不同偏向的進(jìn)化操作.

為了利用群體進(jìn)化過程中多種關(guān)鍵信息，本文考慮劃分不同子群的兩個(gè)指標(biāo)：一是每個(gè)粒子相鄰兩次迭代適應(yīng)值的改變量，二是當(dāng)前迭代適應(yīng)值的大小.粒子前后兩次迭代適應(yīng)值的改變量越大，說明該方向潛力越大；粒子當(dāng)前適應(yīng)值越大，也說明該方向潛力越大.競爭機(jī)制構(gòu)建的兩個(gè)指標(biāo)α和β分別設(shè)置如下,

(2)

(3)

R=λ1α+λ2β.

(4)

綜合競爭指標(biāo)R既考慮解的改變量，又考慮解的優(yōu)異程度，因此從算法搜索狀態(tài)和搜索性能兩方面構(gòu)建了啟發(fā)式信息.對R進(jìn)行降序排列，前1/2作為潛力子群，后1/2作為普通子群.其中F,FN分別是粒子前后兩次迭代的適應(yīng)值,λ1,λ2為參數(shù)，本文初步設(shè)置為1和3;α初始化為0.

針對潛力子群，粒子i的飛行速度和位置向量在第j維上的更新公式如下:

Vij(t+1)=ωVij(t)+r3(randn*Pkj(t)-Xij(t)),

(5)

Xij(t+1)=Xij(t)+Vij(t+1),

(6)

其中w為慣性權(quán)重，更新公式為0.5×(1-FES/maxFES)+0.15.FES為當(dāng)前函數(shù)評價(jià)次數(shù)，maxFES為最大評價(jià)次數(shù).Pk為該子群中隨機(jī)選擇的粒子的歷史最佳經(jīng)驗(yàn).r3為隨機(jī)性參數(shù)，為保證(5)式中學(xué)習(xí)部分的有效性，此參數(shù)不宜過小，故設(shè)置為0.45+r，其中r為(0,1)區(qū)間內(nèi)均勻分布的隨機(jī)數(shù),randn為滿足標(biāo)準(zhǔn)高斯分布的隨機(jī)數(shù).對學(xué)習(xí)樣本施加高斯擾動(dòng),目的是增加種群多樣性，加大粒子的學(xué)習(xí)范圍，研究動(dòng)機(jī)是在精英綜合學(xué)習(xí)的基礎(chǔ)上增加一定的群體多樣性，即選擇多樣化的精英搜索路徑.

針對普通子群，粒子i的飛行速度和位置向量在第j維上的更新公式如下,

(7)

Xij(t+1)=Xij(t)+Vij(t+1),

(8)

其中w,r1的設(shè)置如(1)式；Pl為潛力子群中隨機(jī)選擇的粒子l的歷史最佳經(jīng)驗(yàn);Pg為全局歷史最佳經(jīng)驗(yàn);μ為參數(shù)，設(shè)置為1/(1+(FES/N)(1/2)×exp(i/N)).隨著算法的進(jìn)行，粒子飛向全局歷史最佳經(jīng)驗(yàn)的概率逐漸增加，能夠加速算法收斂；對普通子群粒子更新公式的研究動(dòng)機(jī)是在保持種群多樣性的基礎(chǔ)上加速算法的收斂，并且排名越靠后的粒子飛向全局歷史最佳經(jīng)驗(yàn)的概率越大，有助于加速粒子的收斂速度，從而提高整個(gè)種群解的質(zhì)量.

2.3 算法步驟

步驟1 初始化粒子種群規(guī)模N、粒子搜索空間D、函數(shù)最大評價(jià)次數(shù)maxFES等算法參數(shù)，隨機(jī)初始化粒子的飛行速度和位置；

步驟2 初次按照適應(yīng)值升序排序分為兩個(gè)子群，分別執(zhí)行不同搜索偏向的速度和位置更新操作，轉(zhuǎn)到步驟4；

步驟3 按照競爭機(jī)制將整個(gè)種群分為兩個(gè)子群，對不同子群中的粒子分別執(zhí)行對應(yīng)進(jìn)化操作；

步驟4 對溢出邊界粒子進(jìn)行修正操作；

步驟5 執(zhí)行位置更新公式；

步驟6 保留粒子歷史最佳經(jīng)驗(yàn)，全局最佳經(jīng)驗(yàn)；

步驟7 若函數(shù)最大評價(jià)次數(shù)達(dá)到設(shè)置值，輸出結(jié)果；否則回到步驟3.

3 對比仿真實(shí)驗(yàn)與結(jié)果分析

3.1 測試函數(shù)與參數(shù)設(shè)置

為了驗(yàn)證所提出的MSPSO算法的性能，將MSPSO與標(biāo)準(zhǔn)PSO，CLPSO，Nmp3PSO，標(biāo)準(zhǔn)差分算法DE，SaDE，以及GL25這6種算法在CEC2005的11個(gè)經(jīng)典基準(zhǔn)測試函數(shù)上進(jìn)行對比分析,為方便起見將CEC中的測試函數(shù)重新編號為F1～F11，如表1所示.

表1 基準(zhǔn)測試函數(shù)

表2 7種算法數(shù)值實(shí)驗(yàn)結(jié)果

表2包含各算法運(yùn)行最終所達(dá)到的最優(yōu)值Min、均值Mean和標(biāo)準(zhǔn)差STD，另外小計(jì)部分顯示在11個(gè)測試函數(shù)上各算法的最優(yōu)值Min及均值Mean能達(dá)到相對最優(yōu)結(jié)果的個(gè)數(shù)，總計(jì)部分顯示各算法綜合考慮最優(yōu)值Min以及均值Mean能達(dá)到相對最優(yōu)結(jié)果的個(gè)數(shù).各算法的收斂曲線如圖1所示.

3.2 算法仿真結(jié)果與分析

由表2可以看出，1)PSO，CLPSO，Nmp3PSO，MSPSO，DE，SaDE和GL25在11個(gè)測試函數(shù)最終結(jié)果的最優(yōu)值上分別取得0個(gè)、1個(gè)、2個(gè)、8個(gè)、4個(gè)、4個(gè)和2個(gè)最優(yōu)結(jié)果；2)PSO,CLPSO,Nmp3PSO,MSPSO,DE,SaDE和GL25在11個(gè)測試函數(shù)最終結(jié)果的平均值上分別取得0個(gè)、2個(gè)、0個(gè)、10個(gè)、1個(gè)、1個(gè)和0個(gè)最優(yōu)結(jié)果；3)結(jié)合最優(yōu)值與平均值來看PSO,CLPSO,Nmp3PSO,MSPSO,DE,SaDE和GL25分別取得0個(gè)、3個(gè)、2個(gè)、18個(gè)、5個(gè)、3個(gè)和2個(gè)最優(yōu)結(jié)果.綜合表2和相應(yīng)分析可以看出，在這11個(gè)基準(zhǔn)測試函數(shù)上，MSPSO算法相對優(yōu)于其他對比算法.

圖1給出7種算法在11個(gè)測試函數(shù)上平均適應(yīng)值的進(jìn)化性能對比，可以看出， MSPSO比PSO,CLPSO,Nmp3PSO,DE,SaDE以及GL25有著較為明顯的進(jìn)化優(yōu)勢，說明MSPSO算法有著更快的收斂速度和更高的收斂精度.綜上所述，本文提出的MSPSO算法相比其他對比算法有著較為優(yōu)異的性能.

Friedman檢驗(yàn)[26]是利用秩實(shí)現(xiàn)對多個(gè)總體分布是否存在顯著差異的非參數(shù)檢驗(yàn)方法.為討論7個(gè)算法平均結(jié)果對比統(tǒng)計(jì)的顯著性，對算法所得結(jié)果的平均值做Friedman統(tǒng)計(jì)檢驗(yàn)，結(jié)果如表3所示.由此可見，MSPSO對比PSO，CLPSO，Nmp3PSO，DE，SaDE以及GL25有顯著性差異.

表3 7種算法的Friedman統(tǒng)計(jì)檢驗(yàn)結(jié)果

3.3 高斯擾動(dòng)效用測試

為驗(yàn)證MSPSO算法對于潛力子群中局部歷史最佳經(jīng)驗(yàn)施加高斯擾動(dòng)的有效性，本文設(shè)置了一組對照試驗(yàn)，其中MSPSO1為不加高斯擾動(dòng)的對照組，其余設(shè)置與MSPSO相同.兩種算法的測試函數(shù)仍然為表1中的11個(gè)經(jīng)典基準(zhǔn)函數(shù)，種群規(guī)模、粒子最大飛行速度、函數(shù)最大評估次數(shù)等參數(shù)也與上文保持一致.圖2為MSPSO與MSPSO1在各測試函數(shù)上的收斂曲線對比圖.

從圖2可以看出MSPSO在收斂速度和收斂精度上都比MSPSO1具有明顯的優(yōu)勢.因此MSPSO中對于潛力子群中優(yōu)秀粒子的局部歷史最佳經(jīng)驗(yàn)施加高斯擾動(dòng)是非常有效的，提升了算法找到最優(yōu)解的能力.

3.4 競爭機(jī)制排序的參數(shù)分析

為檢驗(yàn)MSPSO算法中競爭機(jī)制所考慮兩個(gè)指標(biāo)權(quán)重λ1,λ2的參數(shù)敏感性，本文設(shè)置了幾組對比試驗(yàn)，其中MSPSO2,MSPSO3,MSPSO4和MSPSO5分別將(λ1,λ2)設(shè)置為(1,2)、(1,1)、(2,1)和(3,1)，其余設(shè)置與MSPSO相同.這5種算法的測試函數(shù)為由表1中選取的3個(gè)單峰函數(shù)F1,F2和F5，3個(gè)多峰函數(shù)F9～F11.

表4為這5種算法在6個(gè)測試函數(shù)上達(dá)到的平均值對比.由表4可看出這5種算法都能獲得較高精度的解，說明不同的λ1,λ2設(shè)置對算法性能影響不大，但探索其更好的設(shè)置值能為算法提供較好的穩(wěn)定性.本文中MSPSO算法的設(shè)置值要略好于其他4種對比算法.

表4 不同設(shè)置值算法的平均值對比

3.3節(jié)對局部歷史最佳經(jīng)驗(yàn)高斯擾動(dòng)的有效性進(jìn)行了分析，表明算法對高斯擾動(dòng)操作對潛力子群局部歷史最佳經(jīng)驗(yàn)具有較明顯的影響提升；3.4節(jié)對兩個(gè)重要指標(biāo)權(quán)重λ1,λ2參數(shù)敏感性和魯棒性進(jìn)行了分析，結(jié)果表明指標(biāo)權(quán)重參數(shù)λ1,λ2對算法性能的影響不明顯.除此之外，除了30維的測試結(jié)果，又補(bǔ)充了問題維數(shù)50和100時(shí)的結(jié)果，見表5，可以看出MSPSO算法的數(shù)值結(jié)果并未隨著測試函數(shù)維數(shù)上升而有明顯下降，說明MSPSO算法較好的穩(wěn)定性.結(jié)合3.2節(jié)算法仿真結(jié)果分析認(rèn)為MSPSO算法性能不僅具有更高的收斂精度和更快的收斂速度，還具有較好的魯棒性.

表5 MSPSO在不同維度測試函數(shù)上的數(shù)值結(jié)果

4 結(jié) 論

為改善粒子群算法早熟收斂、收斂速度慢的問題，提出了基于競爭機(jī)制和種群分區(qū)的多策略綜合學(xué)習(xí)算法(MSPSO).MSPSO算法通過一種有效的競爭機(jī)制將整個(gè)種群劃分為兩個(gè)子群，對這兩個(gè)子群采用了不同的學(xué)習(xí)策略，一個(gè)子群在精英學(xué)習(xí)的基礎(chǔ)上引進(jìn)更多種群多樣性，另一子群在保持多樣性的基礎(chǔ)上加速了算法收斂，并且兩個(gè)子群體和整個(gè)群體保持協(xié)同進(jìn)化，較好地平衡了算法的尋優(yōu)能力與收斂速度.在11個(gè)經(jīng)典基準(zhǔn)函數(shù)上對MSPSO,PSO,CLPSO,Nmp3PSO,DE,SaDE,GL25算法的性能進(jìn)行了比較.結(jié)果表明，本文所提出的MSPSO算法性能具有更高的收斂精度和更快的收斂速度，并且具有較好的魯棒性.