基于遺傳算法的高校在線考試系統研究

王莉

（河海大學江蘇南京211100）

基于遺傳算法的高校在線考試系統研究

王莉

（河海大學江蘇南京211100）

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

高校教育；遺傳算法；在線考試系統；組卷策略

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

在我國，很多高校結合自身學科特點、職業技能培訓以及教學需要等，已經建立了一些適合自身發展的在線考試系統，而且其系統實現了在線報名、考試、評分以及成績評估等智能化的考試功能［2］。按高校在線考試系統的組成方式可分為按流程模塊方式、按功能模塊方式以及按組合模塊方式等。而目前絕大部分的在線考試系統采用的為以題庫為基礎的按功能模塊方式構建的。

本研究在現有的高校在線考試系統理論的基礎上，添加了成熟的遺傳算法，設計了基于遺傳算法的高校在線考試系統，該系統相對于傳統的高校在線考試系統，其組卷的效果更顯著。

1　遺傳算法技術的概述

1.1遺傳算法介紹

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

1.2遺傳算法的參數

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

1）適應度函數：為計算機智能地選取個體到下一代參照依據。適應度數值的大小表明個體對環境的適應情況。

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

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

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

1.3遺傳算法的設計流程

在了解遺傳算法參數的基礎上，現給出遺傳算法的設計流程圖如圖1所示。

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

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

1.4遺傳算法的優勢

遺傳算法可用于復雜系統的優化，該算法具有較強的魯棒性［5］，其優勢主要有：

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

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

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

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

2　遺傳算法在考試系統中的應用

2.1在線考試系統的目標

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

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

2.2遺傳算法在在線考試系統中的應用

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

2.2.1遺傳算法的編碼方案

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

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

2.2.2初始種群生成

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

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

2.2.3選取適應度函數

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

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

若目標函數值恒為正，則適應度函數直接轉換為目標函數，表達式為：

本研究針對目標分量分配權值，以表明對各個目標的重視程度，由此組卷問題就轉換為目標函數求最小值問題。為了避免系統陷入局部最優，對適應度函數進行線性變換，具體變換表達式為：

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

2.2.4遺傳算法算子

1）選擇算子

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

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

2）交叉算子

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

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

3）變異算子

變異算子概率公式為

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

2.2.5遺傳算法的終止條件

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

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

3　基于遺傳算法的高校在線考試系統設計

3.1在線考試系統架構

該在線考試系統采用B/S結構，也就是瀏覽器/服務器結構。教師和學生可以方便地通過瀏覽器操作系統界面，其服務器端包括大部分的事務邏輯，而且系統的維護和更新都是針對服務器端進行操作的，客戶端沒有附加任何操作。總之，這種系統結構操作簡單，便于維護，能夠有效管理權限和數據庫數據。

基于B/S結構的在線考試系統還會采用ASP、JAVA、SQL以及HTML等技術，其采用的三層網絡架構圖如圖2所示。

圖2　三層網絡架構圖Fig.2The three layer network architecture diagrams

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

該考試系統結構圖如圖3所示。

圖3　在線考試系統結構圖Fig.3Online examination system structure diagram

3.2整個系統功能模塊

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

該在線考試系統功能設計圖如圖4所示。

圖4　在線考試系統功能設計圖Fig.4Online examination system function design

4　結論

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

［1］吳水秀，曾慶鵬，王明文.智能試卷生產和自適應考試系統［J］.計算機與現代化，1999（1）：36-39.

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

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

［4］樂光學，彭小寧，曾志峰.試題庫自動組卷系統的算法設計與實現［J］.計算機應用，2001，21（8）：198-200.

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

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

［7］張亞靜，楊毅.遺傳算法在通用試題庫自動組卷中的應用［J］.湖北民族學院學報：自然科學版，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—），女，安徽阜陽人，碩士。研究方向：財務管理。