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

李阿紅

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

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

李阿紅

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

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

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

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

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

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

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

考試難度約束：試卷的平均難度是指?jìng)€(gè)中題型的難度和其分值的乘積比上試卷總分值。

考試知識(shí)點(diǎn)約束：試卷考察范圍是指從哪些知識(shí)點(diǎn)的來進(jìn)行抽取試卷所要求的各種題型的題目。

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

1.2組卷算法的約束條件

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

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

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

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

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

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

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

2.1初始化

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

表1　試題抽選事例

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

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

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

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

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

2.3選擇

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

2.4交叉

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

2.5變異

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

3　結(jié)　論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

［16］王雍鈞，黃毓瑜.基于知識(shí)點(diǎn)題型分布和分值的智能組卷算法研究［J］.計(jì)算機(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稿件編號(hào)：201512268

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