《電子技術(shù)應用》
您所在的位置:首頁 > 嵌入式技術(shù) > 設計應用 > LO型曲線的自適應遺傳算法研究
LO型曲線的自適應遺傳算法研究
2015年電子技術(shù)應用第12期
徐明明,宋宇博
蘭州交通大學 機電技術(shù)研究所,甘肅 蘭州730070
摘要: 標準的遺傳算法在設置交叉算子和變異算子時使用固定的值,這樣在求解復雜的優(yōu)化問題時會存在解的多樣性差和早熟的缺點。傳統(tǒng)的自適應算法在收斂速度和解的多樣性上是有效的,但是在算子調(diào)整的過程中,對算法演化過程中不同階段的側(cè)重不夠(搜索空間、搜索精度、優(yōu)秀模式的保存及進化動力),這樣會使算法的收斂速度變慢并且減少優(yōu)良解的多樣性。提出一種改進的自適應調(diào)整算法來提高收斂速度及優(yōu)良解的多樣性,用Logistics曲線按照個體的適應度對交叉和變異算子的大小進行非線性調(diào)整,使得算子在演化的過程中滿足不同階段對搜索空間和搜索精度的要求。通過實驗驗證,新算法在收斂速度、穩(wěn)定性及優(yōu)良解的多樣性上比傳統(tǒng)的自適應遺傳算法有優(yōu)勢。
關(guān)鍵詞: 遺傳算法 自適應 性能改進
中圖分類號: TH692;F253
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2015.12.034

中文引用格式: 徐明明,宋宇博. LO型曲線的自適應遺傳算法研究[J].電子技術(shù)應用,2015,41(12):129-132,136.
英文引用格式: Xu Mingming,Song Yubo. The research of the LO type curve of adaptive genetic algorithm[J].Application of Electronic Technique,2015,41(12):129-132,136.
The research of the LO type curve of adaptive genetic algorithm
Xu Mingming,Song Yubo
The Mechachonics T&R Institute,Lanzhou Jiaotong University,Lanzhou 730070,China
Abstract: The Standard Genetic Algorithm(SGA) adopts constant crossover probability as well as invariable mutation probability. It has such disadvantages as premature convergence, low convergence speed and low robustness. Traditional adaptive genetic algorithm can improve the effect of convergence speed,however,when the operator adaptive adjustment, the algorithm of the different stages in the evolution process of focus is not enough(the search space, search precision, excellent model of the preservation and evolutionary dynamics), makes the algorithm convergence speed, stability and diversity not good. This paper puts forward an improved adaptive adjustment algorithm, and crossover operator and mutation operator in accordance with the individual fitness by the Logistics curve of the nonlinear adjustment makes the operator meet in the process of the evolution of different stages of the requirement of the search space and search accuracy. The experimental results show that the new algorithm than the traditional adaptive genetic algorithm on the convergence speed, stability and good solution on diversity has the advantages.
Key words : Genetiealgorithm;self-adaption;performance improve

    

0 引言

    遺傳算法(Genetic Algorithm,GA)是通過仿生物進化來解決優(yōu)化問題的一種有效算法[1]。其中,交叉和變異算子是算法進化的核心,并且對收斂速度和穩(wěn)定性都有一定的影響。傳統(tǒng)的遺傳算法采用固定的控制參數(shù),但選擇恰當?shù)墓潭▍?shù)是比較困難的。自適應調(diào)整遺傳算子是解決該問題的有效辦法,但同時也遇到了新的問題[2],由于在自適應調(diào)整的過程中采用的調(diào)整方式不同,使得算法在求解時的精確度大小不盡相同。Srinvas等[3]提出用線性調(diào)整(Adaptive GA,AGA)來對交叉率和變異率進行改進,從而提高算法的收斂速度,但在初期會出現(xiàn)停滯現(xiàn)象,導致算法的穩(wěn)定性和種群的平均適應度值降低。石山等[4]提出的余弦改進型的自適應遺傳算法(CAGA)提高了算法的收斂速度,在算法的中后期促使不理想的個體模式發(fā)生變化和保留種群中的優(yōu)良模式,缺點是當平均適應度和最大適應度差值較大時,個體的交叉率與變異率會出現(xiàn)較大差異,不利于算法演化的進行。趙越等[5]把交叉率和變異率用曲線進行調(diào)整,使收斂速度變快,但是缺乏對個體基因?qū)哟紊隙鄻有缘母倪M,變異率單調(diào)增大的變化趨勢導致進化初期產(chǎn)生新個體的能力差和進化末期破壞種群中優(yōu)良模式的結(jié)果。

    文章提出用Logistic型曲線調(diào)整交叉算子和變異算子(LOAGA),從進化方向考慮對交叉率和變異率進行自適應調(diào)整,比較當代平均適應度值和個體適應度值的大小以及最優(yōu)個體的適應度值,從而得出該個體的交叉率和變異率。這樣既有利于保留較好個體模式,也提高了較差個體的變異能力,使算法盡量避免局部最優(yōu)解,并且可以克服因早熟產(chǎn)生的不良效果,以及對交叉率和變異率在不同進化階段的側(cè)重,增加了種群在個體層次上和基因?qū)哟紊系亩鄻有裕瑥亩鰪娏巳后w進化的動力。

