基于遺傳算法的在線考試系統的設計與實現

摘 要：在線考試系統中最重要的組成部分之一是試題組卷，本文將遺傳算法應用于《高級程序設計語言》試題庫自動組卷方法中，得出多目標問題求解模型。實踐結果表明，遺傳算法能有效地解決自動組卷問題，具有較好的使用性能和實用性。

關鍵詞：遺傳算法 在線考試系統 自動組卷 在線考試系統

中圖分類號：G4 文獻標識碼：A 文章編號：1673-9795（2013）09（a）-0021-02

傳統紙質考試方式很難較準確地反映出學生的實際動手能力，而且紙質考試還具有考試時間長、試題印制數量大、監考改卷人力耗費大等缺點。為充分利用教學資源，減輕教師的工作負擔，本文設計并實現了一個實用、高效的《高級程序設計語言》在線考試系統。而智能化自動組卷策略是在線考試系統的核心技術，智能組卷遇到的主要問題是保證生成的試卷具有隨機性和合理性的同時，必須最大程度地滿足用戶的各方面需求。因此，智能組卷問題的實質是一個多目標優化問題，傳統數學方法難以求解。本文利用遺傳算法作為求解智能組卷問題的策略，取得了較好的實踐效果。

1 系統結構與設計

基于“高內聚，低耦合”的思想，本文在對《高級程序設計語言》在線考試系統進行結構設計時，考慮使用三層結構開發。通常意義上的三層結構就是將整個業務應用劃分為：表現層（UI）、業務邏輯層（BLL）、數據訪問層（DAL）。表現層是展現給用戶的界面。業務邏輯層是針對具體問題的操作，即對數據業務邏輯處理。數據訪問層是直接操作數據庫，針對數據的增添、刪除、修改、更新、查找等。本文將表現層與數據操作層分離。但有些業務邏輯比較簡單的地方還是讓表現層直接讀取數據，這樣更符合效益與成本原則，同時使得編程更靈活。在業務邏輯層，設置了大量的事務類，處理不同的事務邏輯。

在線考試系統由于數據需要長期保存因此，必須引入數據庫技術。本系統采用Microsoft SQL Server 2005，在對數據庫操作時采用ADO.NET技術。在數據庫中設計了以下9張表：管理員信息表、學生信息表、教師信息表、課程信息表、班級信息表、單選題信息表、多選題信息表、判斷題信息表、分數記錄信息表。另外，在線考試系統還有些數據不需要長期存儲的，因此，采用XML文件記錄，便于傳輸和操作。系統建立了3個XML文件，用于考試設置、遺傳算法的設置、學生考試過程中備份題目和記錄作答情況。

2 系統主要功能的實現方法

系統的主要功能模塊包括：登錄，題庫管理，考試，自動組卷，用戶管理。其中組卷部分，通過使用遺傳算法，滿足試卷難度、題目章節分布、題目完成時間三個目標因素進行組卷，加快了組卷速度，解決了多目標組卷的難題。另外考慮學生考試時，可能會出現系統意外關閉等偶然情況，設計時添加系統自動保存和恢復功能，能夠恢復到意外發生前的作答題目和作答答案狀態。

2.1 考試

考試是本系統中最復雜的過程，特別是涉及出題部分，考試流程為如下所示。

（1）學生選擇考試，系統檢查時間，是否在考試時間范圍內。若符合條件，執行下一步。

（2）檢查學生是否進行過這次考試，若沒進行過則執行（3），若已經進行過考試則執行（4）。

（3）系統生成試題，返回給考生，執行（5）。

（4）系統按之前保存的選題和作答進行恢復，返回顯示給學生，執行（5）。

（5）考生作答，系統記錄作答情況。

（6）考生提交試題，系統返回提交成功信息。

（7）對學生試卷進行評分，并把結果保存。

因此，考試時序圖如圖1所示。

2.2 自動組卷

本系統采用遺傳算法自動組卷，它可以滿足復雜的多目標出題。傳統隨機出題，僅僅是從系統里面隨機生成隨機數字組成試卷，然后驗證試卷是否符合出題要求。這種出題搜索是盲目的，需要搜索大量題目才有可能滿足出題條件，所以幾乎不可能符合復雜的多目標的出題要求。

