基于遺傳算法的職業技能在線考試系統探究

王娜 左浩 鄭志榮

摘 ?要：組卷算法是在線考試系統的核心也是難點，對職業技能理論部分紙質考試的充分調研，明確了系統功能設計模塊，基于對試卷評價指標的研究，系統使用遺傳算法模擬自然因子通過自然選擇機制，建立適應度函數，遺傳算法因子的改進，終止條件的設定，自動組成滿足總分、題量相同等基本約束條件，同時要求難度控制在一定范圍的試卷，從而大大減輕了教師工作量，使教學質量的考察更規范和科學。

關鍵詞：在線考試系統;遺傳算法;自動組卷

中圖分類號：TP311.52 ? ? ?文獻標識碼：A 文章編號：2096-4706（2020）23-0170-04

The Research of the Online Examination System of Vocational Skills Based on Genetic Algorithm

WANG Na，ZUO Hao，ZHENG Zhirong

（School of Transportation Engineering，Xian Vocational University of Automobile，Xian ?710600，China）

Abstract：Test paper generation algorithm is the core and difficulty of online examination system. The paper examination of vocational skills theory is fully investigated，and the system function design module is defined. Based on the research of test paper evaluation index，the system uses genetic algorithm to simulate natural factors through natural selection mechanism，establish fitness function，improvement of genetic algorithm factors，the setting of the termination conditions，automatically constitute basic constraints to meet the total score and the same amount of questions，and at the same time，the difficulty control in a certain range of papers，thus greatly reducing the workload of teachers，making the investigation of teaching quality more standardized and scientific.

Keywords：online examination system;genetic algorithm;automatic test paper generation

0 ?引 ?言

我校職業技能的理論考試暫未使用試題庫軟件，但已建立全面的試題庫。考試時，人工從電子題庫中抽取一套試卷，盡管這種方式可滿足基本要求，但存在不少弊端，沒有真正實現教考分離。隨著信息技術的迅速發展，基于Web的在線考試系統能夠實現無紙化、不受時空限制、方便快捷實現線上考試。所以，本系統以我校校園網為依托，以開展職業教育“雙證融合”為背景，以工程測量中級工理論考試為案例，通過網絡平臺的搭建，實現在線智能考試系統，減少教室的占用、減少紙質試卷的開支、減輕教師負擔等，同時，滿足現代標準化考試的要求。

智能考試系統的試題由電子數據庫提供，將試題手動輸入或以數據庫要求的格式導入數據庫中，在智能組卷系統中，怎樣使自動生成的試卷滿足實際需求，對知識點、試題難度等如何控制，本文從試卷衡量指標的難度、效度、信度和區分度，建立適應度函數，通過對遺傳算法因子的改進，自動組卷，生成若干份試卷，滿足考試需求。

1 ?系統功能模塊設計

本系統主要包括3類用戶：系統管理員、教師和考生。考生角色，可以根據所報名的技能鑒定的項目通過考試系統進行理論的章節測試，組卷測試和正式考試，并可以直接查詢自己的成績，查看測試的答案、在線提問、個人信息管理等，系統通過設置考生功能模塊完成考試過程管理。教師角色負責試卷命題、題庫管理、自動組卷、在線答疑、學生成績管理等，同時，教師可以查看所屬教研室試題。因此，設置試題管理模塊實現試卷的常規操作。系統管理員角色的權限最高，包括對用戶的管理，如教師、班級和學生信息的管理，對題庫的管理，如可以查看所有試卷，并且對試卷和題庫進行增、刪、查、改等操作。同時，不同的用戶具有不同的權限，需要進行用戶驗證，保障系統的安全性。上述權限通過后臺管理模塊的設置來完成。

系統的功能主要圍繞題庫的建設、應用及后期進一步優化等工作展開，自動組卷是關鍵模塊。本系統的功能結構框架圖如圖1所示。

2 ?評價指標設計

根據教師教學的考核要求，系統自動生成科學、規范的試卷。對試卷優劣的評定，一般從試卷的平均分、方差、及格率、優秀率、難度、區分度、信度、效度等指標進行分析[1]。

