基于混合算法的校园网络测评系统开发与研究

郭耀辉

（江苏联合职业技术学院徐州经贸分院 江苏省徐州市 221004）

1 测评系统的基本功能与基本约束

1.1 校园网络测评系统的基本功能

网络测评系统要能够实现在线考试、在线阅卷以及试卷分析汇总、分数转换等基本功能。

（1）考试前的准备功能：允许实现考生基本信息的输入，作为后期在线测试的登录验证标准。建立试题库，支持通过EXCEL文件导入以及手工输入等输入方式，建立题库。允许在考试前生成试卷，进行检测判断试卷是否符合在线测试标准的操作，也支持实时生成试卷的方式。创建考试科目、时间、在线考试时间等准备信息。

（2）网络在线测评功能：发生在实时考试阶段，实现考生通过浏览器，进行身份验证登录测评系统的过程。在线分发试卷，考生在浏览器端进行答题，并且提供自主收卷以及到达规定时间自动收卷两种收卷方式。在即将达到自动收卷时间点前设置提醒功能。

（3）试卷评阅与分析功能：实现自动化阅卷自动核算分数模式，如果加入主观试题，可采用照片方式，加入人工阅卷的参与。对类型题、小题的得分情况进行统计与分析，有价值的参数融入到难度变化数值中。

1.2 试卷的基本约束

试卷的基本约束根据考试科目何内容的不同，可以进行灵活调整。大体包含有：试卷总分、试卷类型题、试卷题目数量、类型题数量、对应分数等基本的约束条件。

2 混合算法在本测评系统中的作用以及混合算法的优势

2.1 算法作用体现

针对早期的测评系统，试卷仅能满足基本约束，试题难度无法控制，试题覆盖度低，造成考生分数集中，无法进行区分，同时对考生的考查目的难以实现的问题。采用混合算法，目的就是控制试卷难度，让难度体现在合理或者设计范围内，能够让优秀、中等、偏差的考生通过考试进行区分，发现不足。体现考试目的。同时通过混合算法还要提升试卷生成的速度和成功率。

2.2 遗传算法的优势

2.2.1 遗传算法与传统算法对比

遗传算法是测评系统智能体现出现早、应用广的算法之一。在此之前测评系统的试卷生成策略常常使用随机算法和回溯算法。随机算法特点是随机对试题进行抽取，不断往复进行，形成符合条件约束的试卷。优点是试卷生成速度快，算法实现简单。缺点是高概率出现重复试题，如果要求试卷体现智能化特点，试卷生成成功率低，耗费大量时间。而回溯算法可以视为随机算法的一种改进算法，随机算法在试卷完全生成后，可能常常出现不满足条件，组卷失败从而重新进行的现象。耗费了大量的时间。而回溯算法可以避免这个问题，通过记录上一状态的相关参数，更早的发现失败冲突，从而回溯到上一步骤，重新进行生成。这种方式时间复杂度与空间复杂度耗费大，算法实现相对繁琐。智能体现不足。

2.2.2 遗传算法的思想与实现

遗传算法的基本思想是利用生物学中达尔文优胜略汰的思想模式，通过与计算机的结合，实现染色体确认、种群规模限定、选择算子、交叉算子、变异算子的下一代繁衍过程。遗传算法的实现目标不是最优解，而是最接近优势解的解的集合，是面向全局的算法。

遗传算法的实现过程：

第一步，二进制编码实现染色体确认：染色体确认在计算机编码中不仅仅有二进制编码方式，也可以巧妙的利用实数形式或者分段方式。但是目前公认的使用二进制编码模式便于理解，也让后面的编程过程更加规范，便于实现。其中通常使用的规则为1 为选中模式，0 为未选中模式。举例说明某8 位染色体位10101001，代表着初始编码长度为8，可能对应8 道试题，初次选中第一、三、五、八题目，共选中四道题目。选中位置是1 出现的编码位置。

第二步，确定种群范围：种群范围其实是遗传算法很关键的一个步骤，涉及到遗传算法相应适应度函数以及相关指标，进行数学迭代的次数以及遗传算法结束的条件。如果单纯的使用遗传算法需要设置控制的范围，计算迭代的次数，以及未曾满足次数情况下是否触发算法继续进行的条件（多次运行未得到进一步优化的情形）。

