基于生物入侵思想的自適應(yīng)遺傳算法優(yōu)化

簡靜芳

(漳州職業(yè)技術(shù)學院 計算機工程系, 福建 漳州 363000)

美國密歇根大學J.H.Holland提出的遺傳算法(Genetic Algorithm，GA)是借鑒生物進化論，模擬生物界自然選擇和遺傳變異機制來求解復雜問題的隨機化搜索和優(yōu)化算法[1]，具有自適應(yīng)尋優(yōu)、智能搜索且收斂性好等特點，能有效解決組卷中的約束優(yōu)化問題，被廣泛應(yīng)用于智能組卷過程中[2-3]。

標準遺傳算法(SGA)采用固定的交叉和變異概率，在搜索更優(yōu)解的過程中將使種群的多樣性降低，從而導致算法停滯不前，使得算法只能搜索到局部最優(yōu)解，因此造成算法早收斂現(xiàn)象及收斂速度慢等問題[4]。

為了解決早收斂問題，目前許多學者進行深入研究，大體上提出3種改進方法：小生境技術(shù)、自適應(yīng)遺傳算法和混合遺傳算法[5]。小生境技術(shù)注重保持種群多樣性，但并沒有產(chǎn)生群體多樣性，雖然對算法有一定地改進，但不能從根本上解決早收斂問題?；旌线z傳算法在算法復雜度和計算量方面耗費較大，所以也非優(yōu)選算法。此外Srinvas等人[6]提出自適應(yīng)遺傳算法(Adaptive GA，AGA),有效地提高了遺傳算法的收斂速度，在一定程度上預(yù)防了早收斂現(xiàn)象，但是由于該算法對較優(yōu)個體進行保護，易使算法陷入局部最優(yōu)，依然不能有效解決早收斂問題[7]。

在這里我們將生物入侵思想引入自適應(yīng)遺傳算法優(yōu)化中，提出基于生物入侵思想的自適應(yīng)遺傳算法(Improved Adaptive Genetic Algorithm based on biological Invasion，IIAGA)，在較大程度上能比較好地解決早收斂現(xiàn)象。

1 早收斂現(xiàn)象分析及應(yīng)對

1.1 早收斂現(xiàn)象分析

早收斂現(xiàn)象是指算法在搜索到最優(yōu)解之前便收斂于局部最優(yōu)解，即出現(xiàn)早熟現(xiàn)象，最終的最優(yōu)個體適應(yīng)度小于實際最優(yōu)個體適應(yīng)度。

由于現(xiàn)實條件制約，種群規(guī)模有限且一般保持一定，遺傳算法的選擇操作會保護優(yōu)秀個體，使種群多樣性降低，而種群多樣性越小，則越不可能產(chǎn)生更優(yōu)子代，將導致算法停滯，因此可能只搜索到局部最優(yōu)解，從而引起早收斂現(xiàn)象。由此可見，算法的早收斂與種群的多樣性有直接的關(guān)系，要解決早收斂現(xiàn)象，就是盡可能保證種群的多樣性[5]。

1.2 早收斂現(xiàn)象的應(yīng)對

遺傳算法存在一個比較矛盾的問題:為保證能全局收斂、避免早收斂，必須要保證種群個體的多樣性；然而，為了使算法擁有較快的收斂速度，又必須保證種群中的個體盡快靠近最優(yōu)解，因而不可避免地在一定程度上降低種群多樣性。因此想要有效地解決早收斂現(xiàn)象就要考慮保持群體多樣性與收斂速度的平衡，只有綜合考慮這兩個方面提出的應(yīng)對早收斂措施，才能起到真正的優(yōu)化作用[8]。

本文提出的IIAGA，就是綜合考慮了多樣性和收斂速度的平衡，盡可能從根本上解決早收斂現(xiàn)象，保證收斂速度，優(yōu)化提高遺傳算法的性能[9]。

2 基于生物入侵思想的自適應(yīng)遺傳算法

IIAGA主要通過兩個方面解決多樣性和收斂速度平衡問題：首先，根據(jù)種群的實際情況對AGA交叉和變異概率進行非線性化調(diào)整，有效地保證種群的多樣性；其次，利用生物入侵思想，用新生個體替換較差個體，并通過控制入侵概率，以保證算法的收斂速度。