難度是指試題的難易程度，本系統試題類型為單選、多選和判斷題，均為客觀題，所以難度的計算使用通過率來衡量，即：難度指數=答對的人數/總人數，一般來說，考試難度控制在0.45～0.65之間;信度指同一試卷相對同一測試群體，或者兩個平行試卷測試時，測試結果的一致性和穩定性。一般要求信度值在0.7以上;效度亦稱為測試的有效性，指測試結果與測試目標的符合程度。效度指的是有效分數方差，系數越高，有效性越大，一般來說，效度正常在0.4～0.7之間，較大規模的考試，要求效度在0.7以上;區分度是區分測試者能力水平高低的指標，試卷的區分度越高，應試者層次區分越合理，區分度D=2（XH-XL）/W，XH為27%的高分組平均分，XL為27%的低分組平均分，W為試卷總分。一般認為，區分度高于0.4，試題可以被接受。

試卷質量評價的四個指標相互影響。信度與效度都為衡量測試質量的重要指標，信度低則效度低，效度高則信度就高;試題的區分度與試題的難度關系密切，一般來說，中等難度試題的區分度比較大，因此，只有在試卷中包含有不同層次的試題，保證整套試題中題目的難度適宜，才能真正鑒別出不同層次的學生，提高區分度。

3 ?遺傳算法

遺傳算法（Genetic Algorithm，GA）借鑒了達爾文進化論中的適者生存、優勝劣汰的思想，具有全局尋找最優解的隨機搜索算法[2]。遺傳算法流程如圖2所示。

遺傳算法主要用于試題的自動組卷。通過建立計算模型，對試題庫中的試題編碼，生成初始種群，然后通過適應度函數進行優劣評估，根據環境進行選擇、交叉、變異等操作，滿足條件的試題生存下來，組合生成新的一代，重復上述操作，直到滿足條件算法終止，將最優解輸出。

4 ?遺傳算法的具體實現

4.1 ?染色體編碼

組卷就是按照多個約束條件，求最優解的過程。把衡量試題質量的多個屬性定義為組卷的約束條件，建立基于遺傳算法的自動組卷數學模型。本文以題型、知識點、分值、難度系數為約束條件，每道題根據屬性建立一個四維向量，假設試卷有n道題目，則某道試題Si=[ai1，ai2，ai3，ai4]，其中0≤i≤n，ai1為題型，ai2為知識點，ai3為分值，ai4為難度系數，ai4難度系數根據實際試題情況而不同，ai4=Ri/Ni，Ri為做對該題的人數，Ni為作答該題的總人數。根據上述四個屬性，約束生成試卷，構成“染色體”。

編碼是遺傳算法的基礎，遺傳算法必須通過編碼將問題轉換成“染色體”標識。常見的編碼方法有二進制編碼、實數編碼和混合型編碼等方式。本文采用分組實數編碼的方式，以題型為基準構建題庫，可以實現對不同題型進行獨立編碼[3]。假如組成一組簡單的測試題，題型有單選、多選和判斷題，每種題型的題量均為5，表1為采用分段實數編碼組卷后兩套試卷的染色體編碼情況。

采用這種編碼方式，每個染色體的含義清晰明了，并且編碼的長度大大縮短，符合人們使用十進制的習慣，減少了算法的復雜性，提高運算效率。

4.2 ?適應度函數建立

適應度函數也稱為評價函數，用來判斷個體在群體中的優劣程度，一般根據目標函數來評估，建立適應度函數f（x）與目標函數g（x）的映射關系來保證適應度函數值非負。映射關系表示為：

（1）

其中，cmax為理論上的最大值，或者是當前所有代數值或最近K代中g（x）的最大值，cmax會隨著代數發生變化。

為了使優秀的染色體被復制，又防止太多優秀的染色體充滿整個種群出現隨機漫游的現象，需要對適應度縮放，即適應度定標，最常用的是指數定標。本文建立適應度函數的方法是比例指數法，F=ewf，其中F為適應度函數，f為目標函數，w=-0.02。通過適應度函數的建立，找出符合難度系數的最優范圍解。

4.3 ?遺傳操作算子

