基于改進(jìn)遺傳算法的智能組卷系統(tǒng)的研究

石慧升+韓志麗+劉沛葉

【摘要】針對傳統(tǒng)的組卷算法具有組卷速度慢、成功率低、組卷質(zhì)量不高等缺點(diǎn)，本文提出了改進(jìn)的遺傳算法組卷問題的新方法。實(shí)踐證明，在這種結(jié)構(gòu)下的數(shù)據(jù)庫能很好的配合改進(jìn)的遺傳算法實(shí)現(xiàn)智能組卷，組卷的成功率和收斂速度都得到了明顯的提高，并且較好的克服了未成熟收斂現(xiàn)象，取得了較滿意的組卷效果。

【關(guān)鍵詞】遺傳算法 智能組卷 數(shù)學(xué)建模

1 引言

隨著計算機(jī)在教學(xué)領(lǐng)域的應(yīng)用和發(fā)展，試題庫的編制和應(yīng)用也越來越顯示出其重要性，而智能組卷是試題庫系統(tǒng)研制的一個難點(diǎn)。一個自動組卷系統(tǒng)的性能評價主要取決于組卷算法和相對于算法的試題庫的庫結(jié)構(gòu)。因此，試題庫的庫結(jié)構(gòu)設(shè)計和組卷算法的設(shè)計是智能型試卷自動生成系統(tǒng)的重要內(nèi)容。遺傳算法是一種模擬自然界生物進(jìn)化過程的計算模型。它的求解問題是從多個可行解開始，然后通過一定的法則進(jìn)行迭代以產(chǎn)生新解，直到得到最優(yōu)結(jié)果。本文提出了一種用改進(jìn)的遺傳算法來求解試題庫組卷問題的方法。

2智能型試卷自動生成系統(tǒng)的組卷問題

2.1智能型試卷自動生成系統(tǒng)中試題庫結(jié)構(gòu)的設(shè)計結(jié)合遺傳算法的特點(diǎn)，系統(tǒng)所采用的試題庫結(jié)構(gòu)要全面客觀反映試題的本質(zhì)，并且易于遺傳算法操作，使組卷實(shí)現(xiàn)智能化，組卷效率高、速度快、數(shù)據(jù)冗余度小。因此，所確定的試題結(jié)構(gòu)如下：（1）章節(jié)：試題內(nèi)容所屬的篇章；（2）試題編號：試題編號具有與每一道試題一一對應(yīng)的性質(zhì)。（3）試題類型：可分為判斷題、選擇題、填空題、操作題、綜合題。為了在生成試卷時能夠快速選取指定類型的試題，和減少冗于度，在建庫時可為每種題型建立一個庫文件；（4）試題難度：在試卷命題過程中，針對不同的考試對象，不同階段的考試，命題難度也不同，所以應(yīng)在數(shù)據(jù)庫中增加難度系數(shù)。（5）試題的內(nèi)容：不參與組卷運(yùn)算的過程。

2.2智能型試卷自動生成系統(tǒng)中組卷的功能要求

（1）考試內(nèi)容由用戶決定，可以按篇章為單位決定。

（2）考試時間由用戶指定。

（3）整卷的難度系數(shù)由用戶根據(jù)學(xué)生的水平?jīng)Q定，一般取0.2～ 0.5。

（4）每份試卷滿分由用戶指定，其中主觀題、客觀題所占分?jǐn)?shù)比例由用戶指定。

2.3智能型試卷自動生成系統(tǒng)中組卷的數(shù)學(xué)模型

組卷中決定一道試題，就決定它的上述13個屬性，也就是說決定一個13維的向量（α1，α2，α3，… α13）決定一份試卷有n道試題，實(shí)際上就是決定一個n× 13階矩陣。

3改進(jìn)遺傳算法在智能型試卷自動組卷系統(tǒng)中的應(yīng)用

3.1遺傳算法的基本思想。大自然的生物進(jìn)化中，一個生物群體要經(jīng)過交配、變異、自然選擇的過程，形成下一代群體，如此循環(huán)下去，不斷進(jìn)化，最后生存下來的總是最優(yōu)的。將這種思想運(yùn)用到算法中去，就形成了遺傳算法。 經(jīng)典的遺傳算法存在搜索后期效率低和易形成未成熟收斂的情況。為此，人們嘗試了許多改進(jìn)方法，包括設(shè)計不同的選擇、交叉及變異算子，改變算法結(jié)構(gòu)，設(shè)計自適應(yīng)交叉和變異概率，將遺傳算法與其它優(yōu)化智能方法相結(jié)合等。

