梁樹杰

（廣東茂名幼兒師范?？茖W(xué)校，廣東 茂名 525200）

基于改進遺傳算法的自動組卷問題研究

梁樹杰

（廣東茂名幼兒師范?？茖W(xué)校，廣東 茂名 525200）

利用標(biāo)準(zhǔn)傳統(tǒng)遺傳算法進行自動組卷，有收斂速度慢和未成熟收斂的缺點。本文運用遺傳算法的原理和分段二進制編碼策略，得到改進遺傳算法。實驗結(jié)果表明，利用改進遺傳算法進行解自動組卷，能夠明顯地提高組卷成功率和減少組卷時間。

遺傳算法；改進；效率；時間

0 引言

隨著計算機和互聯(lián)網(wǎng)的發(fā)展，網(wǎng)上考試系統(tǒng)得到了廣泛的應(yīng)用。自動組卷技術(shù)是網(wǎng)上考試系統(tǒng)的重要技術(shù)。應(yīng)運用高效、科學(xué)的算法，才能有效地解決自動組卷問題，基于改進遺傳算法的自動組卷技術(shù)對于完善網(wǎng)上考試系統(tǒng)具有重要的作用。

1 自動組卷問題分析

一般來說，用戶對最終生成的試卷都有一定的要求，如試卷試題的難度系數(shù)、題型分布、知識覆蓋面和答題時間等。從數(shù)學(xué)方法來看，在組卷之前，應(yīng)建立組卷控制指標(biāo)對應(yīng)的狀態(tài)空間。用an表示控制指標(biāo)，用m表示試卷試題數(shù)量，用S表示試卷矩陣。在矩陣S中，各行由試題難度系數(shù)、知識覆蓋面等控制指標(biāo)狀態(tài)，對這些屬性指標(biāo)用二進制編碼表示；各列為試題控制指標(biāo)的全部取值。在求解組卷問題時，將矩陣S作為目標(biāo)狀態(tài)矩陣，并用S、D、Q、Z、T分別表示試卷的總分、難度、題型、知識范圍和答題時間，并滿足如下約束條件：

2 標(biāo)準(zhǔn)遺傳算法

遺傳算法是對決策變量編碼，并把它作為運算對象來解決問題的一種算法。在運用遺傳算法時，無需獲取問題領(lǐng)域的具體信息，不受搜索空間是否可微或連續(xù)的限制。運用遺傳算法解決問題時，必須制定編碼方案和確定適應(yīng)函數(shù)，并利用適應(yīng)度值度量解的質(zhì)量。在問題的演繹過程中，可以根據(jù)解的適應(yīng)值進行選擇[1]。不僅要確定函數(shù)還要確定選擇策略、選擇控制參數(shù)、算子設(shè)計。通過制定優(yōu)勝劣汰選擇機制，使有較好適應(yīng)值的解的存活概率更高；選擇不同遺傳操作的概率、群規(guī)模、算法執(zhí)行最大代數(shù)，以及有關(guān)的輔助控制參數(shù)；選擇再生、雜交、變異等方法。并確定算法的終止準(zhǔn)則[2]。根據(jù)用戶建立約束條件，從試題庫中搜索與特征參數(shù)相匹配的試題。

3 基于改進遺傳算法的自動組卷問題求解

運用標(biāo)準(zhǔn)遺傳算法自動求解組卷問題，要出現(xiàn)收斂速度慢、早熟等問題。所以，還應(yīng)對標(biāo)準(zhǔn)遺傳算法進行改進，以更好地求解組卷問題。

3.1 制定編碼方案

可以采用分段二進制編碼策略改進標(biāo)準(zhǔn)遺傳算法。將題庫劃分成若干段，每段表示一種題型。結(jié)合各題型的數(shù)量確定各段長度，然后分別對各段進行二進制編碼[3]。根據(jù)試題庫中試題的數(shù)量，確定編碼長度。假設(shè)試題庫的試題數(shù)量為n，有 a、b、c 三種題型， 各段長度分別用 k1、k2、k3表示 ， 則 n={[a1，a2，...，ak1]， [b1，b2，...，bk2],[c1，c2，...，ck3]}，且滿足

