基于遺傳算法的職業(yè)技能在線考試系統(tǒng)探究

王娜 左浩 鄭志榮

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

關(guān)鍵詞：在線考試系統(tǒng);遺傳算法;自動組卷

中圖分類號：TP311.52 ? ? ?文獻(xiàn)標(biāo)識碼：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 ?引 ?言

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

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

1 ?系統(tǒng)功能模塊設(shè)計(jì)

本系統(tǒng)主要包括3類用戶：系統(tǒng)管理員、教師和考生?？忌巧梢愿鶕?jù)所報(bào)名的技能鑒定的項(xiàng)目通過考試系統(tǒng)進(jìn)行理論的章節(jié)測試，組卷測試和正式考試，并可以直接查詢自己的成績，查看測試的答案、在線提問、個人信息管理等，系統(tǒng)通過設(shè)置考生功能模塊完成考試過程管理。教師角色負(fù)責(zé)試卷命題、題庫管理、自動組卷、在線答疑、學(xué)生成績管理等，同時，教師可以查看所屬教研室試題。因此，設(shè)置試題管理模塊實(shí)現(xiàn)試卷的常規(guī)操作。系統(tǒng)管理員角色的權(quán)限最高，包括對用戶的管理，如教師、班級和學(xué)生信息的管理，對題庫的管理，如可以查看所有試卷，并且對試卷和題庫進(jìn)行增、刪、查、改等操作。同時，不同的用戶具有不同的權(quán)限，需要進(jìn)行用戶驗(yàn)證，保障系統(tǒng)的安全性。上述權(quán)限通過后臺管理模塊的設(shè)置來完成。

系統(tǒng)的功能主要圍繞題庫的建設(shè)、應(yīng)用及后期進(jìn)一步優(yōu)化等工作展開，自動組卷是關(guān)鍵模塊。本系統(tǒng)的功能結(jié)構(gòu)框架圖如圖1所示。

2 ?評價(jià)指標(biāo)設(shè)計(jì)

根據(jù)教師教學(xué)的考核要求，系統(tǒng)自動生成科學(xué)、規(guī)范的試卷。對試卷優(yōu)劣的評定，一般從試卷的平均分、方差、及格率、優(yōu)秀率、難度、區(qū)分度、信度、效度等指標(biāo)進(jìn)行分析[1]。

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

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

3 ?遺傳算法

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

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

4 ?遺傳算法的具體實(shí)現(xiàn)

4.1 ?染色體編碼

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

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

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

4.2 ?適應(yīng)度函數(shù)建立

適應(yīng)度函數(shù)也稱為評價(jià)函數(shù)，用來判斷個體在群體中的優(yōu)劣程度，一般根據(jù)目標(biāo)函數(shù)來評估，建立適應(yīng)度函數(shù)f（x）與目標(biāo)函數(shù)g（x）的映射關(guān)系來保證適應(yīng)度函數(shù)值非負(fù)。映射關(guān)系表示為：

（1）

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

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

4.3 ?遺傳操作算子

4.3.1 ?選擇算子

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

4.3.2 ?交叉算子

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

隨機(jī)性的交叉方式，導(dǎo)致交叉后會出現(xiàn)重復(fù)的題號，使得算法早熟收斂。為了防止此情況的產(chǎn)生，使用交叉概率來控制，交叉概率一般為0.90～0.95，交叉操作時，要求交叉的題目分?jǐn)?shù)一樣，并且題目分?jǐn)?shù)之和等于總分，同時要求在交叉點(diǎn)不能出現(xiàn)題目，否則不能進(jìn)行交叉操作。

4.3.3 ?變異算子

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

4.4 ?終止條件的設(shè)定

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

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

（2）適應(yīng)度差值控制法，若是沒有達(dá)到規(guī)定的迭代次數(shù)，但目標(biāo)適應(yīng)度與實(shí)際適應(yīng)度的差值小于設(shè)定的閾值時，也可終止操作。

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

5 ?系統(tǒng)實(shí)現(xiàn)

本系統(tǒng)基于B/S結(jié)構(gòu)模式，應(yīng)用Tomcat服務(wù)器技術(shù)、MySQL后臺數(shù)據(jù)庫、MyEclipse應(yīng)用程序開發(fā)。整個系統(tǒng)代碼結(jié)構(gòu)采用MVC模式，MVC即模型（model）-視圖（view）-控制器（controller）?？蛻舳送ㄟ^瀏覽器實(shí)現(xiàn)考試全過程，客戶端做到零安裝，減少系統(tǒng)升級、更新的工作量，同時方便進(jìn)行遠(yuǎn)程系統(tǒng)維護(hù)和管理，兼容主流瀏覽器（火狐、谷歌、IE10以上版本）。實(shí)際應(yīng)用表明，該系統(tǒng)運(yùn)行性能良好，完成了預(yù)期的研究計(jì)劃。學(xué)生在線考試界面如圖4、圖5所示。

6 ?結(jié) ?論

本文針對職業(yè)技能理論考試部分建立了自動組卷與閱卷在線考試系統(tǒng)，在充分調(diào)研的基礎(chǔ)上，給出了系統(tǒng)需求分析，重點(diǎn)研究了基于遺傳算法考試系統(tǒng)的適應(yīng)度函數(shù)設(shè)計(jì)，選擇、交叉和變異算子的選擇以及遺傳算法的終止條件。經(jīng)運(yùn)行驗(yàn)證，系統(tǒng)自動生成的試卷科學(xué)、規(guī)范，減輕了教師的負(fù)擔(dān)，對考試的信息化建設(shè)具有重要的現(xiàn)實(shí)意義和實(shí)用價(jià)值。

參考文獻(xiàn)：

[1] 丁海霞.基于經(jīng)典測量理論的試卷評價(jià)系統(tǒng)的設(shè)計(jì) [J].常州信息職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2016，15（1）：32-35+46.

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

[3] 馮秀梅.基于遺傳算法的智能組卷考試系統(tǒng)研究與實(shí)現(xiàn) [D].濟(jì)南：山東師范大學(xué)，2016.

作者簡介：王娜（1982—），女，漢族，陜西咸陽人，講師，碩士，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)、教育教學(xué);左浩（1981—），男，漢族，陜西漢中人，副教授，碩士，研究方向：計(jì)算機(jī)技術(shù)與教學(xué)管理;鄭志榮（1978—），男，漢族，陜西禮泉人，實(shí)驗(yàn)師，本科，研究方向：計(jì)算機(jī)技術(shù)與網(wǎng)絡(luò)管理。