1 算法分析

1.1 基本遺傳算法

    GA是一個反復迭代的過程。其步驟如下:

    (1)確定染色體編碼方式和適應度函數(shù)及種群初始化;

    (2)評價個體適應度;

    (3)進化開始,執(zhí)行選擇操作和交叉操作及變異操作,產(chǎn)生的個體作為下一代;

    (4)回到(2),解碼新種群并且計算適應度值,如果到達指定精度或設定的進化代數(shù),那么結(jié)束,否則執(zhí)行步驟(3),繼續(xù)遺傳操作[6]。

    在用遺傳算法解決優(yōu)化問題時,是根據(jù)經(jīng)驗選取固定算子,通過交叉、變異和選擇實現(xiàn)父代重組得到子代個體[7]。而算法實際演化過程中不同階段對開辟搜索區(qū)域的能力和多樣性(個體、基因)的要求不同。演化初期應增強種群個體層次上的多樣性,對搜索空間有較好的覆蓋程度;中期除了考慮搜索空間的覆蓋程度外,應加大變異率,增加基因?qū)哟紊系亩鄻有裕皇諗啃允撬惴ê笃谛枰⒁獾?sup>[8-9]。GA中固定的交叉率和變異率是根據(jù)經(jīng)驗而來,而不是根據(jù)實際問題需要自適應調(diào)節(jié)算子的大小,使得算法在演化過程中的收斂性、穩(wěn)定性及解的多樣性不理想。

    針對固定的遺傳算子不利于演化進行的問題,自適應調(diào)節(jié)遺傳算子是解決這個問題的有效辦法。

1.2 線性自適應遺傳算法

    Srinvas等提出在種群平均適應度值和最大適應度值間進行線性調(diào)整算子的大小。如式(1)和式(2)所示。

    jsj4-gs1-2.gif

其中,fmax是種群最大適應度值,favg是種群平均適應度值,f是變異個體的適應度值,f′是兩個交叉?zhèn)€體中的較大適應度值。在上式中,隨著favg與fmax接近,Pc和Pm就不斷變小直至為零。并且,在進化初期,較優(yōu)個體不發(fā)生變化,但這時的優(yōu)良個體并非全局最優(yōu)解,會出現(xiàn)局部收斂的可能性。文獻[10]中的改進算法(線性自適應,LAGA)可以解決交叉率和變異率為零的問題。式(3)及式(4)是調(diào)整公式。

    jsj4-gs3-4.gif

在式(3)、式(4)中,用Pc max和Pc min表示交叉率最大值和最小值;變異率的最大最小值是Pm max和Pm min。在求解Pc和Pm時,線性自適應遺傳算法是由個體的適應度值在favg與fmax間進行線性變換得出的。當大部分個體的適應度值趨近于favg時,它們模式相當,成為種群中的主要個體。但是當favg和當代種群的fmax接近時,就會出現(xiàn)線性自適應遺傳算法的算子調(diào)整曲線變得比較陡,Pc和Pm會產(chǎn)生較大差異并且變小,出現(xiàn)演化停滯不前的現(xiàn)象。

1.3 余弦自適應遺傳算法

    在文獻[4]中,GA的性能與設置交叉率和變異率是否合適有較大的關(guān)系,對其設置不當,會影響算法的收斂速度。簡單的線性變化得到的交叉率和變異率不能滿足算法演化的要求。進而在該文獻提出余弦改進型的自適應遺傳算法(CAGA),式(5)和式(6)是自適應遺傳算子的調(diào)節(jié)公式:

    jsj4-gs5-6.gif

    圖1是 CAGA自適應交叉變異調(diào)整曲線,在圖1中,CAGA比LAGA提升了適應度處于區(qū)間[favg,(favg+fmax)/2]個體的Pc和Pm,促進了favg附近不理想的個體模式發(fā)生變化。CAGA壓低了處于區(qū)間[(favg+fmax)/2,fmax]個體的Pc和Pm,有利于種群中優(yōu)良模式的保留。

jsj4-t1.gif

    圖2是CAGA與LAGA調(diào)整曲線對比圖,在CAGA中,Pc max和Pc min之間的差值很小,且小于等于1,Pm max和Pm min同樣如此。在圖2中,|Δf|(favg和fmax之間的差值)變化很大,不同優(yōu)化問題之間也存在區(qū)別。當|Δf|很大時,余弦和線性曲線十分接近,說明在一定程度上兩者的性能相當,同樣有停滯不前的現(xiàn)象。