運用二段制編碼，能夠縮小組卷搜索空間，并能提高組卷問題求解效率；也能滿足試卷的題型及其試題數(shù)量要求[4]。在初始化階段，組卷中各題型的分?jǐn)?shù)保持相等，以滿足試卷的總分要求，并降低試卷的冗余度，提高組卷效率。

3.2 適應(yīng)度函數(shù)定義

3.3 遺傳算子設(shè)計

還應(yīng)做好選擇算子、變異算子和交叉算子的設(shè)計工作。首先，在設(shè)計選擇算子時，把最佳個體保存法和適應(yīng)度比例選擇法結(jié)合起來，以選擇最佳的個體。在此基礎(chǔ)上，直接復(fù)制個體，并直接帶入下一代[6]。在選擇其余的個體時，要使用比例選擇法，以確保個體被選中的概率與適應(yīng)度保持一定的比例。個體被選中的概率用表示。在設(shè)計交叉算子時，應(yīng)結(jié)合編碼策略，使用單點交叉法，即在段內(nèi)進行交叉。在設(shè)計變異算子時，利用局部搜索能力，并將其作為組卷問題求解的輔助算法[7]。經(jīng)過初始化后，群體能滿足題分和題型的比例要求。還應(yīng)采用同題型內(nèi)兩點變異法，使題型在所屬編碼段實現(xiàn)變異。

3.4 控制參數(shù)確定

在確定控制參數(shù)時，還要確定變異概率和交叉概率。這兩個參數(shù)對遺傳算法具有重要的影響。在標(biāo)準(zhǔn)遺傳算法中這兩個參數(shù)基本上是固定值。為搜索全局最優(yōu)解，還應(yīng)確定適應(yīng)度標(biāo)準(zhǔn)，在適應(yīng)度發(fā)生變化時，使交叉概率和變異概率隨之改變。還應(yīng)確定最優(yōu)解搜索的終止條件，使種群在出現(xiàn)用戶滿意試卷后停止搜索最優(yōu)解[8]。還應(yīng)規(guī)定最大適應(yīng)度值的變化率，當(dāng)前后兩代最大適應(yīng)度值的變化小于這一數(shù)值，之后不再發(fā)生顯著的進化效果，結(jié)束群體進化過程。

3.4 改進遺傳算法的實驗驗證

下面通過實驗驗證改進遺傳算解決自動組卷問題的效果。從有600道題的試題庫選取試題組卷，包括單選題、多選題、判斷題、填空題、簡答題等五種題型，試卷總分100分，各題型分?jǐn)?shù)固定。在選題時，應(yīng)滿足題型約束，選擇各章節(jié)的試題分值與要求之間的誤差不超過±2分，且難度分值誤差也不超過±2分。首次實驗的群體規(guī)模的變異概率與交叉概率分別設(shè)為0.01和0.6。實驗結(jié)果如表1所示。

表1 群體規(guī)模實驗結(jié)果

分析實驗結(jié)果發(fā)現(xiàn)，在群體規(guī)模較小的情況下，只有少量試題參與組卷，只能在較小的空間范圍查找最優(yōu)解，獲得有效試卷的概率較??；隨著群體規(guī)模逐漸擴大，獲得有效試卷的次數(shù)逐步提高。由此可見，群體規(guī)模對算法的收斂性產(chǎn)生較大影響。群體規(guī)模設(shè)為40和50時，獲得的組卷效果差別并不明顯。因此可以說明，在群體規(guī)模達到一定數(shù)值后，群體規(guī)模變化對算法的收斂性影響較少。群體規(guī)模變化對程序運行時間影響明顯。

為了分析改進遺傳算法中參數(shù)的靈敏性，進行第二次實驗。建立的初始群的試題類型、分?jǐn)?shù)分布達到組卷要求。在利用改進遺傳算法進行組卷問題求解時，還應(yīng)考慮試題難度系數(shù)、組卷時間和試題章節(jié)分布條件。在分析某項約束條件時，應(yīng)把其他誤差對應(yīng)的權(quán)重設(shè)定為零，以排除其他因素的干擾。實驗結(jié)果如表2所示。

