遺傳算法在自動組卷中的應用(圖文)

1、遺傳算法在自動組卷中的應用(圖文)    論文導讀：當前較為先進的組卷方式，是隨機從已有的試題庫中按照考試的各項要求，如題型、考核點分布、難度、分值等因素選擇相應的題目自動組卷，組卷靈活，試卷的維護相對容易，這種方式已經(jīng)被廣泛地應用到各種網(wǎng)絡考試系統(tǒng)當中。本文主要介紹的是使用遺傳算法進行自動組卷的思路與具體的實現(xiàn)。 關鍵詞：遺傳算法，自動組卷，算子    1引言 隨著因特網(wǎng)技術以及教育網(wǎng)絡技術的不斷發(fā)展，越來越多的學校和機構開始采用網(wǎng)絡考試的考核形式，而在網(wǎng)絡考試中采用組卷形式的優(yōu)劣與否將直接影響到試卷的質量與考試

2、的成效。傳統(tǒng)的網(wǎng)絡考試中，學生只是隨機的從已有的幾套試卷中抽取一套，這樣會導致試卷的維護成本變高，同時試卷的重復率相對較大。當前較為先進的組卷方式，是隨機從已有的試題庫中按照考試的各項要求，如題型、考核點分布、難度、分值等因素選擇相應的題目自動組卷，組卷靈活，試卷的維護相對容易，這種方式已經(jīng)被廣泛地應用到各種網(wǎng)絡考試系統(tǒng)當中。自動組卷技術實現(xiàn)的關鍵是組卷算法的選擇與實現(xiàn)，它將直接影響到組卷的質量。本文主要介紹的是使用遺傳算法進行自動組卷的思路與具體的實現(xiàn)。 2常用的自動組卷算法 當前使用較多的自動組卷算法主要有三種。第一種是基于隨機抽題的算法，它根據(jù)問題空間的一些指標，從試題庫中隨機地抽取一道

3、試題放入待生成的試卷中，此過程不斷重復，直到組卷完畢或無法從題庫中抽取滿足條件的試題為止。該組卷方法的重復率高，組卷成功率非常低，即使組卷成功，花費時間也較長。第二種是基于回溯試探法的算法，它是將隨機抽題算法產生的第一狀態(tài)類型記錄下來，當搜索失敗時釋放上次記錄的狀態(tài)類型，然后再根據(jù)一定的規(guī)律變換出一種新的狀態(tài)類型進行試探。該算法的不足之處在于當試卷總題量較大時，狀態(tài)類型的變換便成為一個巨大的數(shù)字。因此這種方法只適用于狀態(tài)類型和試卷總題量都較少的題庫系統(tǒng)。第三種是基于遺傳算法的組卷算法，它可以從群體中選擇更滿足條件的個體，具有很強的智能性。同時它能根據(jù)不同的環(huán)境產生不同的后代，具有動態(tài)性，自適應

4、性，從而能滿足試題庫容量、覆蓋面不斷變化的要求。 3遺傳算法數(shù)據(jù)模型的建立 自動組卷時會根據(jù)組卷的原則對試卷的質量提出很多方面的要求，即試題的控制指標，如每種題型包含的題目數(shù)量、每種題型所占分數(shù)、每道試題的難度系數(shù)等。因此，在組卷之前應該為自動組卷建立模型。其模型如下圖所示：                             

5、60;    a11 a12 a1n a21 a22 a2n am1 am2 amn                               圖1 自動組卷的目標矩陣    模型中每一行代表對某一試題的所有控制指標，假設共有n個控制指標

6、。其中ai代表第i個指標。如果該試卷中一共有m道題，那么上述m*n的目標矩陣即可代表一份試卷。    上述的目標矩陣應滿足以下條件：    （1）試卷的分數(shù)指標：=總分。論文參考網(wǎng)。（設定ai1代表試題的分數(shù)）    （2）各章分數(shù)指標：第j章的分值=（ai2代表章的編號）此指標可以衡量出自動組卷時，相關章節(jié)應占據(jù)的分值。    （3）題型分值指標：第j類題型的分值=（ai3代表題型），此指標可以衡量出自動組卷時，相關類型的試題應占據(jù)的

7、分值。    （4）知識點指標：第j類知識點的分值=（ai4代表相關知識點編號）。此指標可以衡量出自動組卷時，相關知識點應占據(jù)的分值。    （5）難度系數(shù)指標：第j種難度等級的分值=（ai5代表難度系數(shù)值）此指標可以衡量出自動組卷時，各難度等級的題型應占據(jù)的分值。    4組卷的流程    運用遺傳算法解決實際問題時采用的基本流程如下：首先將所要求解決的實際問題進行二進制編碼，然后根據(jù)實際的環(huán)境實施遺傳的基本操作：選擇、交叉、變異，通

8、過多次循環(huán)往復的遺傳操作后，最終收斂到至一個最適應環(huán)境條件的個體上，即得到該問題的最佳解決方案。具體的實現(xiàn)流程如下：    （1）使用染色體編碼方法對試題進行編碼。將一份試卷映射成一個染色體，試卷中的每道試題映射成一個基因，其值用試題的編號表示。    （2）確定組卷的目標函數(shù)。使用函數(shù)描述組卷的目標，該系統(tǒng)使用的目標函數(shù)為：    F=*|-S|+*+*+*（B2(x)- B1(x)>n）    其中的ai表示試卷中第i題所占分

9、值， S表示試卷總分的預期值，bi示試卷中第i章試題所占分值， dbi表示試卷中第i章試題的實際總分值與要求的總分值之間的偏差。ci表示試卷中難度級別為i的試題所占分值，dci表示試卷中難度級別為i的試題的實際總分值與要求的總分值之間的偏差。B2(x)- B1(x)>n表示試卷每道試題在連續(xù)的n份試卷中不能重復出現(xiàn)。，和為相應參數(shù)的權值，可以根據(jù)實際情況進行調節(jié)。    （3）算子的選擇。論文參考網(wǎng)。組卷流程中涉及到的算子主要有三個，分別是選擇算子，交叉算子與變異算子。本系統(tǒng)在選擇算子時使用的是目前遺傳算法中常用的賭輪選擇法，使用公式來決定其后代遺

10、傳的可能性。交叉算子的確定過程則是隨機產生一個0-1的實數(shù)，如果<P，（其中P為事先設定的交叉概率）則交換該基因。變異算子對后代個體的某些基因進行變異，起局部搜索的作用。該系統(tǒng)中引入變異算子pm，使用方法與交叉算子類似。    （4）完成組卷。當組卷達到實際需要時，完成組卷。論文參考網(wǎng)。    5系統(tǒng)的實施效果。    本系統(tǒng)的考試主要是針對本校的VB程序設計考試開發(fā)的，通過使用自動組卷系統(tǒng)，組卷效率得到了較好的提高，也大降低了考試的時間與人力成本，取得了較好的效果。     參考文獻：    1 李惠姝，基于遺傳算法自動組卷的研究與應用，太原理工大學，2007