基于串行式融合的GA 與PSO 優化算法研究

張 海，李士心，劉小鈺

（天津職業技術師范大學電子工程學院，天津 300222）

當今科技發展形勢下，單一智能優化算法已不能滿足當下出現的大規模、多變量、多約束、多極化及非線性等復雜的問題，因此智能算法融合應運而生。遺傳算法（genetic algorithm，GA）由美國 Holland 教授基于生物界優勝劣汰的自然選擇現象，于1975 年提出的用于解決優化問題，又稱進化算法，其過程簡單，多用于函數優化、數據挖掘、圖像處理等[1]。但GA 算法仍有局限性，如在多約束條件下收斂速度減慢，收斂精度不高等[2]。而粒子群優化算法（PSO）是一種通過對鳥類覓食過程的模擬進行優化的算法[3]，其原理簡單，用速度位移公式迭代即可實現，此外需調節的參數較少，粒子也具有記憶性，多用于組合優化、傳感器網絡、車輛調度等[1]。但隨著智能優化算法的不斷完善，其易陷入局部最優，難處理多維問題的缺點也暴露出來[3]。近年來，已有多位學者將其融合，主要形式有3種，分別為并行式混合，如Benvidi 等[4]提出用GA-PSO并行混合優化ANN 參數，并且利用該算法處理了吸光度數據和分析物濃度的關系，取得了很好的效果[1，4]；嵌入式混合，如孫麗平[5]將 GA 算法嵌入 PSO 中用于改進蒙特卡羅濾波和遞推貝葉斯理濾波結合的粒子濾波樣本退化問題，并且實驗證明了其有效性[1，5]；串行式混合，如Zhang 等[6]提出在GA 算法完成后疊加PSO 來實現聚類，然而效果雖可實現，但依舊存在收斂速度慢等問題[1，6]。本文研究串行式混合下GA 與PSO 巧妙結合的原理，提出了一種改進GA 的串行結合方式，在保證計算精度的前提下，提高收斂速度。

1 遺傳算法（GA）

遺傳算法使用群體搜索技術，其所操作的對象以及問題的解均為種群。通過對當前種群施加一系列遺傳操作來產生新一代種群，包括優選強勢個體的選擇、個體間交換基因片段產生新個體的交叉以及某位基因信息突變而產生新個體的變異等。以此逐步迭代進化直到產生最優解[7]。

1.1 變量初始化

群體規模太小不利于遺傳性能的提升，規模大可減小其陷入局部最優，但也意味著復雜度提升，根據前人工作經驗，此類問題的染色體數目設為NP=100較為合適。每條染色體上的基因數D=10，最大遺傳代數G=1 000，交叉概率太大雖可增強搜索新區域的能力，但高性能模式易被破壞，故設Pc=0.8，而變異是為了增加種群多樣性，在整個遺傳算法中屬輔助操作，變異概率過大會使得搜索的隨機性增大[7]，故設Pm=0.1，根據適應度函數要求可令基因值上下限分別為Xs=20，Xx=-20；并為初始種群和子種群賦空間，均為[D，NP]型，再利用下式隨機獲得初始種群

f=rand（D，NP）*（Xs-Xx）+Xx

1.2 染色體排序

根據適應度將各染色體升序排列，具體操作如下：①將各染色體的D 位基因值分別代入適應度函數，得出對應的適應度函數值。②利用sort 函數依據適應度函數升序的方式將各染色體排序。

1.3 遺傳操作及種群合并提取

1.3.1 采用君主方案進行選擇交叉操作

將最小適應度值對應的染色體確定為君主染色體；確定每次交叉點個數為NoPoint=round（D*Pc），Pc位為交叉概率；并利用randint 函數生成一個[NoPoint，NP/2]型，元素均為1-D 內整數的矩陣PoPoint，用于提取交叉基因的位置。此時再將以上排好序的染色體組賦予子種群，并對子種群進行交叉操作：將君主染色體賦在NP 條染色體的奇數位，偶數位保持不變，再根據交叉點個數Nopoint 進行交叉。各染色體由前向后兩兩成對，每對染色體要交叉互換Nopoint 次，交叉互換位則從矩陣PoPoint 中選取。

1.3.2 基于概率的變異操作

逐個染色體、逐個基因進行遍歷。對于染色體上基因，若rand 隨機生成數小于變異概率，則該基因按如下方式變異

nf（n，m）=rand（1，1）*（Xs-Xx）+Xx

此處也可將粒子群算法的位置更新思想融入到變異算子[8]。

1.3.3 染色體重排序

