王莉

（河海大學(xué)江蘇南京211100）

基于遺傳算法的高校在線考試系統(tǒng)研究

王莉

（河海大學(xué)江蘇南京211100）

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，越來越多的高校重視在線考試系統(tǒng)。在線考試系統(tǒng)由于擁有環(huán)保，提高教師工作效率以及考查的多樣性等優(yōu)勢，現(xiàn)在已經(jīng)成為一個研究熱點。本研究首先針對傳統(tǒng)的在線考試系統(tǒng)進行研究，然后利用遺傳算法的優(yōu)勢，將其算法與在線考試系統(tǒng)進行結(jié)合，設(shè)計了一種基于遺傳算法的高校在線考試系統(tǒng)，其系統(tǒng)較傳統(tǒng)的在線考試系統(tǒng)具有組卷效果較好、易于使用和維護以及操作界面友好等優(yōu)點，在教學(xué)過程中受到的師生的認可，有一定的應(yīng)用價值。

高校教育；遺傳算法；在線考試系統(tǒng)；組卷策略

現(xiàn)階段，隨著計算機科學(xué)與技術(shù)的迅猛發(fā)展，高校的教育方式也發(fā)生著變化。教育的考核是高校教育不可或缺的一部分，首先教育的考核可以及時了解學(xué)生學(xué)習的具體情況和把握學(xué)生的知識水平，然后教育的考核也是針對教師教學(xué)效果的評估，根據(jù)具體情況對學(xué)生進行階段性的評估會更好地幫助教師進行教學(xué)方式的調(diào)整。有關(guān)教師和學(xué)生的考核的主要手段就是試卷的評價，因此如何出一份客觀、全面的試卷則尤為重要［1］。而傳統(tǒng)的考試方式缺乏客觀和全面性，因此設(shè)計和開發(fā)高校在線考試系統(tǒng)有了較大的研究前景。

在我國，很多高校結(jié)合自身學(xué)科特點、職業(yè)技能培訓(xùn)以及教學(xué)需要等，已經(jīng)建立了一些適合自身發(fā)展的在線考試系統(tǒng)，而且其系統(tǒng)實現(xiàn)了在線報名、考試、評分以及成績評估等智能化的考試功能［2］。按高校在線考試系統(tǒng)的組成方式可分為按流程模塊方式、按功能模塊方式以及按組合模塊方式等。而目前絕大部分的在線考試系統(tǒng)采用的為以題庫為基礎(chǔ)的按功能模塊方式構(gòu)建的。

本研究在現(xiàn)有的高校在線考試系統(tǒng)理論的基礎(chǔ)上，添加了成熟的遺傳算法，設(shè)計了基于遺傳算法的高校在線考試系統(tǒng)，該系統(tǒng)相對于傳統(tǒng)的高校在線考試系統(tǒng)，其組卷的效果更顯著。

1　遺傳算法技術(shù)的概述

1.1遺傳算法介紹

遺傳算法是近年來發(fā)展迅速的一種模擬自然進化的搜尋最優(yōu)解的全局性優(yōu)化算法［3］，其算法最早由Michigan大學(xué)的J.Holland教授在1962年首次提出的，并且得到推廣和研究。該算法針對約束條件較多且復(fù)雜的系統(tǒng)提出了一種通用的解決方案，并且由于其不依賴于具體領(lǐng)域，具有很強的抗干擾性，因此已經(jīng)被廣泛應(yīng)用在圖像處理、機器學(xué)習、控制等領(lǐng)域。

1.2遺傳算法的參數(shù)

絕大數(shù)的遺傳算法的設(shè)計步驟都很相似［4］，主要實現(xiàn)在群體空間中搜尋最優(yōu)解。其實現(xiàn)過程中常借助以下參數(shù)：

1）適應(yīng)度函數(shù)：為計算機智能地選取個體到下一代參照依據(jù)。適應(yīng)度數(shù)值的大小表明個體對環(huán)境的適應(yīng)情況。

2）適應(yīng)度閾值：為評估群體優(yōu)化程度的一個重要指標。在群體優(yōu)化過程中，當個體的適應(yīng)度與群體適應(yīng)度變化差別較小時，就可以讓遺傳過程終止，而閾值就是衡量適應(yīng)度變化差別的標準。

3）群體規(guī)模：對于遺傳算法的運算效率有很大的影響。當群體規(guī)模較大時，其遺傳算法效率就較低，反之亦然。一般情況下，種群的大小為30到160。

4）交叉概率：在遺傳過程中，父體通過交叉得到子體，而交叉運算法則是由交叉概率決定的。若交叉概率數(shù)值較大時，則容易失去適應(yīng)度數(shù)值較大的結(jié)構(gòu)；而交叉概率值較低時，其一般取值為0.6到0.95。

