在线考试系统组卷模块的分析与设计

李金海 陈鑫宇

摘要：互联网技术的应用给学校的教育方面带来了很大的方便性，特别是当在线考试系统应用在教育行业后，传统纸质考试存在的诸多问题得到了有效解决，因此设计在线考试系统成为教学领域的重要课题。其中，组卷模块的设计是在线考试系统中不可或缺的内容，组卷模块需要进行合理组卷，不管是在难度上还是题型的分布上都应当尽可能合理。在分析对比几种常用组卷算法的基础上，该文设计了实数编码遗传算法实现组卷功能，通过实证验证了基于实数编码遗传算法组卷模块的有效性。

关键词：在线考试;互联网;遗传算法;组卷

中图分类号：G642        文献标识码：A

文章编号：1009-3044（2019）20-0055-03

开放科学（资源服务）标识码（OSID）：

随着互联网技术发展，实现了信息化、智能化、科技化。一个学校数千名学生，每次考试时，监考教师和考场都不能满足需要[1]。一个公司少则数百多则数万名员工，面试、年底考核，考试时间和地点都不能满足人们需求。在线考试系统不受时空限制参与考试、不受考场人数限制[2]，解决了人们的时间和地点的需求，提高了人类的学习、工作效率，使考试形式自动化、智能化，使考试的结果更加公正公平，减少考官徇私舞弊、考生作弊现象。所以对于教育及其他行业，建立一个现代化、新型的在线考试系统至关重要。

考试系统的组卷模块是本系统中必不可少的模块。考试系统，顾名思义，就是能够进行考试的系统，只是考试的试卷已经不再是纸质的试卷，而是由系统来从题库中选择一定数量的且互不相同的题目来组成一套完整的试卷，通过网页或其他方式将这些题目组成的试卷展现在考生电脑屏幕眼前，从而能够让考生进行答题。一个在线考试系统有多个模块，而用来实现上文所述的题库抽题组成试卷并展现的功能的模块称为在线考试系统的组卷模块。

1 文献综述

目前，市场上有着形形色色的在线考试系统，例如有一些开源的考试系统：WEB-SET CAMPUS、eFront-Refreshing eLearning、GARC等。但是，真正占據大比例的在线考试系统主要由IT公司认证。例如Oracle公司的OCA考试、OCP考试以及OCM考试等，微软以及思科等公司也都有自己的考试系统。这些国外考试系统的应用使得各个考试的过程变得十分简洁，也使得管理的方便性以及管理的效率大大的提升。当前，在线考试系统根据结构的不同，可以划分为基于C/S结构（客户机/服务器结构）的在线考试系统以及基于B/S结构（浏览器/服务器）结构的在线考试系统;也可根据网络类型划分为局域网考试系统和广域网考试系统。一些常见的等级考试、行业考试以及职业技能考试的考试系统都是基于局域网的;而考生自测、认证考试以及网络教学系统是基于广域网的考试系统[3]。同时，在线考试系统也是世界上最具实力的网络系统公司Novell所研究的对象[4]。在线考试系统的管理员可以利用系统进行布置作业以及从题库中抽取考试题目来进行考试的功能，考生完成作业或考试后，便可以提交自己的答案，再由系统进行批改[5-7]。

2组卷算法策略的分析与选择

2.1组卷算法策略的分析

当下，在线考试系统已广泛应用于教学网站、公司在线面试等场合中，在线考试系统的存在已经不足为奇了，但是能把组卷模块实现的比较好的考试系统相对较少。以下将研究并比较几种智能组卷算法，并选出最合适的组卷算法。

2.1.1 回溯算法

回溯算法（Backtracking Algorithm）可以用来解决集搜索与优化为一体的问题，这些问题，它们的解分布在一个解空间里，求解这些搜索问题的算法就是一种遍历解空间的系统方法，故解空间又称搜索空间。不管是求解搜索问题还是求解组合优化问题，都是在搜索空间中找到一个解或者全部解，或找到一个最优解或者全部最优解。该算法通常将搜索空间看成是一个树形结构，一个解对应树中的一片树叶。树根就是算法的初始状态，算法从该初始状态出发，尝试所有可达的结点。当走到一个结点不能继续走下去时，就后退一步或若干步，再从其他结点继续搜索，直到所有的结点都试探过。整个回溯的过程带有着系统性和跳跃性。对于考试系统组卷的问题，可以用每个结点来存储试题号，试题分值等数据，由于试题的满分是100分，组卷的结果实质上需要的是一组试题号来获取考试题目从而进行组卷，问题的解是由试题号构成的集合，但是这些试题号所对应的题目分值加起来必须等于100分，在搜索过程中若搜索到某一结点出现总分大于100分的情况就不能再从这个结点继续向下搜索了。此搜索过程与0-1背包问题的回溯解法相类似，假设背包最大载重是100，不同的是0-1背包问题是物品的总质量不能超过100，但组卷问题是必须要等于100，约束性相对于0-1背包问题更强。

2.1.2 启发式算法

