基于遺傳算法的在線考試系統組卷設計

胡木林

摘 要 在線考試系統的核心是組卷算法，利用全局擇優的遺傳算法研究在線考試系統的組卷過程，解決了在線考試系統的核心技術。基于遺傳算法的在線考試系統的實現縮短了考試的工作流程，減輕了教師的工作量，使考試更客觀、公正、環保、高效。

關鍵詞 互聯網+；在線考試系統；遺傳算法；組卷算法

中圖分類號：TP319 文獻標識碼：B

文章編號：1671-489X（2018）12-0023-05

1 前言

2015年，國務院總理李克強在政府工作報告中首次提出“互聯網+”行動計劃，全面實施網絡強國戰略。“互聯網+”模式已成為各行各業發展的新業態，互聯網教育已成為教育發展的必然趨勢。基于互聯網的在線無紙化考試是集考試報名、制卷、閱卷、成績統計與分析等為一體的多功能考試形式，因具有高效、客觀、公正、安全、環保等一系列優點，成為國內外學校教育教學改革重要課題。

在線考試系統的核心部分就是組卷算法，它直接決定著考試檢測的效果。近年來，組卷算法的研究一直是在線考試系統的研究重點，例如：劉洋進行了考試系統中組卷算法的研究與設計[1]；沈建強等研究了組卷系統的優化與實現[2]；劉彬研究了遺傳算法在試題組卷中的應用，重點研究了選取的有效規則[3]。

本文重點研究具有全局優化的遺傳算法，并按照試卷信度、效度、難度、區分度等評價指標，建立目標矩陣和目標函數，對遺傳編碼、遺傳算子、算法終止條件等進行詳細分析與設計。并在遺傳操作的過程中研究采用分段實數編碼方式和指數比例變換方式建立適應度函數，確保隨機生成的試卷更科學、規范、高效。

2 選題理論

考試需要試卷，試卷質量的好壞直接決定著檢測結果的真實性和代表性。因此，在線考試系統如何按照教師的要求自動制出科學、規范、全面的試卷，就體現得尤為重要。系統設計時，采用何種智能算法決定著組卷的質量和效率。目前，較為常用的有誤差補償、隨機抽取和遺傳算法等多種組卷算法，無論采用何種組卷算法，都必須要解決自動按照設定約束條件，選擇符合要求的試題，組成考卷。試卷形成后，要按照特定評價指標給予評價。通常，其評價指標主要有信度、效度、難度、區分度和實用性等[4]。

試題的難度 難度作為試題的評價指標之一，是指試卷中試題的難易程度，用該題的通過率或平均得分率[5]來衡量，一般用P表示。主觀題難度系數和客觀題難度系數的計算方法如下。

1）主觀性試題的難度，基本公式：

2）客觀性試題的難度，基本公式：

上述公式是基于理論分析與推導，實際應用中，信度按以下方法計算。

主觀題信度按克朗巴赫公式法估算：

式中，K指整個測驗的題數，Sx2指測驗的總得分方差，Si2指每道題的得分方差。

客觀題的信度按庫德—理查遜公式估算：

試題的效度 效度是指測量的有效性程度，用R表示。在教育考試領域，相較于信度而言，效度的衡量結果更加重要。在測量理論中，效度為有效分數方差與實得分數方差之比，即：

由上式可知，誤差方差越小，有效分數方差越大，效度越高。

區分度 區分度用來反映試題區分不同水平參試者的程度，同時用來衡量考試試題對參試者水平差異的鑒別能力，即通過考試，能把優秀、中等、差等不同層次的學生真正區分開。區分度越高，層次劃分越合理；反之，區分度越低，考試分數分布就會出現某一區間相對集中，層次劃分越不合理。區分度用D表示，通常采用鑒別指數法計算：

式中，PH指高分組（即得分最高的27%）該題的正確率，PL指低分組（即得分最低的27%）該題的正確率。

