G—PSO：一種改進(jìn)的遺傳粒子組合尋優(yōu)算法

摘 要：對于一些復(fù)雜的目標(biāo)函數(shù)，尋優(yōu)算法存在的主要問題就是收斂速度和全局尋優(yōu)能力是否可以同時提高。本文基于對粒子群算法、遺傳算法以及兩者的組合尋優(yōu)策略的研究，提出了一種新的遺傳粒子組合優(yōu)化算法——G-PSO算法；并以兩個標(biāo)準(zhǔn)性能測試函數(shù)作為適應(yīng)度函數(shù)，通過和GAPSO算法進(jìn)行仿真對比實驗，從收斂速度、收斂精度以及全局尋優(yōu)性能三個方面，驗證了所提算法收斂性能的優(yōu)越性。

關(guān)鍵詞：PSO；粒子群算法；GA；遺傳算法；G-PSO；性能測試

DOI：10.16640/j.cnki.37-1222/t.2016.09.228

1 引言

粒子群算法因其算法簡單、實現(xiàn)容易、精度高、收斂快，時下很受歡迎，各行各業(yè)的很多工程研究人員在都使用它，但是其全局優(yōu)化能力稍弱[1]。遺傳算法是一種生物進(jìn)化過程的模擬，其選擇、交叉、變異等各個環(huán)節(jié)以及很多隨機取值都體現(xiàn)了其全局搜索的特點，可以將解空間中的全體解搜索出來，不會陷入局部最優(yōu)解的快速下降陷阱，但是局部搜索能力較差[2，3]。因此，將兩者以某種方式結(jié)合，優(yōu)勢互補，不失為一種很好的研究方向。

目前，已有少數(shù)學(xué)者對其進(jìn)行研究。彭曉波等人[4]提出對群體中的個體先按適應(yīng)度值的大小進(jìn)行排序，再采用PSO算法對群體1/2大小的優(yōu)秀的個體進(jìn)行提高，剩下的個體直接淘汰，提高以后的個體被保留并進(jìn)入下一代，再用已經(jīng)提高的優(yōu)秀個體通過選擇、交叉和變異步驟得到另外1/2總數(shù)的下一代個體。Z Meng等人提出從已經(jīng)通過PSO算法更新的S個粒子中選擇M（M是偶數(shù)）個適應(yīng)度值高的粒子，然后兩兩匹配并根據(jù)固定交叉概率選擇執(zhí)行交叉操作，以防止PSO算法陷入局部最優(yōu)[5]。但是，參數(shù)M和其粒子選擇是通過粒子的適應(yīng)度比例和一個隨機數(shù)比較來確定的。王婷等人也提出將遺傳算法中的交叉和變異操作應(yīng)用到粒子群算法中[6]，但是對通過PSO算法更新的粒子沒有經(jīng)過篩選而是全部繼續(xù)進(jìn)行遺傳操作，屬于一種疊加尋優(yōu)，速度可能會很慢。

2 新的組合尋優(yōu)策略

2.1 新的思想

由于遺傳算法收斂速度比較慢，而且在進(jìn)化后期搜索效率較低。因此，本文采用將遺傳算法中的交叉、變異操作應(yīng)用到粒子群算法中，以粒子群算法為主，利用兩種算法之間的互補性，既能保證速度，又能提高全局尋優(yōu)能力，從而得到一種整體性能更優(yōu)的算法，簡稱G-PSO算法。

具體思路：首先，初始化粒子的位置、速度，并求其適應(yīng)度值；然后更新粒子的速度、位置，并求各粒子的新適應(yīng)度值、更新局部最優(yōu)值Fbest和全局最優(yōu)值Gbest；接著，計算平均適應(yīng)度值favg，而不是對粒子按適應(yīng)度值排序，并且將適應(yīng)度值大于favg的粒子使用GA算法進(jìn)行隨機兩兩交叉，不做選擇操作；交叉操作后繼續(xù)進(jìn)行變異操作，并將遺傳后的粒子和小于等于favg的粒子組合作為下一代；最后，繼續(xù)迭代操作，若不滿足目標(biāo)值或者迭代次數(shù)沒到，則繼續(xù)重復(fù)上述操作。