2.1 非線性化調(diào)整AGA交叉和變異概率

遺傳算法中控制參數(shù)的設(shè)置直接影響系統(tǒng)性能，這些參數(shù)主要包括交叉概率Pc、變異概率Pm及種群規(guī)模。當Pc、Pm增大，算法新空間搜索能力增強，越能探測到優(yōu)良個體,但容易破壞較優(yōu)個體，影響收斂速度；Pc、Pm減小，算法的開發(fā)能力增強，保持較優(yōu)個體能力增強，但是種群的多樣性降低，易出現(xiàn)早收斂，因此選擇合適的Pc、Pm值直接影響遺傳算法的收斂性[10]。在SGA中，一般取0.4≤Pc≤0.99，0.001≤Pm≤0.1。 固定的Pc、Pm容易引起早收斂，為獲得算法更好的性能，一般根據(jù)算法的實際情況動態(tài)地調(diào)整Pc、Pm參數(shù)。

2.1.1 傳統(tǒng) AGA中交叉和變異概率

在Srinvas等人的傳統(tǒng)AGA中，對Pc、Pm進行線性自適應(yīng)調(diào)整，使Pc、Pm能根據(jù)適應(yīng)度值的變化動態(tài)調(diào)整，如公式(1)和公式(2)所示。k1、k2、k3、k4∈(0，1)，fmax為最大適應(yīng)度值，f′為要交叉的兩個體中取值較大的適應(yīng)度值，favg為平均適應(yīng)度值，f為要變異個體適應(yīng)度值[11]：

(1)

(2)

在遺傳算法中，我們一般用適應(yīng)度分布的離散程度來衡量種群中個體的多樣性程度，當種群的個體適應(yīng)度值趨于一致或局部最優(yōu)時，為避免早收斂，跳出局部最優(yōu)，要增加種群的多樣性，從公式(1)、(2)中可見，此時favg靠近fmax，fmax-favg取值較小，會自適應(yīng)調(diào)整Pc、Pm值變大，達到預(yù)期效果；而當種群個體的適應(yīng)度值比較分散時，需要使種群中的個體盡快靠近最優(yōu)解，以便加快收斂速度，此時fmax-favg取值較大，將調(diào)整Pc、Pm值變小。從理論上可見，這種改進方法在一定程序上解決了多樣性和收斂速度平衡問題，但它們存在一些突出的缺限。

首先，在進化初期，fmax并沒有達到全局最優(yōu)解，而如果此時f或f′達到fmax時，fmax-f′=0和fmax-f=0，因此Pc、Pm均為0，此時算法對最優(yōu)個體進行保護，較優(yōu)個體基本上處于不變化的狀態(tài)，算法停滯，使算法陷入局部最優(yōu)，從而使算法出現(xiàn)早收斂現(xiàn)象。此外，算法進化過程中，Pc、Pm值直接是由個體適應(yīng)度值f或f′進行調(diào)整的，缺乏全局性，因此當算法陷入局部最優(yōu)時，很難跳出，使算法直接陷入早收斂。

2.1.2 IAGA(改進的AGA算法)中交叉和變異概率

IAGA將favg-fmax作為評價種群早收斂程度的重要指標，直接用favg-fmax值對Pc、Pm進行非線性自適應(yīng)調(diào)節(jié)，如公式(3)、公式(4)所示，式中k1、k2均大于0，且根據(jù)算法需要進行取值：

(3)

(4)

在算法進化過程中，favg-fmax≤0，所以Pc∈[0.5，1],Pm∈[0，0.5], 當種群的個體適應(yīng)度值趨于一致或局部最優(yōu)時，favg靠近fmax，favg-fmax取值較大，Pc將變小，Pm將變大，在一定程度上增強種群的多樣性，避免早收斂現(xiàn)象；而當種群個體的適應(yīng)度值比較分散時，favg-fmax取值較小，Pc將變大，Pm變小，在一定程度上增強生成優(yōu)良個體的能力，加快收斂速度。

