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

摘　要：随着信息技术的不断发展，网络平台的日趋完善，应用网络考试系统进行网上考试成为大家广泛推崇的一种考核方法。虽然网上考试较之传统的书面考试有了很大的进步，但依然存在很多弊端，仍有大量可被人利用的漏洞。在这些漏洞中，对考核结果干扰最大的莫过于网络考试系统组卷方法的落后。采用遗传算法进行自动组卷，可以有效填补漏洞，极大提高效率，保证网上考试的公平、公正性。

关键词：遗传算法，网络考试系统，网上考试
      21世纪最宝贵的资源是人才，发现人才最有效的方法是选拔考核。随着社会文明程度的不断提高，人们对选拔考核的效率以及其公平、公正的要求日益提高，改革传统的选拔考核方法成为当前社会广泛关注的问题。现阶段选拔人才的主要方法是考试，而传统的考试方法，从试卷生成、印刷到实施考试，往往需要持续很长时间，花费大量人力、物力，是一项规模庞大而效率低下的工作。由于传统的考试采用人工出卷和阅卷，考试结果难免不会收到出卷和阅卷人员主观因素的干扰，给考试的公平、公正性和严肃性带来负面影响。随着信息技术的不断发展，网络平台的日趋完善，应用网络考试系统进行网上考试成为大家广泛推崇的一种考核方法。相关机构投巨资建立了一系列网上考试平台，如交警部门的驾驶员公路交通法规考试系统、教育部建立的国家计算机等级考试系统、劳动保障部门建立的办公自动化考试系统、人事部门建立的职称计算机考试系统以及被银行、保险公司委托进行从业人员资格认证考试的ATA网上考试系统等。
     虽然网上考试较之传统的书面考试有了很大的进步，但依然存在很多弊端，仍有大量可被人利用的漏洞。在这些漏洞中，对考核结果干扰最大的莫过于网络考试系统组卷方法的落后。网络考试系统主要由两部分构成，一部分是运行于服务器端的题库和组卷、阅卷程序，另一部分是运行于考生客户端的浏览答题程序。进行网络考试时，考生登录并请求考试后，先在服务器端运行组卷程序，完成从题库里抽取试题生成试卷的工作，再将试卷传至考生客户端由考生作答后将答案回传至服务器进行阅卷，最后将考试结果通知考生。在整个考试过程中最核心的环节就是从题库中抽题组卷。理想的抽题组卷结果应该是为同一场次的每个考生都从题库中抽取难度相同但内容各异的同等题量的题目组成试卷，这样既考查了考生的学识、能力，又避免了考生间的相互窥视，窃取答案。然而由于当前主流网络考试系统中普遍存在抽题组卷方法落后、效率低下的问题，导致不能为同一场次的每个考生均抽取不同的试题，甚至不能保证不同场次的考题不同，这就使得场次越靠后的考生越容易事先得知考题，极大的影响了考试的公平、公正。更有甚者，由于抽题组卷效率低下，无法保证现场抽取试题组织试卷，很多网络考试系统采用了事先组卷的方法，即考试前先生成若干套试卷，考试时随机抽取一套试卷进行考试，这就使得考试题目更加容易估计，猜题命中率大幅提高，从而使考试结果的说服力大大降低。要从根本上消除当前网络考试系统中存在的这些弊端，就必须选择一种随机性更好、更具效率的抽题组卷方法。遗传算法恰恰具备选择随机性好、效率高的特点，可以担当网络考试系统现场抽题组卷的大任。
     遗传算法作为一种全局优化搜索算法能模拟自然法则从群体中选择出最适应环境的个体，从而得到最优解。遗传算法把要解决的问题的解解释成“染色体”，在算法中以二进制编码的形式加以体现。在遗传算法执行之前，先要给出一群“染色体”，然后再把这些“染色体”置于解域中的问题环境中，并按适者生存的自然法则，选择出比较适应环境的“染色体”进行复制，再通过交叉，变异产生更加适应问题环境的新一代“染色体”。如此不断的进行进化，最终所有“染色体”会收敛到最适应问题环境的一个“染色体”上，这就是问题的最优解。我们设长度为L的n个二进制串ai(i＝1，2，…，n)组成初始解群。把在每个二进制串中的每个二进制位看作这个染色体的遗传基因。根据进化法则，对群体执行的操作有三种，即选择、交叉和变异。选择是从解群中选出较适应问题环境的个体，这些选中的个体将被用于繁殖下一代个体。交叉是在选中用于繁殖下一代的个体中，对两个不同个体的遗传基因进行交换，从而产生新的个体。变异是在选中的个体中，对个体的部分遗传基因进行异向转化。当个体的适应度达到给定值，或者个体的适应度和群体适应度均不再上升时，算法的迭代过程收敛、算法结束。
