遗传算法在自动组卷中的应用(图文)

1、遗传算法在自动组卷中的应用(图文)    论文导读：当前较为先进的组卷方式，是随机从已有的试题库中按照考试的各项要求，如题型、考核点分布、难度、分值等因素选择相应的题目自动组卷，组卷灵活，试卷的维护相对容易，这种方式已经被广泛地应用到各种网络考试系统当中。本文主要介绍的是使用遗传算法进行自动组卷的思路与具体的实现。 关键词：遗传算法，自动组卷，算子    1引言 随着因特网技术以及教育网络技术的不断发展，越来越多的学校和机构开始采用网络考试的考核形式，而在网络考试中采用组卷形式的优劣与否将直接影响到试卷的质量与考试

2、的成效。传统的网络考试中，学生只是随机的从已有的几套试卷中抽取一套，这样会导致试卷的维护成本变高，同时试卷的重复率相对较大。当前较为先进的组卷方式，是随机从已有的试题库中按照考试的各项要求，如题型、考核点分布、难度、分值等因素选择相应的题目自动组卷，组卷灵活，试卷的维护相对容易，这种方式已经被广泛地应用到各种网络考试系统当中。自动组卷技术实现的关键是组卷算法的选择与实现，它将直接影响到组卷的质量。本文主要介绍的是使用遗传算法进行自动组卷的思路与具体的实现。 2常用的自动组卷算法 当前使用较多的自动组卷算法主要有三种。第一种是基于随机抽题的算法，它根据问题空间的一些指标，从试题库中随机地抽取一道

3、试题放入待生成的试卷中，此过程不断重复，直到组卷完毕或无法从题库中抽取满足条件的试题为止。该组卷方法的重复率高，组卷成功率非常低，即使组卷成功，花费时间也较长。第二种是基于回溯试探法的算法，它是将随机抽题算法产生的第一状态类型记录下来，当搜索失败时释放上次记录的状态类型，然后再根据一定的规律变换出一种新的状态类型进行试探。该算法的不足之处在于当试卷总题量较大时，状态类型的变换便成为一个巨大的数字。因此这种方法只适用于状态类型和试卷总题量都较少的题库系统。第三种是基于遗传算法的组卷算法，它可以从群体中选择更满足条件的个体，具有很强的智能性。同时它能根据不同的环境产生不同的后代，具有动态性，自适应

4、性，从而能满足试题库容量、覆盖面不断变化的要求。 3遗传算法数据模型的建立 自动组卷时会根据组卷的原则对试卷的质量提出很多方面的要求，即试题的控制指标，如每种题型包含的题目数量、每种题型所占分数、每道试题的难度系数等。因此，在组卷之前应该为自动组卷建立模型。其模型如下图所示：                             

5、60;    a11 a12 a1n a21 a22 a2n am1 am2 amn                               图1 自动组卷的目标矩阵    模型中每一行代表对某一试题的所有控制指标，假设共有n个控制指标

6、。其中ai代表第i个指标。如果该试卷中一共有m道题，那么上述m*n的目标矩阵即可代表一份试卷。    上述的目标矩阵应满足以下条件：    （1）试卷的分数指标：=总分。论文参考网。（设定ai1代表试题的分数）    （2）各章分数指标：第j章的分值=（ai2代表章的编号）此指标可以衡量出自动组卷时，相关章节应占据的分值。    （3）题型分值指标：第j类题型的分值=（ai3代表题型），此指标可以衡量出自动组卷时，相关类型的试题应占据的

7、分值。    （4）知识点指标：第j类知识点的分值=（ai4代表相关知识点编号）。此指标可以衡量出自动组卷时，相关知识点应占据的分值。    （5）难度系数指标：第j种难度等级的分值=（ai5代表难度系数值）此指标可以衡量出自动组卷时，各难度等级的题型应占据的分值。    4组卷的流程    运用遗传算法解决实际问题时采用的基本流程如下：首先将所要求解决的实际问题进行二进制编码，然后根据实际的环境实施遗传的基本操作：选择、交叉、变异，通

8、过多次循环往复的遗传操作后，最终收敛到至一个最适应环境条件的个体上，即得到该问题的最佳解决方案。具体的实现流程如下：    （1）使用染色体编码方法对试题进行编码。将一份试卷映射成一个染色体，试卷中的每道试题映射成一个基因，其值用试题的编号表示。    （2）确定组卷的目标函数。使用函数描述组卷的目标，该系统使用的目标函数为：    F=*|-S|+*+*+*（B2(x)- B1(x)>n）    其中的ai表示试卷中第i题所占分

9、值， S表示试卷总分的预期值，bi示试卷中第i章试题所占分值， dbi表示试卷中第i章试题的实际总分值与要求的总分值之间的偏差。ci表示试卷中难度级别为i的试题所占分值，dci表示试卷中难度级别为i的试题的实际总分值与要求的总分值之间的偏差。B2(x)- B1(x)>n表示试卷每道试题在连续的n份试卷中不能重复出现。，和为相应参数的权值，可以根据实际情况进行调节。    （3）算子的选择。论文参考网。组卷流程中涉及到的算子主要有三个，分别是选择算子，交叉算子与变异算子。本系统在选择算子时使用的是目前遗传算法中常用的赌轮选择法，使用公式来决定其后代遗

10、传的可能性。交叉算子的确定过程则是随机产生一个0-1的实数，如果<P，（其中P为事先设定的交叉概率）则交换该基因。变异算子对后代个体的某些基因进行变异，起局部搜索的作用。该系统中引入变异算子pm，使用方法与交叉算子类似。    （4）完成组卷。当组卷达到实际需要时，完成组卷。论文参考网。    5系统的实施效果。    本系统的考试主要是针对本校的VB程序设计考试开发的，通过使用自动组卷系统，组卷效率得到了较好的提高，也大降低了考试的时间与人力成本，取得了较好的效果。     参考文献：    1 李惠姝，基于遗传算法自动组卷的研究与应用，太原理工大学，2007