基于精英保留策略與爆炸算子的改進遺傳算法

羅鳳鳴，呂方林，侯宗琰

(東北石油大學電氣信息工程學院, 黑龍江 大慶 163318)

遺傳算法[1]是一種模擬物種進化的智能算法。它在尋優過程中不需要復雜的微分和積分公式，只須生成大量的隨機數在解空間中進行搜索，即可得到較為合理的最優解，因此，受到學者的廣泛關注。遺傳算法具有較強的優化性和魯棒性，已經在參數調節、路徑規劃等領域[2-5]得到了應用；但是隨著問題維數的提高和約束條件的增多，標準遺傳算法已經無法精確地處理該類問題，尋優過程中存在著收斂緩慢、易早熟和精度低等缺陷[6-7]，難以獲得正確的全局最優解。

針對標準遺傳算法存在的缺陷，研究者提出了很多改進措施[8-13]。陳碧云等[8]提出一種多種群改進遺傳算法(poly-population genetic algorithm，PPGA)以求解電力系統多目標優化問題。由于遺傳算法收斂性能受變異和交叉概率的影響較大，因此，文獻[8]選取不同組的變異和交叉概率進行多種群并行優化；但是由于交叉與變異概率可以形成無數對的組合，以及多種群并行進化勢必會增加算法的計算復雜度的緣故，此方法仍無法根本解決問題。杜卓明等[9]在陳碧云等的基礎上提出一種基于差分的自適應參數改進遺傳算法(differential genetic algorithm，DGA)，算法中的交叉和變異概率根據適應值做動態調整，并與差分進化算法結合，有效地解決了控制參數選取的問題；但是由于種群多樣性不足，因此仍容易陷入局部收斂。針對標準遺傳算法在求解非凸函數時易早熟的不足，程林輝等[10]提出一種基于免疫因子改進遺傳算法(immune genetic algorithm，IGA)的混合優化算法，利用免疫算法的抗體濃度抑制原則和免疫記憶庫，并通過變異算子降低種群內相似個體的數目，避免算法陷入局部收斂，但是在進化后期會出現停止現象導致收斂緩慢。S.M.H. NABAVI等[11]提出一種改進編碼方式的遺傳算法(improved genetic algorithm，IGA)，使染色體數值精度有所提高，改進編碼方式可以避免染色體之間出現“斷崖式”躍變，然而，僅起到提高求解精度的作用。K. SHI等[12]提出一種基于最小生成樹的改進遺傳算法(minimum spanning tree genetic algorithm，MSTGA)，通過聚類算法將單種群劃分為多種群并行搜索計算，但是分類數目的不同對聚類算法分類效果影響較大。由于分類數目的選擇是人為設定的，具有主觀性，因此算法的精度不高。瞿顏等[13]提出一種帶有引向因子和反向搜索技術的遺傳算法(gravitational search genetic algorithm，GSGA)，將引向因子融入交叉算子，以加強群體之間的信息共享，但是仍然存在著種群多樣性不足的缺點。

大多數研究都圍繞交叉和變異運算等控制參數的改進，鮮有在生物進化原理上進行改進。為此，本文提出一種具有爆炸算子的改進遺傳算法(FGA)，引入爆炸算子在原種群基礎上產生新種群，將多個種群結合起來搜索以提高種群的多樣性和競爭能力，最后采用精英保留策略以保留搜索過程中的最優個體。

1 FGA算法

1.1 FGA算法

標準遺傳算法(SGA)是一種模擬生物界“優勝劣汰”策略的啟發式進化算法，是廣泛應用于各領域數值尋優的智能算法之一；但是依然存在易陷入局部最優值、全局搜索能力差、魯棒性不強等缺陷。FGA算法是在SGA算法的基礎上引入爆炸算子和精英保留策略，其算法的基本運算步驟包括種群初始化，適應度值計算，選擇、交叉和變異運算，爆炸運算，精英保留策略。

1.1.1 種群初始化

初始化通常以均勻分布概率密度函數隨機生成種群。計算公式為

(1)

1.1.2 適應度函數