4.3.1 ?選擇算子

選擇指從群體中選擇好的淘汰劣的個體，是生物學中的“優勝劣汰”的應用，它建立在適應度的基礎上，適應度越大，被選中的可能性就越大。本文采用輪盤賭算法，假設種群由N個個體組成，個體Ni的適應度用Ai表示，則Ni個體的選擇概率為，計算最大概率Pmax，在[0，Pmax]之間的按照隨機原則產生隨機值a，若a

4.3.2 ?交叉算子

交叉是模擬生物體進化的過程，是獲得優良個體的重要手段，產生下一代新的個體，交叉操作是按照一定的交叉概率在匹配庫中隨機選取兩個個體進行。單點交叉是最基礎的方式，信息量比較小，本文采用多點交叉，若題目為三種類型，若交叉點為2、3和3，則交叉后子代的染色體如表2所示。

隨機性的交叉方式，導致交叉后會出現重復的題號，使得算法早熟收斂。為了防止此情況的產生，使用交叉概率來控制，交叉概率一般為0.90～0.95，交叉操作時，要求交叉的題目分數一樣，并且題目分數之和等于總分，同時要求在交叉點不能出現題目，否則不能進行交叉操作。

4.3.3 ?變異算子

變異操作是模擬生物體的個體突變。在遺傳算法中，變異算子通過變異概率隨機反轉某位二進制的數值來實現。若變異的概率為Pm，變異操作過程中在[0，1]之間產生一個隨機數rand，若rand0.5時，則算法退出。

4.4 ?終止條件的設定

遺傳算法是在多個問題解中不斷搜索最優解的過程，所以需要設定判斷法則，終止算法的執行。常用的方法有：

（1）規定遺傳的迭代次數，從小開始逐漸遞增，正常設置150～250次為宜。

（2）適應度差值控制法，若是沒有達到規定的迭代次數，但目標適應度與實際適應度的差值小于設定的閾值時，也可終止操作。

本文將兩種方式組合，若在限定的迭代次數中，個體的適應度差值小于閾值時，那么算法終止，相反要不斷進化，直到達到限定的迭代次數，最后停止計算時，滿足最高適應度值的個體為最優解。執行過程如圖3所示。

5 ?系統實現

本系統基于B/S結構模式，應用Tomcat服務器技術、MySQL后臺數據庫、MyEclipse應用程序開發。整個系統代碼結構采用MVC模式，MVC即模型（model）-視圖（view）-控制器（controller）。客戶端通過瀏覽器實現考試全過程，客戶端做到零安裝，減少系統升級、更新的工作量，同時方便進行遠程系統維護和管理，兼容主流瀏覽器（火狐、谷歌、IE10以上版本）。實際應用表明，該系統運行性能良好，完成了預期的研究計劃。學生在線考試界面如圖4、圖5所示。

6 ?結 ?論

本文針對職業技能理論考試部分建立了自動組卷與閱卷在線考試系統，在充分調研的基礎上，給出了系統需求分析，重點研究了基于遺傳算法考試系統的適應度函數設計，選擇、交叉和變異算子的選擇以及遺傳算法的終止條件。經運行驗證，系統自動生成的試卷科學、規范，減輕了教師的負擔，對考試的信息化建設具有重要的現實意義和實用價值。

參考文獻：

[1] 丁海霞.基于經典測量理論的試卷評價系統的設計 [J].常州信息職業技術學院學報，2016，15（1）：32-35+46.

[2] 李金海，陳鑫宇.在線考試系統組卷模塊的分析與設計 [J].電腦知識與技術，2019，15（20）：55-57.

[3] 馮秀梅.基于遺傳算法的智能組卷考試系統研究與實現 [D].濟南：山東師范大學，2016.

作者簡介：王娜（1982—），女，漢族，陜西咸陽人，講師，碩士，研究方向：計算機應用技術、教育教學;左浩（1981—），男，漢族，陜西漢中人，副教授，碩士，研究方向：計算機技術與教學管理;鄭志榮（1978—），男，漢族，陜西禮泉人，實驗師，本科，研究方向：計算機技術與網絡管理。