基于自動組卷與判卷的在線考試系統設計

周志鋒+童凌+王浩茂

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

關鍵詞：程序設計類課程；在線考試系統；遺傳算法；自動組卷；自動判卷

DOIDOI：10.11907/rjdk.171014

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2017）006-0066-04

0 引言

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

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

1 系統功能設計

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

2 核心功能設計

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

遺傳算法的機器自動組卷，利用教師提供的參數，靈活建立相應組卷模型，然后對題目進行篩選，以自動生成科學合理的試卷。

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

該自動組卷實現流程如圖2所示。

2.2.1 染色體編碼與初始群體設計

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

2.2.3 遺傳算子設計

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

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

（3）變異算子。在遺傳中，一般較少發生變異，變異率設置在0.02～0.05范圍內比較適宜。

2.3 自動判卷

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

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

其中每層的解釋如下：

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

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

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

（4）鏈接。經過編譯成功后，獲取對應的obj二進制代碼，通過調用ld鏈接命令，執行自動鏈接，產生可執行代碼，提供給下一步使用。

（5）運行。通過系統調用子進程child_process，child_process運行編譯鏈接后的程序，由父進程監控子進程，一旦子進程崩潰或正常退出，會發送相應的SIGNAL給父進程，此時父進程進行相應處理。

（6）測試數據輸入。當前位置主要是為了數據的輸入和輸出位置的轉換，通過調用Liunx的系統函數，將數據輸入從標準輸入Console轉換到標準測試文件輸入，并將標準輸出Console重定向到一個臨時文件中，供下一步進行比較。

（7）比較。通過上述4步以后，轉入對比結果階段。本階段主要是進行數據對比，通過調用bash命令diff，將該程序通過測試輸入產生的輸出臨時文件與標準輸出答案文件進行對比，并得出正確率。

（8）獲取內存資源等情況。通過父進程監控子進程，可以通過wait4函數，獲取進程狀態和資源占用情況等，判斷是否符合題目要求，一旦檢測出非法狀況，也當作異常處理，轉去計算結果。

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

3 系統實現

本系統采用B/S結構模式，利用Apache服務器、MYSQL數據庫和SSH開源框架進行搭建。Apache服務器、MYSQL數據庫是開源軟件，所以具有更好的穩定性與安全性。SSH即Struts+Spring+Hibernate，利用該體系設計系統，能夠為整個系統后期的維護、擴展等提供更多便利，程序的結構脈絡更加清晰明了。實際應用結果表明，該系統運行性能良好。

4 結語

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

參考文獻：

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

[2]呂苗苗. 基于遺傳算法的自動組卷系統的設計與實現[D].南京：南京理工大學，2012.

[3]張琨，楊會菊，宋繼紅，等. 基于遺傳算法的自動組卷系統的設計與實現[J]. 計算機工程與科學，2012（5）：178-183.

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

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

[6]鄭傳生. 基于B/S結構的程序設計競賽自動測評系統的設計[J]. 計算機與現代化，2007（12）：109-111.

[7]楊呈永. 基于B/S結構的大學英語在線考試系統設計與實現[D].成都：電子科技大學，2011.

[8]李佳. 《計算機基礎》課程上機考試系統的設計與實現[D].成都：電子科技大學，2011.

[9]顏韻. 基于B/S模式的單獨招生在線考試系統設計與實現[D].成都：電子科技大學，2013.

[10]樓玉萍. 基于B/S模式的計算機基礎考試系統的研究與實現[D].長沙：國防科學技術大學，2005.

[11]李亦松. 在線考試系統分析與設計[D].昆明：云南大學，2012.

[12]李敏. 在線考試系統設計與實現[D].濟南：山東大學，2013.

[13]劉楠，孫國道，田賢忠. ACM在線評判系統設計與實現[J]. 計算機時代，2010（2）：34-35，38.

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

[15]張良銀. 淺論C/S和B/S體系結構[J]. 工程地質計算機應用，2006（4）：20-23，28.

[16]陳鵬. 在線評判系統的設計和實現[D].南京：東南大學，2015.

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

（責任編輯：黃 健）

英文摘要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.

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