王莉

（河海大学江苏南京211100）

基于遗传算法的高校在线考试系统研究

王莉

（河海大学江苏南京211100）

随着互联网技术的发展，越来越多的高校重视在线考试系统。在线考试系统由于拥有环保，提高教师工作效率以及考查的多样性等优势，现在已经成为一个研究热点。本研究首先针对传统的在线考试系统进行研究，然后利用遗传算法的优势，将其算法与在线考试系统进行结合，设计了一种基于遗传算法的高校在线考试系统，其系统较传统的在线考试系统具有组卷效果较好、易于使用和维护以及操作界面友好等优点，在教学过程中受到的师生的认可，有一定的应用价值。

高校教育；遗传算法；在线考试系统；组卷策略

现阶段，随着计算机科学与技术的迅猛发展，高校的教育方式也发生着变化。教育的考核是高校教育不可或缺的一部分，首先教育的考核可以及时了解学生学习的具体情况和把握学生的知识水平，然后教育的考核也是针对教师教学效果的评估，根据具体情况对学生进行阶段性的评估会更好地帮助教师进行教学方式的调整。有关教师和学生的考核的主要手段就是试卷的评价，因此如何出一份客观、全面的试卷则尤为重要［1］。而传统的考试方式缺乏客观和全面性，因此设计和开发高校在线考试系统有了较大的研究前景。

在我国，很多高校结合自身学科特点、职业技能培训以及教学需要等，已经建立了一些适合自身发展的在线考试系统，而且其系统实现了在线报名、考试、评分以及成绩评估等智能化的考试功能［2］。按高校在线考试系统的组成方式可分为按流程模块方式、按功能模块方式以及按组合模块方式等。而目前绝大部分的在线考试系统采用的为以题库为基础的按功能模块方式构建的。

本研究在现有的高校在线考试系统理论的基础上，添加了成熟的遗传算法，设计了基于遗传算法的高校在线考试系统，该系统相对于传统的高校在线考试系统，其组卷的效果更显著。

1　遗传算法技术的概述

1.1遗传算法介绍

遗传算法是近年来发展迅速的一种模拟自然进化的搜寻最优解的全局性优化算法［3］，其算法最早由Michigan大学的J.Holland教授在1962年首次提出的，并且得到推广和研究。该算法针对约束条件较多且复杂的系统提出了一种通用的解决方案，并且由于其不依赖于具体领域，具有很强的抗干扰性，因此已经被广泛应用在图像处理、机器学习、控制等领域。

1.2遗传算法的参数

绝大数的遗传算法的设计步骤都很相似［4］，主要实现在群体空间中搜寻最优解。其实现过程中常借助以下参数：

1）适应度函数：为计算机智能地选取个体到下一代参照依据。适应度数值的大小表明个体对环境的适应情况。

2）适应度阈值：为评估群体优化程度的一个重要指标。在群体优化过程中，当个体的适应度与群体适应度变化差别较小时，就可以让遗传过程终止，而阈值就是衡量适应度变化差别的标准。

3）群体规模：对于遗传算法的运算效率有很大的影响。当群体规模较大时，其遗传算法效率就较低，反之亦然。一般情况下，种群的大小为30到160。

4）交叉概率：在遗传过程中，父体通过交叉得到子体，而交叉运算法则是由交叉概率决定的。若交叉概率数值较大时，则容易失去适应度数值较大的结构；而交叉概率值较低时，其一般取值为0.6到0.95。

1.3遗传算法的设计流程

在了解遗传算法参数的基础上，现给出遗传算法的设计流程图如图1所示。

图1　遗传算法的设计流程图Fig.1Design flow chart of genetic algorithm

从上述的遗传算法设计流程图可知，遗传算法进化流程比较明晰，容易理解，而且实现简便。现在只是一个遗传算法的基本框架，若遗传算法得到改善只需对流程图的某一个环节进行修改即可。

1.4遗传算法的优势

遗传算法可用于复杂系统的优化，该算法具有较强的鲁棒性［5］，其优势主要有：

1）可行性求解具有广泛性。遗传算法主要针对基因个体，并不是对象本身，而且针对智能组卷问题的求解多样性提供了理论支持。

2）具有启发式的随机搜寻特点。遗传算法并不是随意盲目地穷举式的搜寻，而是一种自适应的按概率搜寻技术，其操作主要按照概率方式运行。

3）不再需要辅助或帮助信息。

4）适合群体式搜寻特点。遗传算法可以采用多个搜寻点进行搜寻信息，覆盖面较大，利于实现并行计算，可有效加快搜寻进程和全局优化。