試題區分度介于-1～+1之間，若值大于0.4，該題的區分度很好；若值介于0.3～0.39，該題的區分度較好；若值介于0.2～0.29，該題區分度較差，需修改；若值小于0.19，該題區分度差，需要淘汰刪除該題。

3 遺傳算法組卷設計

遺傳算法原理 遺傳算法（Genetic Algorithm，簡稱GA）是一種基于生物學進化規律演化而來，具有全局尋優能力的隨機化搜索方法[6]。其原理為：將問題的解表示成生物界“染色體”和二進制編碼的串，在執行操作之前，給出一群假設解“染色體”，并將“染色體”置于問題的“環境”中，根據生物學領域中適者生存的規律，比較選擇適應“環境”能力較強的染色體進行復制、交叉、變異，產生更適應環境的新一代“染色體”群，一代代地進化，收斂到最適應環境的一個“染色體”上，將其作為問題的最優解輸出[7]。遺傳算法流程圖如圖1所示。

基于遺傳算法的組卷算法設計

1）約束條件的數學模型。組卷就是按照設定的多約束條件、多指標優化求最優解的過程。建立基于遺傳算法的自動組卷系統數學模型，就是把衡量試題質量的約束屬性設定為實際組卷的約束條件。組卷中抽取的每道試題，都由n項指標確定。本文以最具有代表性的分值、所屬的知識點、難度系數和題型等四個指標為例建立模型。每道題的數學模型用一個四維向量（d1，d2，d3，d4）來表示，其中d1，d2，d3，d4分別對應試題的分值、知識點、難度系數、題型四個屬性指標[8]。若該試卷共有m道試題，則m×4的矩陣就表示該試卷的數學模型，如式（8）所示，也稱為試卷目標矩陣。

目標矩陣建立后，需建立目標函數。在組卷過程中，授課教師根據專業不同，確定考試的章節和知識點，并確定相關章節在本次考試中所占的分值以及在組卷時本章所允許的分數誤差。假設試題庫中共有N章知識內容，Zi（i=1，2，...，N）、Yi（i=1，2，...，N）、Wi（i=1，2，...，N）

分別表示生成試卷各章節所占的分數、組卷時設定各章節應占的分數和用戶允許各章節的分數誤差，則生成試卷后是否滿足要求，可以用式（9）、式（10）來表達：

fzw越小，則說明分數誤差越小，生成的試卷質量越高，越滿足使用要求。設生成試卷的難度系數為scndxs，則計算公式如式（11）所示：

式中，di1指第i題的難度系數，N指試卷的總題數。

若教師指定的難度系數為zdndxs，則難度系數誤差ndwc為：

根據式（10）（11）（12）可以得出目標函數（Fmbhs）表達式為：

Fmbhs值越小，說明試卷越符合要求。

2）遺傳編碼。遺傳算法的操作對象是群體中的個體，并對個體不斷優化。因此，必須對個體用基因鏈碼的形式表示出來，這種編制基因鏈碼的過程稱為編碼。編碼技術是遺傳算法的關鍵技術，對遺傳算法的成功實現起著至關重要的作用。編碼的方案和策略對遺傳算子產生直接影響，特別是交叉和變異算子的功能設計[9]。常見的編碼方法有二進制編碼、實數編碼、多參數編碼和DNA編碼等。

實數編碼技術解決了二進制編碼方式搜索空間過大和編碼過長的缺點，能很大程度地提高求解速度和組卷效率。因此，本文以實數編碼進行研究，將每一份試卷映射成為單獨的一個染色體，每一種題型作為一個基因的編碼串，被選中的每一道試題作為染色體的一個基因，且該基因為抽中試題的序號。編碼的過程實際上就是將同種類型的試題標號組合成段，使得每一段編碼表示一種題型，每種類型的試題單獨進行實數編碼，編碼后染色體的個數實為試卷題目的總數。假設要組成的試卷有選擇題、判斷題、客觀題三種題型，每種題型均有五道題目，表1為采用分段實數編碼組卷后兩張試卷的染色體。

