計(jì)算機(jī)輔助考試中的遺傳算法

1、計(jì)算機(jī)輔助考試中的遺傳算法    摘要： 本文運(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)行

2、了論述；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)之一,而如何保證生成的試卷能最大程度的滿足用戶的不同需要,并具有隨機(jī)性、 科學(xué) 性、合理性,這是實(shí)現(xiàn)中的一個(gè)難點(diǎn)。尤其在交互式環(huán)境下用戶對(duì)于組卷速度要求較高，而一個(gè)理論上較完美的算

3、法可能會(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)類型平均出題量較低時(shí)，組卷往往以失敗而告終。 回溯試探法這是將隨機(jī)選取法產(chǎn)生的每一狀態(tài)類型紀(jì)錄下來(lái)，當(dāng)搜索失敗時(shí)釋放上次紀(jì)錄的狀態(tài)類型，然后

4、再依據(jù)一定的 規(guī)律 （正是這種規(guī)律破壞了選取試題的隨機(jī)性）變換一種新的狀態(tài)類型進(jìn)行試探，通過(guò)不斷的回溯試探直到試卷生成完畢或退回出發(fā)點(diǎn)為止，這種有條件的深度優(yōu)先算法，對(duì)于狀態(tà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)是用戶無(wú)法接受的，因此它也不是一種很好的用來(lái)自動(dòng)組卷的算法。 分析 上述兩種算法的優(yōu)缺點(diǎn)，不難發(fā)現(xiàn)，在限制條件狀態(tài)空間的控制下，隨機(jī)選取法有時(shí)能夠抽取出一組令用戶滿意的試題。只不過(guò)由于它隨機(jī)選取試題的范圍太大，無(wú)法確定 目前 條件下哪些區(qū)域能夠抽取合適的

5、試題，反而可能在那些已經(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間斷平衡理論為依

6、據(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)用

7、一般來(lái)說(shuō)，用戶在自動(dòng)組卷時(shí)會(huì)對(duì)試卷的質(zhì)量提出多方面的要求，如總題量、平均難度、題型比例、章節(jié)比例、重點(diǎn)章節(jié)比例、知識(shí)點(diǎn)的交叉與綜合等，自動(dòng)組卷就應(yīng)最大程度的滿足用戶的要求。因此，在組卷之前，我們首先為自動(dòng)組卷過(guò)程建立控制指標(biāo)相應(yīng)狀態(tài)空間D， 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_

8、target：=<d_request>：<d_void><d_request>：=0，1m<d_void>：=0，1n 試題庫(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，D2，Di。 (2) 初始化試題庫(kù)STK。隨機(jī)

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

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

11、，如果其適應(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ī)事件，其概率依賴于上一次選題的過(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 JHHolland ，Adaptation in natural and artificial systemsM，Ann arbor: University of Michigen press,1975. 2 Hamilton M A. Java