2　遗传算法在考试系统中的应用

2.1在线考试系统的目标

在线考试系统的核心是组卷系统，而组卷的算法则是整个系统的最关键的技术之一［6］。首先教师应根据所讲授的课程选定该课程的题量和题型，接着根据学生的认知情况决定试题的难易程度和知识点分布等，然后让考试系统根据上述条件采用组卷的算法生成所需的试卷。

需要注意的是，高校在线考试系统的对象主要是教师和学生，所以在设计该考试系统之前需要了解教师和学生的试卷要求。该系统针对教师提供组卷、评卷以及成绩评估等功能，而对于学生提供试卷测试功能。根据教育的目的对试卷的质量评价标准为：1）试卷难度要适中；2）试卷覆盖的知识点要全面；3）试卷的题型要合理；4）试卷中知识的遗漏率和重复率要低；5）、试卷内容要灵活；6）试卷区分学生学习水平的效果要好。

2.2遗传算法在在线考试系统中的应用

本研究在线考试系统的设计要求和遗传算法的设计流程图的基础上设计一种遗传算法。下面就详细介绍该遗传算法的设计思路。

2.2.1遗传算法的编码方案

编码方式是整个遗传算法基础。本研究针对在线考试系统的组卷约束条件多，编码长度较长以及编码表达意义不明晰等特点，采用分组编码方案。主要因为试题库的试题一般是以题型为单位，而且每种题型都会进行独立编码，最后再针对每个题型的编码执行二进制转换。这种以试题的题号为基础的编码方式表达变量的含义清晰明了，易于理解，不需要额外解码，而且还克服了由题量增多引起的搜寻空间较广以及编码长度较大等缺陷，能够有效地改善遗传算法的正确率和有效率。

若染色体编码采用了分组编码，即各个试题为试卷的基因组合，且用试题的题号表示基因值。例如，要利用选择题、判断题以及填空题组成一份试卷，题型用A、B、C表示，每种题型的题量用m1，m2，m3表示，则所有试题就表示为：A1A2…Am1B1B2…Bm2C1C2…Cm3。采用分组编码使每个染色体的含义清晰，为保证每种题型的题量不变，在遗传算法设计中都要按照分组编码进行。

2.2.2初始种群生成

对题型进行分组编码后就要实现初始种群的生成［7］。首先根据实际情况选定初始种群的规模，一般情况下会选定为50或者100。如果种群过大会导致计算效率下降；如果种群过小会导致计算过早结束，未达到全局最优。

本研究以试卷题型为随机生成初始种群的单位，以简化遗传算法过程，更快地完成组卷。例如，如果生成的试卷选择题数量比重占20%，判断题数量比重占20%，计算题数量比重占40%，问答题数量比重占20%，则生成种群的规则也要满足上述比重要求，由此生成的试卷组卷成功率更好，更容易满足设计者的要求。

2.2.3选取适应度函数

选取适应度函数也会对在线考试系统的构建起到了关键作用。通常由目标函数直接变换得到适应度函数，而适应度会影响种群个体的优劣，即会影响种群的个体是否遗传给下一代。通常适应度值越大说明种群个体的适应能力越强，越有可能遗传给下一代，反之恰恰相反。选取适应度函数有两个准则：1）避免遗传算法出现过早运算完毕的现象；2）克服后期运算的退化情况。

根据上述的选取适应度函数准则，选取的目标函数为越小越好，适应度函数却是越大越好，而且目标函数必须与适应度数值变化方向相反，即：

若目标函数值恒为正，则适应度函数直接转换为目标函数，表达式为：

本研究针对目标分量分配权值，以表明对各个目标的重视程度，由此组卷问题就转换为目标函数求最小值问题。为了避免系统陷入局部最优，对适应度函数进行线性变换，具体变换表达式为：

其中F（X）为适应度函数，f（x）为目标函数，α为正常量，β为常量系数。而且确定系数α和β的方法会根据系统的不同有所变化。

2.2.4遗传算法算子

1）选择算子

相对于交叉算子和变异算子，选择选择对遗传算子的效果效率影响最大，其可以影响遗传算子的方向。选择算子以个体的适应度数值为基准，并根据个体的质量决定淘汰或者复制个体。本研究采用改进的轮盘方式进行复制。

在具体地实现轮盘复制方法时，每一次遗传操作后都要针对子代种群计算其适应度数值，并找出最大值，接着把此最大值与父代种群的适应度最大数值进行比较，若父代的适应度数值大于子代适应度数值，则随机选取子代种群的一个个体进行淘汰，否则不做任何变化，一直循环下去。

