基于遗传算法的职业技能在线考试系统探究
2020-07-09王娜左浩郑志荣
王娜 左浩 郑志荣
摘 要：组卷算法是在线考试系统的核心也是难点，对职业技能理论部分纸质考试的充分调研，明确了系统功能设计模块，基于对试卷评价指标的研究，系统使用遗传算法模拟自然因子通过自然选择机制，建立适应度函数，遗传算法因子的改进，终止条件的设定，自动组成满足总分、题量相同等基本约束条件，同时要求难度控制在一定范围的试卷，从而大大减轻了教师工作量，使教学质量的考察更规范和科学。
关键词：在线考试系统;遗传算法;自动组卷
中图分类号：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，若rand 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—），男，汉族，陕西礼泉人，实验师，本科，研究方向：计算机技术与网络管理。
