一種自動組卷算法的實現

摘要：結合遺傳算法的原理和思想，對考試自動出題組卷的問題進行了深入的研究，找到了一種獲得與考試試題控制指標符合的試題模型的解決方法。

關鍵詞：遺傳算法；全局尋優；自動化組卷

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)26-1718-02

An Algorithm of Exam Paper's Auto-design

MEI Bing-fu

(Guangzhou Radio TV University， Guangzhou 510091， China)

Abstract: After the fully investigation to the problem we are facing in test paper’s auto-design， a algorithm based on genetic algorithm is created to solve the problem， which can make the test paper generated by auto-design meets the standards of teachers and can be modified easily.

Key words: Genetic Algorithm; global optimization; auto-design of exam paper

1 引言

計算機輔助考試系統的自動組卷的效率與質量完全取決于抽題算法的設計。如何設計一個算法從題庫中既快又好的抽出一組最佳解或是抽出一組非常接近最佳解的實體，涉及到一個全局尋優和收斂速度快慢的的問題，很多學者對其進行了研究。遺傳算法以其自適應尋優及良好的智能搜索技術，受到了廣泛的運用。通過理論推導和事實運用，發現遺傳算法在尋優和收斂性方面都是非常有效的。

2 問題描述

自動組卷是考試系統自動化或半自動化操作的核心目標之一，而如何保證生成的試卷能最大程度的滿足用戶的不同需要，并具有隨機性、科學性、合理性，這是實現中的一個難點。尤其在交互式環境下用戶對于組卷速度要求較高，而一個理論上較完美的算法可能會以犧牲時間作為代價，往往不能達到預期的效果。因此，選擇一個高效、科學、合理的算法是自動組卷的關鍵。

以往的具有自動組卷功能的考試系統大多采用隨機選取法和回溯試探法。隨機選取法根據狀態空間的控制指標，由計算機隨機的抽取一道試題放入試題庫，此過程不斷重復，直到組卷完畢，或已無法從題庫中抽取滿足控制指標的試題為止。該方法結構簡單，對于單道題的抽取運行速度較快，但是對于整個組卷過程來說組卷成功率低，即使組卷成功，花費時間也令人難以忍受。尤其是當題庫中各狀態類型平均出題量較低時，組卷往往以失敗而告終。

回溯試探法是將隨機選取法產生的每一狀態類型紀錄下來，當搜索失敗時釋放上次紀錄的狀態類型，然后再依據一定的規律（正是這種規律破壞了選取試題的隨機性）變換一種新的狀態類型進行試探，通過不斷的回溯試探直到試卷生成完畢或退回出發點為止，這種有條件的深度優先算法，對于狀態類型和出題量都較少的題庫系統而言，組卷成功率較好，但是在實際應用時發現這種算法對內存的占用量很大，程序結構相對比較復雜，而且選取試題缺乏隨機性，組卷時間長，后兩點是用戶無法接受的，因此它也不是一種很好的自動組卷算法。

分析上述兩種算法的優缺點，不難發現，在限制條件狀態空間的控制下，隨機選取法有時能夠抽取出一組令用戶滿意的試題。只不過由于它隨機選取試題的范圍太大，無法確定目前條件下哪些區域能夠抽取合適的試題，反而可能在那些已經證明是無法抽取合適試題的區域內反復選題，進行大量的無效操作進入死循環，最終導致組卷失敗。回溯試探法組卷成功率高，但它是以犧牲大量的時間為代價的，對于現今越來越流行的考生網上隨機即時調題的考試過程來說，它已不符合要求。因此，必須結合以上兩種方法尋找一種新的改進算法，這種算法要具有全局尋優和收斂速度快的特點。遺傳算法（GeneticAlgorithms）以其具有自適應全局尋優和智能搜索技術，并且收斂性好的特性能很好的滿足自動考試組卷的要求。

3 遺傳算法描述

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

4 遺傳算法應用

一般來說，用戶在自動組卷時會對試卷的質量提出多方面的要求，如總題量、平均難度、題型比例、章節比例、重點章節比例、知識點的交叉與綜合等，自動組卷就應最大程度的滿足用戶的要求。因此，在組卷之前，首先要為自動組卷過程建立控制指標相應狀態空間D，D=[]。