在實際算法的進化過程中，早收斂現(xiàn)象主要表現(xiàn)在種群內(nèi)適應(yīng)度值暫時最大的那些個體的趨同程度，所以在算法中要考慮計算favg-fmax時一些較差個體將直接影響favg值，從而影響favg-fmax值，因此可以排除這些較差個體的影響，用favg′來替代favg，favg′表示將個體適應(yīng)度值大于favg的先求和后再取平均值，這樣能更好表現(xiàn)適應(yīng)度較優(yōu)的個體間的趨同程度，準確地體現(xiàn)個體的早收斂程度，因此IAGA由公式(5)、(6)調(diào)整Pc、Pm值：

(5)

(6)

2.2 生物入侵優(yōu)化算法

在生物界，生物入侵是一種常見現(xiàn)象，即外來生物在人為因素或自然因素作用下，遷徙到異地，當該物種適應(yīng)當?shù)丨h(huán)境并生長繁殖時，將對當?shù)氐纳锘颦h(huán)境產(chǎn)生影響。我們在優(yōu)化算法時，將生物入侵的思想引入遺傳算法中，目的就是使新生個體代替原來適應(yīng)度較差的個體，為種群注入新的個體，增加種群的多樣性，使得在很大程度上預(yù)防早收斂現(xiàn)象。但是，也不能無限制地增加新生個體數(shù)量。我們引入入入侵率Pr，即入侵的新個體數(shù)量占種群規(guī)模的比例。入侵率越大，表明更新的染色體基因越多，將導致較優(yōu)個體被破壞，影響收斂速度。入侵率越低，表明種群中新生個體越少，越易導致早收斂的發(fā)生[12]。我們圍繞保持群體多樣性與收斂速度的平衡這一問題進行算法改進，在此表現(xiàn)為合理地控制入侵率Pr,如公式(7)所示，以保證算法的平衡：

(7)

其中k3>0,favg′-fmax≤0，所以Pr∈[0，0.5]。當種群適應(yīng)度值趨于早收斂時，要增加種群的多樣性，favg′-fmax取值較大，Pr變大，即入侵率變大，防止早收斂；當種群適應(yīng)度值趨于離散時，favg′-fmax取值較小，Pr變小，將會保持優(yōu)良個體，保證收斂速度?？梢?，引入Pr能有效地平衡保持群體多樣性與收斂速度這兩個方面，很大程度上改善遺傳算法的性能。

3 仿真驗證

為了驗證IIAGA全局收斂性和收斂速度等方面的性能，我們用一個多峰值測試函數(shù)f(x)=xsin(10πx)+2.0,x∈[-1，2]在MATLAB中進行仿真驗證，并與SGA、AGA、IAGA等仿真曲線進行對比，驗證算法的性能優(yōu)劣。函數(shù)f(x)全局收斂于3.850 3，我們對4種遺傳算法均選用二進制編碼，種群規(guī)模設(shè)定為40，編碼長度為10，選用比例選擇操作，同時采用單點交叉和單點變異，并設(shè)置最大進化代數(shù)200作為算法的結(jié)束條件。此外SGA中交叉概率Pc為0.7，變異概率Pm為0.1，在AGA中選擇k1=k2=0.7,k3=k4=0.1,IAGA中設(shè)置k1=0.5,k2=1,IIAGA中取k1=0.5,k2=1,k3=1，在MATLAB中進行算法仿真，仿真結(jié)果如圖1—5所示。

圖1 IIAGA最佳和平均適應(yīng)度曲線 圖2 SGA和IIAGA平均適應(yīng)度曲線

圖3 AGA和IIAGA平均適應(yīng)度曲線 圖4 IAGA和IIAGA平均適應(yīng)度曲線

圖5 SGA、AGA、IAGA和IIAGA最佳適應(yīng)度曲線

其中圖1為IIAGA在進化過程中的最佳適應(yīng)度曲線和平均適應(yīng)度曲線?？梢钥闯?，兩曲線相互趨同，且收斂于極大值處，表明算法收斂得很順利，并沒有陷入早收斂狀態(tài)，保證種群的多樣性，同時收斂速度也比較快，說明算法能滿足我們既定的要求。

接著對另外幾種算法進行比較，圖2是SGA與IIAGA平均適應(yīng)度曲線比較。從曲線中可以看出IIAGA的平均適應(yīng)度值明顯較高，說明IIAGA的種群個體優(yōu)于SGA，同時IIAGA在穩(wěn)定性方面及收斂速度方面明顯優(yōu)于SGA。

