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

羅鳳鳴，呂方林，侯宗琰

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

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

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

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

1 FGA算法

1.1 FGA算法

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

1.1.1 種群初始化

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

(1)

1.1.2 適應度函數(shù)

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

fitness=ymax-obj。

(2)

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

1.1.3 選擇算子

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

1.1.4 交叉算子

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

(3)

1.1.5 變異算子

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

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

(4)

1.1.6 爆炸算子

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

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

(5)

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

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

(6)

其中，a和b是固定常量參數(shù)。

(7)

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

h=Ai·rand(-1,1)

(8)

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

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

(9)

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

(10)

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

1.1.7 精英保留策略

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

1.2 FGA算法偽代碼與流程圖

本文采用偽代碼和流程圖2種形式描述FGA算法對測試函數(shù)的求解流程。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

偽代碼呈現(xiàn)了FGA算法的主程序流程，其中t代表算法的迭代次數(shù)，tmax表示算法的最大迭代次數(shù)；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)分別是經(jīng)過交叉、變異和爆炸運算產(chǎn)生的新種群；X表示整個進化過程中保留的最優(yōu)解。

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

圖1 FGA算法流程圖

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

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

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

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

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

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

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

step 8，直接輸出計算結(jié)果，結(jié)束。

2 仿真驗證

2.1 參數(shù)設(shè)置

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

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

表1 各項參數(shù)表

表2 規(guī)劃結(jié)果

2.2 仿真結(jié)果與分析

針對4個測試函數(shù)分別采用SGA算法和FGA算法進行求解，其結(jié)果如圖2所示?？芍?，引入爆炸算子改進遺傳算法后，F(xiàn)GA算法的收斂速度相比于SGA算法更快，搜索得到的最優(yōu)解精確度更高，F(xiàn)GA算法的種群多樣性和全局搜索能力得到了改善。

圖2 2種算法收斂曲線

結(jié)合表2和圖2，可得出以下結(jié)論。

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

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

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

3 結(jié)束語

本文在遺傳算法原有運算步驟中加入了爆炸算子，爆炸算子能夠通過原解集中的個體產(chǎn)生局部種群，增加了算法探索解空間的能力，形成了類似于“多種群”的遺傳算法，使種群在進化過程中具有更強的競爭性和全局搜索能力，從而能很好地避免算法早熟；同時引入了精英保留策略與之結(jié)合，有效地防止當前群體的最優(yōu)個體在下一代進化過程中被丟失和破壞，提高了算法的魯棒性。最后采用FGA算法和SGA算法對經(jīng)典測試函數(shù)進行數(shù)值優(yōu)化實驗對比。對比結(jié)果分析可知，無論對于單峰函數(shù)、多峰函數(shù)、無約束條件和有約束條件的函數(shù)，本文提出的FGA算法均能快速、穩(wěn)定地獲得全局最優(yōu)解；但是，作者在實驗過程中發(fā)現(xiàn)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回收路徑規(guī)劃[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] 王忠, 柴賀軍, 劉浩吾. 關(guān)于進化遺傳算法的幾點改進[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] 陳碧云, 韋杏秋, 陳紹南,等. 基于多種群遺傳算法的電力系統(tǒng)多目標優(yōu)化[J]. 電力系統(tǒng)及其自動化學報, 2015, 27(7):24-29.

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

[10] 程林輝, 鐘珞. 求解多峰函數(shù)優(yōu)化問題的并行免疫遺傳算法[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]. 智能系統(tǒng)學報, 2014,9(5):515-528.

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