遺傳算法的組卷策略研究

摘要：通過組卷來決定試卷的題量、試卷的知識點分布、試卷類型及考試時間的多少；網絡組卷系統是實現考試規范化、公平化、合理化的重要途徑。運用遺傳算法對考試中的自動化組卷進行了研究。

關鍵詞：遺傳算法；組卷策略；研究

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)05-00ppp-0c

1 引言

自動組卷是考試系統自動化或半自動化操作的核心目標之一。選擇一個高效、科學、合理的算法是自動組卷的關鍵。以往具有自動組卷功能的考試系統大多采用隨機選取法和回溯試探法。在隨機選取法下，可能會出現在那些已經證明是無法抽取合適試題的區域內反復選題，進行大量的無效操作進入死循環，最終導致組卷失敗。盡管回溯試探法組卷成功率高，但它是以犧牲大量的時間為代價的，對于考生網上隨機即時調題的考試過程來說，也不能滿足要求。因此，必須結合以上兩種方法尋找一種新的改進算法，這種算法要具有全局尋優和收斂速度快的特點。遺傳算法以其具有自適應全局尋優和智能搜索技術，并且收斂性好的特性能很好的滿足自動組卷的要求。

2 遺傳算法描述

遺傳算法（Genetic Algorithm，縮寫為GA）是一種有效的解決最優化問題的方法。它最先是由John Holland于1975年提出的。從那以后，它逐漸發展成為一種通過模擬自然進化過程解決最優化問題的計算模型。

2.1 特點

2.1.1 GA是對問題參數的編碼組進行，而不是直接對參數本身

2.1.2 GA的搜索是從問題解的編碼組開始搜索，而不是從單個解開始

2.1.3 GA使用目標函數值（適應度）這一信息進行搜索，而不需導數等其他信息

2.1.4 GA算法使用的選擇、交叉、變異這三個算子都是隨機操作，而不是確定規則

2.2遺傳算法包含6個基本要素

2.2.1 參數編碼：由于遺傳算法不能直接處理解空間的解數據，因此必須通過編碼將它們表示成遺傳空間的基因型串結構數據

2.2.2 生成初始群體：由于遺傳算法的群體型操作需要，所以必須為遺傳操作準備一個由若干初始解組成的初始群體。初始群體的每個個體都是通過隨機方法產生的

2.2.3 適應度評估檢測：遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用適應度（fitness）值來評估個體或解的優劣，并作為以后遺傳操作的依據

2.2.4 選擇（selection）：選擇或復制操作是為了從當前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。個體適應度越高，其被選擇的機會就越多。本文采用與適應度成比例的概率方法進行選擇。具體地說，就是首先計算群體中所有個體適應度的總和（∑f），再計算每個個體的適應度所占的比例（fi/∑f），并以此作為相應的選擇概率ps。

2.2.5 交叉操作：交叉操作是遺傳算法中最主要的遺傳操作。簡單的交叉（即一點交叉）可分兩步進行：首先對種群中個體進行隨機配對；其次，在配對個體中隨機設定交叉處，配對個體彼此交換部分信息

2.2.6 變異：變異操作是按位（bit）進行的，即把某一位的內容進行變異。變異操作同樣也是隨機進行的。一般而言，變異概率ｐｍ都取得較小。變異操作是十分微妙的遺傳操作，它需要和交叉操作配合使用，目的是挖掘群體中個體的多樣性，克服有可能限于局部解的弊病

3 組卷策略

自動組卷就是預先定義一組衡量試卷優劣的指標，在組織試卷時，用戶根據自己的組卷要求，對這些指標提出一定的要求，組織模塊按照一定算法從題庫中挑選試題組成試卷，使其各項指標的實際值與教師提出的目標值盡可能的接近，最大限度地滿足用戶的需求。

組卷要求包括了覆蓋面大，重點突出，各章節分數頒布均衡，各題型分數分布合適，難度符合目的，總分、總時符合要求，以及考察知識點不相重復等多項層次不同的要求。

3.1 較為抽象的組卷要求必須明確化

3.1.1 根據教師常見的“要求”設置試卷指標，用來數量化衡量一張試卷

3.1.2 通過給各項指標設置權重，或將其劃分到不同重要性等級的方法，反映出特定考試中教師對各項指標的不同重視程度

3.1.3 組卷時讓教師對這些預定指標提出希望值，然后系統據此選題組卷

3.2建立試題庫結構必須考慮試題本身固有的特性參數

這些參數主要有考查點所屬的范圍、題型、難度系數、區分度、考試時間等。題型有判斷、單選、多選、填空、論述、分析、計算、案例分析等。為了考核學生對知識的掌握情況，每道試題主要設置如下屬性：

3.2.1 考查點所屬的范圍

