羅鳳鳴，呂方林，侯宗琰

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

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

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

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

1 FGA算法

1.1 FGA算法

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

1.1.1 種群初始化

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

(1)

1.1.2 適應(yīng)度函數(shù)

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

fitness=ymax-obj。

(2)

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

1.1.3 選擇算子

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

1.1.4 交叉算子

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

(3)

1.1.5 變異算子

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

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

(4)

1.1.6 爆炸算子

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

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

(5)

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

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

(6)

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

(7)

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

h=Ai·rand(-1,1)

(8)

式中：h表示爆炸的位移距離；rand(-1,1)是區(qū)間[-1,1]上的一個隨機(jī)數(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 精英保留策略

為避免交叉、變異和爆炸運(yùn)算丟失和破壞上一代種群中的精英個體，故采取精英保留策略存儲運(yùn)算過程中的精英個體。精英保留策略[15]的核心思想是把種群進(jìn)化過程中出現(xiàn)的精英個體復(fù)制到下一代中。精英個體是種群進(jìn)化中搜索到的最優(yōu)適應(yīng)度值的個體，它包含目前最好的基因數(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個個體的適應(yīng)度值；Selection{P(t)}為遺傳算法的選擇運(yùn)算，Ps(t)表示通過比較適應(yīng)度值而被選中的解集；同理Crossover、Mutation 和Fire分別是交叉、變異和爆炸運(yùn)算，與之對應(yīng)的Pc(t)、Pm(t)和Pf(t)分別是經(jīng)過交叉、變異和爆炸運(yùn)算產(chǎn)生的新種群；X表示整個進(jìn)化過程中保留的最優(yōu)解。

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

圖1 FGA算法流程圖

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

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

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

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

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

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

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

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

2 仿真驗(yàn)證

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

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

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

表1 各項(xiàng)參數(shù)表

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

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

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

圖2 2種算法收斂曲線

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

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

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

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

3 結(jié)束語

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

參 考 文 獻(xiàn)

[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]. 機(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] 李雪巖, 李雪梅, 李學(xué)偉,等. 基于混沌映射的元胞遺傳算法[J]. 模式識別與人工智能, 2015,28(1):42-49.

[6] 王忠, 柴賀軍, 劉浩吾. 關(guān)于進(jìn)化遺傳算法的幾點(diǎn)改進(jìn)[J]. 電子科技大學(xué)學(xué)報(bào), 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)多目標(biāo)優(yōu)化[J]. 電力系統(tǒng)及其自動化學(xué)報(bào), 2015, 27(7):24-29.

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

[10] 程林輝, 鐘珞. 求解多峰函數(shù)優(yōu)化問題的并行免疫遺傳算法[J]. 微電子學(xué)與計(jì)算機(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ìn)遺傳算法[J]. 計(jì)算機(jī)仿真, 2015,32(1):301-305.

[14] 譚營, 鄭少秋. 煙花算法研究進(jìn)展[J]. 智能系統(tǒng)學(xué)報(bào), 2014,9(5):515-528.

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