启发式算法（heuristic algorithm），又称人工智能算法或全局优化算法，是相对于最优化算法提出的，具有自学习功能，能够利用部分信息对计算产生推理的算法。虽然目前理论上对其性能方面的评估还不能给以证明，但是其实践效果却不错，启发式算法能在可接受的时间代价下给出一个或一组可行的解，但是这个可行解未必是最优解，并且其与最优解的偏差是无法估计的。启发式算法给出的解往往都是具有偶然性的，这是因为启发式算法只会告诉你该如何去找答案，而不是告诉你该找什么。用启发式算法解决问题的难点是建立符合实际问题的一系列启发式规则，相比于盲目型的搜索，启发式算法的可以搜索得更加高效。在搜索高效的基础上，再仔细地设计与分析相应的启发函数，那么这个启发函数返回的启发值就会更加的合理，从而能够实现问题的解的最优化。如果应用启发式算法来实现组卷算法，那么也必将仔细设计获取试卷题号的函数，并且要在可接受的时间内给出一组合理的解。

2.1.3 人工鱼群算法

人工鱼群算法（Artificial Fish Swarm Algorithm）是一种模仿了鱼群中的觅食行为、聚群行为以及追尾行为这三种行为从而得出问题最优解的智能算法。觅食行为类似于蚁群算法的觅食行为，蚁群算法中的蚂蚁会往信息素比较密集的地方移动，从而找到事物或者窝;相应的，人工鱼群算法中的鱼的觅食行为则是向食物逐渐密集的地方游去。聚群行为即鱼在游动时会自然地聚集成一个群体，并且聚集的过程中，每条鱼都会保持与邻近的鱼同方向，同时也会与邻近的鱼保持一定的距离，防止过分拥挤。追尾行为发生在至少有一条鱼发现食物的时候，跟随其的其他鱼也会一起往有食物的地方游去。在人工鱼群算法中，所有的鱼的个体都在一个大环境中，每个鱼的个体都能够相互交互，相互感知到对方的存在。蚁群算法和人工鱼群算法同样都是模仿了自然界动物行为的算法，但人工鱼群算法与蚁群算法不同之处在于蚁群算法中的蚂蚁相互之间没有直接的关系，而是通过蚂蚁所生产的信息素这个纽带从而产生间接的联系，人工鱼群算法中的鱼就不需要这样的纽带。而且用人工鱼群算法搜索最优解的过程中，为了避免重复搜索，给予了人工鱼记忆能力，使得鱼能够记住哪些区域搜索过，哪些区域没有搜索过，从而避免了重复搜索。可以将这样的思想用在考试系统的组卷算法中，比如在组卷的过程中，需要抽取若干题目构成试卷，常理上一套试卷不应该出现重复题，有了记忆能力，就能够记住哪些题已经加入了试卷中，再在题库搜索的过程中，就避免了将重复的题目加入同一套考卷中。

2.1.4 模拟退火算法

模拟退火算法（Simulated Annealing）是一种改进的局部搜索算法，也是一种求解优化问题效果较好的启发式方法。局部搜索算法的思想类似于回溯法的树形搜索空间的试探思想。首先产生一个初始解，局部搜索算法会试着改变初始解的一部分，看看解的性能是否有所改进，如果是则会使用改进的解来进行下一步的循环，否则就保留原来的解。循环结束后，得出最好的解。但是，局部搜索法可能会导致算法进入一个局部最优解从而导致无法从局部最优解中跳出來，于是便想出偶尔让使得性能变差的解代替当前解，这样就能让算法从局部最优解中跳出来。会出现这样的想法也是源于分子热运动理论的启发，温度越高，分子运动速度越快，活动范围也就越大，活动范围一大，就意味着更容易退出局部最优解，从而就更容易用退步解代替当前解。解的性能不断提高，就应该让温度逐渐降低，模拟退火算法也因此得名。模拟退火算法的基本步骤是，首先要输入一个最优化问题的实例，并生成一个初始解，引入参数温度T，并设初值为T0（T0>0），接下来就是退火的过程，由于退火就意味着温度的降低，固可以设定T=0是循环退火的结束条件，循环中，首先要从当前解的邻域中随机选择一个新的解，若这个新的解是改进解，则代替当前解;否则设新的解的退步幅度为?，以概率e^（-?/T）用新解代替当前解，最后再更新温度T。直到T=0时，退出循环，并输出循环中见到的最好的解。

2.1.5 遗传算法

遗传算法（Genetic Algorithm）也是启发式方法之一，借鉴了达尔文进化论中的适者生存、优胜劣汰的思想。遗传算法将待解决问题看成生物的进化过程，这个过程会经过繁殖、交叉、变异等运算，得出下一代的解，每一代都对应着一个适应度，这个适应度的计算也需要根据具体问题来拟定出计算适应度的函数，淘汰的过程就是舍去适应度函数值低的解，这样在进化若干代之后就能出现适应度函数值很高的个体，从而实现解的最优化。遗传算法的流程普遍上来讲可以像如下描述：首先是对算法参数的初始化;其次是编码，这个编码的过程就是一个转换操作的过程，也称问题的表示，也就是把不能直接对其处理的各种参数转换成可以处理的对象。接着是初始化一个种群，编号为t，在迭代次数尚未达到最大时，计算种群t的适应度值，接着再进行繁殖、交叉、变异等运算，从而形成种群t+1，如果这样的种群还不满足指标，将会回退成种群t的状态，在迭代次数尚未达到最大时再次进行迭代，再经历上述的运算，如果种群满足了指标就可以直接解码，算法结束;如果一直没有满足指标，在迭代次数达到最大时也会直接解码，算法完成。