考查點所屬的范圍是指試題內容所屬的章節。它涉及試題的具體考核內容。知識點的劃分可以將某一課程按章節或內容一層一層從上到下細化確定，一般可劃分為章、節、點3個層次，每個考查點的劃分由編碼字符組成，編碼由系統按層次結構自動生成。教師在錄入知識點時，按課程的章節結構逐層往下深入，首先錄入課程的章，然后對每個章分配節，最后在每個節次中布置考查點。教師在編輯試題是選擇相應的考查點。試題的內容盡量覆蓋該課程的各個章節，且各章內容根據教學大綱的安排，合理分配試題所占的比重。

3.2.2 題型

題型是指試題的題型。試題的題型包括客觀性試題和主觀性試題。客觀性試題主要是知識性的的試題，包括：單項選擇、多項選擇、判斷、填空、改錯和填圖，主要考查學生對基礎知識的理解；主觀性試題主要是能力性試題，包括：名詞解釋、簡答、論述、分析、計算、證明、作文、案例分析和作圖等等，主要考查學生的思維水平能力、分析運算能力和語言表達能力。

3.2.3 難度系數

難度系數是指在試卷命題過程中，針對不同考試對象、不同階段的考試，命題難度也不同。試題難度系數定義為 s=1-(平均分/ 該項滿分)。難度系數是試題難易程度的指標，它由教師錄入試題時給定。難度系數一般分為較易、中難、較難、難度大四個級別。

3.2.4 區分度

區分度是指試題對考生的水平鑒別和區分程度的指標。為了估計區分度，我們將考生分成高分組和低分組兩個組，分別統計高分組和低分組的得分率，我們把區分度定義為：區分度=高分組的得分率-低分組的得分率。

3.2.5 考試時間

考試時間是由學校教務統一指定。

3.2.6 卷面總分

卷面總分是由學校教務統一指定。

3.2.7 認知分類

反映試題對教學內容的要求層次和對學生學習能力的培養。

根據用戶輸入的試卷總體要求，然后分別匹配試卷的知識分布、題型分布、認知分類分布、難度分布、區分度分布、時間分布、分數分布，形成組卷參數表，然后根據該參數表從試題庫中選題。組成一份 n 道題的試卷就是從試題庫中抽取 n 道題，組成一個 n ×7 的矩陣，矩陣中的每一列代表一個屬性，每一行代表一道題。即

M =

S11 S12 S13 S14 S15 S16 S17

S21 S22 S23 S24 S25 S26 S27

S31 S32 S33 S34 S35 S36 S37

…………………

Sn1 Sn2 Sn3 Sn4 Sn5 Sn6 Sn7

4 遺傳算法應用

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

4.1 一個完善的試題庫組卷算法應滿足以下三個條件

4.1.1 抽出的試題具有隨機性；

4.1.2 同一份試卷滿足用戶給定的參數要求；

4.1.3 組成的試卷滿足教師給定的參數要求。

4.2 考試自動出題的遺傳算法

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

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

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

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

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

(3)從試題庫[PAPER]中取出PAPER[n](0≤n≤j)與狀態空間庫[F]中的指標F[m](0≤m≤i)進行匹配。如果STK[n]與D[m]完全匹配，則

flexibility[k]<-flexibility[k]+1

如果不匹配，則有

flexibility[k]<-flexibility[k]+0

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

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

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

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

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

以上用遺傳算法抽題時，交換概率Pc和變異概率Pm的確定很重要。太小使選題工作開展緩慢，太大則會破壞適應值高的試題模型。通常規定其為0.4左右。同樣，Pm太小不能產生新的試題模型，太大又會產生過多的試題模型。它宜規定為0.1左右。自動選題時，選題的方式可采用父親挑選和生存選擇兩種。兩種選擇方式共同作用于選題，保證了選題的順利完成。在選題的過程中，哪一道題目被選中是一個隨機過程，其概率依賴于上一次選題的過程。

5 結束語

本文利用遺傳算法的全局尋優和收斂速度快的特點，設計出一種用于自動組卷的較好的算法，提高了自動組卷的成功率。要進一步減小自動組卷的誤差精度和提高自動組卷的收斂速度，還需更深層次的研究。

參考文獻：

[1]王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安交通大學出版社，2002.

[2]張文修，梁怡.遺傳算法的數學基礎[M].西安大學交通大學出版社，2001.

[3]于志敏，劉延華.選題組卷策略研究[J].電腦開發與應用，2001，14(3):32-34.

[4]Martin T Hagan，Howard B Demuth， Mark H Beale.神經網絡設計[M].北京:機械工業出版社.

收稿日期：2007-12-12

作者簡介：李江萍（1982-），女，江西高安人，助教，學士，現在在廣東工業大學計算機學院就讀工程碩士，研究方向：計算機應用技術。