適應度函數是算法的關鍵，通過適應度函數對繁衍出來的后代進行量化評估，進而選擇優秀個體保留至下一代。選取不同適應度函數會影響算法的收斂速度、結果和性能。常用的適應度函數有3種：絕對誤差、相對誤差和條件判斷的適應度函數。由于本文測試函數求取的是最小值，故選用相對誤差的適應度函數，計算公式為

fitness=ymax-obj。

(2)

式中：fitness表示所有解集的適應度值；obj表示所有解集的目標函數值；ymax表示解集中目標函數的最大值。

1.1.3 選擇算子

本文采用的選擇操作是賭轉輪盤法[13]，這種方法簡單有效。

1.1.4 交叉算子

在交叉運算中，決定個體是否進行運算的參數是交叉概率(Pc)，其范圍設置為0.6～0.9。計算公式為：

(3)

1.1.5 變異算子

同交叉運算類似，決定個體變異的參數是變異概率(Pm)，變異概率范圍設置為0.02～0.2。計算公式為

x(i,j)=x(i,j)+Δx。

(4)

1.1.6 爆炸算子

交叉運算容易導致解集發生躍變。雖然變異運算可以進行局部搜索，但是變異概率較小，導致變異運算執行次數少。又鑒于解集發生變異多為有害的情況，故不能大幅度提高變異概率。當求解非凸函數時，算法的全局搜索能力較差。為此，譚營教授團隊提出FA算子以解決全局復合函數最優化的問題[14]。該算子表示一種爆炸搜索進程，從搜索算法的角度看，要想提高算法搜索性能必須在最優解局部進行爆炸搜索，并且爆炸產生的個體數目要多，反之，距離最優解較遠的則產生較少個體進行搜索。由于單個解爆炸能產生多個新個體，待爆炸的解選取過多勢必會增加計算量，降低算法優化效率。基于上述分析，本文從解集中選取n(n≤10)個解進行爆炸搜索，最后結合上一代解集形成“父子混合解集”進行選擇，這有效地提高了算法探索新的解空間的能力。解xi產生爆炸個體數目的計算步驟如下。

step 1，根據種群中個體優劣的不同，通過式(5)生成相應的子群。

(5)

式中：Ci表示第i個解產生的個體數目大小；μ是控制n個解產生個體總數的常量參數；ymax是解集中目標函數的最大值；ε表示最小值常量，用來避免除0錯誤。

step 2，為避免爆炸生成個體數目過多或過少影響算法的效率和搜索能力，需要對其進行修正。修正函數定義為：

(6)

其中，a和b是固定常量參數。

(7)

式中：Ai表示第i個解爆炸的位移幅度；Amax表示最大爆炸振幅；ymin是解集中目標函數的最小值。

h=Ai·rand(-1,1)

(8)

式中：h表示爆炸的位移距離；rand(-1,1)是區間[-1,1]上的一個隨機數。

x′(i,j)=h+x(i,j)，

(9)

式中x′(i,j)表示爆炸產生的新個體。若產生的新個體不滿足解域空間范圍，根據式(9)將其映射回解域

(10)

式中x″(i,j)為轉化后滿足解域范圍的新個體。

1.1.7 精英保留策略

為避免交叉、變異和爆炸運算丟失和破壞上一代種群中的精英個體，故采取精英保留策略存儲運算過程中的精英個體。精英保留策略[15]的核心思想是把種群進化過程中出現的精英個體復制到下一代中。精英個體是種群進化中搜索到的最優適應度值的個體，它包含目前最好的基因數據。精英保留策略有效地提高了算法的收斂能力。

1.2 FGA算法偽代碼與流程圖

本文采用偽代碼和流程圖2種形式描述FGA算法對測試函數的求解流程。FGA算法主程序偽代碼如下。

Procedures of the proposed FGA algorithm

Begin

t= 0；

InitializeP(t)；

P(t)={X1(t)，X2(t)，…，Xn(t)}

EvaluateP(t)；

f(P(t))={f(X1(t))，f(X2(t))，…，f(Xn(t))}

