解析HGTPA的一种启发式组卷算法
来源:用户上传
作者: 胡志刚 刘洋
摘 要：组卷算法是在线考试系统的核心，本文结合遗传算法的优点，提出一种新的启发式遗传组卷算法（Heuristic Genetic Test Paper Algorithm, HGTPA），该算法能克服遗传算法的缺点，并在实验测试中取得比较满意的结果。
关键词：组卷算法；遗传算法；HGTPA
中图分类号: TP393 文献标志码: A
1 引言
随着计算机技术的发展和教学改革的深入，计算机辅助教学作为计算机应用的一个新领域，已经在许多方面显示出它的重要性。组卷算法是在线考试系统的核心，目前国内的在线组卷系统所采用的方法主要有随机抽题法、回溯生成法、自适应式遗传算法等。这些传统的组卷算法生成的试卷将试卷的科学性、试题的区分度和配合网络教学等因素考虑的较少。
因此，本文结合遗传算法的优点，提出一种新的启发式遗传组卷算法（Heuristic Genetic Test Paper Algorithm, HGTPA），该算法能克服遗传算法的缺点，并在实验测试中取得比较满意的结果。
2.1 HGTPA算法的设计思想
在组卷前，系统将会为自动组卷过程建立控制指标相应题库状态空间S(S为一个二维数组)。S的每一行由某一试题的控制指标组成，如题号、题型、难度等因素，并且这些属性指标都进行编码表示成二进制0和1形式，而每一列的取值（0或者1）表示题库中的某一指标。试题库中的每一道试题在建库时都输入了相应的属性指标。
由于二进制编码很长，设题库中有m道题，分别用x1，x2…，xi…xm表示，xi表示题库?专中的第i个试题。染色体的编码长度由试题库中的试题量来决定，比如m道题对应的染色体长度就为m位。染色体采用二进制编码方案，比如染色体x1x2，…xi…xm，当xi=1时，表示在本次的组卷过程中，试题xi被选中；否则xi=0，表示没有被抽取。初始群体对HGTPA算法有重要的影响，要实现全局最优，初始群体在解空间应尽量分散，这样可以减少了组卷目标的多重约束条件，提高组卷的效率。
2.2 适应度函数
在本算法中，我们设计的适应度函数考虑到各种约束条件，尽量保证求取综合指标的重要性达到最大或综合指标误差达到最小。本文的适应度函数定义如下：
其中i对应n项参考指标中的第i项，wi是第i项指标（包含答题时间，试题的难度，试题的区分度，试题的分值等）对组卷的重要程度的权重值，ri表示的是该组试卷中第i项指标对组卷目标的误差。
2.3 选择操作
我们精英选择操作：首先评估种群中每个个体的适应度值，然后根据适应度的大小进行降序排序。我们将群体中适应度最高的个体不进行配对交叉操作而直接选择到下一代中。在实际应用过程中，习惯于将其余交叉和变异操作配合起来使用，才会产生最佳的效果。另外，还有锦标赛选择，轮盘赌选择，无回放随机选择和随机遍历抽样等选择操作方法。
2.4 交叉操作
交叉操作是指对两个染色体按某种方式相互交换其部分基因，从而产生两个新个体的过程。它是产生新个体，保持种群多样性的主要方法。常用的交叉操作有多点交叉，均匀交叉，算术交叉等方法。本文采用的是单点交叉的方式。
2.5 变异操作
常用的变异操作有二进制变异、均匀变异、非均匀变异和高斯变异等方法。本文采用二进制变异的方法如下：
对于二进制串组成的染色体，我们通过变量的翻转方式实现变异操作。对于每个个体，变量值的改变是随机的，我们将下面有20位变量的个体中的第10位发生了翻转。
变异前：11011101110011010110
变异后：11011101111011010110
2.6 终止条件
设定最大进化代数 ，当算法执行到最大进化代数时，算法自动结束。
3 HGTPA算法的设计框架
本文设计的HGTPA算法流程如下：
(1)根据考卷出题的要求，规划题库状态空间库S中的数据，随机产生初始种群P(t)，并进行二进制编码，同时确定合适的交换概率Pc，变异概率Pm和最大进化代数ＭaxGen，进化代数t=1。
(2)计算初始种群中每个个体的适应度值，并根据适应度值的大小进行降序排序；
(3)根据前面3.3节设计的选择算子，以一定的选择概率从P(t)中随机选取个体xit和xjt进行交叉操作，产生一个新的试题模型群P'(t)。
(4)根据前面3.4节设计的交叉算子，以一定的交换概率从P'(t)中随机选取进行个体yit和yjt进行交叉操作，产生一个新的试题模型群P"(t)。
(5)根据前面3.5节设计的变异算子，以一定的变异概率从P"(t)中随机选出一个个体Zjt进行变异操作，产生一个新的试题模型群P(t+1)。
(6)当t?莛MaxGen时，试题组卷成功，转向步骤(7)；否则，t=t+1，转向步骤(3)继续执行。
(7)输出相应的考试试题，组卷结束。
4 组卷算法的性能比较
为了验证本文设计的算法有效性，我们将本文设计的HGTPA算法与文献[5]随机选取法，文献[6]遗传算法进行对比实验。本实验中，HGTPA算法和遗传算法的交叉概率、变异概率、种群规模取值相同分别为0.85，0.01，100。对题库量分别是1000,1500,2000的《计算机系统结构》课程试题进行了组卷，且设定试卷满分为100分。
在三种不同题库量状态下，我们将三种组卷算法分别运行50次，并统计出三种不同组卷算法成功找到最优解的概率(%)，最好值，最差值以及运行时间(/s),其结果表明本文设计的HGTPA算法和文献[6]的遗传算法在题库量为1000和1500时均能以100％的概率找到最优解，而随机选取法抽取的试卷获得最优解的概率是最低的，但是它运行的时间是最少的，这主要是因为随机选取法不需要进行大量的并行搜索，简化了搜索的复杂度。在不同题量时，HGTPA算法的最好值和最差值都表现的最好。
5 总结
本文主要提出了一种新的启发式遗传组卷算法的设计思路和实现方案，最后将本文设计的自动组卷算法与传统的组卷算法应用到在线考试系统中，进行了对比实验，该算法取得了较理想的实验结果。
参考文献
[1]王红艳等. 基于题库自适应在线考试系统地分析与设计[J]. 武汉理工大学学报, 2008, 30(4): 157～160.
[2]王萌，金汉均,王晓荣．集合随机抽取法在智能组卷中的研究[J].计算机工程与设计,2006,27 (19):3583～3585.
[3]全惠云,范国闯.基于遗传算法的试题库智能组卷系统研究[J].武汉大学学报(自然科学版) ,1999,45 (5) :758~760.
[4]朱明，王俊普.一种智能组卷方法的研究与实现[J].微小型计算机开发与应用，1997，4 (5) :5～9.
[5]李小勇，王 瑛.题库管理系统中的自动化组卷算法[J].西北师范大学学报(自然科学版)，2002，38 (4)：41-43．
[6]张瑞，苏健民.基于改进遗传算法的智能组卷在试题库建设中的研究[J]．计算机应用，2010，29(1):41-43.
转载注明来源:https://www.xzbu.com/8/view-47361.htm
