計算機輔助考試中的遺傳算法

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

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

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

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

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

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

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

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

9、從題庫中抽出一組試題，并進行編號STK1,STK2STKj,確定合適的交換概率Pc和變異概率Pm；并定義其適應值flexibilityk(k=1,2j) flexibilityk<-0 (k=1,2j) (3) 從試題庫STK中取出STKm(0mj)與狀態(tài)空間庫D中的指標Dn (0ni)進行匹配。如果STKm與Dn完全匹配，則 flexibilityk<-flexibilityk+1 如果不匹配，則有 flexibilityk<-flexibilityk+0 (4) 進行淘汰選擇，保留具有高適應度的試題。即把flexibilityk為0的STKm去掉，這樣就生成了一個新的試題

10、模型STKh。 (5) 重復過程2生成新的試題模型STKp。按一定的交換概率Pc從STK中隨機選取模型STKh和STKp，交換彼此位串中對應的值，產(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進行基因突變，產(chǎn)生一個新的試題模型。 (7) 在完成以上選擇、交叉、變異步驟后，產(chǎn)生一個考試試題模型，按照事先確定的誤差精度對其進行收斂性的判別，當其適應度高時，試題組卷成功，轉向步驟8

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