基于改進(jìn)遺傳算法的自動(dòng)組卷問(wèn)題研究

梁樹(shù)杰

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

基于改進(jìn)遺傳算法的自動(dòng)組卷問(wèn)題研究

梁樹(shù)杰

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

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

遺傳算法；改進(jìn)；效率；時(shí)間

0 引言

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

1 自動(dòng)組卷問(wèn)題分析

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

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

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

3 基于改進(jìn)遺傳算法的自動(dòng)組卷問(wèn)題求解

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

3.1 制定編碼方案

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

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

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

3.3 遺傳算子設(shè)計(jì)

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

3.4 控制參數(shù)確定

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

3.4 改進(jìn)遺傳算法的實(shí)驗(yàn)驗(yàn)證

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

表1 群體規(guī)模實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

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

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

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

[8]宋秋蓮.改進(jìn)型遺傳算法在自動(dòng)組卷系統(tǒng)中的應(yīng)用研究[J].計(jì)算機(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

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

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