遗传与蚁群混合算法实现在线考试系统组卷设计研究

摘  要：在线考试系统的算法主要体现在组卷设计模块当中，要实现自主组卷，并且组卷成功率高。生成的试卷在满足试卷的基本约束条件基础上，还要体现试卷的难度控制以及考试区分度。这就需要通过算法来进行设计实现。本文就多种算法进行对比，分析优劣，选取了遗传算法与蚁群算法混合优化，实现组卷设计模块。对两种算法实现在线考试组卷模块的思想和实现方法进行了详细阐述。

关键词：随机算法;遗传算法;蚁群算法;工作流程;区分度

中图分类号：TP18;TP391.6       文献标识码：A 文章编号：2096-4706（2019）20-0023-03

Abstract：The algorithm of online examination system is mainly embodied in the design module of generating test papers. To achieve self-generating test papers，and the success rate of generating test papers is high. On the basis of satisfying the basic constraints of the test paper，the generated test paper should also reflect the difficulty control and the test discrimination. This requires the design and implementation of the algorithm. This paper compares several algorithms，analyses their advantages and disadvantages，and chooses the hybrid optimization of genetic algorithm and ant colony algorithm to realize the test paper design module. This paper elaborates on the idea and implementation method of two algorithms to realize online examination paper module.

Keywords：stochastic algorithm;genetic algorithm;ant colony algorithm;workflow;discrimination

1  在线考试系统组卷模块算法对比分析

1.1  在线考试系统模块简单说明

在线考试系统，要完成一个通过浏览器登录，进行身份验证，获得权限，通过服务器获取考卷，实现在线考试并且自动阅卷统计等基本功能。相关的主要模块一般包含考生情况管理模块、口令登录模块、组卷模块、阅卷模块、报表与维护模块等。实现在线考试，这一基本功能，已经屡见不鲜。对在线考试系统的主要研究侧重于通过算法的优化，实现试卷的生成。算法优化的主要目的是提升试卷的总体质量（难度、区分度的设置与控制），提升试卷生成的成功率，降低试卷生成算法执行时间等。

1.2  试卷生成模块相关算法优劣分析

1.2.1  随机算法

随机算法是最早出现的试卷生成应用算法之一，是采用随机数的方式，在满足基本约束的条件下，从题库当中进行试题的抽取。这种算法的实现非常简单，而且试卷生成的速度也很快。但是相对而言，随机算法的缺点也非常明显。因为算法简单，抽取是采用随机的方式，所以对试题库的题量要求很高，如果题库数目不充足，就会出现试卷试题大量重复的现象。同时也由于在前面的算法中只采用随机方式进行抽取，试卷后面的试题抽取可能无法满足约束条件，频繁出现试卷组卷失败的现象。即便解决了题库数量的问题，试卷组卷失败后，需要进行重新随机算法试卷生成，大量的重复会耗费大量的试卷生成时间。这两点对在线考试系统而言，弊端较大，目前随机算法只在一些小型的在线考试系统中采用，应用范围小。

1.2.2  回溯算法

这种算法是建立在随机算法的基础上的，针对随机算法试卷生成率低，进行的算法改进。就是在执行随机算法的同時，进行每一步状态的记录。当随机算法在N步骤无法进行，组卷失败后，退回到试卷生成的上一状态，重新进行试卷的生成，提高了组卷的成功率。但是这种算法也出现了新的问题，状态的记录与回溯，耗费了大量的算法运行时间，提升了时间复杂度。同时也丧失了随机算法单次组卷的快速优势，实现方法相对也比较复杂，目前的实际应用也不多。

1.2.3  遗传算法

遗传算法是在智能化的在线考试系统开发中，大量应用的一种算法。它是借用遗传学的思想，通过编码的方式确定染色体，形成种群，再通过交叉算子的选择、交叉、变异等计算过程，从种群中选取具有优势的下一代，也就是更贴近理想解的集合。遗传算法是借用遗传学思想，通过数学的迭代计算方式，利用计算机编码来实现完成。这种算法前期的收敛性能好，能够很快地获取前期优势的解集，在试卷生成中，我们要与适应度这个目标函数的贴近度来进行判断。但是在后期，由于种群接近优势解，所以竞争能力降低，算法效率降低，迭代次数设置成为难题。如果设置过大，则会出现两个问题，一方面，试卷不能生成，但迭代次数没有完成仍然需要无用的大量计算;另一方面，迭代作用减弱，对优势解集的帮助不大。如果迭代次数过小，无法进行充分计算，试卷生成概率降低。也就是说，遗传算法对比前两种算法具有一定的优势，全局搜索能力佳，前期算法效率高，应用较广，但是也存在一定的弊端。本文提出遗传算法与蚁群算法混合实现组卷模块设计的设计思想。

