- 相關(guān)推薦
遺傳算法在試題組卷中的應(yīng)用
遺傳算法在試題組卷中的應(yīng)用
摘要： 本文運(yùn)用遺傳算法的全局尋優(yōu)對(duì)考試中的自動(dòng)化組卷進(jìn)行了研究，并得到了一個(gè)解決適合考方要求的試題模型的好的算法。
關(guān)鍵詞：遺傳算法 全局尋優(yōu) 自動(dòng)化組卷
1 引言
計(jì)算機(jī)輔助考試系統(tǒng)的自動(dòng)組卷的效率與質(zhì)量完全取決于抽題算法的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)算法從題庫(kù)中既快又好的抽出一組最佳解或是抽出一組非常接近最佳解的實(shí)體，涉及到一個(gè)全局尋優(yōu)和收斂速度快慢的的問(wèn)題，很多學(xué)者對(duì)其進(jìn)行了研究。遺傳算法以其自適應(yīng)尋優(yōu)及良好的智能搜索技術(shù)，受到了廣泛的運(yùn)用。Potts J C等人基于變異和人工選擇的遺傳算法對(duì)最優(yōu)群體規(guī)模進(jìn)行了論述；Hamilton M A等結(jié)合遺傳算法把其運(yùn)用到神經(jīng)網(wǎng)絡(luò)中，并取得了良好的效果[4]；也有眾多的學(xué)者對(duì)保留最佳狀態(tài)的遺傳算法的收斂速度做了討論。通過(guò)理論推導(dǎo)和事實(shí)運(yùn)用，發(fā)現(xiàn)遺傳算法在尋優(yōu)和收斂性方面都是非常有效的。
本文結(jié)合遺傳算法的原理和思想，對(duì)考試自動(dòng)出題組卷的問(wèn)題進(jìn)行了研究，找到了一種獲得與考試試題控制指標(biāo)符合的試題模型的解決方法。
2 問(wèn)題描述
自動(dòng)組卷是考試系統(tǒng)自動(dòng)化或半自動(dòng)化操作的核心目標(biāo)之一,而如何保證生成的試卷能最大程度的滿足用戶(hù)的不同需要,并具有隨機(jī)性、科學(xué)性、合理性,這是實(shí)現(xiàn)中的一個(gè)難點(diǎn)。尤其在交互式環(huán)境下用戶(hù)對(duì)于組卷速度要求較高，而一個(gè)理論上較完美的算法可能會(huì)以犧牲時(shí)間作為代價(jià)，往往不能達(dá)到預(yù)期的效果。因此，選擇一個(gè)高效、科學(xué)、合理的算法是自動(dòng)組卷的關(guān)鍵。
以往的具有自動(dòng)組卷功能的考試系統(tǒng)大多采用隨機(jī)選取法和回溯試探法。隨機(jī)選取法根據(jù)狀態(tài)空間的控制指標(biāo)，由計(jì)算機(jī)隨機(jī)的抽取一道試題放入試題庫(kù)，此過(guò)程不斷重復(fù)，直到組卷完畢，或已無(wú)法從題庫(kù)中抽取滿足控制指標(biāo)的試題為止。該方法結(jié)構(gòu)簡(jiǎn)單，對(duì)于單道題的抽取運(yùn)行速度較快，但是對(duì)于整個(gè)組卷過(guò)程來(lái)說(shuō)組卷成功率低，即使組卷成功，花費(fèi)時(shí)間也令人難以忍受。尤其是當(dāng)題庫(kù)中各狀態(tài)類(lèi)型平均出題量較低時(shí)，組卷往往以失敗而告終。
回溯試探法這是將隨機(jī)選取法產(chǎn)生的每一狀態(tài)類(lèi)型紀(jì)錄下來(lái)，當(dāng)搜索失敗時(shí)釋放上次紀(jì)錄的狀態(tài)類(lèi)型，然后再依據(jù)一定的規(guī)律（正是這種規(guī)律破壞了選取試題的隨機(jī)性）變換一種新的狀態(tài)類(lèi)型進(jìn)行試探，通過(guò)不斷的回溯試探直到試卷生成完畢或退回出發(fā)點(diǎn)為止，這種有條件的深度優(yōu)先算法，對(duì)于狀態(tài)類(lèi)型和出題量都較少的題庫(kù)系統(tǒng)而言，組卷成功率較好，但是在實(shí)際到一個(gè)應(yīng)用時(shí)發(fā)現(xiàn)這種算法對(duì)內(nèi)存的占用量很大，程序結(jié)構(gòu)相對(duì)比較復(fù)雜，而且選取試題缺乏隨機(jī)性，組卷時(shí)間長(zhǎng)，后兩點(diǎn)是用戶(hù)無(wú)法接受的，因此它也不是一種很好的用來(lái)自動(dòng)組卷的算法。
分析上述兩種算法的優(yōu)缺點(diǎn)，不難發(fā)現(xiàn)，在限制條件狀態(tài)空間的控制下，隨機(jī)選取法有時(shí)能夠抽取出一組令用戶(hù)滿意的試題。只不過(guò)由于它隨機(jī)選取試題的范圍太大，無(wú)法確定目前條件下哪些區(qū)域能夠抽取合適的試題，反而可能在那些已經(jīng)證明是無(wú)法抽取合適試題的區(qū)域內(nèi)反復(fù)選題，進(jìn)行大量的無(wú)效操作進(jìn)入死循環(huán)，最終導(dǎo)致組卷失敗�；厮菰囂椒ńM卷成功率高，但它是以犧牲大量的時(shí)間為代價(jià)的，對(duì)于現(xiàn)今越來(lái)越流行的考生網(wǎng)上隨機(jī)即時(shí)調(diào)題的考試過(guò)程來(lái)說(shuō)，它已不符合要求。因此,必須結(jié)合以上兩種方法尋找一種新的改進(jìn)算法，這種算法要具有全局尋優(yōu)和收斂速度快的特點(diǎn)。遺傳算法（Genetic Algorithms）以其具有自適應(yīng)全局尋優(yōu)和智能搜索技術(shù)，并且收斂性好的特性能很好的滿足自動(dòng)考試組卷的要求。
3 遺傳算法描述
遺傳算法是一種并行的、能夠有效優(yōu)化的算法，以Morgan的基因理論及Eldridge 與Gould間斷平衡理論為依據(jù)，同時(shí)融合了Mayr的邊緣物種形成理論和Bertalanffv一般系統(tǒng)理論的一些思想，模擬達(dá)爾文的自然界遺傳學(xué)：繼承（基因遺傳）、進(jìn)化（基因突變）優(yōu)勝劣汰（優(yōu)的基因大量被遺傳復(fù)制，劣的基因較少被遺傳復(fù)制）。其實(shí)質(zhì)就是一種把自然界有機(jī)體的優(yōu)勝劣汰的自然選擇、適者生存的進(jìn)化機(jī)制與同一群體中個(gè)體與個(gè)體間的隨機(jī)信息交換機(jī)制相結(jié)合的搜索算法。運(yùn)用遺傳算法求解問(wèn)題首先需將所要求解的問(wèn)題表示成二進(jìn)制編碼，然后根據(jù)環(huán)境進(jìn)行基本的操作：selection，crossover，mutation……這樣進(jìn)行不斷的所謂“生存選擇”，最后收斂到一個(gè)最適應(yīng)環(huán)境條件的個(gè)體上，得到問(wèn)題的最優(yōu)解。[6,7]
4 遺傳算法應(yīng)用
一般來(lái)說(shuō)，用戶(hù)在自動(dòng)組卷時(shí)會(huì)對(duì)試卷的質(zhì)量提出多方面的要求，如總題量、平均難度、題型比例、章節(jié)比例、重點(diǎn)章節(jié)比例、知識(shí)點(diǎn)的交叉與綜合等，自動(dòng)組卷就應(yīng)最大程度的滿足用戶(hù)的要求。因此，在組卷之前，我們首先為自動(dòng)組卷過(guò)程建立控制指標(biāo)相應(yīng)狀態(tài)空間D，
D的每一行由某一試題的控制指標(biāo)組成，如題號(hào)、題型、章節(jié)、難度等，并且這些屬性指標(biāo)都進(jìn)行編碼表示成二進(jìn)制形式，而每一列是題庫(kù)中的某一指標(biāo)的全部取值。在具體出題時(shí)，考方可能不會(huì)用到所有的指標(biāo)，所以D包含的個(gè)體d_target可以表示為d_request和d_void，d_request表示考方要求的控制指標(biāo)，d_void表示考方不要求的控制指標(biāo)。即
d_target：：=<d_request>：<d_void>
<d_request>：：={0，1}m
<d_void>：：={0，1}n
試題庫(kù)[STK]中的每一道試題在建庫(kù)時(shí)都輸入了相應(yīng)的屬性指標(biāo)。試題模型的產(chǎn)生形式是：
if <data> then
<model>
<data>：：={0，1，#}m
#表示0和1之間的任意一位。
考試自動(dòng)出題的遺傳算法如下：
(1) 根據(jù)考方的出題要求，規(guī)劃狀態(tài)空間庫(kù)D中的數(shù)據(jù)，保留d_request部分，而不要d_void部分，對(duì)其剩余部分進(jìn)行編碼D [1]，D[2]，……D[i]。
(2) 初始化試題庫(kù)[STK]。隨機(jī)從題庫(kù)中抽出一組試題，并進(jìn)行編號(hào)STK[1],STK[2]……STK[j],確定合適的交換概率Pc和變異概率Pm；并定義其適應(yīng)值flexibility[k](k=1,2……j)
flexibility[k]<-0 (k=1,2……j)
(3) 從試題庫(kù)[STK]中取出STK[m](0≤m≤j)與狀態(tài)空間庫(kù)[D]中的指標(biāo)D[n] (0≤n≤i)進(jìn)行匹配。如果STK[m]與D[n]完全匹配，則
flexibility[k]<-flexibility[k]+1
如果不匹配，則有
flexibility[k]<-flexibility[k]+0
(4) 進(jìn)行淘汰選擇，保留具有高適應(yīng)度的試題。即把flexibility[k]為0的STK[m]去掉，這樣就生成了一
個(gè)新的試題模型STK[h]。
(5) 重復(fù)過(guò)程2生成新的試題模型STK[p]。按一定的交換概率Pc從[STK]中隨機(jī)選取模型STK[h]和STK[p]，交換彼此位串中對(duì)應(yīng)的值，產(chǎn)生新的試題模型STK[h]、STK[p]，如
交換前STK[h]=1 1 0 1 0 1 1
STK[p]=0 0 1 1 1 1 0
交換前STK[h]=1 1 1 1 0 1 1
STK[p]=1 1 1 1 1 1 0
(6) 按一定的變異概率從題庫(kù)[STK]中隨機(jī)選出一試題模型STK[h]進(jìn)行基因突變，產(chǎn)生一個(gè)新的試題模型。
(7) 在完成以上選擇、交叉、變異步驟后，產(chǎn)生一個(gè)考試試題模型，按照事先確定的誤差精度對(duì)其進(jìn)行收斂性的判別，當(dāng)其適應(yīng)度高時(shí)，試題組卷成功，轉(zhuǎn)向步驟8，如果其適應(yīng)度低，則轉(zhuǎn)向步驟3繼續(xù)執(zhí)行。
(8) 輸出相應(yīng)的考試試題，組卷結(jié)束。
以上用遺傳算法抽題時(shí)，交換概率Pc和變異概率Pm的確定很重要。Pc
太小使選題工作進(jìn)展緩慢，太大則會(huì)破壞適應(yīng)值高的試題模型。通常規(guī)定其為0.4。同樣，Pm太小就不能產(chǎn)生新的試題模型，太大又會(huì)產(chǎn)生過(guò)多的試題模型。它宜規(guī)定為0.1。
在自動(dòng)選題時(shí)，選題的方式可采用父輩挑選和生存選擇兩種。父輩挑選就是采用不返回隨機(jī)抽樣，它使每個(gè)題目都有被選中的可能；生存選擇采用允許父輩和子代進(jìn)行競(jìng)爭(zhēng)，并讓其中的優(yōu)良者進(jìn)入下一輪競(jìng)爭(zhēng)環(huán)境的二分之一擇優(yōu)選擇。兩種選擇方式共同作用于選題保證了選題的順利完成。在選題的過(guò)程中，哪一道題目被選中是一個(gè)非均勻隨機(jī)事件，其概率依賴(lài)于上一次選題的過(guò)程。
5結(jié)束語(yǔ)
本文利用遺傳算法的全局尋優(yōu)和收斂速度快的特點(diǎn)，結(jié)合隨機(jī)選取法和回溯試探法的優(yōu)點(diǎn)，設(shè)計(jì)了一種用于自動(dòng)組卷的好的算法，使自動(dòng)組卷的成功率和速度都得到了明顯的提高。要使自動(dòng)出題的誤差精度和收斂速度進(jìn)一步得到改進(jìn)，還需要做出更深的研究。
參考文獻(xiàn)
[1] J．H．Holland ，Adaptation in natural and artificial systems[M]，Ann arbor: University of Michigen press,1975.
[2] Hamilton M A. Java and the Shift to Net-centric Computing. IEEE Computer, 29(8),1996.
[3] 袁富宇等，多目標(biāo)相關(guān)分類(lèi)的算法，浙江大學(xué)學(xué)報(bào)，33(3),1999
[4] 張師超 蔣運(yùn)承 ，模糊數(shù)據(jù)庫(kù)中近似相等的研究，計(jì)算機(jī)科學(xué)，25(6),1998.
[5] 余建橋，預(yù)測(cè)模型獲取的遺傳算法研究，計(jì)算機(jī)科學(xué)，25(2),1998.
【遺傳算法在試題組卷中的應(yīng)用】相關(guān)文章：
2012年中考應(yīng)用文試題分類(lèi)解析08-15
"試題組合"在化學(xué)習(xí)題教學(xué)中的應(yīng)用策略分析08-25
比法在物理中的應(yīng)用08-17
生活中的化學(xué)在教學(xué)中的應(yīng)用08-23
CAI在“光的反射”中的應(yīng)用08-17