基于自動組卷與判卷的在線考試系統(tǒng)設(shè)計

周志鋒+童凌+王浩茂

摘要：網(wǎng)上在線考試目前正在逐步取代傳統(tǒng)的考試方式。針對程序設(shè)計類課程，實現(xiàn)了一種能夠進(jìn)行自動組卷和判卷的在線考試系統(tǒng)。首先利用遺傳算法將試題模擬自然因子通過自然選擇機(jī)制，自動組成符合要求的試卷。完成考試后，借鑒ACM在線測評機(jī)制自動對試卷進(jìn)行評判，從而大大減輕了教師工作量。該系統(tǒng)具有實用性強(qiáng)、使用方便等優(yōu)點，在實際應(yīng)用中取得了良好效果。

關(guān)鍵詞：程序設(shè)計類課程；在線考試系統(tǒng)；遺傳算法；自動組卷；自動判卷

DOIDOI：10.11907/rjdk.171014

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）006-0066-04

0 引言

隨著計算機(jī)技術(shù)在教學(xué)中的廣泛應(yīng)用，考試方式由以前單一、固定試題和人工閱卷的傳統(tǒng)方式，逐漸向多樣化、靈活試題和計算機(jī)自動評分的無紙化考試過渡。在數(shù)字化考試中，使用在線網(wǎng)絡(luò)考試是當(dāng)今主流的考試方式。在歐美地區(qū)，較有影響力的機(jī)構(gòu)如美國教育考試中心ETS舉辦的美國研究生入學(xué)考試GRE和計算機(jī)文化考試、高級就業(yè)計算機(jī)科學(xué)考試等，其考試形式即完全采用計算機(jī)在線進(jìn)行。除此之外，目前的托福和雅思等標(biāo)準(zhǔn)化英語水平能力測試也采用了網(wǎng)絡(luò)考試方式。很多職業(yè)資格認(rèn)證機(jī)構(gòu)、教育主管部門以及大型公司招聘應(yīng)屆生時都開發(fā)了針對各自目標(biāo)考生的考試系統(tǒng)，如中國計算機(jī)學(xué)會計算機(jī)職業(yè)資格認(rèn)證（CCF）即采用了網(wǎng)上出題、在線編程提交的方式。在各大高校，在線網(wǎng)絡(luò)考試也得到了廣泛認(rèn)可，如清華大學(xué)、上海交通大學(xué)等高校都開發(fā)出了符合學(xué)校需求的在線考試系統(tǒng)[1]。

在上述眾多考試系統(tǒng)中，大部分考試系統(tǒng)都實現(xiàn)了對客觀題的自動評分，部分考試系統(tǒng)還研究出了對于不同種類主觀題的評分方法。如在GRE考試中，美國教育考試中心根據(jù)近年來對作文的自動評分研究機(jī)制，推出了對于考試寫作部分的自動化評分系統(tǒng)，減輕了閱卷人過去批改大量作文的負(fù)擔(dān)；中國計算機(jī)學(xué)會在其開展的計算機(jī)職業(yè)資格認(rèn)證考試系統(tǒng)中，也對考生提交的代碼實行自動評分。然而，實現(xiàn)主觀題評分的系統(tǒng)適用性很窄，無法將其項目推廣到程序設(shè)計類課程考試中。針對這些問題，本文提出一種借鑒ACM在線測評機(jī)制的自動判卷功能方式，對程序設(shè)計類的主觀編程試題進(jìn)行客觀評判。同時，自動組卷也是實現(xiàn)在線考試的重要環(huán)節(jié)之一，本設(shè)計采用遺傳算法，按照教師對試卷構(gòu)成的期望，隨機(jī)、高效、快速地從試題庫中抽取試題，組成一套高質(zhì)量的試卷。通過自動組卷與判卷兩者的結(jié)合，實現(xiàn)面向程序設(shè)計的高度自動化的考試系統(tǒng)，進(jìn)一步擺脫了人工干預(yù)，提供了一個能更好地展示學(xué)生實踐和思維能力的平臺。

1 系統(tǒng)功能設(shè)計

本系統(tǒng)主要涉及3類用戶：管理員、教師、學(xué)生。對于不同用戶，則需要設(shè)置用戶管理模塊來維系這種角色分級，并設(shè)置不同權(quán)限。對于學(xué)生角色，系統(tǒng)設(shè)置在線答卷模塊來管理整個考試過程；對于教師角色，需參與出卷、組卷、發(fā)布考試的考試準(zhǔn)備流程。因此，設(shè)置試卷管理模塊來實現(xiàn)對于試卷的常用操作，同時設(shè)置題庫管理模塊，由教師負(fù)責(zé)出題、管理題庫；管理員角色具備所有權(quán)限，主要涉及對各種關(guān)鍵實體的管理，因此設(shè)置了后臺管理模塊。系統(tǒng)自動完成的模塊是自動組卷模塊和自動判卷模塊，該模塊是本系統(tǒng)的關(guān)鍵模塊。本系統(tǒng)的功能架構(gòu)如圖1所示。

