基于遺傳算法的試題庫組卷研究

李迎斌++王春峰++劉麗萍

摘要：組卷問題是一個多重優化約束目標求解問題，使用傳統方法解決此種問題較困難，考試題庫以及組卷算法的設計決定了組卷的效率和質量。文中提出一種基于遺傳算法的組卷方法，給出了初始種群方法，分段編碼及交叉算子、變異算子，優化了搜索過程，實驗證明求解組卷問題采用該方法行之有效，有利于實現考試的規范化、科學化、教考分離。

關鍵詞：組卷 遺傳算法 試題庫 計算機輔助測驗

中圖分類號：TP39 文獻標識碼：A 文章編號：1007-9416（2014）12-0128-02

Abstract：Test paper construction is a multi-object optimization restrict problem，it is quite difficultly to solve using traditional mathematics method.The efficiency and the quality completely are decided to tries the question bank design as well as pulls out the topic algorithm the design.This paper puts forward an intelligent algorithm，which optimizes the search course and adopts the segment code.The experiment proves that the algorithm has practicability.It is a key way to separate the examination from teaching and make the exam more standard.

Key Words： test paper construction， Genetic algorithm， item bank， computer assisted testing

計算機輔助測驗[1]（computer assisted testing，簡稱CAT）是現代管理教學中的重要組成部分之一，它綜合利用信息和網絡技術協助對考生的研習效果進行測驗和學習能力評估，并對測驗的結果做出相應解析。通常情況下，完善的CAT系統是以試題庫為基礎，包括試題庫模塊、試卷組合模塊、聯機測試、考卷批閱、測試分析、成績管理與總結等。組卷是CAT非常重要的一部分，考卷可以全面地反應考生的真實水平，它的質量直接決定了本次考試的有效性。因此，組卷模塊是影響CAT系統性能指標的重要參考依據。

文中基于遺傳算法的基本原理和思想方法，設計了一個組卷算法，能夠在較短的時間內生成較高質量的試卷。

1 遺傳算法的基本原理

遺傳算法[2，3]的本質可以理解為一種求解問題的高效并行全局搜索方法，它模仿整個群體的學習過程，每個個體都表示既定問題中搜索空間的一個待解點。

首先，需要對問題數據進行抽象，實現從問題到位串的編碼映射，初始種群也會從解中隨機產生出來。將初始化群體置于遺傳算法的執行過程中，依據適者生存的原則，由個體適應度函數值的大小決定出適應環境的個體進行復制，再通過隨機選擇、交叉和變異等遺傳操作過程產生出更適應的下一代種群，使群體逐代地進化到搜索空間中越來越適應環境的區域，直到解趨于收斂，得到最優解為止。

2 組卷問題的基本原則

組卷過程中應遵循一些準則，以使產生的試卷能夠滿足高可信度的測驗要求：

（1）按設定指標適當配比題目分數以保證組成試卷的效度。

（2）試卷內試題知識點涵蓋面較全，數目適當，為確保試卷的可信度，應盡量避免臨近知識點試題多次抽取在同一份試卷中。

（3）適當設定試卷的難度，同時使試卷具有較好的區分度，適當地調整試卷的難易程度。

（4）設定卷面的滿分值和考試用時，一般的，卷面滿分為100分，考試用時2小時。

（5）適當降低考題抽中率。

3 數學描述

根據文中問題的基本原則和特點，通過分析試卷指標，采用矩陣理論方法，建立問題空間的數學模型。如果各考卷包含m道考題，且各題包含5個屬性，如表1所示，可以映射為建構一個m×5階的目標矩陣X，如下所示。其中，m表示每份試卷題目數，行代表某一道考題，列表示考題的某種屬性。

4 組卷算法

4.1 編碼方案

文中應用分段自然數編碼方法，在此方法中，首先將編碼按題型分為三組，每組編碼代表一個題型，每個題型的編碼方法同樣應用自然數編碼，也就是在試題庫中各題型的題目單獨建立試題表，題目均使用自然數編號。按照組卷的需求，在試題庫中每個題型都要篩選題目（編號）組成染色體，染色體采用變長編碼策略，一個考題就代表染色體中的某一位基因，考卷所含考題的數目就是染色體包含基因的數目，不同題型間的編碼都是相對獨立的。

試卷包含選擇、判斷、簡答等3種題型，每個題型的數目分別為m1、m2、m3，總共100道考題，如下所示。

4.2 初始種群

針對組卷問題，初始種群是指從試題庫中按照設定的參數隨機抽取的考題組成的考卷。設定的初始種群的大小對組卷算法的收斂速度和性能有很大影響，故初始種群的設置一定要合理。文中使用初始試卷的套數作為初始種群，且參與算法的試卷數目設置要合理，因數目過多將減緩算法的收斂速度，過少則對生成最優試卷造成消極影響。設初始群體大小為100，從題庫中分別隨機抽取考題，構成100套初始試卷，并計算它們的適應度值。

4.3 適應度函數

本文適應度函數設計如下：endprint

其中，

，。

