基于遺傳算法智能組卷方案的調整

謝志偉

引言：本文介紹了傳統遺傳算法的組卷方案，針對遺傳算法的“早熟”現象分析傳統遺傳算法組卷的缺點，并提出了改進方案，是對遺傳算子合理設置，通過實際組卷評估，此方案能大大減少組卷時間，并能組出較高質量的試卷，大大提高工作效率。

一、傳統遺傳算法

傳統遺傳算法是使用二進序列組合進行編碼的。有一個最初的編碼集合，我們稱為初始種群。在此基礎上，采用適應度函數進行策略選擇，使用交差和變異兩種操作來產生下一代種群，就這樣，一代一代的遺傳下去，直到出現滿足條件時候為止。

二、傳統遺傳算法“早熟”現象分析

隨著種群進化的不斷擴大，就會產生很多高適應度模式的個體，并且是呈指數冪次的速度遞增，這樣就會導致種群個體相應部位的基因趨于收斂，最終種群個體的多樣性就會受到影響。在理論上，遺傳算法的種群規模是不受限制的，上一代群體中的優秀模式一定能夠在下一代中，因此，隨著種群多樣性的減小，種群必然收斂到問題的最優解。但我們在實際應用中，由于時間、資源、種群規模等各種因素的制約，就不可避免的造成種群個體多樣性過早的趨于一致，會使搜索算法停滯不前，最終收斂于一個局部最優解，而無法收斂于全局最優解，這就是“早熟”現象。

“早熟”現象原因：

（1） 群體規模：當群體規模較小時，就會使群體中先天的等位基因不足，即便是人為的調整變異算子，生成具有較好的基因群體的幾率也會很小。隨著變異算子調整操作的加強，對群體中已有的優秀個體的破壞力也在增加。

（2） 選擇算子：如果選擇群體中最優個體的比例大的話，個體選擇壓力加強，導致群體的多樣性迅速降低，很快就保持一致，趨于收斂；相反，如果抽樣選擇當前群體中最優個體比例小的話，個體選擇壓力太小，模式競爭能力就會減小，遺傳算子重組生成優秀模式的能力降低，也會盡早的出現“早熟”現象。

（3） 變異算子：如果變異算子調整到比較小時，群體的多樣性就會大大減小，容易將優秀模式的基因丟失，并且是不可恢復；如果變異算子設置較大時，可以使群體多樣性保持在較高水平，但優秀模式被破壞的概率也會大大增大。

（4） 適應度函數：適應度函數如果保持高度非線性，染色體基因是高度相關，優秀模式更容易被破壞，多樣性迅速降低，很快就會趨于一致。

（5） 群體初始化：群體初始化時候要相對保持均勻，不要出現局部分布現象，這樣會導致局部收斂，很快的就會使個體趨于一致。

三、避免“早熟”現象發生的參數調整

（1） 合理初始化種群，做到分配均勻

種群初始初始化情況對遺傳算法的計算有著重大的影響，要做到全局最優，種群在解空間中應盡量的均勻分布。

具體方法是：

子空間分割是分別對m維變量在其可行解空間進行均勻分割得到n個變量子空間（n值的大小可以根據可行解空間的大小和計算的精度要求確定，考慮到計算效率，一般不宜過大）。對這m*n個變量子空間進行組合得到n^m個可行解子空間。

產生子空間初始種群是依上述思路在可行解子空間內對m維變量進行均勻分割產生k個子區間，設某一變量子區間的邊界為[b1，b2]，則以b1+（b2-b1）/2作為該子區間的均值。采用變量子區間均值的組合作為初始種群，初始種群為k^m。這種辦法產生初始種群的優勢在于不僅使初始種群[24]中包含最優解組合的概率增強，而且可以避免性能接近的個體入選，以減小種群大小。該方法與后面的遺傳算子相結合，可提高搜索效率和收斂于全局最優解的概率。

當然，也可不進行后面子空間分割直接依上述思路在可行解空間產生初始種群。

（2） 交叉算子和變異算子參數的動態調整

交叉算子可以使基因更加優化，產生新生個體。傳統的遺傳算法中，交叉率Pc是個常數，實際上交叉率Pc與遺傳代數的有著密切的關系。遺傳迭代初期，Pc如果選的大，可以造成足夠的擾動，從而增強遺傳算法的適應能力；而在后期，Pc選的小，會破壞優良基因，加快收斂速度。所以我們要根據情況適時調整交叉算子，才能使遺傳的后代為優良的后代。

以上分析表明，種群進化情況可以根據自適應函數來動態地調整交叉算子Pc和變異算子Pm，交叉率和變異率與個體的適應度在種群平均適應度和最大適應度之間呈線性關系。在進化初期，采用較大的群體規模，較大的交叉概率和較小的變異概率，這樣可以有效的增加群體的多樣性，提高算法的全局收斂性，克服早熟現象。在進化后期，減小群體規模和交叉概率，提高算法效率和局部搜索能力，提高變異概率，提高群體的多樣性，避免陷入局部極值點。

小結：上面講了傳統遺傳算法的組卷方案，分析傳統遺傳算法組卷的不足，并提出了改進措施，進而給出了改進遺傳算法的流程，通過反復實驗加以驗證，改進措施確實在很大程度提高了算法的效率和試卷的質量。

參考文獻

[1]毛秉毅.基于遺傳算法的智能組卷系統數據庫結構的研究，計算機工程與應用.2003，28（6），230-232頁.

[2]徐江濤.基于遺傳算法的試題庫智能組卷研究.湖南師范大學碩士論文.2007：9-47頁.

[3]王萌，金漢均，王曉榮.集合隨機抽選法在智能組卷中的研究.計算機工程與設計.2006，27（19）：353-358頁.

（作者單位：黑龍江農墾職業學院 ）