基于改進遺傳算法的智能組卷系統的研究

石慧升+韓志麗+劉沛葉

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

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

1 引言

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

2智能型試卷自動生成系統的組卷問題

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

2.2智能型試卷自動生成系統中組卷的功能要求

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

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

（3）整卷的難度系數由用戶根據學生的水平決定，一般取0.2～ 0.5。

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

2.3智能型試卷自動生成系統中組卷的數學模型

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

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

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

根據遺傳算法，在采用遺傳算法尋優時，通常按以下主要步驟進行：

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

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

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

4實驗結果及分析

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

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

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

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

5結束語

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

參考文獻：

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

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

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