G—PSO：一種改進的遺傳粒子組合尋優算法

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

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

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

1 引言

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

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

2 新的組合尋優策略

2.1 新的思想

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

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

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

2.2 主要參數設置

為更好的發揮G-PSO算法的尋優性能，其主要參數的特定設置如下：

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

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

式中，ωmax為初始的最大慣性權重；ωmin為終止時的最小慣性權重；k為當前迭代次數；G為最大迭代次數。

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

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

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

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

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

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

3 性能測試實驗

3.1 性能測試函數設置

為了對所提出的G-PSO算法進行性能評估，選取了一組廣泛用于測試數值函數優化算法性能的標準測試函數[8，9]，所選取的兩個標準函數如下所示：

（a） Sphere函數： （6）

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

（b） Rastigrin函數： （7）

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

因此，本文用其做適應度函數對所提出的G-PSO算法進行仿真測試。它們的維數、可行空間、理論最小值以函數目標值的取值如表1所示。

3.2 實驗分析

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

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

4 結束語

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

參考文獻：

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

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

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

[4]彭曉波，桂衛華，黃志武等.GAPSO：一種高效的遺傳粒子混合算法及其應用[J].系統仿真學報，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神經網絡預測控制方法的研究[D].太原理工大學，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].西南大學，2006.

[9]黃平.粒子群算法改進及其在電力系統的應用[D].華南理工大學，2012.

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