1.3遺傳算法的設(shè)計流程

在了解遺傳算法參數(shù)的基礎(chǔ)上，現(xiàn)給出遺傳算法的設(shè)計流程圖如圖1所示。

圖1　遺傳算法的設(shè)計流程圖Fig.1Design flow chart of genetic algorithm

從上述的遺傳算法設(shè)計流程圖可知，遺傳算法進化流程比較明晰，容易理解，而且實現(xiàn)簡便?，F(xiàn)在只是一個遺傳算法的基本框架，若遺傳算法得到改善只需對流程圖的某一個環(huán)節(jié)進行修改即可。

1.4遺傳算法的優(yōu)勢

遺傳算法可用于復(fù)雜系統(tǒng)的優(yōu)化，該算法具有較強的魯棒性［5］，其優(yōu)勢主要有：

1）可行性求解具有廣泛性。遺傳算法主要針對基因個體，并不是對象本身，而且針對智能組卷問題的求解多樣性提供了理論支持。

2）具有啟發(fā)式的隨機搜尋特點。遺傳算法并不是隨意盲目地窮舉式的搜尋，而是一種自適應(yīng)的按概率搜尋技術(shù)，其操作主要按照概率方式運行。

3）不再需要輔助或幫助信息。

4）適合群體式搜尋特點。遺傳算法可以采用多個搜尋點進行搜尋信息，覆蓋面較大，利于實現(xiàn)并行計算，可有效加快搜尋進程和全局優(yōu)化。

2　遺傳算法在考試系統(tǒng)中的應(yīng)用

2.1在線考試系統(tǒng)的目標

在線考試系統(tǒng)的核心是組卷系統(tǒng)，而組卷的算法則是整個系統(tǒng)的最關(guān)鍵的技術(shù)之一［6］。首先教師應(yīng)根據(jù)所講授的課程選定該課程的題量和題型，接著根據(jù)學(xué)生的認知情況決定試題的難易程度和知識點分布等，然后讓考試系統(tǒng)根據(jù)上述條件采用組卷的算法生成所需的試卷。

需要注意的是，高校在線考試系統(tǒng)的對象主要是教師和學(xué)生，所以在設(shè)計該考試系統(tǒng)之前需要了解教師和學(xué)生的試卷要求。該系統(tǒng)針對教師提供組卷、評卷以及成績評估等功能，而對于學(xué)生提供試卷測試功能。根據(jù)教育的目的對試卷的質(zhì)量評價標準為：1）試卷難度要適中；2）試卷覆蓋的知識點要全面；3）試卷的題型要合理；4）試卷中知識的遺漏率和重復(fù)率要低；5）、試卷內(nèi)容要靈活；6）試卷區(qū)分學(xué)生學(xué)習水平的效果要好。

2.2遺傳算法在在線考試系統(tǒng)中的應(yīng)用

本研究在線考試系統(tǒng)的設(shè)計要求和遺傳算法的設(shè)計流程圖的基礎(chǔ)上設(shè)計一種遺傳算法。下面就詳細介紹該遺傳算法的設(shè)計思路。

2.2.1遺傳算法的編碼方案

編碼方式是整個遺傳算法基礎(chǔ)。本研究針對在線考試系統(tǒng)的組卷約束條件多，編碼長度較長以及編碼表達意義不明晰等特點，采用分組編碼方案。主要因為試題庫的試題一般是以題型為單位，而且每種題型都會進行獨立編碼，最后再針對每個題型的編碼執(zhí)行二進制轉(zhuǎn)換。這種以試題的題號為基礎(chǔ)的編碼方式表達變量的含義清晰明了，易于理解，不需要額外解碼，而且還克服了由題量增多引起的搜尋空間較廣以及編碼長度較大等缺陷，能夠有效地改善遺傳算法的正確率和有效率。

若染色體編碼采用了分組編碼，即各個試題為試卷的基因組合，且用試題的題號表示基因值。例如，要利用選擇題、判斷題以及填空題組成一份試卷，題型用A、B、C表示，每種題型的題量用m1，m2，m3表示，則所有試題就表示為：A1A2…Am1B1B2…Bm2C1C2…Cm3。采用分組編碼使每個染色體的含義清晰，為保證每種題型的題量不變，在遺傳算法設(shè)計中都要按照分組編碼進行。

2.2.2初始種群生成

對題型進行分組編碼后就要實現(xiàn)初始種群的生成［7］。首先根據(jù)實際情況選定初始種群的規(guī)模，一般情況下會選定為50或者100。如果種群過大會導(dǎo)致計算效率下降；如果種群過小會導(dǎo)致計算過早結(jié)束，未達到全局最優(yōu)。

