基于遺傳算法智能組卷方案的調(diào)整

謝志偉

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

一、傳統(tǒng)遺傳算法

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

二、傳統(tǒng)遺傳算法“早熟”現(xiàn)象分析

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

“早熟”現(xiàn)象原因：

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

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

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

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

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

三、避免“早熟”現(xiàn)象發(fā)生的參數(shù)調(diào)整

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

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

具體方法是：

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

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

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

（2） 交叉算子和變異算子參數(shù)的動態(tài)調(diào)整

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

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

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

參考文獻

[1]毛秉毅.基于遺傳算法的智能組卷系統(tǒng)數(shù)據(jù)庫結(jié)構(gòu)的研究，計算機工程與應(yīng)用.2003，28（6），230-232頁.

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

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

（作者單位：黑龍江農(nóng)墾職業(yè)學院 ）