2 核心功能設(shè)計

2.1 基于遺傳算法的自動組卷

遺傳算法的機(jī)器自動組卷，利用教師提供的參數(shù)，靈活建立相應(yīng)組卷模型，然后對題目進(jìn)行篩選，以自動生成科學(xué)合理的試卷。

遺傳算法（Genetic Algorithm，簡稱GA）是一種借鑒生物進(jìn)化機(jī)制（適者生存、優(yōu)勝劣汰）的隨機(jī)搜索算法[2-4]。其通過建立計算模型，模擬達(dá)爾文的遺傳選擇和生物進(jìn)化過程，搜索出符合“環(huán)境”要求的最優(yōu)解，所以該算法常用來解決多約束下求最優(yōu)解的問題。本系統(tǒng)在應(yīng)用遺傳算法之前，首先要將試卷解碼成“染色體”，然后抽取一定數(shù)量的攜帶遺傳物質(zhì)的試卷集合初始化為種群，再根據(jù)環(huán)境選擇、交叉、變異等一些基本的演化操作，模擬生物進(jìn)化行為，篩選出最適合“環(huán)境”生存的最優(yōu)試卷集。

該自動組卷實現(xiàn)流程如圖2所示。

2.2.1 染色體編碼與初始群體設(shè)計

按照傳統(tǒng)的遺傳算法問題，首先將要求解的問題化成0、1形式的編碼染色體。染色體應(yīng)該按題型分段，因為本文針對的是程序設(shè)計類考試，基本題型是單選、多選、判斷、程序設(shè)計4種類型，所以分段染色（例如一個數(shù)據(jù)結(jié)構(gòu)試題有單選5、雙選5、判斷5、程序設(shè)計題2），如圖3所示。

2.2.3 遺傳算子設(shè)計

（1）選擇算子。選擇算子主要用于模擬自然選擇的選擇概率，確定該個體是否能夠“生存”。本文采用輪盤賭算法，每個個體的選擇概率為Aj/∑Nj=1Aj。其中Aj代表第j個個體的適應(yīng)度，適應(yīng)度高的個體將有更大機(jī)率“生存”下來。

（2）交叉算子。由于染色體是分段編碼，所以采用多點交叉，交叉率設(shè)為0.90～0.95比較合適。在“交叉”時必須保證互換的題目分?jǐn)?shù)一樣，分?jǐn)?shù)相加等于總分，而且不能在交叉點前出現(xiàn)題目，否則此次“交叉”不合法。

（3）變異算子。在遺傳中，一般較少發(fā)生變異，變異率設(shè)置在0.02～0.05范圍內(nèi)比較適宜。

2.3 自動判卷

要實現(xiàn)較為客觀地考核學(xué)生的編程能力，程序設(shè)計類考試的重點不是單純地將選擇、填空等客觀題搬到計算機(jī)上，而是包含代碼編寫類試題的考核，這類試題可較為準(zhǔn)確、客觀地反映學(xué)生對程序設(shè)計思想和語言的掌握情況。本文根據(jù)程序設(shè)計試題代碼的特點，設(shè)計沙盒來真實運(yùn)行學(xué)生編寫的代碼，并根據(jù)得到的結(jié)果智能評判該類主觀題的得分。

本文設(shè)計的自動判卷是面向程序設(shè)計類的客觀題和主觀題。對于客觀題，系統(tǒng)可以直接通過與標(biāo)準(zhǔn)答案對比而得出對應(yīng)分?jǐn)?shù)[5-6]；對于主觀題，它的輸入和輸出也具備唯一性，其中一個輸入對應(yīng)一個輸出，利用預(yù)先設(shè)置的測試數(shù)據(jù)即輸入集，執(zhí)行輸入程序，得出輸出集。通過將輸出集的每個點與標(biāo)準(zhǔn)答案輸出集對比，即可將通過測試點作為該題的評分依據(jù)，得到該題的分?jǐn)?shù)。通過該方式可大大減少對主觀程序題的主觀性判斷，而是以更科學(xué)的客觀依據(jù)進(jìn)行判斷。在此期間，自動判卷功能輔助子系統(tǒng)必須保持沉睡狀態(tài)，以等待喚醒。自動判卷流程如圖4所示。