本研究以試卷題型為隨機生成初始種群的單位，以簡化遺傳算法過程，更快地完成組卷。例如，如果生成的試卷選擇題數(shù)量比重占20%，判斷題數(shù)量比重占20%，計算題數(shù)量比重占40%，問答題數(shù)量比重占20%，則生成種群的規(guī)則也要滿足上述比重要求，由此生成的試卷組卷成功率更好，更容易滿足設(shè)計者的要求。

2.2.3選取適應(yīng)度函數(shù)

選取適應(yīng)度函數(shù)也會對在線考試系統(tǒng)的構(gòu)建起到了關(guān)鍵作用。通常由目標函數(shù)直接變換得到適應(yīng)度函數(shù)，而適應(yīng)度會影響種群個體的優(yōu)劣，即會影響種群的個體是否遺傳給下一代。通常適應(yīng)度值越大說明種群個體的適應(yīng)能力越強，越有可能遺傳給下一代，反之恰恰相反。選取適應(yīng)度函數(shù)有兩個準則：1）避免遺傳算法出現(xiàn)過早運算完畢的現(xiàn)象；2）克服后期運算的退化情況。

根據(jù)上述的選取適應(yīng)度函數(shù)準則，選取的目標函數(shù)為越小越好，適應(yīng)度函數(shù)卻是越大越好，而且目標函數(shù)必須與適應(yīng)度數(shù)值變化方向相反，即：

若目標函數(shù)值恒為正，則適應(yīng)度函數(shù)直接轉(zhuǎn)換為目標函數(shù)，表達式為：

本研究針對目標分量分配權(quán)值，以表明對各個目標的重視程度，由此組卷問題就轉(zhuǎn)換為目標函數(shù)求最小值問題。為了避免系統(tǒng)陷入局部最優(yōu)，對適應(yīng)度函數(shù)進行線性變換，具體變換表達式為：

其中F（X）為適應(yīng)度函數(shù)，f（x）為目標函數(shù)，α為正常量，β為常量系數(shù)。而且確定系數(shù)α和β的方法會根據(jù)系統(tǒng)的不同有所變化。

2.2.4遺傳算法算子

1）選擇算子

相對于交叉算子和變異算子，選擇選擇對遺傳算子的效果效率影響最大，其可以影響遺傳算子的方向。選擇算子以個體的適應(yīng)度數(shù)值為基準，并根據(jù)個體的質(zhì)量決定淘汰或者復(fù)制個體。本研究采用改進的輪盤方式進行復(fù)制。

在具體地實現(xiàn)輪盤復(fù)制方法時，每一次遺傳操作后都要針對子代種群計算其適應(yīng)度數(shù)值，并找出最大值，接著把此最大值與父代種群的適應(yīng)度最大數(shù)值進行比較，若父代的適應(yīng)度數(shù)值大于子代適應(yīng)度數(shù)值，則隨機選取子代種群的一個個體進行淘汰，否則不做任何變化，一直循環(huán)下去。

2）交叉算子

通常在種群中隨機選擇兩個染色體，并在染色體某一點隨機進行點交換，以得到下一代的新個體。自適應(yīng)交叉概率公式為：

其中fmax為種群適應(yīng)度數(shù)值的最大值，favg為每代種群的適應(yīng)度數(shù)值的平均值，f′為兩個個體的適應(yīng)值的較大值，pc1=0.9，pc2=0.6。

3）變異算子

變異算子概率公式為

其中fmax為種群適應(yīng)度數(shù)值最大值，favg為每代種群的適應(yīng)度數(shù)值的平均值，f為準備變異個體的適應(yīng)度數(shù)值，pm1= 0.1，pm2=0.001。

2.2.5遺傳算法的終止條件

終止遺傳算法的條件主要有：1）限制遺傳迭代次數(shù)，比如可設(shè)置迭代次數(shù)300次就結(jié)束；2）通過適應(yīng)度數(shù)值差值進行控制。

本研究的遺傳算法的終止條件為上述兩種方式的結(jié)合體。在迭代次數(shù)限制的情況下，若個體的適應(yīng)度數(shù)值差值小于預(yù)定值則停止進化；否則會一直進化直到達到規(guī)定的迭代次數(shù)。

3　基于遺傳算法的高校在線考試系統(tǒng)設(shè)計

3.1在線考試系統(tǒng)架構(gòu)

