謝志偉

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體方法是：

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

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

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

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

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

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

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

參考文獻(xiàn)

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

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

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

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