2  用遗传算法与蚁群算法混合实现组卷模块思想分析

2.1  算法对比结果

从上文我们可以看出，在组卷模块中，相对于随机算法和回溯算法而言，使用遗传算法具有一定的先进性。遗传算法使用遗传学思想，通过编码确定染色体，利用初始化种群操作确定初始群体数量，然后利用适应度函数实现优化目标，再通过遗传算子，进行选择交叉变异等操作。但遗传算法在试卷生成中也遇到了问题，虽然遗传算法具有全局优势，前期优势解集获得速度快，但是后期算子的竞争速度变慢，迭代次数设置难以标准化。简单地说，就是遗传算法在运算的前期，运算效率高，但是在后期需要耗费大量的时间，整体的运算次数设置难以实现精准化，所以也存在一定的弊端。

2.2  算法混合的作用

为了弥补遗传算法的不足，我们发现蚁群算法具有快速收敛，鲁棒性强等特点，而且这种算法具有较高的融合性，可以实现与其它算法的配合，完成最优解集的求解过程。

2.2.1  蚁群算法简单说明

利用蚁群觅食中寻找路径的特性，应用于最优解集的求解。其算法思想简单描述为：蚂蚁在搬运食物的过程中，通过分泌信息熵这种具有挥发性气味的特殊元素，来进行路径选择。相对而言路径短的，在一定时间内，完成搬运的次数多，经过的蚂蚁也就较多，分泌的信息熵浓度较高，同时挥发的也较少，利用蚂蚁辨认信息熵的特性，进行路径的选择。从这种思想我们也可以得出，这种算法具有正反馈机制。从实现过程来分析，也就是信息熵浓度越高，路径被选择概率越高，完成最优路径选择越快。也就意味着算法的后期，运行效率高，实现优势解集求解优势大。

2.2.2  两种算法混合的思想

两种算法混合的出发点是，在遗传算法实现组卷模块的基础上，优化组卷算法，解决遗传算法中存在的问题。在研究过程中，发现了蚁群算法的特点，蚁群算法具有正反馈机制，后期寻求优势解集效率高，融合性强。从这些特点正好能够解决遗传算法后期，后代竞争效率低，算法效率低，迭代次数不容易科学设置的问题。

蚁群算法是否更加适合完成组卷模块，替代遗传算法呢？研究到此，是必须要考虑的问题。如果蚁群算法更具有优越性，那么就没必要进行算法融合，直接使用蚁群算法实现组卷才更有意义。蚁群算法也有自身的不足，从算法的思想我们可以看出，蚂蚁是根据信息熵的浓度实现路径选择，而在初始化阶段，路径多，每条路径的信息熵浓度概率相对平等，要完成初始化工作，需要的时间较长（需要蚂蚁实现遍历路径，而且进行多次遍历后实现）。这意味着，蚁群算法初期的初始化路径需要花费较长时间。

因此，将蚁群算法融合入遗传算法当中，在前期使用遗传算法，实现快速解集的实现，相当于用较高的算法效率实现蚁群算法的初始化过程;在后期融合蚁群算法，替代遗传算法的后期运算过程。这样就降低了对遗传算法迭代次数设置的精准性，同时提升了算法的整体运算效率，试卷生成时间短，能够生成高质量试卷。

3  试卷难度与区分度的计算以及选取标准

所谓高质量的试卷，是通过试卷的试题难度以及在考试中所体现的区分度来实现的。通过算法生成的试卷可以实现难度数值的控制，以及区分度的辨别。下面分别进行介绍。

3.1  试卷难度

试卷的难度系数来源于不同难度试题的选取，这里为了便于理解，从试题的难度开始说明。

3.1.1  试题难度公式

试题难度通过试题的失分率来体现，对于某道客观化试题，失分率越高说明难度越大。