對進行過遺傳操作的子種群按照與以上相同的方式進行升序排列，再將排好序的子種群與原排好序的父種群的適應度函數值及其染色體組進行合并，并重新升序排列。取前NP 個染色體及其適應度函數值作為優化結果，最小的適應度函數值作為當代最優值。

1.4 迭代尋優

迭代上述過程G 次，將G 個適應度函數值繪成曲線。

2 粒子群算法（PSO）

粒子群算法通過對鳥類覓食過程的模擬，尋找最優解，可用于很多優化問題[9-10]。PSO 算法中的每個粒子肩負2 個值：位置和速度。粒子的位置表征可行解，速度用來決定粒子的運動方向和距離。此外，所有粒子通過跟蹤自身經驗極值和全局極值來更新自己的位置和速度[7]。

2.1 變量初始化

為與其他算法進行控制變量式對比，粒子群的種群規模也設為個數N=100，其維數設為D=10，最大迭代次數T=1 000；對于加速常數，即學習因子c1 和c2，根據粒子速度和位置的更新公式可知，這2 個學習因子分別調節粒子向個體最優極值pbest 和全局極值gbest 方向飛行的步長，也即決定粒子運行軌跡的個體經驗和群體經驗，一般設置c1=c2=1.5；慣性權重可控制粒子向新區域的探索能力和在原區域深度開發的能力，設w=0.8 時可使該算法有更快的收斂速度[7]；根據適應度函數要求可確定粒子運動范圍，即位置的最大值Xmax=20 和最小值Xmin=-20，另外為了避免粒子飛過優秀區域或是陷入局部最優，設定速度最大值Vmax=10，最小值 Vmin=-10。

2.2 種群初始化

種群初始化包括種群個體，個體最優位置和最優值以及全局最優位置和最優值。個體包含位置x 和速度 v 兩個值，且矩陣 x 和 v 等型，均為[N，D]型，x =rand（N，D）*（Xmax- Xmin）+ Xmin，v 的生成方式與此類似，這樣初始化得到每個粒子的位置和速度。對于個體最優位置p，由于前面工作已進行了初始化，只需將粒子的初始化位置賦予最優位置p，而個體最優值pbest 也可由初始位置x 代入適應度函數求得。對于全局最優位置g 和最優值gbest，將各個個體最優pbest與全局最優初始值比較，較小者作為全局最優值并將于此對應的個體最優位置作為全局最優位置。

2.3 種群更新

種群初始化后，需更新種群并不斷進化才可實現尋優。包括更新個體的最優位置和最優值，全局最優位置和最優值，各粒子的位置和速度以及邊界條件的處理。對每個粒子都要做如下更新。

2.3.1 個體的最優位置和最優值的更新

將初始化的位置代入適應度函數，將求得的函數值與對應pbest 值比較，若該函數值較小，則將該粒子的位置放于對應個體最優位置矩陣p 中，暫當該粒子的個體最優位置，且此時對應的個體最優值pbest 也更換為該函數值。

2.3.2 全局最優位置和最優值的更新

將更換后得到的pbest 值與已初始化得到的全局最優值gbest 作比較。若更換后的pbest 值小于初始化的gbest 值，將更換后的pbest 值對應的位置放入全局最優位置矩陣g 中，暫當全局最優位置。

2.3.3 粒子的位置和速度的更新

對該粒子的速度和位置做出更新，公式如下

式中：j 為某個粒子，j 取（1，N）。

在速度更新公式中，w*v（j，：）為粒子維持原先速度的慣性；c1*rand（p（j，：）-x（j，：））為粒子向個體最優位置靠近，即為自我認知；c2*rand（g-x（j，：））為粒子向全局最優位置靠近，即社會引導[7]。

此外，對于慣性權重w 可采用非線性動態自適應進行更新，以便很好地進行開發能力與探索能力的分配。

2.3.4 對邊界條件的處理

對于該粒子上的每一位元素（位置、速度），若存在大于最大速度或小于最小速度的情況，即飛行速度不合理，則將該位的速度重新規范在規定的最大最小速度區間內，即 v=rand（Vmax-Vmin）+Vmin。同理，若存在大于最大位置或小于最小位置的情況，即超出了邊界，將該位的位置規范進先前的區域內，即x=rand（Xmax-Xmin）+Xmin。

2.4 遍歷尋優

當所有粒子遍歷上述操作后，即完成了一代的更新。將這一代所得的全局最優值和最優位置進行記錄。將遍歷T 代后所得的T 個全局最優值繪制成曲線。

3 GA 與PSO 的串行式融合

3.1 先PSO后GA