D的每一行由某一試題的控制指標組成，如題號、題型、章節、難度等，并且這些屬性指標都進行編碼表示成二進制形式，而每一列是題庫中的某一指標的全部取值。在具體出題時，考方可能不會用到所有的指標，所以D包含的個體d_target可以表示為d_request和d_void，d_request表示考方要求的控制指標，d_void表示考方不要求的控制指標。即：

d_target：：=＜d_request＞：＜d_void＞

＜d_request＞：：={0，1}m

＜d_void＞：：={0，1}n

試題庫[STK]中的每一道試題在建庫時都輸入了相應的屬性指標。試題模型的產生形式是：

if＜data＞then

＜model＞

＜data＞：：={0，1，#}m

#表示0和1之間的任意一位。

考試自動出題的遺傳算法如下：

1）根據考方的出題要求，規劃狀態空間庫D中的數據，保留d_request部分，而不要d_void部分，對其剩余部分進行編碼D[1]，D[2]，……D[i]。

2）初始化試題庫[STK]。隨機從題庫中抽出一組試題，并進行編號STK[1]，STK[2]……STK[j]，確定合適的交換概率Pc和變異概率Pm；并定義其適應值flexibility[k](k=1，2……j)。

3）從試題庫[STK]中取出STK[m](0≤m≤j)與狀態空間庫[D]中的指標D[n](0≤n≤i)進行匹配。如果STK[m]與D[n]完全匹配，則：flexibility[k]＜-flexibility[k]+1。如果不匹配，則有：flexibility[k]＜-flexibility[k]+0。

4) 進行淘汰選擇，保留具有高適應度的試題。即把flexibility[k]為0的STK[m]去掉，這樣就生成了一個新的試題模型STK[h]。

5) 重復過程2生成新的試題模型STK[p]。按一定的交換概率Pc從[STK]中隨機選取模型STK[h]和STK[p]，交換彼此位串中對應的值，產生新的試題模型STK[h]、STK[p]，如交換前STK[h]=1101011，STK[p]=0011110，交換前STK[h]=1111011，STK[p]=1111110。

6) 按一定的變異概率從題庫[STK]中隨機選出一試題模型STK[h]進行基因突變，產生一個新的試題模型。

7) 在完成以上選擇、交叉、變異步驟后，產生一個考試試題模型，按照事先確定的誤差精度對其進行收斂性的判別，當其適應度高時，試題組卷成功，轉向步驟8，如果其適應度低，則轉向步驟3繼續執行。

8) 輸出相應的考試試題，組卷結束。

以上用遺傳算法抽題時，交換概率Pc和變異概率Pm的確定很重要。Pc 太小使選題工作進展緩慢，太大則會破壞適應值高的試題模型，通常規定其為0.4。同樣，Pm太小就不能產生新的試題模型，太大又會產生過多的試題模型。它宜規定為0.1。

在自動選題時，選題的方式可采用父輩挑選和生存選擇兩種。父輩挑選就是采用不返回隨機抽樣，它使每個題目都有被選中的可能；生存選擇采用允許父輩和子代進行競爭，并讓其中的優良者進入下一輪競爭環境的二分之一擇優選擇。兩種選擇方式共同作用于選題保證了選題的順利完成。在選題的過程中，哪一道題目被選中是一個非均勻隨機事件，其概率依賴于上一次選題的過程。

5 結束語

本文利用遺傳算法的全局尋優和收斂速度快的特點，結合隨機選取法和回溯試探法的優點，設計了一種用于自動組卷的算法，使自動組卷的成功率和速度都得到了明顯的提高，為自動化考試系統的設計提供有益的參考。

參考文獻：

[1] Holland J H.Adaptationinnaturalandartificialsystems[M].Annarbor:University of Michigen press，1995.

[2] Hamilton M A.Java and the shift to Net-Centric Computing[J]. IEEE Computer，1996，29(8):31-39

[3] 袁富宇.多目標相關分類的算法[J].浙江大學學報，2001，33(3):178-180.

[4] 張師超，蔣運承.模糊數據庫中近似相等的研究[J].計算機科學，2004，25(6):83-85.

[5] 余建橋.預測模型獲取的遺傳算法研究[J].計算機科學，2005，25(2):51-52.