0 引言

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

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

1 算法分析

1.1 基本遺傳算法

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

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

    (2)評價個體適應(yīng)度；

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

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

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

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

1.2 線性自適應(yīng)遺傳算法

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

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

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

1.3 余弦自適應(yīng)遺傳算法

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

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

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

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

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

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

2 LO型曲線的自適應(yīng)遺傳算法改進(jìn)

2.1 算法改進(jìn)

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

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

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

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

2.2 算法流程

    改進(jìn)的自適應(yīng)算法實現(xiàn)步驟如下：

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

    (2)計算適應(yīng)度值；

    (3)根據(jù)f_avg和即將進(jìn)行交叉及變異操作個體的適應(yīng)度值，結(jié)合自適應(yīng)調(diào)節(jié)公式得出P_c和P_m，并進(jìn)行交叉、變異操作；

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

3 實驗驗證

3.1 算法參數(shù)選擇

3.1.1 選取函數(shù)

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

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

3.1.2 算法參數(shù)

    P_{c max}=0.8，P_{c min}=0.5，P_{m min}=0.05，P_{m max}=0.005，f₁的進(jìn)化代數(shù)是150代，f₂為500代，各運行20次，取均值。

3.2 算法評價

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)

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

[2] 黃樟燦，李煒.有界區(qū)域上多峰函數(shù)全局優(yōu)化問題的改進(jìn)演化算法[J].武漢大學(xué)學(xué)報(理學(xué)版)，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īng)遺傳算法的無刷直流電機的優(yōu)化設(shè)計[J].西安交通大學(xué)學(xué)報，2002，36(12)：1215-1218.

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

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

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

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

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

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