第三步，遗传与变异（选择、交叉、变异算子）：首先，选择算子，也就是对下一代的生父母进行选择，从种群中进行选择，采用轮盘赌的算法选择，利用轮盘滚动的思想，不同的滚动对应不同的区域，多次到达的轮盘区域代表适应性更强，更利于繁衍优秀的下一代算子。其次，交叉算子，采用数学的方式进行逻辑计算，产生下一代，最后根据变异率，从产生变异的算子中选择优秀的，适合优解的继续进行迭代过程。

2.2.3 遗传算法的具体优点

从遗传算法的思想以及实现过程我们可以总结出，遗传算法是一种全局算法，适合求解优势的解的集合。鲁棒性能强，可以在多方面得到应用。在算法前期执行优化的过程迅速。当然任何算法都有自身的不足，比如遗传算法是全局算法，那么它针对局部解的能力就弱。由于是针对优势解集而不是最优解，在算法后期进化求解的过程就过慢，甚至出现无效运算的现象。遗传算法已经初步的可以根据适应度函数实现试卷难度的控制，体现测评系统的智能性。

2.3 蚁群算法进行混合的合理性分析

为了让试卷具有难度控制和区分度体现的智能目标，采用遗传算法，但是遗传算法的不足，使得试卷生成成功率不足够高，生成效率也需要进一步优化。而使用蚁群算法可以让两种算法的优势结合。提升试卷生成成功率以及试卷生成速度。

2.3.1 蚁群算法的思想

篇幅限制，这里简单用文字进行说明。蚁群思想借用的是生物学蚂蚁寻找食物选择优化路径的过程。蚂蚁在寻找食物过程中，总是能在一定时间内找出相对短的可行路径。通过的是气味（信息熵）的散发，在初始过程中，随机进行路径选择。并且在走过的路径上分泌信息熵，如果路径短，那么信息熵挥发的速度慢，浓度也就相对高。从而吸引更多的蚂蚁选择相应路径。而更多的蚂蚁又分泌出更多的信息熵。这毫无疑问是一种有效的正反馈机制。路途较远的路径在浓度对比中信息熵越来越低，从而被放弃。

蚁群算法的优势：从蚁群算法思想我们可以看出，第一点，也是最为重要的一点，是蚁群算法具有高效的正反馈机制，能够快速寻找最优解。第二点，鲁棒性也很强，适合不同领域，适合算法进行融合。第三点，从蚁群寻找路径的过程，可以看出该算法属于分布式算法。具有分布式算法优势。

当然蚁群算法也有自己的不足，那就是初期的路径遍历过程缓慢，具有很强的随机性。

2.3.2 蚁群算法融合的作用

从遗传算法和蚁群算法的优缺对比，就可以看出两种算法融合实现最优解集寻找的可行性。遗传算法运行在初期收敛快，全局算法，但是在后期因为是针对较优解集，所以迭代过程中可能存在多次进行，但无法继续优化的问题。浪费算法时间。而且这个迭代发生的具体次数，无法具体提前精确预估。而蚁群算法初期遍历过程缓慢，但是在前期过程完成后，形成高效的正反馈，利于高效的获取最优解集。所以通过前期遗传算法解决初期遍历问题，然后融入蚁群算法，寻找成功试卷的组卷，是又实际算法应用价值的。

2.4 混合算法融合点的设置与判断

到此两种算法的融合的作用和可行性，已经完成介绍，但是在实际应用中的难点，也就是两种算法运行的具体融合点，才是应用的关键。如何定义这个融合点呢？

（1）算法的先后顺序已经理清，前期使用遗传算法，到达融合点后转入蚁群算法，利用正反馈机制实现高效优化作用。

（2）遗传算法实现过程无疑问进行编码，种群确定，选择、交叉与变异。