該在線考試系統(tǒng)采用B/S結(jié)構(gòu)，也就是瀏覽器/服務(wù)器結(jié)構(gòu)。教師和學(xué)生可以方便地通過瀏覽器操作系統(tǒng)界面，其服務(wù)器端包括大部分的事務(wù)邏輯，而且系統(tǒng)的維護和更新都是針對服務(wù)器端進行操作的，客戶端沒有附加任何操作?？傊?，這種系統(tǒng)結(jié)構(gòu)操作簡單，便于維護，能夠有效管理權(quán)限和數(shù)據(jù)庫數(shù)據(jù)。

基于B/S結(jié)構(gòu)的在線考試系統(tǒng)還會采用ASP、JAVA、SQL以及HTML等技術(shù)，其采用的三層網(wǎng)絡(luò)架構(gòu)圖如圖2所示。

圖2　三層網(wǎng)絡(luò)架構(gòu)圖Fig.2The three layer network architecture diagrams

采用三層網(wǎng)絡(luò)架構(gòu)的高校在線考試系統(tǒng)，用戶只需要在操作界面上進行注冊和登錄即可使用相應(yīng)功能。在實際的考試過程中，學(xué)生只需要與服務(wù)器進行交互，Web和服務(wù)器會對數(shù)據(jù)進行處理，因此考試平臺是安全并且開放的。

該考試系統(tǒng)結(jié)構(gòu)圖如圖3所示。

圖3　在線考試系統(tǒng)結(jié)構(gòu)圖Fig.3Online examination system structure diagram

3.2整個系統(tǒng)功能模塊

針對在線考試系統(tǒng)需求，將該考試系統(tǒng)分為用戶管理模塊、題庫管理模塊、評估管理模塊、成績查詢模塊以及考試管理模塊這5大管理模塊。

該在線考試系統(tǒng)功能設(shè)計圖如圖4所示。

圖4　在線考試系統(tǒng)功能設(shè)計圖Fig.4Online examination system function design

4　結(jié)論

本研究在傳統(tǒng)的在線考試系統(tǒng)的基礎(chǔ)上，將遺傳算法與在線考試系統(tǒng)進行有機結(jié)合，設(shè)計了一種基于遺傳算法的高校在線系統(tǒng)。經(jīng)過測試對比，相對于傳統(tǒng)的在線考試系統(tǒng)，其基于遺傳算法的系統(tǒng)具有組卷成功率高、操作界面友好以及方便使用和維護等優(yōu)勢，具有較好的教學(xué)使用價值。

［1］吳水秀，曾慶鵬，王明文.智能試卷生產(chǎn)和自適應(yīng)考試系統(tǒng)［J］.計算機與現(xiàn)代化，1999（1）：36-39.

［2］張瑞，蘇建民.基于改進遺傳算法的智能組卷在試題庫建設(shè)中的研究［J］.自動化技術(shù)與應(yīng)用，2010，29（1）：41-43.

［3］馬德良，盧昌輝，王小樂.基于改進遺傳算法的智能組卷方法［J］.計算機應(yīng)用，2009（7）：1884-1886.

［4］樂光學(xué)，彭小寧，曾志峰.試題庫自動組卷系統(tǒng)的算法設(shè)計與實現(xiàn)［J］.計算機應(yīng)用，2001，21（8）：198-200.

［5］馮冬青，王非，馬雁.遺傳算法中選擇交叉策略的改進［J］.計算機工程，2008，34（19）：189-191.

［6］張砦，王友仁.遺傳算法在網(wǎng)絡(luò)子線智能組卷中的應(yīng)用研究［J］.計算機測量與控制，2005，13（11）：1223-1225.

［7］張亞靜，楊毅.遺傳算法在通用試題庫自動組卷中的應(yīng)用［J］.湖北民族學(xué)院學(xué)報：自然科學(xué)版，2005，20（5）：714-719.

Research on the online examination system of colleges and universities based on genetic algorithm

WANG Li
（Hohai University，Nanjing 211100，China）

With the development of Internet technology，more and more colleges and universities pay attention to online examination system.Online examination system withenvironmental protection，improve the efficiency of teachers and examine the diversityadvantage，now has become a hot topic of research.This research firstly onlineexamination system of the traditional research，and then use genetic algorithmadvantage，the algorithm and the online examination system are combined，the design of a online examination system of colleges and Universities Based on genetic algorithm，thesystem of online examination system has better effect than traditional test，it is easy touse and maintain and friendly operation interface and so on，are in the process of teaching teachers and students recognition，it has certain application value.

higher education；genetic algorithm；online examination system；test paper strategy

TN99

A

1674－6236（2015）24-0029-03

2015-03-19稿件編號：201503252

王莉（1989—），女，安徽阜陽人，碩士。研究方向：財務(wù)管理。