2.2 组卷算法的选择

为了能够抽取出最佳的试题组合成试卷，即要使得试卷中各个题目在题型上、难度上、考点上等各方面分布合理。本文上一节中介绍的五种算法都可以实现组卷，但是经过对以上五种算法的综合分析，用遗传算法来实现组卷功能更合适。如果用回溯算法进行组卷，就要不断地搜索树形空间，只用试卷的总分进行限制，最终组成的试卷也就只能在总分上满足需求，就会有题型、难度分布不合理的可能。如果用启发式算法进行组卷，在启发函数的设计上就需要特别仔细，但是用启发式函数得到的可行解与最优解之间的偏差无法估计，当这个偏差特别大的时候，组成的试卷就会让考生用户体验较差。而利用人工鱼群、模拟退火以及遗传算法进行组卷，组成的试卷质量会比回溯法与启发式算法好很多。但是从长远角度来讲，如果要对在线考试系统的功能进行扩充与改进，组卷的要求也会越来越繁多且不固定，相比之下，遗传算法更适合智能组卷的要求。

2.3 实数编码遗传算法实现组卷功能

遗传算法首先要解决编码问题，传统的遗传算法使用采用的是二进制编码。在二进制编码中，个体被抽象为一个01字串，使得所有的个体与各自的编码一一对应。对于本在线考试系统而言，个体就是一道试题，用二进制编码的方式对题库进行编码，如果题库中某试题被抽取为一张试卷中的某道题，那么久将其编码为1，否则就编码为0。但是利用这种方式编码，当题库太大时，编码和解码都会很烦琐。故可以用实数编码的方式来进行组卷，实现物以类聚，题以同型题放在一起。本系统实际需求中，对试卷有题数、题型、总分等约束，可以在一开始就设定组卷规则来指定不同题型数量来满足这些约束。

3 组卷模块的设计与验证

3.1 组卷模块的设计

为了保证考试的公平和随机性，要保证每个人抽取到的试卷是随机的，可以减少作弊现象。本系统的组卷模块图，如图1所示：

其中，智能组卷模块就是从数据库中获取该考生选择的试题的组卷方式，然后再用算法将其进行组卷，最后将试卷分布到页面中。

智能组卷功能的执行流程如下：

1）考生在前端界面中选择考试类型;

2）当考生选择好考试类型后，系统会根据考生所选择的考试类型，在题目的数据库中抽取题目，题目抽取完成后形成相应的试卷;

3）系统将考试的界面展现给考生，考生即可开始答题。

3.2 组卷模块的验证

由图2与图3可以看出，题库中的题目顺序和考试界面的题目顺序是不一样的，组卷模块会基于试卷设定的题型的分值分布，自动随机抽取题库数据库中的题目，并将题目按照题目类型完成自动分配，说明本系统可以实现智能组卷功能。

4 结论

本文主要说明了在线考试系统的组卷模块，研究了一些组卷算法，最后根据本在线考试系统的实际的数据库等信息的设计情况研究了适合本系统的组卷算法。以上的功能经过了系统的测试都是可以成功实现的，经运行验证，组卷模块的設计是有效的，设计思路总体正确。

虽然本系统的重点的组卷功能已经实现，但毕竟时间和精力都有限，从系统的总体功能来看，本系统还有一些可以扩展的地方。例如，考试系统的考试界面还没有答题卡功能，这就不能让考生能够清晰地看出自己是否有漏答的题目，也就是说还可以扩展做一个答题卡的功能。随着对在线考试系统研究的不断深入，将对考试系统进行不断优化。

参考文献：

[1] 王卿蕾.物理教学中在线考试系统的应用与成绩分析[J].中学物理教学参考，2018，47（20）：12-13.

[2] 王沛.基于SSH框架的在线考试系统设计与实现[D].济南：山东师范大学，2018.

[3] 李红艳.在线考试系统智能组卷策略的设计与实现[D].长沙：湖南大学，2012.

[4] 胡欢平.《计算机文化》在线考试管理系统的设计与实现[D]. 南昌：南昌大学，2013.

[5] Lai S. Research and realization of key technologies for an online exam system[J]. Journal of Minxi Vocational and Technical College， 2009， 3：032.

[6] Li G. A research of online exam system based on SSH architecture[C]// the 6th international conference on computer science & education， 2011：358-360.

[7] Ahmad A， Khan N U， Abbas A W. PHP+MySQL Based Online Examination System with Power Failure Handing and Dropbox Capability[C]// IEEE， International Conference on Software Security and Reliability-Companion， 2013：21-25.

【通联编辑：王力】