（3）如何判断遗传算法终止，转入蚁群算法。采用了两种方式。第一种根据遗传算法中数学迭代设置的最大次数。如果达到最大迭代次数，遗传算法运行完整结束，转入蚁群算法。这个迭代次数通常是根据试卷对应题库的数量与相对实验进行预估的，有一定的合理性，并且保证迭代次数的最大值通常能让遗传算法应用得到满足。但这个迭代次数是不可能精确的，设置中可能通常也会设置数值偏大。第二种方式，就是设置进化率。也就是在不断的下一代繁衍过程中，子代与父代差异的数值，当多次差异数值小于规定数值后，也就是下一代的繁衍优化非常不明显，也就意味着可以允许遗传算法结束，后续过程视为无意义。这就是融合的关键点。当然在一些运算中，为了避免局部优解出现，也就是在几次过程中没有出现优化，但遗传算法实际运转不久，还没有产生优势解集的问题，也可以给遗传算法设置一个最小迭代次数，当最小迭代次数未达到时，进化率不能成为结束的融合点。这样保证了试卷生成的成功率更高。

3 算法中的指标与公式的使用

3.1 试卷难度公式

实现测评系统试卷智能化的第一个点就是控制试卷难度。试卷难度可以根据具体考试与考查目标进行合理修改。这里设置在0.45-0.55 之间，考试难度适中，试卷价值较高。

从公式中我们可以看出，K 代表的我们所寻找的试卷的难度数值，k 代表不同试题的难度权值，公式中的g 代表着不同试题的分值，公式分子为题目分值与对应题目难度系数乘积的累加和，分母为试题分值的累加和。

3.2 试卷区分度的公式

利用同样的思路，我们能够求解出试卷的区分度，是否能够将得分的高低，成绩优秀的和成绩差的，成绩居中的考生区分出来。当然试题的难度可以设置为5 档、3 档甚至根据需要更多的档。比如五档就可以设置为（极简、简单、普通、难、极难），三档就更容易理解，这里就不再赘述。

Q 为试卷整体的区分度，其中q 代表对应试题的区分度，g 仍然为对应试题的分数。通过累加数值的比例求出试卷整体的区分度。

3.3 试卷整体难度和试卷整体区分度的公式支持

从整体公式可以看出，试卷整体难度和整体区分度都根据具体每个题目的难度和区分度进行累加和求比。试题难度k 和试题区分度q

都可以采用两种方式进行公式标注，就是对应的人数和总体人数比值以及对应得分和总体得分比值得出。

试题难度公式：k=1-sd/sa或者 k=1-ave/A

试题区分度公式：q=(sg-sd)/s 或者q=(aveg-aved/A)

试题难度公式的含义分别是，用整体1 减去作对试题的人数除以总人数。所以作对试题的人越多，难度数值越低。反之作对试题的人数越少难度数值越高。用另外一个公式，代表试题的平均得分数除以试题分值，平均分越高，试题难度越小，反之亦然。（sd代表得分人数，sa代表总人数，ave 代表平均得分）。

试题区分度公式的含义是，高分人数减去低分人数，除以高低分组人数和，代表区分度。相差越大区分度越大。高分组平均得分减去低分组平均得分，除以题目对应的满分数值。

对于客观化试题，两种公式都能起到试题区分度、试题难度的测试作用。所以给出两组公式是作为未来拓展主观化试卷做准备。

3.4 区分度和难度权值的确定

从上文可以看出，不同试题对应不同的难度权值和区分度权值。这些权值并不是完全用后面的试题公式计算出来的，试题公式是通过多次测试，不断的提供权值变化的参考。真正的权值应该有一定的采样和教师做出修正。从系统实际应用角度，初始化的权值是没有的，因为一次测试也没有，需要教师的参与。同时一次或者几次的测试，也不能准确的确定权值。很多因素也影响着对应的权值。这里简单说明，例如题目的曝光度，也就是题目在试卷中出现的次数，出现次数越多，受到关注越多，掌握的人越多，这种题目就不能准确的反应出难度系数。所以曝光度高的题目权值应该下降。再比如在某次测试中，题目得分率很低，但题目难度并不大，存在题目理解的问题。这些都需要关注，合理修订试题难度权值和区分度权值。