基于離散變量自適應(yīng)遺傳算法的改進(jìn)

呂秀芹

（江蘇農(nóng)林職業(yè)技術(shù)學(xué)院，江蘇句容 212400）

遺傳算法(Genetic Algorithm，GA)是一種基于模擬自然界生物遺傳演化規(guī)律的隨機(jī)探索和優(yōu)化算法[1]。算法將問題對象進(jìn)行編碼，形成類似生物學(xué)上的染色體，通過對染色體的遺傳進(jìn)化，從而得到問題的優(yōu)化解。算法能有效地處理大量離散參數(shù)，在求解之初可以采取一些方法使得初始種群在解空間合理分散，并且通過基因交叉和變異操作，增加了全局尋優(yōu)的能力。遺傳算法目前已廣泛地應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、自動(dòng)控制、圖像處理、生產(chǎn)調(diào)度等多個(gè)行業(yè)。

算法的基本運(yùn)算過程[2]為：將問題對象以二進(jìn)制或?qū)崝?shù)等形式進(jìn)行編碼，把問題的單個(gè)可行解看成是一個(gè)符號(hào)串，從而形成類似生物學(xué)上的染色體或個(gè)體。然后隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)，用已設(shè)計(jì)好的適應(yīng)度函數(shù)計(jì)算當(dāng)前群體中每個(gè)染色體的適應(yīng)度值，系統(tǒng)根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇新的染色體，使用選擇算子將適應(yīng)度高的染色體選擇進(jìn)入下一代，然后再利用這些已選擇的染色體進(jìn)行交叉、變異等操作，產(chǎn)生出代表新的解集的群體P(t)。上述生成新群體P(t)的過程不斷重復(fù)，直到找到問題的解滿足用戶的要求為止。由于交叉、變異后產(chǎn)生的新種群與其父種群相比，更能適應(yīng)于環(huán)境，當(dāng)算法結(jié)束后，將末代種群中包含的最優(yōu)個(gè)體進(jìn)行解碼即可得到問題的較優(yōu)解。

遺傳算法通過計(jì)算比較個(gè)體染色體的適應(yīng)度與群體平均適應(yīng)度決定該個(gè)體進(jìn)化或淘汰，但進(jìn)化到了后期，算法搜索到最優(yōu)解附近時(shí)，要確定最優(yōu)解要花費(fèi)大量時(shí)間，甚至無法精確定位最優(yōu)解的位置，且算法容易出現(xiàn)“早熟”。針對算法的這些缺點(diǎn)，有不少學(xué)者在遺傳算子的改進(jìn)方面做了不少研究并取得了豐碩的成果，引入了自適應(yīng)策略改善遺傳的性能。

1 自適應(yīng)遺傳算法

遺傳算法中遺傳算子影響進(jìn)化的進(jìn)行，其中交叉概率Pc和變異概率Pm對種群的優(yōu)化起著決定性的作用。交叉概率和變異概率大，則新個(gè)體產(chǎn)生的速度快，有利于保持種群的多樣性，但過大又會(huì)使優(yōu)選出的個(gè)體被壞，不利于選擇算子的作用。交叉概率和變異概率過小，容易產(chǎn)生局部收斂，算法出現(xiàn)早熟。遺傳算法按照優(yōu)勝劣汰的規(guī)則,將適應(yīng)度較高的個(gè)體更多地遺傳到下一代，算法使得種群后期的適應(yīng)度要高于初期的適應(yīng)度。Srinvivas等提出根據(jù)種群進(jìn)化程度自適應(yīng)遺傳算法的策略，即算法根據(jù)種群的適應(yīng)度動(dòng)態(tài)調(diào)整交叉概率Pc和變異概率Pm，具體見公式1和公式2。算法的基本思想是：對于適應(yīng)度高于群體平均適應(yīng)度的個(gè)體，取較小的交叉概率Pc和變異概率Pm，使得該解得以保護(hù)進(jìn)入下一代；對于適應(yīng)度低于群體平均適應(yīng)度的個(gè)體，取較大的交叉概率Pc和變異概率Pm，使該解被淘汰[2]。

其中fmax為群體中最大的適應(yīng)度值；fave為群體的平均適應(yīng)值；f′為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f為要變異個(gè)體的適應(yīng)度值；k1，k2，k3，k4取值在[0，1]區(qū)間，根據(jù)不同的問題特征，可根據(jù)實(shí)驗(yàn)或經(jīng)驗(yàn)確定其值的大小。

