遺傳算法試題組卷

1、遺傳算法試題組卷    摘要： 本文運用遺傳算法的全局尋優(yōu)對考試中的自動化組卷進(jìn)行了研究，并得到了一個解決適合考方要求的試題模型的好的算法。 關(guān)鍵詞：遺傳算法 全局尋優(yōu) 自動化組卷 1 引言 計算機輔助考試系統(tǒng)的自動組卷的效率與質(zhì)量完全取決于抽題算法的設(shè)計。如何設(shè)計一個算法從題庫中既快又好的抽出一組最佳解或是抽出一組非常接近最佳解的實體，涉及到一個全局尋優(yōu)和收斂速度快慢的的問題，很多學(xué)者對其進(jìn)行了研究。遺傳算法以其自適應(yīng)尋優(yōu)及良好的智能搜索技術(shù)，受到了廣泛的運用。Potts J C等人基于變異和人工選擇的遺傳算法對最優(yōu)群體規(guī)模進(jìn)行了論述；Hamilton

2、 M A等結(jié)合遺傳算法把其運用到神經(jīng)網(wǎng)絡(luò)中，并取得了良好的效果4；也有眾多的學(xué)者對保留最佳狀態(tài)的遺傳算法的收斂速度做了討論。通過理論推導(dǎo)和事實運用，發(fā)現(xiàn)遺傳算法在尋優(yōu)和收斂性方面都是非常有效的。 本文結(jié)合遺傳算法的原理和思想，對考試自動出題組卷的問題進(jìn)行了研究，找到了一種獲得與考試試題控制指標(biāo)符合的試題模型的解決方法。 2 問題描述 自動組卷是考試系統(tǒng)自動化或半自動化操作的核心目標(biāo)之一,而如何保證生成的試卷能最大程度的滿足用戶的不同需要,并具有隨機性、科學(xué)性、合理性,這是實現(xiàn)中的一個難點。尤其在交互式環(huán)境下用戶對于組卷速度要求較高，而一個理論上較完美的算法可能會以犧牲時間作為代價，往往不能達(dá)到

3、預(yù)期的效果。因此，選擇一個高效、科學(xué)、合理的算法是自動組卷的關(guān)鍵。 以往的具有自動組卷功能的考試系統(tǒng)大多采用隨機選取法和回溯試探法。隨機選取法根據(jù)狀態(tài)空間的控制指標(biāo)，由計算機隨機的抽取一道試題放入試題庫，此過程不斷重復(fù)，直到組卷完畢，或已無法從題庫中抽取滿足控制指標(biāo)的試題為止。該方法結(jié)構(gòu)簡單，對于單道題的抽取運行速度較快，但是對于整個組卷過程來說組卷成功率低，即使組卷成功，花費時間也令人難以忍受。尤其是當(dāng)題庫中各狀態(tài)類型平均出題量較低時，組卷往往以失敗而告終。 回溯試探法這是將隨機選取法產(chǎn)生的每一狀態(tài)類型紀(jì)錄下來，當(dāng)搜索失敗時釋放上次紀(jì)錄的狀態(tài)類型，然后再依據(jù)一定的規(guī)律（正是這種規(guī)律破壞了選取

4、試題的隨機性）變換一種新的狀態(tài)類型進(jìn)行試探，通過不斷的回溯試探直到試卷生成完畢或退回出發(fā)點為止，這種有條件的深度優(yōu)先算法，對于狀態(tài)類型和出題量都較少的題庫系統(tǒng)而言，組卷成功率較好，但是在實際到一個應(yīng)用時發(fā)現(xiàn)這種算法對內(nèi)存的占用量很大，程序結(jié)構(gòu)相對比較復(fù)雜，而且選取試題缺乏隨機性，組卷時間長，后兩點是用戶無法接受的，因此它也不是一種很好的用來自動組卷的算法。 分析上述兩種算法的優(yōu)缺點，不難發(fā)現(xiàn)，在限制條件狀態(tài)空間的控制下，隨機選取法有時能夠抽取出一組令用戶滿意的試題。只不過由于它隨機選取試題的范圍太大，無法確定目前條件下哪些區(qū)域能夠抽取合適的試題，反而可能在那些已經(jīng)證明是無法抽取合適試題的區(qū)域內(nèi)

5、反復(fù)選題，進(jìn)行大量的無效操作進(jìn)入死循環(huán)，最終導(dǎo)致組卷失敗?；厮菰囂椒ńM卷成功率高，但它是以犧牲大量的時間為代價的，對于現(xiàn)今越來越流行的考生網(wǎng)上隨機即時調(diào)題的考試過程來說，它已不符合要求。因此,必須結(jié)合以上兩種方法尋找一種新的改進(jìn)算法，這種算法要具有全局尋優(yōu)和收斂速度快的特點。遺傳算法（Genetic Algorithms）以其具有自適應(yīng)全局尋優(yōu)和智能搜索技術(shù)，并且收斂性好的特性能很好的滿足自動考試組卷的要求。 3 遺傳算法描述 遺傳算法是一種并行的、能夠有效優(yōu)化的算法，以Morgan的基因理論及Eldridge 與Gould間斷平衡理論為依據(jù)，同時融合了Mayr的邊緣物種形成理論和Bertal

