摘 要：對于一些復(fù)雜的目標函數(shù)，尋優(yōu)算法存在的主要問題就是收斂速度和全局尋優(yōu)能力是否可以同時提高。本文基于對粒子群算法、遺傳算法以及兩者的組合尋優(yōu)策略的研究，提出了一種新的遺傳粒子組合優(yōu)化算法——G-PSO算法；并以兩個標準性能測試函數(shù)作為適應(yīng)度函數(shù)，通過和GAPSO算法進行仿真對比實驗，從收斂速度、收斂精度以及全局尋優(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]。遺傳算法是一種生物進化過程的模擬，其選擇、交叉、變異等各個環(huán)節(jié)以及很多隨機取值都體現(xiàn)了其全局搜索的特點，可以將解空間中的全體解搜索出來，不會陷入局部最優(yōu)解的快速下降陷阱，但是局部搜索能力較差[2，3]。因此，將兩者以某種方式結(jié)合，優(yōu)勢互補，不失為一種很好的研究方向。

目前，已有少數(shù)學者對其進行研究。彭曉波等人[4]提出對群體中的個體先按適應(yīng)度值的大小進行排序，再采用PSO算法對群體1/2大小的優(yōu)秀的個體進行提高，剩下的個體直接淘汰，提高以后的個體被保留并進入下一代，再用已經(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ù)進行遺傳操作，屬于一種疊加尋優(yōu)，速度可能會很慢。

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

2.1 新的思想

由于遺傳算法收斂速度比較慢，而且在進化后期搜索效率較低。因此，本文采用將遺傳算法中的交叉、變異操作應(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算法進行隨機兩兩交叉，不做選擇操作；交叉操作后繼續(xù)進行變異操作，并將遺傳后的粒子和小于等于favg的粒子組合作為下一代；最后，繼續(xù)迭代操作，若不滿足目標值或者迭代次數(shù)沒到，則繼續(xù)重復(fù)上述操作。

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

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

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

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

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

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

（2）為了使粒子在早期的迭代過程中具有較大的自我學習能力和較小的社會學習能力，體現(xiàn)較強的全局搜索能力；并且使其在后期具有較大的社會學習能力和較小的自我學習能力，能夠較快收斂到全局最優(yōu)，本文對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太大，種群中已生成的優(yōu)秀個體可能會遭到損壞；反之，在進行迭代時新個體的生成速度就會變慢。如果Pm太大，變異操作就接近于隨機搜索算法了；相反，生成新個體能力就會變?nèi)?，不利于維持種群的多樣性。所以，本文采用自適應(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算法進行性能評估，選取了一組廣泛用于測試數(shù)值函數(shù)優(yōu)化算法性能的標準測試函數(shù)[8，9]，所選取的兩個標準函數(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算法進行仿真測試。它們的維數(shù)、可行空間、理論最小值以函數(shù)目標值的取值如表1所示。

3.2 實驗分析

由于Z Meng等人提出的GAPSO算法和本文所提算法都屬于PSO算法中引入部分GA算法的模式，所以本文比較G-PSO算法和該GAPSO算法的尋優(yōu)性能，體現(xiàn)改進算法的優(yōu)越性。粒子群體規(guī)模設(shè)置為80，迭代次數(shù)限制到500。其中，GAPSO算法的參數(shù)設(shè)置還是同其原文。G-PSO算法的參數(shù)設(shè)置如下：學習因子的線性變化取值范圍為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é)束語

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

參考文獻：

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

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

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

[4]彭曉波，桂衛(wèi)華，黃志武等.GAPSO：一種高效的遺傳粒子混合算法及其應(yīng)用[J].系統(tǒng)仿真學報，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].太原理工大學，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]黃平.粒子群算法改進及其在電力系統(tǒng)的應(yīng)用[D].華南理工大學，2012.

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