可以看出，當(dāng)個(gè)體的適應(yīng)度值大于平均適應(yīng)度值時(shí)，交叉概率Pc和變異概率Pm隨著個(gè)體的適應(yīng)度增大呈線性遞減。當(dāng)適應(yīng)度越接近最大適應(yīng)度時(shí)，即當(dāng)前解越接近最優(yōu)解，交叉概率和變異概率越小；當(dāng)個(gè)體的適應(yīng)度值接近或等于最大適應(yīng)度值時(shí)，交叉概率和變異概率接近或等于零，算法停止收斂操作，將當(dāng)前個(gè)體作為最優(yōu)解[3]。上述的自適應(yīng)過程在算法執(zhí)行到后期有很好的收斂效果，但在算法運(yùn)行的初期，由于此時(shí)的種群可能集中在解集的某個(gè)區(qū)域，優(yōu)良個(gè)體可能是某一個(gè)區(qū)域的相對優(yōu)解，而不是全局的最優(yōu)解。因此，上述的自適應(yīng)算法在進(jìn)化初期容易產(chǎn)生局部收斂，產(chǎn)生“早熟”。

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

在進(jìn)化初期，為了保持種群的多樣性，應(yīng)增加種群的交叉和變異操作。隨著遺傳算法進(jìn)化過程的進(jìn)行，群體中適應(yīng)度較低的一些個(gè)體被逐漸淘汰掉，而適應(yīng)度較高的一些個(gè)體會(huì)越來越多，種群已經(jīng)接近最優(yōu)解。為了使種群的一些好的特性不被破壞，此時(shí)的交叉和變異操作應(yīng)降低。在進(jìn)化后期，個(gè)體間的相似度增加，容易過早的收斂，此時(shí)應(yīng)適當(dāng)增加變異概率[4]。對于離散變量，初始種群一般以一定的方法盡量分散在解集中，其離散程度較大，進(jìn)化若干代后，新的個(gè)體已經(jīng)接近最優(yōu)解，其離散程度明顯減小。本文設(shè)計(jì)根據(jù)個(gè)體的離散程度來送別其進(jìn)化的程度，從而得到不同的遺傳概率。

考慮到種群在不斷的進(jìn)化，交叉和變異操作不能盲目進(jìn)行，相互之間應(yīng)配合進(jìn)行。本文對上述的自適應(yīng)過程進(jìn)行人工干預(yù)，引入兩個(gè)概率系數(shù)c和m分別影響交叉概率和變異概率的取值，從而有效防止其在進(jìn)化初期陷入局部尋優(yōu)，具體見公式(3)和公式(4)。

其中c，m為分別為交叉概率系數(shù)和遺傳概率系數(shù)，且c≤1，m≤1，其余參數(shù)含義同上。

隨著迭代進(jìn)化的進(jìn)行，每一代種群中個(gè)體適應(yīng)度值的差異是不同的，概率系數(shù)c和m隨著進(jìn)化的進(jìn)行而變化的。在進(jìn)化初期，種群的個(gè)體差異大，各染色體之間的適應(yīng)度差別也較大，為了增加種群的多樣性，實(shí)現(xiàn)全局收斂性，此時(shí)c和m均取較大值，即交叉概率和變異概率取較大值，以加快進(jìn)化的速度。隨著進(jìn)化的發(fā)展，此時(shí)的解已經(jīng)接近取優(yōu)解的雛形，為了保讓優(yōu)質(zhì)個(gè)體被選擇復(fù)制到下一代遺傳，c和m的取值均應(yīng)適當(dāng)降低。到了進(jìn)化的后期，種群中個(gè)體的適應(yīng)度差別變小，交叉概率進(jìn)一步變小，進(jìn)化速度變慢，易陷入局部最優(yōu)，此時(shí)應(yīng)適當(dāng)增加變異操作，避免進(jìn)入種群“早熟”。

給概率系數(shù)c和m取值前，首先要判斷種群的進(jìn)化程度，本文根據(jù)種群的離散程度系數(shù)Df和平均適應(yīng)度與最優(yōu)適應(yīng)度之間的差值系數(shù)Dv進(jìn)行衡量。離散程度以種群中個(gè)體的適應(yīng)度的均方差表示，具體見公式(5)和公式(6)。