While (t

Ps(t)=Selection{P(t)}；

Pc(t)=Crossover{Ps(t)}；

Pm(t)=Mutation {Pc(t)}；

Pf(t)=Fire{Pm(t)}；

EvaluatePf(t)；

Ift<1 then

doX=min{Pf(t)}；

Else

IfX

doX=min{pf(t)}；

End

End

t=t+ 1；

End

PrintfX；

End

偽代碼呈現了FGA算法的主程序流程，其中t代表算法的迭代次數，tmax表示算法的最大迭代次數；InitializeP(t)表示初始化種群；P(t)表示第t代種群，Xi(t)表示第t代種群中的第i個個體；EvaluateP(t)表示評價種群，其中f(Xi(t))表示第i個個體的適應度值；Selection{P(t)}為遺傳算法的選擇運算，Ps(t)表示通過比較適應度值而被選中的解集；同理Crossover、Mutation 和Fire分別是交叉、變異和爆炸運算，與之對應的Pc(t)、Pm(t)和Pf(t)分別是經過交叉、變異和爆炸運算產生的新種群；X表示整個進化過程中保留的最優解。

FGA算法的具體步驟如圖1所示。

圖1 FGA算法流程圖

step 1，隨機初始化種群和迭代次數t，生成規模大小為N的初代種群Pt。

step 2，判斷迭代次數t是否達到最大迭代次數tmax，若沒有執行step 3，否則執行step 8。

step 3，計算解集的適應度值，使用賭轉輪盤法進行選擇操作，復制出N個優秀個體，形成子代種群Qt。

step 4，進行交叉、變異操作對種群進行進化(此時種群仍稱為Qt)。

step 5，選取n(n≤10)個局部最優解進行爆炸運算(此時種群仍稱為Qt)。

step 6，將Pt和Qt結合形成混合種群Rt，并執行精英保留策略。

step 7，從混合種群Rt生成規模為N的新種群Pt，此時t=t+1，并執行step 2。

step 8，直接輸出計算結果，結束。

2 仿真驗證

2.1 參數設置

本文參考文獻[13]中應用的測試函數，任選4個函數作為驗證案例，各項參數如表1所示。利用本文提出的FGA算法和SGA算法對表1中的4個測試函數進行數值尋優。

遺傳算法的參數設置為：種群大小50；測試函數Spherical、Rastigrin和G6最大迭代數為100，由于Schwefel函數較為復雜，因此求解該函數時迭代數設定為1 000；Pc取0.7，Pm取0.1；n=5，m=50，a=0.04，b=0.8，Ai=40。2種算法獨立優化20次，計算測試函數所得最優解的平均值、標準差和最優值如表2所示。

表1 各項參數表

表2 規劃結果

2.2 仿真結果與分析

針對4個測試函數分別采用SGA算法和FGA算法進行求解，其結果如圖2所示。可知，引入爆炸算子改進遺傳算法后，FGA算法的收斂速度相比于SGA算法更快，搜索得到的最優解精確度更高，FGA算法的種群多樣性和全局搜索能力得到了改善。

圖2 2種算法收斂曲線

結合表2和圖2，可得出以下結論。

1)采用2種算法對無約束的單峰函數Spherical求解。由表2可知，2種算法都可以得到理想值，但是SGA算法求得的解集平均值和標準差值明顯劣于FGA算法所得的結果。這說明本文提出的FGA算法相比于SGA算法，不僅有效地提高最優解精度，而且降低了最優解的標準差。

2)采用2種算法對尋優難度大的無約束的多峰函數Rastigrin和Schwefel進行求解。由圖2、表2可知，對于函數最優值附近的陡峭區域，2種算法都能精確地求得理想值，然而FGA算法能保證在20次優化過程中，最優解的均值和標準差都為0，并且相較于SGA算法具有更快的收斂速度。這說明本文提出的爆炸算子能有效地改善標準遺傳算法的種群多樣性和解空間的搜索能力。

3)對于帶約束的函數優化，往往很難生成滿足條件的初代種群，從而導致后期求解困難，然而引入爆炸算子和精英保留策略后，可以使解的搜索范圍擴大，并且保證不丟失符合約束的解集，從而使求解復雜度維數降低。由表2可知，FGA算法求得的最優值能精確到1×10-8數量級，而SGA算法求得的解的標準差近似為90。這說明本文提出的FGA算法在處理高維復雜函數能近似地求得理論值，進一步體現了本文提出的改進算法具有更好的全局搜索能力。

