基于遗传算法和蚁群算法融合的在线测评系统

文/姚楠

在线测评系统在我国一些领域已经得到了一定的应用，尤其是在高校当中，很多高校已经采用在线测评系统来进行多种科目的成绩考核与评估。但是在应用过程中仍然存在着一些问题，那就是试卷的试题是从试题库进行抽取的，很多测评都是通过随机算法实现，这样虽然能够快速的实现试卷的生成，但是无法控制试卷的难度和覆盖范围，试卷质量不高，会出现部分测评不能真正体现考核目的的现象。

1 基于遗传算法和蚁群算法的在线测评系统开发的作用与意义

1.1 在线测评系统的作用

在线测评系统主要是完成客观还试题的测试作用，目前开发的常见架构主要是浏览器服务器模式，同时还伴有浏览器服务器模式与客户服务器模式共用的模式，能够实现参考者在规定时间内登录浏览器进行考试的过程。降低了组织考试过程中，教室、纸质试卷等物质的消耗，减少了教师监考，人工阅卷等人力资源的使用。同时减少了组织考试必须进行的教师编排、试卷封装、巡考等考试的环节。

1.2 基于遗传算法和蚁群算法融合的在线测评系统作用

本系统中，遗传算法与蚁群算法的应用主要体现在组卷策略模块当中，算法的应用目的是为了实现试卷试题的难度控制，将难度控制在需求的难度区间之内，从而提升试卷的质量，让测评具有实际的评估价值。试卷难度过高，或者试卷难度过低，都不能体现应试者的真实水平，也不能给试卷组织题库组织者很好的反馈，无法对试卷的试题做出准确评价。应用算法则可以控制难度范围，使得测试范围和测试难度适中，合理对应试者水平进行区分。而使用两种算法并进行融合的目的，是为了弥补算法本身的弱点，实现高效率快速的试卷生成策略，并总体的提升试卷组卷的成功率。简单概括的话，蚁群算法便于易于求出优势解的集合，适合全局算法，但是在算法初期的路径选择过程中耗费大量时间，而遗传算法可以快速的实现初期的路径选择过程，两者合作，提升试卷生成的效率和成功率。后文会详细介绍。

2 蚁群算法与遗传算法简介

2.1 蚁群算法简介

蚁群算法顾名思义，是借鉴了生物群体蚂蚁的路径选择而形成的算法思想，蚂蚁由于个体微小，在搬运物品与食物的过程中，都是通过群体合作完成，而大量的蚂蚁群体在这个过程中却能够选择较短的合理的路径。这种原理的思想源于蚂蚁本身的气味分泌功能，蚂蚁可以分泌出特殊气味并附着在经过的路径当中，这种物质我们定义为信息熵。信息熵具有迭加和挥发的特性，这也就意味着经过这条路径的蚂蚁越多，信息熵浓度越高，同样的路径越短，经过的时间也越短，信息熵的挥发也越少。形成了有效的正反馈机制。如图1。

蚂蚁群体在起点A处出发，可以通过若干路径的集合1或者若干的路径结合2到达目的地B处，这两条路径集合的选择就是一群算法的体现。初始路径选择中，由于没有可以借鉴的信息，对路径的选择是困难的，是随意出发的，甚至会出现错路信息，无法到达目的地。而伴随初期路径选择过程的实现，两条路径当中，相对通过实践较短的会被选中。这是因为时间T越短，单位时间内平均通过的蚂蚁数量多，信息熵的浓度增大，同时时间T越短，信息熵挥发越少，浓度也性对更高。那么蚁群的选择标准是信息熵浓度相对高的路径，不断循环这个过程，路程短、通过时间短的路径信息熵浓度会越来越高，也会受到更多的蚂蚁选择，正反馈机制帮助找出相对优解。

蚁群算法优势与不足：

算法优点：

（1）算法属于正反馈机制：浓度高则提升被选择度，而被选择度高，也会提升路径浓度，是一种正向反馈机制，便于快速收敛，求出优势解集。但快速收敛其实也是一把双刃剑，过于快速收敛容易形成无解集合，在开发过程中应该注意。避免系统工作出现错误。

（2）求解过程并不是寻求最优解，而是进行较优解的范围与集合目标探索，全局性能高。

（3）蚁群算法鲁棒性强，在多个领域得到应用，适合进行优势集合的问题解决，例如货郎问题，组卷问题、考场安排问题、工业控制问题等等。

存在的不足：任何算法都有其不足之处，蚁群算法也不例外。在试卷生成策略当中，我们也可以看出蚁群算法的缺点，在路径进行选择的初期，没有有效的办法，需要通过长时间的信息熵的积累，才能达到辨别的浓度，应用到算法生成中，耗费大量算法时间。当然蚁群算法实现试卷生成也可能出现收敛速度快而造成的误解状态，这就需要题库的题目数量足够，当然通过遗传算法进行配合，也是实现试卷组卷成功率保障的一个有效方法。

2.2 遗传算法简介

遗传算法的思想来源于生物学，是通过群体的进化规律而进行最优解的求解过程。遗传算法的实现过程是首先，产生生物学中的染色体，生物特性是通过染色体实现的，而算法中的染色体是通过二进制编码的形式进行区别和实现的。不同的编码对应不同的染色体。编码完成之后，遗传算法就通过设置迭代次数实现选择、交叉、变异三个过程。选择是对编码后的染色体进行选择，挑选出适合求解的优秀遗传个体，而交叉是通过迭代过程，将选出的算子进行数学操作，获得新解，产生新的下一代。而变异过程则产生更加优秀的个体。

遗传算法的随机性能强，通过随机性能对初期的路径进行快速的优解，具有一定的作用。

3 算法公式说明

3.1 算法在试卷生成模块中的具体功能

要使用公式，就要分析算法的具体功能，在试卷生成中，首先要实现试卷的最基本约束条件，也就是普通试卷中的各种设置约束，例如分值、试题类型、试题数量等等。这种功能实现相对简单，多种算法都可以实现。其次，要进行难度控制，也就是实现应试者学习程度的区分，让难度数值控制在中等难度区间，从而使得应试者的考试表现不同，让试卷更加具有实际应用价值。最后，在一些考试中，要注意考点的覆盖，对不同章节覆盖程度大为佳。这里算法融合主要是针对难度的控制，产生区分。

3.2 具体公式说明与使用

篇幅有限，这里简单罗列几个重点公式：

这个公式为难度控制公式，通过公式求出评卷难度，也就是设置难度的具体指标。N为难度，n为每道试题的难度，C为成绩得分项。将总得分除以所有题目难度和，求出评卷难度指标。

算法实现过程中，通过概率来实现新路径的选择可能性。S为最终信息熵的具体数值。也就是说明数值的大小与新路径的选择有关，结果大选择新路径，结果小，直到得出相同选择，算法实现，得到优势解集。

4 算法融合实现的说明

算法初期，使用遗传算法，降低初期路径选择的时间复杂度。遗传算法的实现在于迭代次数的设置。也就相当于设置最小的进化率，如果算法中实际的进化率小于了我们设置的数值，并且一直小于，则遗传算法完成任务，使用蚁群算法，利用正反快机制和快速收敛等特点，进行快速求解。从而提升试卷生成效率并且提升成功概率。