自動組卷中簡單遺傳算法的應用

劉召華?李建良

摘 要：隨著計算機技術的發展，利用計算機存儲大量的試題信息并結合數據庫技術實現試題的自動組卷功能已成為一項實際可行且應用性廣泛的課題。本文就試題組卷遺傳算法進行了論述和總結。

關鍵詞：自動組卷；遺傳算法；試題庫

隨著信息技術不斷發展，傳統考試方式已經不能適應現代化考試需求，設計開發和應用計算機考試管理系統成為現代教育教學改革的一項重要任務。計算機技術不斷發展，并結合現有成熟的數據庫技術，為計算機考試管理系統開發提供了可靠保證。考試管理系統設計中，建立一個好的試題庫尤為重要，而良好的組卷方法卻是核心。如何保證生成的試卷能最大程度地滿足用戶的不同需求，并具有隨機性、科學性、合理性；尤其在交互環境下，對組卷速度要求較高，而一個在理論上能搜索到全局最優的算法可能會以犧牲時間為代價，往往達不到預期的效果。因此，選擇一個高效、科學的算法是自動組卷的關鍵。以往具有自動組卷功能的考試系統大多采用隨機選取法和回溯試探法。在限制條件狀態空間的控制下，隨機選取法有時能夠抽取出一組令用戶滿意的試題，但由于它隨機選取試題的范圍太大，有可能在無法抽取合適試題的區域內反復選題，進入死循環，最終導致組卷失敗。回溯試探法組卷成功率高，卻以犧牲大量的時間為代價。遺傳算法（Genetic Algorithms）以其全局尋優和智能搜索技術，及收斂性好的特性能很好地滿足自動組卷的要求。

1. 遺傳算法原理

遺傳算法（Genetic Algorithm，GA）是模擬自然界自然選擇遺傳機制進行搜索尋優的方法，通過模擬生物在染色體層面的各種遺傳優化作用而設計人工尋優方法，GA本質上是一個群體迭代過程，從一個隨機的初始群體出發，依據優勝劣汰原則.通過競爭、選擇、繁衍、變異等遺傳操作，產生性能更優的下一代群體。直到滿足環境約束的優良體或合乎具體的應用準則為止。遺傳算法的這種特點使其很適合解決多重條件最優解的問題。

2. 組卷問題的數學模型建立

通過實際組卷分析，組卷約束條件主要有知識點，題型，章節，認知層次，題量，分值，答題時間，難度，區分度，曝光度等10個方面。根據對上述組卷約束條件的分析，可以構建組卷問題的數學模型。由于一張試卷存在10個約束變量，所以針對于整個試卷所有的題目構成了一個10維度變量的空間：知識點，題型，章節，認知層次，題量，分值，答題時間，難度，區分度，曝光度。為了減小組卷算法的復雜度，提高組卷算法的效率，需要對這個10維空間進行化簡處理。一般而言，要出一份試卷，我們總是先確定試題難度、試卷的滿分值和所用的題型以及各種題型的題目和分數以及知識點分布，而且對一種考試而言，這種難度分布常保持相對穩定。不同難度試題的分數分布通常成正態分布，我們可以根據難度系數、各知識點分數、各題型分數來約束將要被選中的試題個數以及試題難度分布，計算出不同難度級別的題目在試卷中所占的比例。再結合各知識點、各題型的分數在試卷中所占的比例，可將10維空間簡化為一個5維的空間——試卷（知識點，章節，題型，分值，難度），在這個5維空間里對試題進行操作來完成組卷。不同的計算機系統通常采用不同的二進制文件格式。

3. 遺傳算法在自動組卷中的應用

遺傳算法模擬達爾文的自然界遺傳學：繼承（基因遺傳）、進化（基因突變）和優勝劣汰（優的基因大量被遺傳復制，劣的基因較少被遺傳復制）。其實質就是一種把自然界有機體優勝劣汰的自然選擇、適者生存的進化機制與同一群體中個體與個體間的隨機信息交換機制相結合的搜索算法。運用遺傳算法求解問題，首先需將所要求解的問題表示成二進制編碼，然后根據環境循環進行基本的操作：selection（選擇）、crossover（交叉）、mutation（變異），最后收斂到一個最適應環境條件的個體上，得到問題的最優解。算法步驟如下：

（1）染色體的編碼：假設試題庫中有m道題，可用一個m位的二進制串來表示，形式為：a1，a2，a3 ，...am，，其中若ai為1，則表示該題被選中；若ai 為0，則表示該題未被選中，即ai=1，第i道題被選中；ai=0，第i道題未被選中。

（2）初始化群體：通過隨機的方法生成初始化的串群體，在串群體中，串的長度是相同的，群體的大小按需要根據經驗或實驗給出。

（3）計算當前種群每個個體的目標函數：本問題的目標函數可定義為

F=

Fi表示第i個屬性指標與用戶要求的誤差的絕對值，Wi表示第i個指標對組卷重要程度的權值，F是所有指標與用戶要求的誤差絕對值之和。該目標函數越大，則適應度越小，被淘汰的概率越大。

（4）選擇：按照一定的選擇概率對種群進行復制，選擇較好的串生成下一代（個體的適應度函數值越大，該串的性能越好，選擇概率越大），去掉較差的串。

（5）交叉：交叉是兩個串按照一定的概率（交叉概率P ），從某一位開始逐位互換。首先，對每個二進制串產生一個0～1范圍內的隨機數；若該數小于P ，則選擇該串進行交叉，否則不予選擇。然后隨機地對被選擇的二進制串進行配對，并根據二進制串的長度 ，隨機產生交叉位置i，i為[1，n-1]上的一個整數。

（6）變異：變異是二進制串的某一位按照一定的概率（突變概率Pm）發生反轉，1變為0，0變為1。這里Pm 較小，Pm 可小于0.001。但在實踐中發現，在有些遺傳算子中，Pm為0.1時更好。

（7）終止：記錄進化的代數，并判斷是否滿足終止條件。若滿足，則輸出結果，否則轉向步驟3繼續執行。終止條件如下：（a）出現種群滿足F=0；（b）某個個體目標函數值（個體適應度值）達到指定要求；（c）達到指定的進化代數；（d）當前種群中最大目標函數值與以前各代中最大目標函數值相差不大，進化效果不顯著。

遺傳算法在試題組卷中的應用可以將教師從繁重的考試出卷等工作中解放出來，最大限度地減少人為因素在組卷過程中的影響，最大程度地實現了組卷的自動化，有效提高試卷的質量。我們也可以對簡單遺傳算法改進，利用組卷過程中的誤差對遺傳算法中的隨機性選擇進行誘導，保證產生的新個體的誤差相比對于同一個體的其他信息位的變異所產生的新個體而言，產生的誤差最小。理論分析與實驗結果表明，基于遺傳算法的試題組卷算法具有較好的智能組卷性能。

參考文獻

1.王小平.《遺傳算法——理論、應用與軟件實現》西安交通大學出版社，2002

2.張文修，梁怡.《遺傳算法的數學基礎》西安交通大學出版社，2003

3.樂光學，彭小寧，曾志峰.試題庫自動組卷系統的算法與實現，計算機應用，2001；21（8）：198-200

4.孫勇，柏云.基于遺傳算法的試題組卷策略.淄博學院學報（自然科學版），2002；（3）：27—28

5.劉彬，李勇，糜長軍.智能組卷系統中專家知識的表示與實現.計算機工程與應用，2002；38（17）：229— 231

6.王慧，劉寶坤，曹明，等.一種改進遺傳算法及應用.天津理工學院學報，1998；14（4）：62—65