表2 參數(shù)靈敏度實驗結(jié)果

從表2的實驗分析結(jié)果發(fā)現(xiàn)，改進的遺傳算法對試題章節(jié)分布影響最大。如果消除這個影響，能明顯提高改進遺傳算法的成功率，明顯縮短組卷問題求解的時間。因此，應(yīng)適當(dāng)降低各章節(jié)試題分布的誤差權(quán)重。

按照組卷要求，采用標(biāo)準(zhǔn)遺傳算法和改進遺傳算法分別進行實驗，并比較實驗結(jié)果，結(jié)果如表3所示。實驗結(jié)果表明，采用改進遺傳算法能夠提高組卷成功率，明顯減少平均組卷時間。因此，采用改進遺傳算法能更好地解決自動組卷問題。

表3 標(biāo)準(zhǔn)進遺傳算法和改進進遺傳算法組卷實驗結(jié)果比較

4 結(jié)論

通過研究發(fā)現(xiàn)，標(biāo)準(zhǔn)傳統(tǒng)遺傳算法不能滿足快速組卷的需求。利用遺傳算法原理和分段二進制策略獲得的改進遺傳算法，能減少組卷迭代次數(shù)，提高組卷成功率，減少組卷時間。因此改進遺傳算法能提高在線考試系統(tǒng)自動組卷的效率。

[1]陳國彬,張廣泉.基于改進遺傳算法的快速自動組卷算法研究[J].計算機應(yīng)用研究,2015（10）:2996-2998.

[2]席衛(wèi)文，張春輝，王飛，等.一種基于改進遺傳算法的醫(yī)學(xué)題庫自動組卷設(shè)計與實現(xiàn)[J].中國醫(yī)學(xué)物理學(xué)雜志,2016（8）:861-864.

[3]宋芝蘭.基于遺傳算法自動組卷問題的設(shè)計研究[J].商場現(xiàn)代化，2011（4）:9-10.

[4]樊光輝,韓寶強.改進遺傳算法在自動組卷中的應(yīng)用[J].軟件導(dǎo)刊，2011（11）:74-76.

[5]楊世達,金敏,梅磊.面向自動組卷問題的改進類電磁算法[J].計算機工程與應(yīng)用，2011（35）:51-53.

[6]黃小明,劉長安.改進遺傳算法在自動組卷系統(tǒng)中的應(yīng)用[J].科學(xué)技術(shù)與工程，2010（8）:1999-2002.

[7]王鳳蕊,王文宏,潘全科等.解決智能組卷問題的和聲搜索算法研究[J].計算機仿真,2010（3）:298-301.

[8]宋秋蓮.改進型遺傳算法在自動組卷系統(tǒng)中的應(yīng)用研究[J].計算機光盤軟件與應(yīng)用,2013（24）:117-118.

責(zé)任編輯仇大勇

Problems of the Automatic Test Paper Based on the Improved Genetic Algorithm

LIANG Shujie
(Guangdong Preschool Normal College in Maoming,Maoming Guangdong 525200,China)

The standard traditional genetic algorithm for automatic test paper has the disadvantages of slow and premature convergence.The genetic algorithm is improved by applying its principle and the segmented binary encoding strategy in this paper.The experimental results show that the improved genetic algorithm for automatic test paper can significantly improve the success rate of test and reduce the test time.

genetic algorithm;improvement;efficiency;time

TP18

A

1674－5787（2017）02－0149－03

10.13887/j.cnki.jccee.2017（2）.39

2017-03-02

本文系全國教育信息化項目“網(wǎng)絡(luò)環(huán)境下教師繼續(xù)教育研修模式的研究”(項目編號：1436219964)的研究成果之一。

梁樹杰（1981—），男，廣東高州人，碩士，廣東茂名幼兒師范專科學(xué)校講師，研究方向：計算機應(yīng)用技術(shù)。