圖3為AGA與IIAGA平均適應(yīng)度曲線比較。AGA在曲線上的表現(xiàn)優(yōu)于圖2中的SGA，雖然在收斂速度上和IIAGA相差不多，但是AGA的平均適應(yīng)度值總體低于IIAGA曲線，即IIAGA擁有更優(yōu)秀的個體。

圖4所示為IAGA與IIAGA平均適應(yīng)度曲線比較。IAGA平均適應(yīng)度值大體與IIAGA趨同，但穩(wěn)定性方面較差，同時收斂速度上也差于IIAGA，由此可見IIAGA在性能上相較于其它遺傳算法都有所改善，顯示IIAGA的可行性。

圖5為SGA、AGA、IAGA和IIAGA最佳適應(yīng)度曲線。從圖中可以看出，AGA和SGA在算法開始時，陷入局部最大適應(yīng)度值，在曲線上表現(xiàn)為出現(xiàn)一定時間上的停滯，進化多代后才最終收斂于全局最大適應(yīng)度值，即兩者均出現(xiàn)不同程度的早收斂現(xiàn)象，其中SGA情況比AGA來得嚴重些，AGA的收斂速度優(yōu)于SGA。IIAGA和IAGA最佳適應(yīng)度曲線明顯優(yōu)于SGA、AGA，尤其表現(xiàn)在收斂性方面，IIAGA和IAGA能較快地收斂于全局最大適應(yīng)度值。但從圖中也可以發(fā)現(xiàn)IAGA在曲線穩(wěn)定性方面不如IIAGA，在算法開始的一小段時間內(nèi)，出現(xiàn)小幅度的振蕩，且并非在全局極大值處，即出現(xiàn)早收斂傾向，雖然最后還是收斂于全局極大值處，但在收斂速度方面受一定的影響，由此也可以驗證出IIAGA的優(yōu)勢，它能有效地保證種群的多樣性，即防止出現(xiàn)早收斂，同時還能保證收斂速度，且具有較好的穩(wěn)定性。

4 結(jié) 語

從上述結(jié)果可以看出，改進的IIAGA在平衡種群多樣及收斂速度上有明顯的效果，有效地防止早收斂現(xiàn)象，可以進一步應(yīng)用于智能組卷過程中，同時可以通過對k1、k2、k3進行進一步的選擇，使算法具有更好的性能。

[參考文獻]

[1] 耿輝，武妍.基于動態(tài)入侵的自適應(yīng)遺傳算法研究[J].計算機工程與應(yīng)用，2011,47(7):40-42.

[2] 薛清龍，李郴.自動組卷策略中遺傳算法的優(yōu)化[J].電腦編程技巧與維護,2010(6):50-52.

[3] 李軍.基于遺傳算法的智能組卷系統(tǒng)研究[D].天津:天津大學，2008.

[4] 張宇，郭晶，周激流.動態(tài)變異遺傳算法[J].電子科技大學學報，2002,31(3):234-239.

[5] 趙苓.基于遺傳算法的智能組卷策略的研究[D].哈爾濱:哈爾濱工程大學，2012.

[6] SRINVAS M ,PATNAIK L M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Transactions on Systems,Man and Cybernetics,1994,24(4):656-667.

[7] 金晶，蘇勇.一種改進的自適應(yīng)遺傳算法[J].計算機工程與應(yīng)用,2005(18):65-69.

[8] 吳浩揚，朱長純，常炳國，等.基于種群過早收斂程度定量分析的改進自適應(yīng)遺傳算法[J].西安交通大學學報，1999,33(11):27-30.

[9] 王淑佩.基于改進的遺傳算法組卷系統(tǒng)應(yīng)用研究[D].湖南:湖南大學，2005.

[10] 劉懷蘭，牛輝，王佳.基于改進遺傳算法的智能組卷模型優(yōu)化[J].華中科技大學學報：自然科學版，2013,41(5):82-85.

[11] 張開便，李喜艷，董振華.一種自適應(yīng)遺傳算法在自動組卷中的應(yīng)用[J].福建電腦，2013(4):119-121.

[12] 潘曉輝.在線考試系統(tǒng)中組卷技術(shù)的研究[J].價值工程，2010(14):159-161.