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

石慧升+韓志麗+劉沛葉

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

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

1 引言

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

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

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

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

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

（2）考試時(shí)間由用戶指定。

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

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

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

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

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

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

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

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

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

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

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

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

由于在建庫(kù)時(shí)為每種題型建立了一個(gè)庫(kù)文件，故每種題型可各自獨(dú)立編碼。因此，編碼方案可采用分組實(shí)數(shù)編碼策略，就是根據(jù)各個(gè)題型各自進(jìn)行實(shí)數(shù)編碼，然后對(duì)每一個(gè)題型再采用傳統(tǒng)二進(jìn)制編碼策略進(jìn)行處理，但題型組之間的編碼是獨(dú)立的，每一組編碼反映一種題型。這樣，可以克服以往采用二進(jìn)制編碼搜索空間過(guò)大和編碼長(zhǎng)度過(guò)長(zhǎng)的缺點(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ù)是用來(lái)評(píng)判試卷群體中個(gè)體的優(yōu)劣程度的指標(biāo)，遺傳算法利用適應(yīng)度值這一信息來(lái)指導(dǎo)搜索方向。

5結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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