6、anffv一般系統(tǒng)理論的一些思想，模擬達(dá)爾文的自然界遺傳學(xué)：繼承（基因遺傳）、進(jìn)化（基因突變）優(yōu)勝劣汰（優(yōu)的基因大量被遺傳復(fù)制，劣的基因較少被遺傳復(fù)制）。其實質(zhì)就是一種把自然界有機體的優(yōu)勝劣汰的自然選擇、適者生存的進(jìn)化機制與同一群體中個體與個體間的隨機信息交換機制相結(jié)合的搜索算法。運用遺傳算法求解問題首先需將所要求解的問題表示成二進(jìn)制編碼，然后根據(jù)環(huán)境進(jìn)行基本的操作：selection，crossover，mutation這樣進(jìn)行不斷的所謂“生存選擇”，最后收斂到一個最適應(yīng)環(huán)境條件的個體上，得到問題的最優(yōu)解。6,74 遺傳算法應(yīng)用 一般來說，用戶在自動組卷時會對試卷的質(zhì)量提出多方面的要求，如總

7、題量、平均難度、題型比例、章節(jié)比例、重點章節(jié)比例、知識點的交叉與綜合等，自動組卷就應(yīng)最大程度的滿足用戶的要求。因此，在組卷之前，我們首先為自動組卷過程建立控制指標(biāo)相應(yīng)狀態(tài)空間D， D= D的每一行由某一試題的控制指標(biāo)組成，如題號、題型、章節(jié)、難度等，并且這些屬性指標(biāo)都進(jìn)行編碼表示成二進(jìn)制形式，而每一列是題庫中的某一指標(biāo)的全部取值。在具體出題時，考方可能不會用到所有的指標(biāo)，所以D包含的個體d_target可以表示為d_request和d_void，d_request表示考方要求的控制指標(biāo)，d_void表示考方不要求的控制指標(biāo)。即 d_target：=<d_request>：<d

8、_void><d_request>：=0，1m<d_void>：=0，1n 試題庫STK中的每一道試題在建庫時都輸入了相應(yīng)的屬性指標(biāo)。試題模型的產(chǎn)生形式是： if <data> then<model><data>：=0，1，#m #表示0和1之間的任意一位。 考試自動出題的遺傳算法如下： (1) 根據(jù)考方的出題要求，規(guī)劃狀態(tài)空間庫D中的數(shù)據(jù)，保留d_request部分，而不要d_void部分，對其剩余部分進(jìn)行編碼D 1，D2，Di。 (2) 初始化試題庫STK。隨機從題庫中抽出一組試題，并進(jìn)行編號STK1,STK2STKj,確定

9、合適的交換概率Pc和變異概率Pm；并定義其適應(yīng)值flexibilityk(k=1,2j) flexibilityk<-0 (k=1,2j) (3) 從試題庫STK中取出STKm(0mj)與狀態(tài)空間庫D中的指標(biāo)Dn (0ni)進(jìn)行匹配。如果STKm與Dn完全匹配，則 flexibilityk<-flexibilityk+1 如果不匹配，則有 flexibilityk<-flexibilityk+0 (4) 進(jìn)行淘汰選擇，保留具有高適應(yīng)度的試題。即把flexibilityk為0的STKm去掉，這樣就生成了一個新的試題模型STKh。 (5) 重復(fù)過程2生成新的試題模型STKp。按一

10、定的交換概率Pc從STK中隨機選取模型STKh和STKp，交換彼此位串中對應(yīng)的值，產(chǎn)生新的試題模型STKh、STKp，如 交換前STKh=1 1 0 1 0 1 1 STKp=0 0 1 1 1 1 0 交換前STKh=1 1 1 1 0 1 1 STKp=1 1 1 1 1 1 0 (6) 按一定的變異概率從題庫STK中隨機選出一試題模型STKh進(jìn)行基因突變，產(chǎn)生一個新的試題模型。 (7) 在完成以上選擇、交叉、變異步驟后，產(chǎn)生一個考試試題模型，按照事先確定的誤差精度對其進(jìn)行收斂性的判別，當(dāng)其適應(yīng)度高時，試題組卷成功，轉(zhuǎn)向步驟8，如果其適應(yīng)度低，則轉(zhuǎn)向步驟3繼續(xù)執(zhí)行。 (8) 輸出相應(yīng)的考試

11、試題，組卷結(jié)束。 以上用遺傳算法抽題時，交換概率Pc和變異概率Pm的確定很重要。Pc 太小使選題工作進(jìn)展緩慢，太大則會破壞適應(yīng)值高的試題模型。通常規(guī)定其為0.4。同樣，Pm太小就不能產(chǎn)生新的試題模型，太大又會產(chǎn)生過多的試題模型。它宜規(guī)定為0.1。 在自動選題時，選題的方式可采用父輩挑選和生存選擇兩種。父輩挑選就是采用不返回隨機抽樣，它使每個題目都有被選中的可能；生存選擇采用允許父輩和子代進(jìn)行競爭，并讓其中的優(yōu)良者進(jìn)入下一輪競爭環(huán)境的二分之一擇優(yōu)選擇。兩種選擇方式共同作用于選題保證了選題的順利完成。在選題的過程中，哪一道題目被選中是一個非均勻隨機事件，其概率依賴于上一次選題的過程。 5結(jié)束語 本文利用遺傳算法的全局尋優(yōu)和收斂速度快的特點，結(jié)合隨機選取法和回溯試探法的優(yōu)點，設(shè)計了一種用于自動組卷的好的算法，使自動組卷的成功率和速度都得到了明顯的提高。要使自動出題的誤差精度和收斂速度進(jìn)一步得到改進(jìn)，還需要做出更深的研究。 參考文獻(xiàn) 1 JHHolland ，Adaptation in natural and artificial systemsM，Ann arbor: University of Michigen press,1975. 2 Hamilton M A. Ja