3 結束語

本文在遺傳算法原有運算步驟中加入了爆炸算子，爆炸算子能夠通過原解集中的個體產生局部種群，增加了算法探索解空間的能力，形成了類似于“多種群”的遺傳算法，使種群在進化過程中具有更強的競爭性和全局搜索能力，從而能很好地避免算法早熟；同時引入了精英保留策略與之結合，有效地防止當前群體的最優個體在下一代進化過程中被丟失和破壞，提高了算法的魯棒性。最后采用FGA算法和SGA算法對經典測試函數進行數值優化實驗對比。對比結果分析可知，無論對于單峰函數、多峰函數、無約束條件和有約束條件的函數，本文提出的FGA算法均能快速、穩定地獲得全局最優解；但是，作者在實驗過程中發現FGA算法耗時相對較長，還有待于進一步改進，以提高其計算效率。

參 考 文 獻

[1] GOLDBERG D E. Genetic algorithm in search, optimization, and machine learning[M]. Massachusetts: Addison-Wesley Professional, 1989:2104-2116.

[2] WIES R W, CHUKKAPALLI E, MUELLER-STOFFELS M. Improved frequency regulation in mini-grids with high wind contribution using online genetic algorithm for PID tuning[C]//Pes General Meeting Conference & Exposition. National Harbor:IEEE, 2014:1-5.

[3] 李曄, 姜言清, 張國成,等. 考慮幾何約束的AUV回收路徑規劃[J]. 機器人, 2015, 37(4):478-485.

[4] CHAKRAVARTY S, MITTRA R. Design of microwave filters using a binary-coded genetic algorithm[J]. Microwave & Optical Technology Letters, 2015, 26(3):162-166.

[5] 李雪巖, 李雪梅, 李學偉,等. 基于混沌映射的元胞遺傳算法[J]. 模式識別與人工智能, 2015,28(1):42-49.

[6] 王忠, 柴賀軍, 劉浩吾. 關于進化遺傳算法的幾點改進[J]. 電子科技大學學報, 2002, 31(1):76-79.

[7] DING H F, LIU X L, LIU X. An improved genetic algorithm for combinatorial optimization[C]//IEEE International Conference on Computer Science and Automation Engineering. Shanghai： IEEE, 2011:58-61.

[8] 陳碧云, 韋杏秋, 陳紹南,等. 基于多種群遺傳算法的電力系統多目標優化[J]. 電力系統及其自動化學報, 2015, 27(7):24-29.

[9] 杜卓明, 耿國華, 徐鵬,等. 改進遺傳算法在差分像運動圖像實時處理中的應用[J]. 模式識別與人工智能, 2012, 25(5):879-884.

[10] 程林輝, 鐘珞. 求解多峰函數優化問題的并行免疫遺傳算法[J]. 微電子學與計算機, 2015, 32(5):117-121.

[11] NABAVI S M H, HAJFOROOSH S, HAJFOROOSH S, et al. Maximizing the overall satisfaction degree of all participants in the market using real code-based genetic algorithm by optimally locating and sizing the thyristor-controlled series capacitor[J]. Journal of Electrical Engineering & Technology, 2011, 6(4):493-504.

[12] SHI K, SONG Q, LIN S, et al. An improved genetic algorithm for degree constrained minimum spanning trees[C]//Control and Decision Conference. Yinchuan： IEEE, 2016:4603-4607.

[13] 瞿顏, 袁建濤, 郭陳江,等. 一種基于引向因子和反向搜索的改進遺傳算法[J]. 計算機仿真, 2015,32(1):301-305.

[14] 譚營, 鄭少秋. 煙花算法研究進展[J]. 智能系統學報, 2014,9(5):515-528.

[15] 王瑞琪, 李珂, 張承慧,等. 基于多目標混沌量子遺傳算法的分布式電源規劃[J]. 電網技術, 2011, 35(12):183-189.