先PSO 后GA 的結合方式使種群先經PSO 優化，可以得到很多接近最優解的個體，此時再利用GA 的交叉變異去改善種群，提升種群多樣性，這樣在很大程度上避免了陷入局部最優，并且可以快速準確地在接近最優解的個體中尋得最優值，實現全局快速尋優[11-12]。

初始化部分包括群體粒子個數、染色體數、粒子維數、基因數，粒子群最大迭代次數、遺傳算法最大遺傳代數；2 個相等的學習因子；限定粒子空間位置的最大值、最小值；約束粒子飛行跨度的速度最大值、最小值，慣性權重；遺傳算法的交叉、變異概率以及初始種群和子種群賦空間。

先執行粒子群算法部分，借鑒單獨使用PSO 的方式，可得到迭代T 代后的粒子群最優位置矩陣p。由于PSO 部分與GA 部分的初始矩陣互為轉置關系，故此處只需要將PSO 優化后得到的最優位置矩陣p 轉置后作為GA 的初始矩陣，即簡單實現了PSO 與GA 的串行混合，此處的GA 部分也與前面單獨使用GA 部分保持一致。最后將GA 迭代了G 代后，得到的各適應度值繪制成曲線。

3.2 先GA后PSO

對于先遺傳算法后粒子群算法，也可借鑒以上做法，將單獨使用GA 部分的執行結果作為單獨執行PSO 部分的初始矩陣，也可實現GA 與PSO 的簡單串行混合。初期采用GA 將隨機初始化的粒子群個體進行優化，用以提高計算精度，而后采用PSO 向最優解均勻移動來提高收斂速度[13-14]。此處，本研究對GA 的優化方式做了進一步改進，以改良遺傳算法在全局尋優方面的性能，即將隨機初始化的粒子群個體的位置及速度經GA 優化一遍直接交由PSO 執行。

3.2.1 初始化

采用GA 對每個粒子的初始位置、速度、個體的最優位置、個體最優值進行優化，并將優化后的值作為執行PSO 部分的初始值。將單個粒子初始位置、速度、最優位置、最優值矩陣合并為A，并利用sortrows 函數將整體按照初始單個粒子最優值（適應度值）升序排列為B。

將適應度值低的前一半粒子直接放入下一代，將后一半粒子放入Cross 中進行一系列遺傳操作。

①基于概率的交叉操作。若由rand 函數隨機生成的數小于交叉概率且利用randint 函數生成的一行一列數組中的某位元素為1 時，則將后一半粒子兩兩成對地把元素為1 對應位交換，實現基于概率的交叉。

②基于概率的變異操作。將粒子總數與變異概率的乘積作為迭代上限，并將粒子維數與變異概率之積作為要變異的位數，再利用randint 函數從[1，N/2]和[1，D]中隨機選取要變異的粒子體積元素位進行取反變異，反復迭代實現基于概率的變異操作。

3.2.2 遺傳算法優化

將更換后得到的pbest 值與已初始化得到的全局最優值gbest 作比較。若更換后的pbest 值小于初始化的gbest 值，將更換后的pbest 值對應的位置放入全局最優位置矩陣g 中，暫當全局最優位置。

3.2.3 Cross部分的更新

①將進行過交叉變異的位置代入適應度函數中，將其函數值放入Cross 中粒子最優值處，然后與原B中后N/2 個粒子的對應值比較。若該函數值小于B 中對應值，則將該函數值對應的位置放入Cross 對應最優位置矩陣，否則將B 的該值對應的最優位置放入Cross 對應最優位置矩陣處。

②經過以上更新后，Cross 的最優位置矩陣處全部為各粒子的最優位置，再將這些最優位置代入適應度函數，所得值放入對應最優值處，此時得到Cross 的最優位置及最優值。

③將Cross 與B 中后半部分進行合并，再次利用sortrows 函數對最優值進行升序排列，將排序所得前N/2整體投入下一代與原來直接進入下一代的粒子群體組成由GA 優化后的粒子群，也即執行PSO 的初始值。

3.2.4 粒子群算法的對接

執行PSO 部分包括依次迭代更新個體最優位置、最優值，更新全局最優位置、最優值，更新個體的位置、速度、邊界條件的處理以及記錄歷代全局最優值等，均與單獨執行PSO 部分完全一致。

該結合方式相對于以上所述的先單獨執行上文的GA 部分再單獨執行上文的PSO 部分，優勢是顯而易見的，該結合方式不需要GA 多次迭代，只需一次優化即可，節省了大量尋優時間，同時全局尋優性能也有所提升。

4 Matlab 仿真測試與結果分析

4.1 基準測試函數

