LO型曲線的自適應遺傳算法研究

徐明明，宋宇博

（蘭州交通大學 機電技術研究所，甘肅 蘭州 730070）

0 引言

遺傳算法（Genetic Algorithm，GA）是通過仿生物進化來解決優化問題的一種有效算法[1]。其中，交叉和變異算子是算法進化的核心，并且對收斂速度和穩定性都有一定的影響。傳統的遺傳算法采用固定的控制參數，但選擇恰當的固定參數是比較困難的。自適應調整遺傳算子是解決該問題的有效辦法，但同時也遇到了新的問題[2]，由于在自適應調整的過程中采用的調整方式不同，使得算法在求解時的精確度大小不盡相同。Srinvas等[3]提出用線性調整（Adaptive GA，AGA）來對交叉率和變異率進行改進，從而提高算法的收斂速度，但在初期會出現停滯現象，導致算法的穩定性和種群的平均適應度值降低。石山等[4]提出的余弦改進型的自適應遺傳算法（CAGA）提高了算法的收斂速度，在算法的中后期促使不理想的個體模式發生變化和保留種群中的優良模式，缺點是當平均適應度和最大適應度差值較大時，個體的交叉率與變異率會出現較大差異，不利于算法演化的進行。趙越等[5]把交叉率和變異率用曲線進行調整，使收斂速度變快，但是缺乏對個體基因層次上多樣性的改進，變異率單調增大的變化趨勢導致進化初期產生新個體的能力差和進化末期破壞種群中優良模式的結果。

文章提出用Logistic型曲線調整交叉算子和變異算子（LOAGA），從進化方向考慮對交叉率和變異率進行自適應調整，比較當代平均適應度值和個體適應度值的大小以及最優個體的適應度值，從而得出該個體的交叉率和變異率。這樣既有利于保留較好個體模式，也提高了較差個體的變異能力，使算法盡量避免局部最優解，并且可以克服因早熟產生的不良效果，以及對交叉率和變異率在不同進化階段的側重，增加了種群在個體層次上和基因層次上的多樣性，從而增強了群體進化的動力。

1 算法分析

1.1 基本遺傳算法

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

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

(2)評價個體適應度；

(3)進化開始，執行選擇操作和交叉操作及變異操作，產生的個體作為下一代；

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

在用遺傳算法解決優化問題時，是根據經驗選取固定算子，通過交叉、變異和選擇實現父代重組得到子代個體[7]。而算法實際演化過程中不同階段對開辟搜索區域的能力和多樣性（個體、基因）的要求不同。演化初期應增強種群個體層次上的多樣性，對搜索空間有較好的覆蓋程度；中期除了考慮搜索空間的覆蓋程度外，應加大變異率，增加基因層次上的多樣性；收斂性是算法后期需要注意的[8-9]。GA中固定的交叉率和變異率是根據經驗而來，而不是根據實際問題需要自適應調節算子的大小，使得算法在演化過程中的收斂性、穩定性及解的多樣性不理想。

針對固定的遺傳算子不利于演化進行的問題，自適應調節遺傳算子是解決這個問題的有效辦法。

1.2 線性自適應遺傳算法

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

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

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

1.3 余弦自適應遺傳算法

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

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

圖1 CAGA自適應交叉變異調整曲線

圖2是CAGA與LAGA調整曲線對比圖，在CAGA中，Pcmax和Pcmin之間的差值很小，且小于等于 1，Pmmax和Pmmin同樣如此。 在圖 2 中，|Δf|（favg和fmax之間的差值）變化很大，不同優化問題之間也存在區別。當|Δf|很大時，余弦和線性曲線十分接近，說明在一定程度上兩者的性能相當，同樣有停滯不前的現象。

圖2 CAGA與LAGA調整曲線對比圖

在文獻[5]中提出的自適應調節公式中，雖然也提到用Logistic曲線對算子進行改進，但在用種群相似度控制變異率時，對進化后期基因層次上的多樣性改進不夠，變異率偏大會破壞種群中的優良模式。

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

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

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

2.1 算法改進

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

圖3為 Logistic函數曲線圖，可以看出（a＞0），該曲線（比余弦）變化更加細膩。當ax≥9.903 438時，y接近1；當 ax＜-9.903 438 時，y接近 0。 式(9)和式(10)是用該曲線求解優化問題的調節公式（交叉率和變異率），其中a=9.903 438。圖4和圖5分別是LOAGA的自適應調整曲線（交叉率和變異率）。

