簡靜芳

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

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

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

為了解決早收斂問題，目前許多學(xué)者進(jìn)行深入研究，大體上提出3種改進(jìn)方法：小生境技術(shù)、自適應(yīng)遺傳算法和混合遺傳算法[5]。小生境技術(shù)注重保持種群多樣性，但并沒有產(chǎn)生群體多樣性，雖然對算法有一定地改進(jìn)，但不能從根本上解決早收斂問題。混合遺傳算法在算法復(fù)雜度和計算量方面耗費較大，所以也非優(yōu)選算法。此外Srinvas等人[6]提出自適應(yīng)遺傳算法(Adaptive GA，AGA),有效地提高了遺傳算法的收斂速度，在一定程度上預(yù)防了早收斂現(xiàn)象，但是由于該算法對較優(yōu)個體進(jìn)行保護(hù)，易使算法陷入局部最優(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ī)模有限且一般保持一定，遺傳算法的選擇操作會保護(hù)優(yōu)秀個體，使種群多樣性降低，而種群多樣性越小，則越不可能產(chǎn)生更優(yōu)子代，將導(dǎo)致算法停滯，因此可能只搜索到局部最優(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交叉和變異概率進(jìn)行非線性化調(diào)整，有效地保證種群的多樣性；其次，利用生物入侵思想，用新生個體替換較差個體，并通過控制入侵概率，以保證算法的收斂速度。

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

遺傳算法中控制參數(shù)的設(shè)置直接影響系統(tǒng)性能，這些參數(shù)主要包括交叉概率Pc、變異概率Pm及種群規(guī)模。當(dāng)Pc、Pm增大，算法新空間搜索能力增強(qiáng)，越能探測到優(yōu)良個體,但容易破壞較優(yōu)個體，影響收斂速度；Pc、Pm減小，算法的開發(fā)能力增強(qiáng)，保持較優(yōu)個體能力增強(qiáng)，但是種群的多樣性降低，易出現(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進(jìn)行線性自適應(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)度分布的離散程度來衡量種群中個體的多樣性程度，當(dāng)種群的個體適應(yīng)度值趨于一致或局部最優(yōu)時，為避免早收斂，跳出局部最優(yōu)，要增加種群的多樣性，從公式(1)、(2)中可見，此時favg靠近fmax，fmax-favg取值較小，會自適應(yīng)調(diào)整Pc、Pm值變大，達(dá)到預(yù)期效果；而當(dāng)種群個體的適應(yīng)度值比較分散時，需要使種群中的個體盡快靠近最優(yōu)解，以便加快收斂速度，此時fmax-favg取值較大，將調(diào)整Pc、Pm值變小。從理論上可見，這種改進(jìn)方法在一定程序上解決了多樣性和收斂速度平衡問題，但它們存在一些突出的缺限。

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

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

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

(3)

(4)

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

在實際算法的進(jìn)化過程中，早收斂現(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)的個體間的趨同程度，準(zhǔn)確地體現(xiàn)個體的早收斂程度，因此IAGA由公式(5)、(6)調(diào)整Pc、Pm值：

(5)

(6)

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

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

(7)

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

3 仿真驗證

為了驗證IIAGA全局收斂性和收斂速度等方面的性能，我們用一個多峰值測試函數(shù)f(x)=xsin(10πx)+2.0,x∈[-1，2]在MATLAB中進(jìn)行仿真驗證，并與SGA、AGA、IAGA等仿真曲線進(jìn)行對比，驗證算法的性能優(yōu)劣。函數(shù)f(x)全局收斂于3.850 3，我們對4種遺傳算法均選用二進(jìn)制編碼，種群規(guī)模設(shè)定為40，編碼長度為10，選用比例選擇操作，同時采用單點交叉和單點變異，并設(shè)置最大進(jìn)化代數(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中進(jìn)行算法仿真，仿真結(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在進(jìn)化過程中的最佳適應(yīng)度曲線和平均適應(yīng)度曲線?？梢钥闯?，兩曲線相互趨同，且收斂于極大值處，表明算法收斂得很順利，并沒有陷入早收斂狀態(tài)，保證種群的多樣性，同時收斂速度也比較快，說明算法能滿足我們既定的要求。

接著對另外幾種算法進(jìn)行比較，圖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)一定時間上的停滯，進(jìn)化多代后才最終收斂于全局最大適應(yīng)度值，即兩者均出現(xiàn)不同程度的早收斂現(xiàn)象，其中SGA情況比AGA來得嚴(yán)重些，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é)果可以看出，改進(jìn)的IIAGA在平衡種群多樣及收斂速度上有明顯的效果，有效地防止早收斂現(xiàn)象，可以進(jìn)一步應(yīng)用于智能組卷過程中，同時可以通過對k1、k2、k3進(jìn)行進(jìn)一步的選擇，使算法具有更好的性能。

[參考文獻(xiàn)]

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

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

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

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

[5] 趙苓.基于遺傳算法的智能組卷策略的研究[D].哈爾濱:哈爾濱工程大學(xué)，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] 金晶，蘇勇.一種改進(jìn)的自適應(yīng)遺傳算法[J].計算機(jī)工程與應(yīng)用,2005(18):65-69.

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

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

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

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

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