算法的性能比較往往需要基準函數來驗證，本研究中選取了 Sphereh 函數，Rastrigrin 函數，Ackley 函數3 個常用的基準測試函數[15]。

（1）Sphere 函數

該函數在xi=0 時取得最優值0，函數曲面平滑，對稱，單峰。

（2）Rastrigrin 函數

該函數在xi= 0 時取得最優值0，為非線性多峰值函數，具有極多局部最優點，極難優化。

（3）Ackley 函數

該函數在xi= 0 時取得最優值0，為多峰值函數，具有較多的局部最優點。

4.2 各優化算法的函數測試結果及分析

本研究要比較的算法分別為GA，PSO，PSO-GA，GA-PSO，*GA-PSO（改進GA-PSO）。本實驗在Matlab 環境下，利用3 個基準函數對5 種算法分別驗證，將每個函數的5 種尋優過程置于同一比例圖中，分別如圖1—圖3 所示。此外，為便于對其性能進行對比，還將各算法在各函數上的平均目標函數值及平均收斂迭代次數值繪于同一表中，平均目標函數值及平均收斂迭代次數對比如表1 所示。

圖1 5 種算法在Sphereh 函數上的尋優過程比較

圖2 5 種算法在Rastrigrin 函數上的尋優過程比較

圖3 5 種算法在Ackley 函數上的尋優過程比較

表1 平均目標函數值及平均收斂迭代次數對比

由圖1 和表1 可知，上述5 種優化算法的平均目標函數值均達到了很高的精度，而且其迭代收斂次數也均在100 代以內。由于Sphere 函數平滑、單峰且無其他局部極小值，因而PSO 的易陷入局部極值的缺點并未顯露，反而利用其原理簡單、參數少、粒子具有記憶性等優點，使尋得的最優值優于GA 算法。混合算法相對于PSO 在計算精度和收斂速度上均有所提升，其中PSO-GA 表現最優；還可以看出，*GA-PSO 相對于GA-PSO 計算精度相差不大，但由于改進GA 使用了對隨機初始粒子優化次數銳減的方法，進而也相對提高了*GA-PSO 的收斂速度。

由圖2、圖3 和表1 可知，對于多峰函數而言，以上單優化算法的缺點被暴露，與此同時，融合算法的優勢也更加明顯。GA 算法由于其操作的盲目無方向性，使得收斂迭代次數居高不下，但其計算精度方面的性能卻較為優秀。PSO 雖早早收斂，但卻使其陷入了局部最優值。對比PSO 與GA-PSO 發現，前期經GA 的迭代，已在全局范圍內尋得次優解，此時再利用PSO 均勻朝最優解移動的特點，使得GA-PSO 收斂精度及收斂速度均有所提升，但可以發現提升效果并不明顯，這是由于前期GA 在迭代過程中以及后期PSO在移向最優值的過程中，它們的缺點依舊存在，使得收斂精度和收斂速度并沒有急速提升。

對比GA 與PSO-GA 發現，種群先經PSO 優化，可以得到很多接近最優解的個體，此時再利用GA 算法的交叉變異去改善種群，提升種群多樣性，這樣可以在很大程度上避免了陷入局部最優，并且可以快速準確地在接近最優解的個體中尋得最優值，實現全局快速尋優，由以上實驗結果發現，對于多峰函數優化問題，PSO-GA 表現尤為突出，無論是收斂精度還是收斂速度，相對于GA 算法均有明顯提高。

此外，對比 GA-PSO 與 *GA-PSO 發現，*GA-PSO相對于GA-PSO 計算精度相差不大，但由于改進強化后的GA 算法對隨機初始粒子只實施一次優化便交由PSO 去向最優解均勻移動，在一定程度上提高了*GA-PSO 的收斂速度。

5 結 語

GA 算法的交叉變異等操作可以極大豐富種群的多樣性，但多約束情況會使得整個迭代過程變得漫長，求解精度也遠遠不夠，本研究中對GA 算法的優化方式提出改進，使得其優化能力極大提升，優化次數有效減少，收斂速度也明顯提高；粒子群算法利用其均勻朝著最優解移動的特點，可以在初步優化后得到很多接近最優解的個體，但面臨多維問題時依舊會有陷入局部最優值的可能。本研究對以上單一算法的串行式融合，有效避免了各自的弊端，并成功地結合了各自的優勢，使得求解精度、收斂速度及全局穩定性均有極大提升。此外，為了探索研究出效果更佳的優化算法，課題組下一步要做的工作是將粒子群算法的位置更新思想融入到變異算子，將慣性權重w 采用非線性動態自適應進行更新等。