其中D为难度数值，PR是试题答对的人数，PA是全体参考人数（R代表right，A代表all）。公式含义便于理解。用整体1减去试题答对人员占的概率数值，那么就是做错人数的概率数值，也就是失分概率数值，数值越大难度也就越高。

其中  代表某道试题所有考生的得分平均数值，s容易分析出是试题的总分，用1减去概率数值，得到的是试题的相应难度数值，同样的数值越大代表越难，数值越小代表越简单。

3.1.2  试卷难度判断公式

其中整张试卷的难度为D，用某道试题的难度系数di乘以该道试题的对应分值si，进行求和累加，再除以试卷的总分数A。

以上为试卷难度产生的相应公式说明。在研究中发现，初期认为难度系数处于中间数值，试卷质量较高。但随着研究的增多，应该更加侧重于应用性，视考试的目的而定，不同的考试，选拔目的不同，最优的试卷难度系数应该是不同的。

3.2  区分度公式说明

试卷的区分度，即是试卷试题对考生的水平考核的差度。如果体现出高分段、低分段、和中等分段三个阶梯式表现，就代表区分度较佳。总分的前百分之三十为高分段，总分的后百分之三十为低分段。

3.2.1  试题区分度公式举例

其中试题区分度为T，用高分组人数ph减去低分组人数pi除以总人数A，就得出了区分度。这种公式适用于客观化试题。当然如果在在线考试系统，使用主观化试题，那么就不能使用人数比值。同样的将公式转型为对应的平均得分差值和总分的比值，就仍然有效。

3.2.2  试卷区分度公式

其中T为试卷区分度，si为分值，ti为试题区分度，相对而言区分度接近0.5为最佳。

3.3  相关指标说明

通过设计与实验发现，通常情况下，试题难度居中，能够体现试卷的价值，居中的指标这里认为在0.45到0.6之间的范围。并且试卷难度在这个范围区间，通常试卷的区分度数值一般较高。但在一些选拔性考试当中，要根据考试需要进行难度算法设置，要以实用性为标准进行算法指标调整。通常的顾虑是难度过大或者过小，区分度数值较低。难度数值相对居中，区分度数值较高。

4  混合算法流程图

如图1所示，遗传算法与蚁群算法的融合点，是通过最小进化率数值来实现的。当遗传算法的进化率多次小于最小进化率后，我们认为前期算法完成，后期的收敛速度减慢，为蚁群算法提供前期初始化数据，转入蚁群算法进行计算，并得到最终优势解集。

5  結  论

通过多种算法的对比，得出遗传算法在在线考试系统的试卷生成模块中具有一定的优越性，但是遗传算法也存在后期收敛速度慢，优势解集求解过程长，算法时间消耗较高迭代次数设置不容易精确等问题。采用蚁群算法与遗传算法混合，前期利用遗传算法进行快速信息优势解集求解，后期利用蚁群算法的正反馈机制，节省算法运行时间，提升了试卷生成的成功率。从时间复杂度，求解成功率方面使在线考试系统得到了大幅优化。

参考文献：

[1] 赵俊普，殷进勇，金同标，等.遗传蚁群算法在云计算资源调度中的应用 [J].计算机工程与设计，2017，38（3）：693-697.

[2] 田增瑞，赵阳，赵袁军，等.基于遗传算法与蚁群算法的最佳旅游路线设计 [J].数学的实践与认识，2016，46（24）：41-48.

[3] 黄永青，杨善林，梁昌勇.交互式蚁群遗传算法 [J].小型微型计算机系统，2016，37（11）：2567-2570.

[4] 蔡延光，汤雅连.关联运输调度问题带遗传算子的自适应蚁群算法 [J].计算机应用研究，2015，32（8）：2313-2318+2360.

[5] 张新萍，张月琴，冯珊珊，等.一种求解图着色问题的蚁群遗传算法 [J].计算机应用与软件，2014，31（11）：207-209.

[6] 陈亚云，韩文涛，崔鹤平.遗传算法与蚁群算法的改进融合 [J].中国农机化学报，2014，35（4）：246-249.

[7] 刘传领.改进的蚁群遗传优化算法及其应用 [J].计算机应用，2013，33（11）：3111-3113+3128.

作者简介：苏楠（1980.07-），女，汉族，吉林人，讲师，本科，研究方向：软件技术。