基于遺傳算法的在線考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

摘 要：在線考試系統(tǒng)中最重要的組成部分之一是試題組卷，本文將遺傳算法應(yīng)用于《高級(jí)程序設(shè)計(jì)語言》試題庫自動(dòng)組卷方法中，得出多目標(biāo)問題求解模型。實(shí)踐結(jié)果表明，遺傳算法能有效地解決自動(dòng)組卷問題，具有較好的使用性能和實(shí)用性。

關(guān)鍵詞：遺傳算法 在線考試系統(tǒng) 自動(dòng)組卷 在線考試系統(tǒng)

中圖分類號(hào)：G4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1673-9795（2013）09（a）-0021-02

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

1 系統(tǒng)結(jié)構(gòu)與設(shè)計(jì)

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

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

2 系統(tǒng)主要功能的實(shí)現(xiàn)方法

系統(tǒng)的主要功能模塊包括：登錄，題庫管理，考試，自動(dòng)組卷，用戶管理。其中組卷部分，通過使用遺傳算法，滿足試卷難度、題目章節(jié)分布、題目完成時(shí)間三個(gè)目標(biāo)因素進(jìn)行組卷，加快了組卷速度，解決了多目標(biāo)組卷的難題。另外考慮學(xué)生考試時(shí)，可能會(huì)出現(xiàn)系統(tǒng)意外關(guān)閉等偶然情況，設(shè)計(jì)時(shí)添加系統(tǒng)自動(dòng)保存和恢復(fù)功能，能夠恢復(fù)到意外發(fā)生前的作答題目和作答答案狀態(tài)。

2.1 考試

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

（1）學(xué)生選擇考試，系統(tǒng)檢查時(shí)間，是否在考試時(shí)間范圍內(nèi)。若符合條件，執(zhí)行下一步。

（2）檢查學(xué)生是否進(jìn)行過這次考試，若沒進(jìn)行過則執(zhí)行（3），若已經(jīng)進(jìn)行過考試則執(zhí)行（4）。

（3）系統(tǒng)生成試題，返回給考生，執(zhí)行（5）。

（4）系統(tǒng)按之前保存的選題和作答進(jìn)行恢復(fù)，返回顯示給學(xué)生，執(zhí)行（5）。

（5）考生作答，系統(tǒng)記錄作答情況。

（6）考生提交試題，系統(tǒng)返回提交成功信息。

（7）對(duì)學(xué)生試卷進(jìn)行評(píng)分，并把結(jié)果保存。

因此，考試時(shí)序圖如圖1所示。

2.2 自動(dòng)組卷

本系統(tǒng)采用遺傳算法自動(dòng)組卷，它可以滿足復(fù)雜的多目標(biāo)出題。傳統(tǒng)隨機(jī)出題，僅僅是從系統(tǒng)里面隨機(jī)生成隨機(jī)數(shù)字組成試卷，然后驗(yàn)證試卷是否符合出題要求。這種出題搜索是盲目的，需要搜索大量題目才有可能滿足出題條件，所以幾乎不可能符合復(fù)雜的多目標(biāo)的出題要求。

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

在線考試系統(tǒng)遺傳算法的實(shí)現(xiàn)：

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

在本文考試系統(tǒng)中，遺傳算法的編碼方式不是采用傳統(tǒng)的01編碼，而是采用如下的編碼方式：設(shè)一張?jiān)嚲碛?0道題目，則有10個(gè)基因，每個(gè)基因用題庫中題目號(hào)表示，如51，3，21，5，11，6，55，32，44，21即是一個(gè)基因串。

（2）產(chǎn)生初代種群。

實(shí)現(xiàn)代碼如下：

public List GetInitPopulation（）//生成設(shè)定數(shù)目的初代種群

{ List al = new List（）；

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

{ al.Add（GetRandomPaper （））； }

return al； }

（3）適應(yīng)度函數(shù)。

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是難度評(píng)價(jià)差異計(jì)算函數(shù)，TimeEval是時(shí)間差異計(jì)算函數(shù)，ChapterEval是章節(jié)分布差異計(jì)算函數(shù)。 *3000，*15操作是對(duì)三個(gè)不同的因素差異影響數(shù)量級(jí)進(jìn)行調(diào)整。差異的倒數(shù)為試卷的適應(yīng)度fitness，*10000操作也是用于調(diào)整數(shù)量級(jí)。由上面函數(shù)可以看出，在線考試系統(tǒng)抽題時(shí)需要考慮的因素是可以擴(kuò)展的，只需添加新的差異計(jì)算函數(shù)就行了。差異越小意味著試卷適應(yīng)度越高，這樣的試卷就是越符合設(shè)定的難度、完成時(shí)間和章節(jié)分布。

（4）選擇。

也就是從父代選出交配的對(duì)象。在本系統(tǒng)中，選擇輪盤法作為選擇算子。這樣適應(yīng)度越高，被選擇的機(jī)會(huì)越高，而適應(yīng)度低的，被選擇的機(jī)會(huì)就低。通過多次輪盤后就產(chǎn)生的交配的序列。

（5）交叉。

通過上面的選擇產(chǎn)生的一列交配對(duì)隊(duì)列。本系統(tǒng)采用單點(diǎn)交叉算子。實(shí)現(xiàn)代碼如下：

public void Crossover（Paper paper1， Paper paper2）

//交叉操作。其中，paper1和paper2表示兩個(gè)要雜交的對(duì)象。

{double d = random.NextDouble（）；

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

If （d

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

int temp = 0；

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

{ temp = paper1.sq[m]；

//交換交叉點(diǎn)后的所有題目

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

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

（6）變異。

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

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

在線考試系統(tǒng)就是經(jīng)過這一系列的過程（選擇、交配和突變），產(chǎn)生出不同于初始一代的新一代個(gè)體，并一代一代向增加整體適應(yīng)度的方向發(fā)展。每個(gè)個(gè)體被評(píng)價(jià)，計(jì)算出適應(yīng)度，兩個(gè)個(gè)體交配，然后突變，產(chǎn)生第三代。周而復(fù)始，直到終止條件滿足為止。

3 結(jié)語

本文設(shè)計(jì)和開發(fā)了一個(gè)基于B/S的在線考試系統(tǒng)，并應(yīng)用遺傳算法解決多目標(biāo)約束條件下的自動(dòng)組卷問題，實(shí)踐證明用遺傳算法求解組卷問題具有很好的效果。

參考文獻(xiàn)

[1]譚浩強(qiáng).C++程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2004.

[2]蘇成.C++程序設(shè)計(jì)教程[M].2版.北京：清華大學(xué)出版社，2013.

[3]丁振國，胡志芳，朱建新.基于J2EE平臺(tái)的在線考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].陜西理工學(xué)院學(xué)報(bào)：自然科學(xué)版，2009，25（1）：56-61.

[4]張敬敏，曲文龍.離散數(shù)學(xué)網(wǎng)上考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（8）：2143-2145.