2）交叉算子

通常在种群中随机选择两个染色体，并在染色体某一点随机进行点交换，以得到下一代的新个体。自适应交叉概率公式为：

其中fmax为种群适应度数值的最大值，favg为每代种群的适应度数值的平均值，f′为两个个体的适应值的较大值，pc1=0.9，pc2=0.6。

3）变异算子

变异算子概率公式为

其中fmax为种群适应度数值最大值，favg为每代种群的适应度数值的平均值，f为准备变异个体的适应度数值，pm1= 0.1，pm2=0.001。

2.2.5遗传算法的终止条件

终止遗传算法的条件主要有：1）限制遗传迭代次数，比如可设置迭代次数300次就结束；2）通过适应度数值差值进行控制。

本研究的遗传算法的终止条件为上述两种方式的结合体。在迭代次数限制的情况下，若个体的适应度数值差值小于预定值则停止进化；否则会一直进化直到达到规定的迭代次数。

3　基于遗传算法的高校在线考试系统设计

3.1在线考试系统架构

该在线考试系统采用B/S结构，也就是浏览器/服务器结构。教师和学生可以方便地通过浏览器操作系统界面，其服务器端包括大部分的事务逻辑，而且系统的维护和更新都是针对服务器端进行操作的，客户端没有附加任何操作。总之，这种系统结构操作简单，便于维护，能够有效管理权限和数据库数据。

基于B/S结构的在线考试系统还会采用ASP、JAVA、SQL以及HTML等技术，其采用的三层网络架构图如图2所示。

图2　三层网络架构图Fig.2The three layer network architecture diagrams

采用三层网络架构的高校在线考试系统，用户只需要在操作界面上进行注册和登录即可使用相应功能。在实际的考试过程中，学生只需要与服务器进行交互，Web和服务器会对数据进行处理，因此考试平台是安全并且开放的。

该考试系统结构图如图3所示。

图3　在线考试系统结构图Fig.3Online examination system structure diagram

3.2整个系统功能模块

针对在线考试系统需求，将该考试系统分为用户管理模块、题库管理模块、评估管理模块、成绩查询模块以及考试管理模块这5大管理模块。

该在线考试系统功能设计图如图4所示。

图4　在线考试系统功能设计图Fig.4Online examination system function design

4　结论

本研究在传统的在线考试系统的基础上，将遗传算法与在线考试系统进行有机结合，设计了一种基于遗传算法的高校在线系统。经过测试对比，相对于传统的在线考试系统，其基于遗传算法的系统具有组卷成功率高、操作界面友好以及方便使用和维护等优势，具有较好的教学使用价值。

［1］吴水秀，曾庆鹏，王明文.智能试卷生产和自适应考试系统［J］.计算机与现代化，1999（1）：36-39.

［2］张瑞，苏建民.基于改进遗传算法的智能组卷在试题库建设中的研究［J］.自动化技术与应用，2010，29（1）：41-43.

［3］马德良，卢昌辉，王小乐.基于改进遗传算法的智能组卷方法［J］.计算机应用，2009（7）：1884-1886.

［4］乐光学，彭小宁，曾志峰.试题库自动组卷系统的算法设计与实现［J］.计算机应用，2001，21（8）：198-200.

［5］冯冬青，王非，马雁.遗传算法中选择交叉策略的改进［J］.计算机工程，2008，34（19）：189-191.

［6］张砦，王友仁.遗传算法在网络子线智能组卷中的应用研究［J］.计算机测量与控制，2005，13（11）：1223-1225.

［7］张亚静，杨毅.遗传算法在通用试题库自动组卷中的应用［J］.湖北民族学院学报：自然科学版，2005，20（5）：714-719.

Research on the online examination system of colleges and universities based on genetic algorithm

WANG Li
（Hohai University，Nanjing 211100，China）

With the development of Internet technology，more and more colleges and universities pay attention to online examination system.Online examination system withenvironmental protection，improve the efficiency of teachers and examine the diversityadvantage，now has become a hot topic of research.This research firstly onlineexamination system of the traditional research，and then use genetic algorithmadvantage，the algorithm and the online examination system are combined，the design of a online examination system of colleges and Universities Based on genetic algorithm，thesystem of online examination system has better effect than traditional test，it is easy touse and maintain and friendly operation interface and so on，are in the process of teaching teachers and students recognition，it has certain application value.

higher education；genetic algorithm；online examination system；test paper strategy

TN99

A

1674－6236（2015）24-0029-03

2015-03-19稿件编号：201503252

王莉（1989—），女，安徽阜阳人，硕士。研究方向：财务管理。