jsj4-t2.gif

    在文獻[5]中提出的自適應調(diào)節(jié)公式中,雖然也提到用Logistic曲線對算子進行改進,但在用種群相似度控制變異率時,對進化后期基因?qū)哟紊系亩鄻有愿倪M不夠,變異率偏大會破壞種群中的優(yōu)良模式。

    分析得到以上算法的主要問題是演化過程中停滯不前,CAGA和LAGA一定程度上性能接近,進化過程中不同階段側(cè)重不夠。因此,從以下幾方面解決問題,首先,在favg處的調(diào)整曲線應該緩慢過渡,目的是較大地提高交叉率和變異率(在適應度接近平均適應度的過程中)。其次,為了當|Δf|較大時,不會出現(xiàn)線性調(diào)整的現(xiàn)象,避免停滯不前的現(xiàn)象。再次,使算子的自適應調(diào)整滿足算法進化前期空間大后期精度高的要求。同時,使接近fmax處的曲線變得更平滑,目的是保留較優(yōu)個體的模式。

    所以,針對線性自適應調(diào)節(jié)中出現(xiàn)停滯不前,余弦自適應調(diào)節(jié)中對算法演化不同階段側(cè)重不夠而使收斂速度慢和解的多樣性差的問題,文章用變化更平滑的曲線(Logistics)對交叉和變異算子進行非線性調(diào)整,提高算法的收斂速度和解的多樣性。

2 LO型曲線的自適應遺傳算法改進

2.1 算法改進

    Logistics曲線方程是Verhu推導出來的,在描述某些有界增長現(xiàn)象上有比較好的效果,應用廣泛,并且能較好地平衡線性和非線性行為之間的變化。以下是簡化處理的方程:

    jsj4-gs7-8.gif

    圖3為Logistic函數(shù)曲線圖,可以看出(a>0),該曲線(比余弦)變化更加細膩。當ax≥9.903 438時,y接近1;當ax<-9.903 438時,y接近0。式(9)和式(10)是用該曲線求解優(yōu)化問題的調(diào)節(jié)公式(交叉率和變異率),其中a=9.903 438。圖4和圖5分別是LOAGA的自適應調(diào)整曲線(交叉率和變異率)。

jsj4-t3.gif

jsj4-t4.gif

jsj4-t5.gif

    jsj4-gs9-10.gif

    從改進公式知,當種群開始進化時,LOAGA調(diào)整的變異率比余弦函數(shù)小,保持種群的優(yōu)良模式。當favg與fmax接近并且大部分個體的適應度值相近時,大多數(shù)個體的Pc和Pm變大,且高于余弦函數(shù)調(diào)整的幅度(圖6中a點)。同時,在接近fmax時,低于余弦函數(shù)調(diào)整的幅度(如圖6中b點),盡可能保留了fmax附近個體的優(yōu)良模式。在圖6的曲線變化趨勢上,滿足算法進化過程中對不同階段的側(cè)重(搜索空間上、個體和基因?qū)哟紊系亩鄻有砸约八惴ê笃诘氖諗糠矫妫?/p>

jsj4-t6.gif

    在改進后的調(diào)整曲線中,無論|Δf|怎么變化都與CAGA和LAGA拉開較大差距,帶動了演化的前進,擺脫局部收斂,防止演化停滯不前,如圖7所示。

jsj4-t7.gif

2.2 算法流程

    改進的自適應算法實現(xiàn)步驟如下:

    (1)種群初始化,二進制編碼;

    (2)計算適應度值;

    (3)根據(jù)favg和即將進行交叉及變異操作個體的適應度值,結(jié)合自適應調(diào)節(jié)公式得出Pc和Pm,并進行交叉、變異操作;

    (4)返回(2),解碼并重新進行適應度評價,如果達到指定的要求(精度或進化代數(shù))則結(jié)束,否則進行步驟(3),繼續(xù)執(zhí)行操作。流程如圖8。

jsj4-t8.gif

3 實驗驗證

3.1 算法參數(shù)選擇

3.1.1 選取函數(shù)

    通過對比LOAGA、CAGA、LAGA實驗后的數(shù)據(jù),來驗證改進算法的性能(收斂性和穩(wěn)定性)。選以下兩種函數(shù)進行試驗。

    jsj4-gs11-12.gif

    理論最小值是-1.031 628,收斂值是-1.031 60。

3.1.2 算法參數(shù)

    Pc max=0.8,Pc min=0.5,Pm min=0.05,Pm max=0.005,f1的進化代數(shù)是150代,f2為500代,各運行20次,取均值。