3）適應度函數的確定。適應度（值）是表示個體對環境的適應能力和繁殖后代的能力[10]。適應度函數是用來判斷群體中的個體優劣程度的指標，適應度越大，個體越好。在遺傳算法的搜索進化過程中，適應度函數是用來評估個體或解優良程度的唯一依據，是遺傳操作重要條件。為便于操作，適應度函數值必須非負值。多數情況下，對于給定約束的優化，目標函數值有正有負，這就必須要建立適應度函數和目標函數之間的映射關系來確保適應度函數值的非負。建立適應度函數f（x）和目標函數g（x）的映射關系如下：

式中dmax是一個輸入值，也可以是當前所有代數值，或者是最近K代中g（x）的最大值，此時dmax隨著代數會有變化。

現建立目標函數Fmbhs和適應函數Fsyhs之間的映射關系式如下：

為讓優秀的染色體有更多的機會被復制，同時避免復制過多優秀的染色體充滿整個種群，提高偏差較小的染色體之間的競爭力，多數采用指數比例的方法來設計適應度函數，采用比例指數法建立的適應度函數Fsydhs如下：

其中β=0.03。

4）產生初始種群。在初始種群之前，首現確定初始規模及群的大小M，初始規模的大小對組卷起著很大的影響：過大，算法效率較低；過小易早熟，無法達到最優解。在實際應用中，M一般取100左右。

5）遺傳算子操作。

①選擇算子。選擇算子是指選擇優良的個體遺傳給下一代。目前，選擇算子方法主要有適應度比例法、聯賽選擇法、Boltzmann選擇法等多種方法。其中，適應度比例法又稱輪賭選擇法，是遺傳算法中使用最多最廣的一種方法。本文研究采用適應度比例法，其原理為：利用計算個體的適應度函數值來劃分輪盤的比例區域，適應度越大，所占輪盤的區域就越大，被選取遺傳的概率就越大。假設群體大小為M，第i個個體的適應度為Si，整個種群的適應度為Sn，那么個體i被選取的概率Pi可表示為：

具體選取過程如下：

a.計算個體的適應度Si、整個種群適應度Sn、個體被選中的概率Pi；

b.確定種群中個體的最大選擇概率Pmax，并且在[0，Pmax]之間生成隨機概率數R；

c.比較選取，若R

d.重復步驟b與c，至個體數目滿足設定的需要條件為止。

②交叉算子。交叉算子是遺傳算法的核心之處，常用單點交叉和均勻隨機交叉。本文研究采用單點交叉，其原理為：先確定交叉的概率Pc，一般為0.6～0.8（執行交換個體達到60%～80%）。同理，依據選擇算子的方式確定交叉的個體，并隨機產生一個斷點，依次兩兩進行交換（交換雙親斷點之后的部分），原理如表2和表3所示。

基因交叉后如出現基因重復（出現相同兩道題）或者順序混亂（大序號題目在前，小序號題目在后），系統首先就要做出判斷，找出重復基因或要重新排序的基因的下標范圍，其方法為[11]：分別將交叉點的基因同交叉點之前和之后的基因依次比較（之前的按照從后向前的順序，之后的按照從前向后的順序），找出第一個比變異點小的基因和第一個比變異點大的基因，分別記錄i1和i2，要替換重復的基因和重新排序的基因就在區間[i1，i2]內。假設交叉點下標為i，則兩層循環就在[i1，i-1]，[i，i2]這兩個區間判斷，如果出現重復，按約束條件隨機抽取的一個沒有出現的染色體（試題的編碼）將[i，i2]區間內的重復基因替換掉。新染色體中就不再出現重復基因，再將新染色體的基因重新排序即可。

③變異算子。變異是產生新個體的另一種方法，對遺傳算法起著積極的作用，可以提高遺傳算法的全局搜索能力和保持群體的多樣性[12]。變異個體的選擇以及變異位置的確定，都是采用隨機的方法產生。執行過程如下：