該方法有三個特點：（1）不使用排序操作篩選不積極的（即適應(yīng)度值不變小或者微變小的）粒子，而是使用favg篩選，可以提高效率，并且在適應(yīng)度值分布不均勻時，不積極粒子更少，理論上更合理；（2）使用GA算法良好的全局尋優(yōu)能力，可以防止陷入局部最優(yōu)，相當(dāng)于給不積極粒子進(jìn)行改良；（3）不使用選擇操作，而是直接隨機兩兩交叉，全局化效果更好。

2.2 主要參數(shù)設(shè)置

為更好的發(fā)揮G-PSO算法的尋優(yōu)性能，其主要參數(shù)的特定設(shè)置如下：

（1）本文對PSO的慣性權(quán)重的取值采用線性遞減法，目的是使算法在早期有較強的全局尋優(yōu)能力，在后期可以進(jìn)行局部精細(xì)搜索，迭代公式如式（1）所示：

ω（k）=ωmax-（ωmax-ωmin）*k/G （1）

式中，ωmax為初始的最大慣性權(quán)重；ωmin為終止時的最小慣性權(quán)重；k為當(dāng)前迭代次數(shù)；G為最大迭代次數(shù)。

（2）為了使粒子在早期的迭代過程中具有較大的自我學(xué)習(xí)能力和較小的社會學(xué)習(xí)能力，體現(xiàn)較強的全局搜索能力；并且使其在后期具有較大的社會學(xué)習(xí)能力和較小的自我學(xué)習(xí)能力，能夠較快收斂到全局最優(yōu)，本文對PSO算法的學(xué)習(xí)因子的取值采用異步線性變化取值方法，如式（2）和式（3）所示：

c1=c1b+（c1f-c1b）*k/G （2）

c2=c2b+（c2f-c2b）*k/G （3）

式中， c1b和c2b分別是學(xué)習(xí)因子c1和c2的迭代初值； c1f和c2f分別是學(xué)習(xí)因子c1和c2的迭代終值。并且，自我學(xué)習(xí)因子c1的取值是由大變小，社會學(xué)習(xí)因子c2的取值為有小變大。

（3）交叉對象兩兩隨機選擇，交叉與變異操作也仍然采用隨機方法，但是交叉概率Pc和變異概率Pm不再使用固定值。因為如果Pc太大，種群中已生成的優(yōu)秀個體可能會遭到損壞；反之，在進(jìn)行迭代時新個體的生成速度就會變慢。如果Pm太大，變異操作就接近于隨機搜索算法了；相反，生成新個體能力就會變?nèi)酰焕诰S持種群的多樣性。所以，本文采用自適應(yīng)交叉概率和變異概率，其定義如式（4）和式（5）所示[7]：

其中，fmax是群體中的最大適應(yīng)值；favg是群體平均值；f是要交叉的兩個個體中較大的適應(yīng)度值；f是要變異個體的適應(yīng)度值；k1，k2，k3，k4為常數(shù)。

3 性能測試實驗

3.1 性能測試函數(shù)設(shè)置

為了對所提出的G-PSO算法進(jìn)行性能評估，選取了一組廣泛用于測試數(shù)值函數(shù)優(yōu)化算法性能的標(biāo)準(zhǔn)測試函數(shù)[8，9]，所選取的兩個標(biāo)準(zhǔn)函數(shù)如下所示：

（a） Sphere函數(shù)： （6）

該函數(shù)是對稱的單峰值函數(shù)，不同維之間可以分離，主要用它來測試算法的尋優(yōu)精度。

（b） Rastigrin函數(shù)： （7）

該函數(shù)是一個非常復(fù)雜的、擁有很多局部最優(yōu)點的多峰值函數(shù)。一般的算法用它來測試很容易陷入局部最優(yōu)值，主要用來測試函數(shù)的全局收斂性能以及尋優(yōu)精度。

因此，本文用其做適應(yīng)度函數(shù)對所提出的G-PSO算法進(jìn)行仿真測試。它們的維數(shù)、可行空間、理論最小值以函數(shù)目標(biāo)值的取值如表1所示。

