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

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

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

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

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

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

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

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

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

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