而使用遺傳算法可以將比較優越的子代留到下一代，然后讓其突變，也就是改變少量基因，從而有可能產生更優的一代。將其應用于在線考試系統中，可以把較好的試卷保留下來，微調其中小部分題目，讓其有可能變得更好；然后再評價，選出評價高的，讓它獲得雜交遺傳的機會。如果恰巧雜交序列的兩個雜交對象一樣，也就是這個對象獲得完全復制，那再進行變異操作，這點對于在線考試系統實現隨機出題是非常重要的。就算不能完成復制，也有可能把較好的基因保留，這樣能夠提高在線考試系統的出題效果。

在線考試系統遺傳算法的實現：

（1）染色體編碼（基因串）。

在本文考試系統中，遺傳算法的編碼方式不是采用傳統的01編碼，而是采用如下的編碼方式：設一張試卷有10道題目，則有10個基因，每個基因用題庫中題目號表示，如51，3，21，5，11，6，55，32，44，21即是一個基因串。

（2）產生初代種群。

實現代碼如下：

public List GetInitPopulation（）//生成設定數目的初代種群

{ List al = new List（）；

for （int i = 0； i < initNum； i++）

{ al.Add（GetRandomPaper （））； }

return al； }

（3）適應度函數。

public void Evaluation（Paper paper）

{ double deviation = 0；

deviation = LevelEval（paper） * 3000 + TimeEval（paper） + ChapterEval（paper） * 15；

paper.deviation = deviation；

paper.fitness = 1 / （deviation + 1） * 10000； }

其中，LeveLEval是難度評價差異計算函數，TimeEval是時間差異計算函數，ChapterEval是章節分布差異計算函數。 *3000，*15操作是對三個不同的因素差異影響數量級進行調整。差異的倒數為試卷的適應度fitness，*10000操作也是用于調整數量級。由上面函數可以看出，在線考試系統抽題時需要考慮的因素是可以擴展的，只需添加新的差異計算函數就行了。差異越小意味著試卷適應度越高，這樣的試卷就是越符合設定的難度、完成時間和章節分布。

（4）選擇。

也就是從父代選出交配的對象。在本系統中，選擇輪盤法作為選擇算子。這樣適應度越高，被選擇的機會越高，而適應度低的，被選擇的機會就低。通過多次輪盤后就產生的交配的序列。

（5）交叉。

通過上面的選擇產生的一列交配對隊列。本系統采用單點交叉算子。實現代碼如下：

public void Crossover（Paper paper1， Paper paper2）

//交叉操作。其中，paper1和paper2表示兩個要雜交的對象。

{double d = random.NextDouble（）；

//以一定的概率交叉，若不交叉，則直接不變遺傳到下代。

If （d

{ int m = random.Next（0， paper1.sq.Count - 1）； //產生交叉點的位置

int temp = 0；

for （； m < paper1.sq.Count； m++）

{ temp = paper1.sq[m]；

//交換交叉點后的所有題目

paper1.sq[m] = paper2.sq[m]；

paper2.sq[m] = temp； } }}

（6）變異。

在本系統中，對群中所有個體以事先設定的編譯概率判斷是否進行變異；對進行變異的個體隨機選擇變異位進行變異。對于每次選擇的變異個體，只選擇一個變異位進行變異。本系統的變異率設置為0.3，要高于傳統建議的0.1。這是因為對于在線考試系統而言，變異比交叉更為重要。由于在線考試系統收斂得比較快，高變異率有利于進化。

使用變異操作的意義在于，在適應度高的試卷下微調一道題目，產生的結果可能變得更好或者更差。變得更好的試卷，在選擇算子選擇時更有可能遺傳到下一代；而變差的試卷更容易被淘汰，那些沒變異的試卷則以介于它們兩者之間的可能性遺傳到下一代。由此可看出一代將比一代優勝。

在線考試系統就是經過這一系列的過程（選擇、交配和突變），產生出不同于初始一代的新一代個體，并一代一代向增加整體適應度的方向發展。每個個體被評價，計算出適應度，兩個個體交配，然后突變，產生第三代。周而復始，直到終止條件滿足為止。

3 結語

本文設計和開發了一個基于B/S的在線考試系統，并應用遺傳算法解決多目標約束條件下的自動組卷問題，實踐證明用遺傳算法求解組卷問題具有很好的效果。

參考文獻

[1]譚浩強.C++程序設計[M].北京：清華大學出版社，2004.

[2]蘇成.C++程序設計教程[M].2版.北京：清華大學出版社，2013.

[3]丁振國，胡志芳，朱建新.基于J2EE平臺的在線考試系統的設計與實現[J].陜西理工學院學報：自然科學版，2009，25（1）：56-61.

[4]張敬敏，曲文龍.離散數學網上考試系統的設計與實現[J].計算機工程與設計，2008，29（8）：2143-2145.