根據(jù)遺傳算法，在采用遺傳算法尋優(yōu)時，通常按以下主要步驟進(jìn)行：

①基因編碼；②初始群體生成；③群體中個體適應(yīng)度值的計算；④對群體中個體進(jìn)行遺傳操作（即選擇、交叉和變異）；⑤適應(yīng)度值的再次計算；⑥如果滿足終止條件，疊代停止，輸出問題的最優(yōu)解；否則，轉(zhuǎn)向步驟④。

上述遺傳算法的每一步都對優(yōu)化搜索的收斂速度和解的質(zhì)量有影響。

3.2改進(jìn)遺傳算法在智能型試卷自動生成系統(tǒng)中的應(yīng)用針對試題組卷的具體情況，我們對簡單遺傳算法進(jìn)行改進(jìn)后應(yīng)用于智能型試卷自動生成系統(tǒng)中，下面給出具體的解決方案：（1）確定編碼方案。（2）適應(yīng)度函數(shù)的確定。（3）組卷問題中對遺傳算子的改進(jìn)。（4）對遺傳算法控制參數(shù)

4實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)條件：將《計算機(jī)基礎(chǔ)》中800道試題按要求分別建立5個庫文件，其中判斷、填空、操作題各200道，選擇、綜合題各100道。為了使試題的各種屬性分布合理，可用隨機(jī)函數(shù)產(chǎn)生試題的各種屬性值。遺傳算法的控制參數(shù)為：種群規(guī)模N= 200；最大代數(shù)Maxgen= 500；初始交叉概率pc= 0.6；變異概率pm=0.1；智能型試卷自動生成系統(tǒng)中組卷約束條件：總分為100分；估時為120分鐘；題型分?jǐn)?shù)比例為：判斷、填空各占10%，選擇占20%，綜合題占40%，算法設(shè)計題占20%；能力層次為：識記：20%，理解：30%，應(yīng)用：35%，綜合：15% ；難度為：容易：20%，中等：30%，較難：40%，難：10%。

由于在建庫時為每種題型建立了一個庫文件，故每種題型可各自獨(dú)立編碼。因此，編碼方案可采用分組實(shí)數(shù)編碼策略，就是根據(jù)各個題型各自進(jìn)行實(shí)數(shù)編碼，然后對每一個題型再采用傳統(tǒng)二進(jìn)制編碼策略進(jìn)行處理，但題型組之間的編碼是獨(dú)立的，每一組編碼反映一種題型。這樣，可以克服以往采用二進(jìn)制編碼搜索空間過大和編碼長度過長的缺點(diǎn)。

為了加快遺傳算法的收斂并減少迭代次數(shù)，試卷初始種群p（0）完全隨機(jī)的方法產(chǎn)生，而是根據(jù)題型（或各篇章內(nèi)容或各考查點(diǎn)）所占分?jǐn)?shù)比例、總分的要求隨機(jī)產(chǎn)生，使得初始種群已經(jīng)滿足了題型（或篇章或考查點(diǎn)）和總分的要求。

適應(yīng)度函數(shù)是用來評判試卷群體中個體的優(yōu)劣程度的指標(biāo)，遺傳算法利用適應(yīng)度值這一信息來指導(dǎo)搜索方向。

5結(jié)束語

一個自動組卷系統(tǒng)的性能主要取決于組卷算法，一個好的組卷算法既要保證組卷的成功率，又要保證數(shù)據(jù)運(yùn)算的時間效率。在傳統(tǒng)的組卷算法中，組卷成功率較低，時間和空間開銷都比較大，適合于小型題庫系統(tǒng)。將遺傳算法應(yīng)用于組卷中，使組卷的成功率和收斂速度都得到顯著提高，適合于較大型題庫系統(tǒng)。由于求解精度和收斂速度是相互矛盾的，要使組卷的誤差精度和收斂速度進(jìn)一步得到改進(jìn)，還需要做出更深入的研究。

參考文獻(xiàn)：

[1]李小勇，王瑛.題庫管理系統(tǒng)中的自動化組卷算法[J].西北師范大學(xué)學(xué)報（自然科學(xué)版），2002，38（4）：41- 43

[2]涂振華，王勇等.智能組卷算法研究[J].江西教育學(xué)院學(xué)報，2002，23（6）：51- 52

作者簡介：石慧升 男 石家莊工商職業(yè)學(xué)院 高級工程師 碩士 ；韓志麗 女 石家莊工商職業(yè)學(xué)院 助理工程師 學(xué)士；劉沛葉 女 石家莊工商職業(yè)學(xué)院 工程師 碩士。