張 海，李士心，劉小鈺

（天津職業(yè)技術(shù)師范大學(xué)電子工程學(xué)院，天津 300222）

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

1 遺傳算法（GA）

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

1.1 變量初始化

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

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

1.2 染色體排序

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

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

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

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

1.3.2 基于概率的變異操作

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

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

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

1.3.3 染色體重排序

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

1.4 迭代尋優(yōu)

迭代上述過程G 次，將G 個適應(yīng)度函數(shù)值繪成曲線。

2 粒子群算法（PSO）

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

2.1 變量初始化

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

2.2 種群初始化

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

2.3 種群更新

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

2.3.1 個體的最優(yōu)位置和最優(yōu)值的更新

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

2.3.2 全局最優(yōu)位置和最優(yōu)值的更新

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

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

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

式中：j 為某個粒子，j ?。?，N）。

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

此外，對于慣性權(quán)重w 可采用非線性動態(tài)自適應(yīng)進行更新，以便很好地進行開發(fā)能力與探索能力的分配。

2.3.4 對邊界條件的處理

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

2.4 遍歷尋優(yōu)

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

3 GA 與PSO 的串行式融合

3.1 先PSO后GA

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

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

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

3.2 先GA后PSO

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

3.2.1 初始化

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

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

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

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

3.2.2 遺傳算法優(yōu)化

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

3.2.3 Cross部分的更新

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

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

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

3.2.4 粒子群算法的對接

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

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

4 Matlab 仿真測試與結(jié)果分析

4.1 基準測試函數(shù)

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

（1）Sphere 函數(shù)

該函數(shù)在xi=0 時取得最優(yōu)值0，函數(shù)曲面平滑，對稱，單峰。

（2）Rastrigrin 函數(shù)

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

（3）Ackley 函數(shù)

該函數(shù)在xi= 0 時取得最優(yōu)值0，為多峰值函數(shù)，具有較多的局部最優(yōu)點。

4.2 各優(yōu)化算法的函數(shù)測試結(jié)果及分析

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

圖1 5 種算法在Sphereh 函數(shù)上的尋優(yōu)過程比較

圖2 5 種算法在Rastrigrin 函數(shù)上的尋優(yōu)過程比較

圖3 5 種算法在Ackley 函數(shù)上的尋優(yōu)過程比較

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

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

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

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

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

5 結(jié) 語

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