自動組卷系統中遺傳算法的設計與研究

李阿紅

（咸陽職業技術學院 電子信息學院，陜西 咸陽 712000）

自動組卷系統中遺傳算法的設計與研究

李阿紅

（咸陽職業技術學院 電子信息學院，陜西 咸陽 712000）

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

遺傳算法；設計原則；算法設計；組卷算法

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

1　自動組卷系統算法設計的基本原則

1.1組卷算法參數設定

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

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

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

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

1.2組卷算法的約束條件

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

1.3組卷算法設計的流程

1）算法設計流程：如圖1所示。

圖1　算法設計流程圖

2　組卷算法設計研究

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

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

2.1初始化

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

表1　試題抽選事例

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

2.2計算機適應度

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

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

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

2.3選擇

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

2.4交叉

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

2.5變異

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

3　結　論

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

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

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

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

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

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

［6］王瓊瑤.智能化組卷系統的研究和實現［D］.南京:南京理工大學，2010.

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

［8］吳樹錦.基于遺傳算法智能組卷系統的研究與實現［D］.上海:華東師范大學，2008.

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

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

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

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

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

［14］張克.基于C/S結構的試題庫隨機組卷系統的研究［D］.合肥:合肥工業大學，2007.

［15］梁海麗.基于通用試題庫的智能組卷系統的開發與實現［D］.石家莊:河北科技大學，2011.

［16］王雍鈞，黃毓瑜.基于知識點題型分布和分值的智能組卷算法研究［J］.計算機應用與軟件，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—），女，陜西乾縣人，碩士，講師。研究方向：智能信息系統。