石慧升+韓志麗+劉沛葉

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4實驗結果及分析

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

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

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

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

5結束語

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

參考文獻：

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

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

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