其中，Df為離散程度系數(shù)，Dv為平均適應(yīng)度與最優(yōu)適應(yīng)度之間的差值；N為種群規(guī)模，ffit為系統(tǒng)設(shè)置的目標(biāo)最優(yōu)適應(yīng)度，fi為種群中個(gè)體的適應(yīng)度值。Df反映的是當(dāng)前種群中個(gè)體間適應(yīng)度的相似程度的大小。在進(jìn)化初期，個(gè)體間離散大，其適應(yīng)度值差異大，Df和Dv的值較大。進(jìn)化到后期，個(gè)體接近最優(yōu)解，種群中個(gè)體的相似度增大，Df和Dv的值較小。具體操作時(shí)，綜合這兩個(gè)系數(shù)衡量種群進(jìn)化程度，引入進(jìn)化程度系數(shù)D，令D=Df+Dv。通過比較D與第一代種群進(jìn)化系數(shù)Df1的關(guān)系，從而得到當(dāng)前種群的進(jìn)化程度，以決定概率系數(shù)c和m的值，函數(shù)公式如下：

由于進(jìn)化過程不斷進(jìn)行，在進(jìn)化初期，種群的進(jìn)化程度系數(shù)接近Df1；；到最化后期，個(gè)體接近最優(yōu)解，故進(jìn)化系數(shù)接近0，故上面的公式中進(jìn)化系數(shù)D在(0,Df1)間取值。對于不同特征的問題，c和m的值會(huì)有變化，本文以典型的離散問題——組卷問題為例，給出c和m的分段取值。可以看出，函數(shù)依據(jù)進(jìn)化系數(shù)判斷進(jìn)化的程度，從而決定概率系數(shù)c和m的不同取值，得到不同進(jìn)化時(shí)期的交叉概率和變異概率，可以很好地控制進(jìn)化過程，提高算法的性能。

3 算法性能驗(yàn)證

為了驗(yàn)證算法經(jīng)過改進(jìn)后其執(zhí)行的效率和效果，本文應(yīng)用改進(jìn)前后的算法進(jìn)行組卷試驗(yàn)。試驗(yàn)題庫包括600道題目，其中單選題300道，多選題100道，判斷題200道，按各種題型采用分段實(shí)數(shù)編碼的方案，設(shè)定知識(shí)點(diǎn)覆蓋率、難度系數(shù)、各題型題量等要求。使用Visual Studio.net提供的C#語言進(jìn)行編程設(shè)計(jì)，程序在Xeon E5506 2.13GHZ，4GBDDR3，WindowServer2003環(huán)境下執(zhí)行。通過設(shè)定不同的初始種群規(guī)模和最大迭代次進(jìn)行組卷試驗(yàn)，結(jié)果表明，算法經(jīng)改進(jìn)后在不同的遺傳代數(shù)其最優(yōu)個(gè)體的適應(yīng)度明顯高于改進(jìn)前，提高了組卷成功率，降低了組卷時(shí)間。

4 結(jié)論

本文基于遺傳算法進(jìn)化的特征，結(jié)合自適應(yīng)遺傳算法提出的自動(dòng)調(diào)整交叉概率和遺傳概率的理念，提出判斷每代個(gè)體的進(jìn)化程度的方法，設(shè)計(jì)根據(jù)進(jìn)化程度賦予個(gè)體的不同的交叉概率系數(shù)和遺傳概率系數(shù)，從而得到不同進(jìn)化時(shí)期的交叉概率和遺傳概率，對個(gè)體的遺傳進(jìn)行進(jìn)化，實(shí)現(xiàn)算法的快速收斂，并避免了“早熟”現(xiàn)象。將算法用于處理典型的離散問題——組卷問題，算法性能有了較大的提高，其收斂速度明顯加快，組卷的成功率也有了提高。

[1]陳曉東,王宏宇.一種基于改進(jìn)遺傳算法的組卷算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2005(9):1174-1175.

[2]張京釗,江濤.改進(jìn)的自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2010(46):54.

[3]張國強(qiáng),彭曉明.自適應(yīng)遺傳算法的改進(jìn)與實(shí)現(xiàn)[J].船舶電子工程,2010(1):83-84.

[4]盧長娜,王如云,陳耀登.自適應(yīng)遺傳算法[J].計(jì)算機(jī)仿真,2006(1):172-175.