　　应用遗传算法进行抽题组卷时，系统设计者先要对题库中题目的属性进行筛选，过滤掉跟抽题组卷无关的属性，采用的试题属性定义如下： 题目编号，题库中考试题目的唯一标识；题型编号，各种题目类型的代号；试题分值，题目分值；难度系数，难度系数=1- 平均分/该题满分；知识点，表示该题目属于学科的哪个知识点；估时，完成该题目所需的估计时间；层次，该题目的教学要求：了解、理解、掌握和综合。我们在解域中用一个矩阵Sg描述抽取试题的目标及约束关系，它满足以下约束条件： 卷面总分 ，卷面难度 ，T（整卷时间），Q（知识点数量约束），R（某一题型数量约束），D（区分度）。从Sg矩阵我们可以看出抽题组卷问题是一个有多重约束的目标求解问题，而且目标状态不是唯一的。Sg中的每一行都是一个分目标，我们将Sg的第i个分目标记为Sg(i)。我们发现上述约束条件的内在关系为：由整卷难度期望值求不同难度系数的小题的选取数量；由卷面总分值确定抽取的各题型不同难度的题目的分值。上述准备工作完成后可以进行具体的算法设计。经过前面的分析，遗传算法可以被定义为一个8元组，即SGA=(C，E，P，M，选择算子，交叉算子 ，变异算子 ，遗传终止条件 ) 其中C为个体的编码；E为个体适应度评价函数；P为初始群体；M为群体规模。 进化选择机制是遗传算法处理多目标优化问题的关键。
　　1.染色体编码
　　染色体编码是遗传算法的基础。遗传算法不直接讨论研究对象，而是通过某种编码机制把研究对象统一编码，完成问题域到遗传算法解域的映射。我们经过大量实验分析，最后确定采用分段实数编码机制，将题目编号作为遗传基因直接构成染色体，而染色体的长度由题目的数量决定。假设要求抽取的选择题数量为20，而题库中选择题数量为2000，每个题目编号为4位整数，每位整数由 4位二进制数表示，则染色体的长度为320（4*4*20）位二进制数。由于染色体长度较短，为了保证种群的个体多样性，就要扩大种群规模，同时不能再完全套用Holland的遗传理论，要重新设计遗传算子。
　　2.适应度函数
　　遗传算法采用适应度函数来描述个体的优劣程度，适应度函数就是目标函数。根据适应度对个体进行比较，按一定策略进行个体的选择。适应度函数为F(xi)= μ(ri), 其中ri为个体xi按照满足条件的个数进行排序的序号，满足的条件越多，序号越靠前，最好的个体序号为1，次最好的序号为2，依次类推。我们采用的指数比例变换取μ(ri)=exp(-βri)只能在一定程度上提高相近遗传基因之间的竞争。我们将题库中的题目的染色体排序：将染色体按其适应度大小进行排列，根据染色体的位置指定选择概率。设Pk为种群中排在第k位的染色体的选择概率。令Pk为g(1-g)k-1。则g越大，被选择的概率越大。若取g值为0.99，则最优个体适应度为1。
　　3.遗传算子
　　重新设计的遗传算子包括交叉和变异。交叉是指当染色体的选取过程中产生无效解时，如某种题型中的某题的题目编号超出该题型的题目编号取值范围，强制重新进行交叉运算或直接淘汰掉所选题目。变异是指以较小的变异率Pm选择染色体，随机删除某个遗传基因位，再随机产生一个基因集合中没有的遗传基因(题目编号)，在题型题号取值范围内插入到该位。
　　4.迭代终止条件
　　假设新选个体的适应度F≤f(t) -ε,其中F为期望的个体适应度，ε为期望的误差。如果种群p(t)中不存在该个体，则把该个体添加到种群中，如果种群的规模达到指定大小，则终止进化过程。
　　5.局部修正
　　在抽题组卷系过程中，采用遗传算法组成的试卷很难完全满足目标约束，在实际抽题组卷过程中要通过对各试题的参数进行局部微调使其完全满足出卷的约束的条件。在众多的约束条件中，不同约束条件的重要性不同，为此我们将约束条件按重要性强弱分成四类：强约束、亚约束、柔性约束和弱约束。抽题组卷时在满足强约束和亚约束的前提下，可以适当的调整后面两种约束指标，以提高抽题组卷的成功率。
     我们采用上述方法进行了大量抽题组卷实验。遗传算法完美实现了全局并行搜索并且搜索空间较大，搜索过程中不断向可能包含最优解的方向调整搜索空间，从而易于找到最优解。在实验中可以看出遗传算法能有效的解决网络考试系统的抽题组卷问题。与传统的组卷方法相比，能较快的找到满足条件的解，大大提高了网络考试系统的工作效率，保证了网上考试的公平、公正性。
本文链接：http://www.qk112.com/lwfw/jsjlw/zhinengkeji/231804.html