圖3 Logistic函數曲線圖

圖4 交叉率自適應調節曲線

圖5 變異率自適應調節曲線

從改進公式知，當種群開始進化時，LOAGA調整的變異率比余弦函數小，保持種群的優良模式。當favg與fmax接近并且大部分個體的適應度值相近時，大多數個體的Pc和 Pm變大，且高于余弦函數調整的幅度(圖6中a點)。同時，在接近 fmax時，低于余弦函數調整的幅度(如圖 6中b點)，盡可能保留了fmax附近個體的優良模式。在圖6的曲線變化趨勢上，滿足算法進化過程中對不同階段的側重（搜索空間上、個體和基因層次上的多樣性以及算法后期的收斂方面）。

圖6 LAGA和LOAGA中自適應交叉率、變異率調整

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

2.2 算法流程

改進的自適應算法實現步驟如下：

(1)種群初始化，二進制編碼；

(2)計算適應度值；

圖7 LAGA、CAGA、LOAGA自適應調整曲線對比

(3)根據favg和即將進行交叉及變異操作個體的適應度值，結合自適應調節公式得出Pc和Pm，并進行交叉、變異操作；

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

圖8 LOAGA算法流程圖

3 實驗驗證

3.1 算法參數選擇

3.1.1 選取函數

通過對比 LOAGA、CAGA、LAGA實驗后的數據，來驗證改進算法的性能（收斂性和穩定性）。選以下兩種函數進行試驗。

理論最大值是1，收斂值是0.999 9。

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

3.1.2 算法參數

Pcmax=0.8，Pcmin=0.5，Pmmin=0.05，Pmmax=0.005，f1的 進化代數是 150代，f2為 500代，各運行 20次，取均值。

3.2 算法評價

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

算法進化的核心是Pc和Pm。整個搜索空間的覆蓋程度由Pc控制，用來尋找最優解存在的區域；為保證算法具有全局收斂性，變異算子的作用就是使算法能搜索到解空間中的每一點。文章中在進化的初期提高交叉率（提高搜索空間的覆蓋程度），壓低變異率（保存原始種群的優良模式）；在中期朝最大適應度進化時拉高交叉（提高提高搜索空間的覆蓋程度）和變異算子（使種群有足夠基因層次上的多樣性）及接近最大適應度時壓低兩個算子（保存優良模式，收斂），使算法不斷進化，盡量避免局部最優解。從表1的數據可以看出，隨著種群規模增大，各自的收斂速度變慢（搜索空間變大），LOAGA的收斂速度比CAGA和LAGA的收斂速度慢，但在收斂代數上LOAGA增加的比CAGA和LAGA少（快速找到優良解），不僅在favg上高于LAGA，其收斂速度也比前兩者快，所以，文章中提出的算法有較快的收斂速度。

表1 算法改進數據比較（均取計算20次結果的平均值）

影響解的多樣性有交叉操作產生的個體多樣性、變異操作產生的基因多樣性及允許父代參與當代競爭的復制方式等因素，文章通過改善交叉率、變異率，增強種群個體和基因層次上的多樣性來優化解的多樣性，提高解的質量。從表1的數據可以看出隨著種群規模的增大，收斂代數增加（搜索空間變大），但LOAGA的收斂值要比CAGA和LAGA的更加接近理想值，（而且增加的收斂代數比CAGA要少，改進后的算法能更快找到優良解），說明提出的算法有更多的優良解。

從表1知，f2函數LOAGA的收斂總次數比其他兩種要多（快速找到優良解），說明其穩定性好。

4 總結

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

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

[2]黃樟燦，李煒.有界區域上多峰函數全局優化問題的改進演化算法[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]石山.基于自適應遺傳算法的無刷直流電機的優化設計[J].西安交通大學學報，2002，36(12)：1215-1218.

[5]趙越，徐鑫.自適應記憶遺傳算法研究[J].計算機技術與發展，2014，24（2）：63-66.

[6]王凌.智能優化算法及其應用[M].北京：清華大學出版社，2000：36-50.

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

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

[9]雷秀娟.群智能優化算法及其應用[M].北京：科學出版社，2012：70-74.

[10]王小平，曹立明.遺傳算法:理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.