基于離散變量自適應遺傳算法的改進

呂秀芹

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

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

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

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

1 自適應遺傳算法

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

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

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

2 自適應遺傳算法的改進

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

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

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

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

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

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

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

3 算法性能驗證

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

4 結論

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

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

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

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

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