3.2 實驗分析

由于Z Meng等人提出的GAPSO算法和本文所提算法都屬于PSO算法中引入部分GA算法的模式，所以本文比較G-PSO算法和該GAPSO算法的尋優(yōu)性能，體現(xiàn)改進(jìn)算法的優(yōu)越性。粒子群體規(guī)模設(shè)置為80，迭代次數(shù)限制到500。其中，GAPSO算法的參數(shù)設(shè)置還是同其原文。G-PSO算法的參數(shù)設(shè)置如下：學(xué)習(xí)因子的線性變化取值范圍為c1∈[2.6，0.9]，遞減，c1∈[0.9，2.6]，遞增；慣性權(quán)重ω的最大值和最小值分別取0.9和0.4；雜交概率k1和k2分別設(shè)置為0.5和0.9，變異概率k3和k4分別取值0.02和0.05。最后，讓G-PSO算法和GAPSO算法分別獨立運行100次，得到其各方面性能比較結(jié)果如表2所示。

由表2可知，對Sphere函數(shù)尋優(yōu)時，G-PSO算法和GAPSO算法在100次重復(fù)測試后的尋優(yōu)成功率都是100%，但是G-PSO算法使用的平均迭代次數(shù)更少一點，即其平均收斂速度更快一點；同時，其平均最優(yōu)解也更優(yōu)一點，即收斂精度也更接近于零；但是，兩個算法整體收斂性能差別不大。對Rastigrin函數(shù)尋優(yōu)時，G-PSO算法和GAPSO算法在100次重復(fù)測試后的尋優(yōu)成功率都不是100%，但是，G-PSO算法的成功率比GAPSO算法的成功率高14%，即全局尋優(yōu)性能更好一些；同時，G-PSO算法的平均收斂速度跟快一些，收斂精度也更好一點。總之，G-PSO算法的收斂性能要比GAPSO算法好一些。

4 結(jié)束語

本文在認(rèn)真研讀了大量相關(guān)文獻(xiàn)以及反復(fù)做了很多相關(guān)實驗后，提出了一種兼顧收斂速度和全局尋優(yōu)性能的改進(jìn)型遺傳粒子組合算法（G-PSO），為智能尋優(yōu)算法的研究提供了一種新的思路，也為進(jìn)一步的深入研究打下了一定的理論基礎(chǔ)。

參考文獻(xiàn)：

[1]黃磊.粒子群優(yōu)化算法綜述[J].機械工程與自動化，2010，05（05）：197-199.

[2]席裕庚，柴天佑，惲為民.遺傳算法綜述[J].控制理論與應(yīng)用，1996（06）：697-708.

[3]沈艷，郭兵，古天祥.粒子群優(yōu)化算法及其與遺傳算法的比較[J].電子科技大學(xué)學(xué)報，2005，34（05）：696-699.

[4]彭曉波，桂衛(wèi)華，黃志武等.GAPSO：一種高效的遺傳粒子混合算法及其應(yīng)用[J].系統(tǒng)仿真學(xué)報，2008（18）：5025-5027.

[5]Meng Z， Qiao J， Zhang L. Design and Implementation： Adaptive Active Queue Management Algorithm Based on Neural Network[C]// Computational Intelligence and Security （CIS）， 2014 Tenth International Conference on. IEEE， 2014：104-108.

[6]王婷.基于GAPSO算法和RBF神經(jīng)網(wǎng)絡(luò)預(yù)測控制方法的研究[D].太原理工大學(xué)，2015.

[7]Chen C. Adaptive Selection of Crossover and Mutation Probability of Genetic Algorithm and Its Mechanism[J]. Control Theory & Applications， 2002， 19（1）：41-43.

[8]王芳.粒子群算法的研究[D].西南大學(xué)，2006.

[9]黃平.粒子群算法改進(jìn)及其在電力系統(tǒng)的應(yīng)用[D].華南理工大學(xué)，2012.

作者簡介：羅運廣（1986-），男，安徽霍邱人，碩士，計算機、軟件開發(fā)工程師，研究方向：嵌入式系統(tǒng)應(yīng)用。