U（0≤U≤1）代表每個約束條件分屬權重，|sMi|代表考卷中難度為i的考題分值總和同第i種設定難度的分值Mi的偏差值的絕對值；|sNj|表示考卷中第j個知識點的考題的分值總和同第j種設定知識點的數值Ni的偏差的絕對值；|sQh|表示考卷中第h種考題要求度的分數總和與第h種設定要求度的數值Qh的偏差的絕對值。

4.4 選擇算子

選擇操作的作用是確定下一步要進行交叉和變異操作的個體，通常情況下，由適應度函數值的高低來決定要使用哪些優良個體。文中使用輪盤賭選擇方法[4]，算子描述：

（1）分別計算當前考卷群體中各個考卷的適應度函數值，分別得到累計值Ki，以及最末一個累計值Kn；

（2）在區間[0，Kn]產生一個隨機數X；

（3）分別將Ki與X做對比，當產生第一個Ki≥X的考卷i時，即作為復制對象；

（4）重復操作上述兩步，直到滿足所需個體數目為止。

4.5 交叉算子

文中應用分段單點交叉策略：不同題型在各自的編碼段內隨機設定交叉點，實現交叉時，對其附近的某些基因進行交換。依據基本遺傳算法的應用經驗，交叉概率Qc常在0.5-0.8間選取，按此Qc值，在群體中抽出M（M=Qc×群體規模N）個適應度值較高的個體組成一個群體。隨機選出試卷S1和P1配對，并在各段中均隨機生成一個交叉點，各段逐一交換對應基因位上的基因，產生一對新的個體S2和P2。新考卷個體S2和P2在段內可能出現相同考題，但并不調整每個題型數目，此時需將重復的試題編號替換成此段中未出現過的編號。操作方法是：產生一個范圍為1-K的隨機數i，判斷其是否與考卷中同類型題號相同，如果相同則繼續隨機抽取，不相同則替換掉重復出現的題號。如圖1所示。

4.6 變異算子

針對編碼特點，文中將變異算子Hm的操作轉換為對新試題的搜索和替換，以確保變異后的編號未超出指定范圍。具體的變異操作如下：

（l）設nMax作為考卷考題數目，變異操作前將當前查找新考題的次數N=0。

（2）在區間[0，1]內隨機生成實數J，若J不小于Hm，該位基因不變；否則，產生一個隨機數用來標記變異基因的位置，由此位置判斷歸屬題型。開始在題庫中搜索新試題，如搜索成功，則將新題號替換掉該基因的值，如失敗則繼續。

（3）搜索次數N增1，如N>nMax，則停止搜索，該基因位保持不變。

（4）判斷新搜索試題所在章節是否在本次考試范圍內，如不是，重復第三步；判斷新題號與已有題號是否一致，如是，重復第三步。

（5）將原染色體基因替換為新試題編號。

變異操作如圖2所示。

如上所示，隨機生成一個實數J，因大于Hm，隨機數指出變異的基因位在箭頭所指處，此位置位于判斷題型內，在判斷題范圍內隨機生成一個整數88當做新考題編號，在父個體判斷題段編碼串中沒有88，將原基因位上的編號35用88代替，變異操作完成。

5 結果分析

為證實文中方法的有效性和可操作性，在.NET環境下采用C#語言實現了該程序，完成組卷試驗。本次實驗有選擇、判斷、簡答等題型，共1000道試題，各題2分，分屬7章。題庫中難度分布如下，容易試題100道，難度系數0.85-1.0，較易試題240道，難度系數0.76-0.85，中等試題330道，難度系數0.66-0.75，較難試題250道，難度系數0.56-0.65，難試題110道，難度系數0.0-0.55。程序運行前需設置參數包括群體規模、變異概率、難度系數、最大迭代次數、交叉概率。試卷滿分為100，期望平均得分為85。

實驗證實，當設置的參數適當，群體規模M取100，變異概率Hm在0.01-0.02之間，交叉概率Pc在0.5-0.6之間，平均迭代次數70次，此時組卷效果較好。

6 結語

本文采用分段編碼方法在組卷問題中實現了遺傳算法，能夠更好的反映實際組卷情況，相應的采用段交叉算子和段內變異算子，恰當的適應度函數比較好的解決了組卷問題，不僅提高了搜索效率，也可以使種群較快地收斂于全局最優解。應用分段編碼方式不需在進化過程中控制題型和題目數量，問題求解難度得到了顯著降低。實踐說明，采用遺傳算法解決組卷問題可以得到良好的組卷效果。

參考文獻

[1]馬宗梅.遺傳算法在考試系統組卷中的應用與研究[D].鄭州：鄭州大學，2009.

[2]孫鳳喜.基于遺傳算法的智能組卷系統的設計與實現[D].石家莊：河北科技大學，2013.

[3]李會民，張仁津，馬桂英.基于遺傳算法的交規考試自動組卷方法研究[J].計算機工程與設計，2009：4333-4335.

[4]韓蕾.基于遺傳算法的自動組卷系統的研究與實現[D].青島：中國海洋大學，2010.endprint