王莉

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

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

王莉

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

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

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

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

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

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

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

1.1遺傳算法介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1在線(xiàn)考試系統(tǒng)的目標(biāo)

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

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

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

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

2.2.1遺傳算法的編碼方案

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

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

2.2.2初始種群生成

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

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

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

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

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

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

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

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

2.2.4遺傳算法算子

1）選擇算子

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

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

2）交叉算子

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

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

3）變異算子

變異算子概率公式為

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

2.2.5遺傳算法的終止條件

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

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

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

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

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

基于B/S結(jié)構(gòu)的在線(xiàn)考試系統(tǒng)還會(huì)采用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)的高校在線(xiàn)考試系統(tǒng)，用戶(hù)只需要在操作界面上進(jìn)行注冊(cè)和登錄即可使用相應(yīng)功能。在實(shí)際的考試過(guò)程中，學(xué)生只需要與服務(wù)器進(jìn)行交互，Web和服務(wù)器會(huì)對(duì)數(shù)據(jù)進(jìn)行處理，因此考試平臺(tái)是安全并且開(kāi)放的。

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

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

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

針對(duì)在線(xiàn)考試系統(tǒng)需求，將該考試系統(tǒng)分為用戶(hù)管理模塊、題庫(kù)管理模塊、評(píng)估管理模塊、成績(jī)查詢(xún)模塊以及考試管理模塊這5大管理模塊。

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

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

4　結(jié)論

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

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

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

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

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

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

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

［7］張亞靜，楊毅.遺傳算法在通用試題庫(kù)自動(dòng)組卷中的應(yīng)用［J］.湖北民族學(xué)院學(xué)報(bào)：自然科學(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稿件編號(hào)：201503252

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