a.初始化搜索新題的次數為零，并設置最大次數為M；

b.隨機產生的概率系數Pm1，若Pm1>Pm（Pm為0.001～

0.01），基因保持不變；反之，則將依據此基因的值來確定所屬題型。

c.把搜索次數J加1，如果J>M，那么將停止新題搜索，且該基因保持不變；反之，將在此題型所包含的題號范圍內隨機生成一個與此基因值不相同的另一整數，作為新題的題號；

d.如果選擇的新題所包含的知識點與本個體中的其他題目相同，則重復c的操作；

e.基因值用新題題號替換。

表4表示變異前染色體A、表5表示變異后染色體A′，變異后如出現基因重復（如A′中第二段的6與后面基因重復），則要重新隨機選取一個等位基因（題號）再進行替換；若出現順序混亂非法時（如A′中第三段的37比后面基因36大），則首先將變異點同變異點前后的基因標號依次比較，找出順序混亂的區間，重新進行排序。

遺傳運算終止條件的設計 遺傳算法是一種反復迭代的搜索過程，它通過多次進化逐漸逼近最優解，而不是恰好等于最優解，因此需要確定終止條件。常用的有以下幾種方法：

1）直接規定遺傳迭代次數，即預先設置一定的次數，然后按情況增加代數（可達上千次）；

2）控制目標函數的方差實現終止，即當目標函數值和實際的目標值之間的差異小于允許值時，遺傳終止；

3）查看適應度的變化來確定算法是否終止，即當最優個體的適應度沒有明顯變化或者變化很小時，則遺傳終止。

考慮組卷的實效，研究采用第一種和第三種的結合作為遺傳運算的終止條件，即在預先規定的代數內有一個個體的適應度值已經滿足要求，則就停止；反之則一直迭代，直到達到規定的代數為止，取出終止時的最優個體作為算法最優解輸出。流程圖如圖2所示。

4 總結

本文深入分析了在線考試系統組卷時試題選取的相關理論，研究了基于遺傳算法考試系統的目標函數的設計、適應度函數的設計、種群的初始化、遺傳算子的選擇、遺傳算子的交叉與變異和遺傳算法的終止條件。系統功能實現后，通過大量組卷實驗，基于遺傳組卷算法在線考試系統組卷安全、方便、快捷，很大程度減輕了教師的教學負擔，提高了教學效率，具有很好的實用性。同時突破時空的界限，適應互聯網教育發展趨勢。

參考文獻

[1]劉洋.遺傳算法在考試系統中組卷算法的研究與設計[J].湖南城市學院學報，2013，22（1）：75-78.

[2]沈建強，張寶明，鄒軒.組卷系統的優化與實現[J].計算機應用，2003，23（s1）：38-39.

[3]劉彬.遺傳算法在試題組卷中的應用[J].燕山大學學報，2002，26（3）：193-195.

[4]金娣，王剛.教育評價與測量[M].北京：教育科學出版社，2002：12-20.

[5]郭曉君.智能組卷策略淺析[J].科技展望，2015（32）：108.

[6]徐濤.基于遺傳算法的組卷研究與設計[J].軟件導刊，2014，13（12）：109-111.

[7]周艷麗.基于改進遺傳算法的自動組卷問題研究[J].計算機仿真，2010（9）：319-322.

[8]莫家慶，胡忠望.基于遺傳算法的組卷系統的研究與實現[J].福建電腦，2014（6）：31-33.

[9]譚新良.基于整數編碼和自適應遺傳算法的智能組卷算法[J].電腦與信息技術，2007（4）：33-35，62.

[10]周芳.組卷技術中遺傳算法的改進研究[J].信息通信，2016（7）：31-32.

[11]潘莉.遺傳算法在自動組卷中的應用方法研究[D].長春：東北師范大學，2010.

[12]林關成，吳代文.基于遺傳算法的在線考試系統自動組卷策略優化[J].計算機與數字工程，2012（3）：24-26.