3.2 算法評價

    性能標準的確定:兩個函數(shù)分別用LOAGA、CAGA、LAGA算法進行測試(運行20次),算法穩(wěn)定性用平均收斂次數(shù)衡量,收斂速度用平均收斂代數(shù)衡量,以平均收斂值接近理想收斂值的程度作為衡量解多樣性的標準。

    算法進化的核心是Pc和Pm。整個搜索空間的覆蓋程度由Pc控制,用來尋找最優(yōu)解存在的區(qū)域;為保證算法具有全局收斂性,變異算子的作用就是使算法能搜索到解空間中的每一點。文章中在進化的初期提高交叉率(提高搜索空間的覆蓋程度),壓低變異率(保存原始種群的優(yōu)良模式);在中期朝最大適應度進化時拉高交叉(提高提高搜索空間的覆蓋程度)和變異算子(使種群有足夠基因?qū)哟紊系亩鄻有裕┘敖咏畲筮m應度時壓低兩個算子(保存優(yōu)良模式,收斂),使算法不斷進化,盡量避免局部最優(yōu)解。從表1的數(shù)據(jù)可以看出,隨著種群規(guī)模增大,各自的收斂速度變慢(搜索空間變大),LOAGA的收斂速度比CAGA和LAGA的收斂速度慢,但在收斂代數(shù)上LOAGA增加的比CAGA和LAGA少(快速找到優(yōu)良解),不僅在favg上高于LAGA,其收斂速度也比前兩者快,所以,文章中提出的算法有較快的收斂速度。

jsj4-b1.gif

    影響解的多樣性有交叉操作產(chǎn)生的個體多樣性、變異操作產(chǎn)生的基因多樣性及允許父代參與當代競爭的復制方式等因素,文章通過改善交叉率、變異率,增強種群個體和基因?qū)哟紊系亩鄻有詠韮?yōu)化解的多樣性,提高解的質(zhì)量。從表1的數(shù)據(jù)可以看出隨著種群規(guī)模的增大,收斂代數(shù)增加(搜索空間變大),但LOAGA的收斂值要比CAGA和LAGA的更加接近理想值,(而且增加的收斂代數(shù)比CAGA要少,改進后的算法能更快找到優(yōu)良解),說明提出的算法有更多的優(yōu)良解。

    從表1知,f2函數(shù)LOAGA的收斂總次數(shù)比其他兩種要多(快速找到優(yōu)良解),說明其穩(wěn)定性好。

4 總結(jié)

    文章通過分析交叉率、變異率對遺傳算法的影響,指出固定的交叉算子和變異算子及傳統(tǒng)改進方法在收斂性和穩(wěn)定性上的不足。結(jié)合Logistics曲線方程,設計了一種新的算法(LOAGA)。它的交叉算子和變異算子受適應度影響,隨Logistics曲線自適應調(diào)節(jié),相比LAGA和CAGA,無論|Δf|如何變化,通過對新算法的使用,能夠較快完成對算子的調(diào)整,使算法盡早跳出局部收斂,而且,對交叉率和變異率的自適應調(diào)整滿足在演化過程中不同階段對搜索范圍和搜索精度的要求。文中提出的算法在收斂速度上和穩(wěn)定性上有較明顯的優(yōu)勢。因此,LOAGA是一種實用的算法,在提高算法的收斂性和增強算法的穩(wěn)定性及優(yōu)良解的多樣性上是有效果的。

參考文獻

[1] Ann Arbor.Adaption in Naural and Artificial Systems[M].University of Michigan Press,1975.

[2] 黃樟燦,李煒.有界區(qū)域上多峰函數(shù)全局優(yōu)化問題的改進演化算法[J].武漢大學學報(理學版),2007,53(1):55-58.

[3] SRINVAS M,PATNAIK L M.Adaptive probabilities of crossover and,mutation in genetic algorithms[C].In:IEEE Trans on Systems,Man and Cybernetics,1994,24(4).

[4] 石山.基于自適應遺傳算法的無刷直流電機的優(yōu)化設計[J].西安交通大學學報,2002,36(12):1215-1218.

[5] 趙越,徐鑫.自適應記憶遺傳算法研究[J].計算機技術(shù)與發(fā)展,2014,24(2):63-66.

[6] 王凌.智能優(yōu)化算法及其應用[M].北京:清華大學出版社,2000:36-50.

[7] 李書全.遺傳算法中的交叉算子的述評[J].計算機工程與應用,2012,48(1):36-39.

[8] 劉勝.遺傳交叉和變異對種群多樣性的影響[J].控制與決策,2009,24(10):1535-1539.

[9] 雷秀娟.群智能優(yōu)化算法及其應用[M].北京:科學出版社,2012:70-74.

[10] 王小平,曹立明.遺傳算法:理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,002.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。