李阿紅

（咸陽職業(yè)技術(shù)學(xué)院 電子信息學(xué)院，陜西 咸陽 712000）

自動組卷系統(tǒng)中遺傳算法的設(shè)計與研究

李阿紅

（咸陽職業(yè)技術(shù)學(xué)院 電子信息學(xué)院，陜西 咸陽 712000）

基于滿足信息時代考試模式改革的要求和保證考試的公正性、有效性的目的，文中在分析研究自動組卷系統(tǒng)中算法設(shè)計原則和流程的基礎(chǔ)上，通過分析發(fā)現(xiàn)遺傳算法在組卷時雖性能和效率比有明顯提高，但在種群樣本使用適應(yīng)函數(shù)為線性時，試題樣本種群無法發(fā)揮其優(yōu)勢，于是采用初始化進化迭代次數(shù)計算器，提高系統(tǒng)的運算速度，利用適應(yīng)度計算法提高初始種群的適應(yīng)度，借助選擇、交叉和變異的方法提高組卷系統(tǒng)算法的有效性和合理性。

遺傳算法；設(shè)計原則；算法設(shè)計；組卷算法

自動組卷系統(tǒng)是現(xiàn)代化考試的重要手段之一，而組卷算法是實現(xiàn)自動組卷系統(tǒng)的核心技術(shù)，它對試卷的科學(xué)性和有效性起著決定性的作用，因此，組卷算法已成為計算機輔助考試領(lǐng)域研究的熱點問題之一。

1　自動組卷系統(tǒng)算法設(shè)計的基本原則

1.1組卷算法參數(shù)設(shè)定

總體參數(shù)一般是指總體約束條件，比如：試卷期望的難度、考查范圍等。同時要說明試卷的一些其他的信息：比如：總分、試卷標題、試卷考試題型等的屬性。

考試難度約束：試卷的平均難度是指個中題型的難度和其分值的乘積比上試卷總分值。

考試知識點約束：試卷考察范圍是指從哪些知識點的來進行抽取試卷所要求的各種題型的題目。

題型控制：指考試試卷中希望出現(xiàn)什么類型的題目而組卷是通過用戶根據(jù)自己的需要從存在的試題類型中選擇，用戶也可以創(chuàng)建屬于自己的試題類型，但是要保證對應(yīng)的類型在試題庫中有對應(yīng)的題目。

1.2組卷算法的約束條件

組卷最重要的地方就在于組出高質(zhì)量的試卷。而要提高組卷的質(zhì)量必須依靠兩個核心要素，第一是高質(zhì)量的試題庫，題庫質(zhì)量高抽選的題目質(zhì)量也自然會提高；第二是一個合適的組卷約束條件，這一點在只能組卷方面是至關(guān)重要的，因為如果我們在組卷的時候沒有一個針對于算法的約束條件就不能得到好的試卷。而高質(zhì)量的試題庫也就意味著題庫也是相當(dāng)?shù)凝嫶螅鴱凝嫶蟮脑囶}庫中抽取到若干題目組成一套合適的試卷，而從龐大的數(shù)據(jù)庫中篩選出一定得題目，就要給這些試題一定得屬性，這也對后面檢驗抽題好壞給出了一個指標。因此一套試題就需要很多條件約束：知識點、難度、題型、分值、所屬章節(jié)等等。知識點可根據(jù)慣例或教學(xué)要求進行分類；難度區(qū)分難度的好處在于出卷的時候可以方便的、適當(dāng)?shù)倪x擇要出題的難度；分數(shù)對題庫中的題目進行分數(shù)自定義，非常人性化的設(shè)置。這時也就到了我們的第二個重要的點找出約束條件。多目標約束條件：指要組出來的試卷有多個指標，所有的目標都對應(yīng)有自己的一個約束條件：所抽選試題的總數(shù)量應(yīng)該與試卷期望數(shù)量一致；所抽選試題的分值應(yīng)該與試卷期望總扥只一致；所抽選試題的難度平均值要盡量與系統(tǒng)期望難度值接近；所抽選試題的適應(yīng)度應(yīng)該與試卷期望適應(yīng)度一致。

1.3組卷算法設(shè)計的流程

1）算法設(shè)計流程：如圖1所示。

圖1　算法設(shè)計流程圖

2　組卷算法設(shè)計研究