其中每層的解釋如下：

（1）試題程序傳入。首先利用Linux消息隊列方式，將試題中源程序的代碼、題號、所用語言等信息封裝在上述mesg上，寫入Linux系統(tǒng)下的消息隊當(dāng)中。通過系統(tǒng)msgget函數(shù)[intmsgget（key_t key，intoflag）；]創(chuàng)建消息隊列，命名為key，并獲取消息隊列的標(biāo)識符，然后調(diào)用系統(tǒng)msgsnd函數(shù)[intmsgsnd（intmsqid，const void * ptr，size_t length，int flag）]將消息存入對應(yīng)的消息隊列中。

（2）試題程序接收。在接受消息時，通過系統(tǒng)msgget函數(shù)[intmsgget（key_t key，intoflag）；]獲取對應(yīng)key的消息隊列的標(biāo)識符，再通過系統(tǒng)msgrcv函數(shù)[ssize_tmsgrcv（intmsqid，void * ptr，size_t length，long type，int flag）；]讀取對應(yīng)標(biāo)識符消息隊列中的一條消息mesg，從而獲取隊列中的消息內(nèi)容。

（3）編譯。對GCC、JDK等編譯器進(jìn)行必要的安全處理，利用bash命令對C++/C、Pascal、Java等語言程序的程序源碼選擇對應(yīng)的編譯器進(jìn)行編譯。編譯成功則進(jìn)行下一步，否則返回結(jié)果到父進(jìn)程等待計算。

（4）鏈接。經(jīng)過編譯成功后，獲取對應(yīng)的obj二進(jìn)制代碼，通過調(diào)用ld鏈接命令，執(zhí)行自動鏈接，產(chǎn)生可執(zhí)行代碼，提供給下一步使用。

（5）運(yùn)行。通過系統(tǒng)調(diào)用子進(jìn)程child_process，child_process運(yùn)行編譯鏈接后的程序，由父進(jìn)程監(jiān)控子進(jìn)程，一旦子進(jìn)程崩潰或正常退出，會發(fā)送相應(yīng)的SIGNAL給父進(jìn)程，此時父進(jìn)程進(jìn)行相應(yīng)處理。

（6）測試數(shù)據(jù)輸入。當(dāng)前位置主要是為了數(shù)據(jù)的輸入和輸出位置的轉(zhuǎn)換，通過調(diào)用Liunx的系統(tǒng)函數(shù)，將數(shù)據(jù)輸入從標(biāo)準(zhǔn)輸入Console轉(zhuǎn)換到標(biāo)準(zhǔn)測試文件輸入，并將標(biāo)準(zhǔn)輸出Console重定向到一個臨時文件中，供下一步進(jìn)行比較。

（7）比較。通過上述4步以后，轉(zhuǎn)入對比結(jié)果階段。本階段主要是進(jìn)行數(shù)據(jù)對比，通過調(diào)用bash命令diff，將該程序通過測試輸入產(chǎn)生的輸出臨時文件與標(biāo)準(zhǔn)輸出答案文件進(jìn)行對比，并得出正確率。

（8）獲取內(nèi)存資源等情況。通過父進(jìn)程監(jiān)控子進(jìn)程，可以通過wait4函數(shù)，獲取進(jìn)程狀態(tài)和資源占用情況等，判斷是否符合題目要求，一旦檢測出非法狀況，也當(dāng)作異常處理，轉(zhuǎn)去計算結(jié)果。

（9）計算總分并返回。通過將原試卷主觀題與客觀題分類后，經(jīng)過兩個子進(jìn)程得到的總分相加，得到本試卷的分?jǐn)?shù)，并將其存入數(shù)據(jù)庫對應(yīng)試卷的學(xué)生id位置。消息隊列的交互如圖5所示。

3 系統(tǒng)實現(xiàn)

本系統(tǒng)采用B/S結(jié)構(gòu)模式，利用Apache服務(wù)器、MYSQL數(shù)據(jù)庫和SSH開源框架進(jìn)行搭建。Apache服務(wù)器、MYSQL數(shù)據(jù)庫是開源軟件，所以具有更好的穩(wěn)定性與安全性。SSH即Struts+Spring+Hibernate，利用該體系設(shè)計系統(tǒng)，能夠為整個系統(tǒng)后期的維護(hù)、擴(kuò)展等提供更多便利，程序的結(jié)構(gòu)脈絡(luò)更加清晰明了。實際應(yīng)用結(jié)果表明，該系統(tǒng)運(yùn)行性能良好。

4 結(jié)語

本項目旨在讓目前高校計算機(jī)程序設(shè)計類課程考試脫離傳統(tǒng)紙質(zhì)考試的限制。平臺采用了一種自動組卷算法，能夠大大提高組卷效率以及卷面題目構(gòu)成的合理性，以符合教師的組卷期望。同時，針對程序設(shè)計類課程的特點，引入并實現(xiàn)了特殊的自動裁判評分機(jī)制。該在線考試系統(tǒng)可大大減輕教師的工作量，在實踐中更加有效地考核并提升學(xué)生的編碼能力。

參考文獻(xiàn)：

[1]余穎，李曉昀，左貴啟，等. 基于自適應(yīng)遺傳算法的自動組卷策略研究[J]. 南華大學(xué)學(xué)報：自然科學(xué)版，2016（3）：61-65.

[2]呂苗苗. 基于遺傳算法的自動組卷系統(tǒng)的設(shè)計與實現(xiàn)[D].南京：南京理工大學(xué)，2012.

[3]張琨，楊會菊，宋繼紅，等. 基于遺傳算法的自動組卷系統(tǒng)的設(shè)計與實現(xiàn)[J]. 計算機(jī)工程與科學(xué)，2012（5）：178-183.

[4]袁鋒. 遺傳算法在自動組卷系統(tǒng)中的應(yīng)用[J]. 山東師范大學(xué)學(xué)報：自然科學(xué)版，2006（1）：53-56.

[5]楊志偉，曾艷姍. 基于Linux的ACM在線評測系統(tǒng)研究[J]. 計算機(jī)與現(xiàn)代化，2010（6）：166-169.

[6]鄭傳生. 基于B/S結(jié)構(gòu)的程序設(shè)計競賽自動測評系統(tǒng)的設(shè)計[J]. 計算機(jī)與現(xiàn)代化，2007（12）：109-111.

[7]楊呈永. 基于B/S結(jié)構(gòu)的大學(xué)英語在線考試系統(tǒng)設(shè)計與實現(xiàn)[D].成都：電子科技大學(xué)，2011.

[8]李佳. 《計算機(jī)基礎(chǔ)》課程上機(jī)考試系統(tǒng)的設(shè)計與實現(xiàn)[D].成都：電子科技大學(xué)，2011.

[9]顏韻. 基于B/S模式的單獨招生在線考試系統(tǒng)設(shè)計與實現(xiàn)[D].成都：電子科技大學(xué)，2013.

[10]樓玉萍. 基于B/S模式的計算機(jī)基礎(chǔ)考試系統(tǒng)的研究與實現(xiàn)[D].長沙：國防科學(xué)技術(shù)大學(xué)，2005.

[11]李亦松. 在線考試系統(tǒng)分析與設(shè)計[D].昆明：云南大學(xué)，2012.

[12]李敏. 在線考試系統(tǒng)設(shè)計與實現(xiàn)[D].濟(jì)南：山東大學(xué)，2013.

[13]劉楠，孫國道，田賢忠. ACM在線評判系統(tǒng)設(shè)計與實現(xiàn)[J]. 計算機(jī)時代，2010（2）：34-35，38.

[14]趙磊，吳玉培，廖彬. 基于ACM/ICPC在線測評系統(tǒng)的設(shè)計[J]. 電腦知識與技術(shù)，2013（8）：5004-5006.

[15]張良銀. 淺論C/S和B/S體系結(jié)構(gòu)[J]. 工程地質(zhì)計算機(jī)應(yīng)用，2006（4）：20-23，28.

[16]陳鵬. 在線評判系統(tǒng)的設(shè)計和實現(xiàn)[D].南京：東南大學(xué)，2015.

[17]余穎，李曉昀，歐陽純萍. 一種SSH框架的在線程序自動評判系統(tǒng)的設(shè)計與實現(xiàn)[J]. 南華大學(xué)學(xué)報：自然科學(xué)版，2012（4）：65-68.

（責(zé)任編輯：黃 健）

英文摘要Abstract：Online Testing System has gradually replaced the paper-based examination in actual institutions nowadays. With regard to the language programming course， We designed and realized an online examination system based on an automated questions assemblage technique. First， the system generated high-quality examination papers by means of adopting genetic algorithm which conducts natural selection according to question dataset. We borrowed the merit of online judge which deals with codes and marks programming-based test papers automatically. With high efficiency and convenience， the system could be applied to other test systems and achieve a great applicability.

英文關(guān)鍵詞Key Words： Language Programming Course； Genetic Algorithm； Automatic Question-assemblage System； Automatic Grading System