遺傳算法是一類從生物界的進化規(guī)律演化而來的隨機化搜索方法，遺傳算法由于其自適應(yīng)和良好而又高效的搜索技術(shù)成為當(dāng)前比較流行的組卷算法，可以從整體上對試卷進行優(yōu)化控制；試題樣本種群在不斷的進行交叉變異提高試題樣本種群的適應(yīng)度，這樣才能盡可能的得到搜索的全局最優(yōu)。

遺傳算法具有自適應(yīng)性、快速收斂和全局優(yōu)化等的特點。性能和效率也明顯較之前面的算法有明顯提高，但是也存在弊端，種群樣本在使用適應(yīng)度函數(shù)為線性時，考慮不到對試卷整體的影響，不利于試題樣本種群向好的方面進化。

2.1初始化

初始化進化迭代次數(shù)計數(shù)器，按照試卷的要求隨機生成總?cè)骸３跏蓟倪M化迭代器相當(dāng)于將變異進化的代數(shù)進行限制，否則在組卷過程中會因為找不到合適的解集而不停變異循環(huán)。初始化種群前，先解決編碼問題，一般遺傳算法編碼常常采用二進制編碼，在本系統(tǒng)中使用二進制編碼在交叉和變異遺運算操作時不容易控制，因此本系統(tǒng)采用實數(shù)編碼，具體表現(xiàn)為使用試題的題號作為基因。舉例子選擇題5道，填空題5道，分析題3道，設(shè)計題2道，則染色體編碼是：

表1　試題抽選事例

在種群初始化的時候是根據(jù)題型、總分、總題型等限制后隨機抽得。這樣在初始化后系統(tǒng)就滿足試題數(shù)目、總分值等限制。使得后面更容易產(chǎn)生結(jié)果提高運算結(jié)果的速度。

2.2計算機適應(yīng)度

按照適應(yīng)度計算方法計算初始化種群的適應(yīng)度。適應(yīng)度是我們判斷試題種群好壞程度的指標，遺傳算法利用適應(yīng)度值這一信息來指導(dǎo)搜索方向，而不需要適應(yīng)度函數(shù)連續(xù)或可導(dǎo)以及其它輔助信息。在試題種群初始化的時候我們已經(jīng)對題量、總分已經(jīng)考慮過，所以在這里我們只需要對知識點和試題的難度考慮了。試卷的難度系數(shù)本系統(tǒng)按照公式考慮，i=1，2，....N，N是試卷所含的題目數(shù)，Ti，Si分別是第i題的難度系數(shù)和分數(shù)：

知識點的覆蓋率做為知識點分布，比如試卷期望考到N個知識點，而所有題目知識點含有M個，覆蓋率就為M/N。試卷期望難度EH與實際組成試卷難度H差距越接近越符合要求，知識點的覆蓋率約接近一越好。其中f1為知識點分布的權(quán)重，f2為難度系數(shù)所占權(quán)重。因此適應(yīng)度函數(shù)如下：

當(dāng)f1=0時退化為只限制試題難度系數(shù)，當(dāng)f2=0時退化為只限制知識點分布。這這里系統(tǒng)根據(jù)設(shè)定將f1和f2的值作為固定的參數(shù)，用戶在操作過程中不用考慮算法參數(shù)。

2.3選擇

選擇是用來確定重組或交叉的個體，以及被選個體將產(chǎn)生多少子個體。按照上面得出的適應(yīng)度進行父代個體的選擇。系統(tǒng)采用輪盤賭選擇算法進行。輪盤賭算是現(xiàn)在在交叉選擇中比較常用到的算法之一。算法規(guī)模為M的群體P中各個個體的適應(yīng)度為P=｛A1、A2、…Am｝，其被選擇概率為：Ai/ （i從0到m）。

2.4交叉

基因重組是結(jié)合來自父代交配種群中的信息產(chǎn)生新的個體。系統(tǒng)采用實數(shù)編碼。所以系統(tǒng)采用簡單的單點交叉，從真?zhèn)€試題染色體上看是多點交叉。將群體中的染色體任意進行兩兩配對，對每對染色體產(chǎn)生一個［0，N-2］的隨機數(shù)r，r即為分段點，將r后的兩道題目互換（保證分值相加一樣）得到下一代。交叉后生成的子代有可能因存在重復(fù)的題號而非法。出現(xiàn)這種情況要將出現(xiàn)的題號換成該段中沒有出現(xiàn)過的題號，這樣重新得到新子代。

2.5變異

交叉之后子代經(jīng)歷的變異，實際上是子代基因按小概率擾動產(chǎn)生的變化。依據(jù)個體編碼表示方法的不同，應(yīng)用實值變異。在遺傳算法中，變異概率一般較小。這里不分段進行變異，而是只對某段上的某個基因進行變異。變異的操作如下：在［1，n］范圍內(nèi)隨機生成一個變異位置P，以一定的原則從題庫中選擇一個變異基因，變異基因的選擇原則為：與原基因題型相同的，分數(shù)相同，與至少包含原題目一個有效知識點。

3　結(jié)　論

選擇合適的算法以快速生成高質(zhì)量的試卷仍然是一項具有非常重要意義的研究，本組卷系統(tǒng)采用多目標約束條件下的組合優(yōu)化求解算法──遺傳算法，對不同的題目類型采用分組二進制的編碼方法，使種群在一開始時就滿足一定的約束條件從而減少組卷的冗余度，有利于提高組卷效率提高自動組卷系統(tǒng)的組卷效率和試卷質(zhì)量。

［1］王友仁.智能組卷系統(tǒng)的建模與算法研究［J］.系統(tǒng)工程理論與實踐，2004（9）:89-89.

［2］于志敏，劉延華.選題組卷策略研究［J］.電腦開發(fā)與應(yīng)用. 2001（3）:32-34.

［3］宋海沂，張乾清.高等院校試題庫建立及試卷自動生成系統(tǒng)的開發(fā)及意義.［J］科技創(chuàng)業(yè)2009，22（12X）:117-118.

［4］丁庶煒，閆宏印，王世兵，等.基于集合隨機抽選法的智能組卷的研究與應(yīng)用［J］.電腦開發(fā)與應(yīng)用，2010（5）:10-11.

［5］關(guān)淞元，劉大有，金弟，等.基于局部搜索的遺傳算法求解自動組卷問題［J］.吉林大學(xué)學(xué)報（理學(xué)版），2009（5）:961-968.

［6］王瓊瑤.智能化組卷系統(tǒng)的研究和實現(xiàn)［D］.南京:南京理工大學(xué)，2010.

［7］馬德良，陸昌輝，王小樂.基于改進遺傳算法的智能組卷方法［J］.計算機應(yīng)用，2009，29（7）:1884-1886.

［8］吳樹錦.基于遺傳算法智能組卷系統(tǒng)的研究與實現(xiàn)［D］.上海:華東師范大學(xué)，2008.

［9］馮長寶.一種基于遺傳算法的智能組卷模型與系統(tǒng)設(shè)計［D］.長春:東北師范大學(xué)，2010.

［10］焦翠珍，戴文華.基于遺傳算法的智能組卷方案研究［J］.微電子學(xué)與計算機，2006（6）:27-29，33.

［11］鄒茜.基于Qt的GUI應(yīng)用程序開發(fā)［J］.科技信息，2010（18）: 596-597.

［12］秦子實.使用Qt/C++編程操作Microsoft Office軟件的應(yīng)用［J］.電腦開發(fā)與應(yīng)用，2013（1）:54-56.

［13］路景.基于改進遺傳算法的智能組卷研究［D］.長沙:中南大學(xué)，2007.

［14］張克.基于C/S結(jié)構(gòu)的試題庫隨機組卷系統(tǒng)的研究［D］.合肥:合肥工業(yè)大學(xué)，2007.

［15］梁海麗.基于通用試題庫的智能組卷系統(tǒng)的開發(fā)與實現(xiàn)［D］.石家莊:河北科技大學(xué)，2011.

［16］王雍鈞，黃毓瑜.基于知識點題型分布和分值的智能組卷算法研究［J］.計算機應(yīng)用與軟件，2004（8）:111-113.

Research on genetic algorithm design in automatic paper generating system

LI A-hong
（College of Technics Information，Xianyang Vocational＆amp;Technical College，Xianyang 712000，china）

To meet the requirements of the examination reform and ensure the fairness，and the effectiveness of the test.The paper points out genetic algorithm can improve the function and the efficiency in generating test paper，but it can not play its advantages in linear function and proposes the speed operation of the system can be improved by initializing iteration number calculator and the fitness of the original population by using fitness algorithm and the effectiveness and the rationality of genetic algorithm in the Automatic System by the selection，the crossing，and the variation.

genetic algorithm；design principles；algorithm design；paper generating algorithm

TN02

A

1674－6236（2016）16-0041-02

2015-12-27稿件編號：201512268

李阿紅（1977—），女，陜西乾縣人，碩士，講師。研究方向：智能信息系統(tǒng)。