遗传算法在自动组卷中的应用

朱郭峰

摘要：为了减轻考试系统中老师出卷的工作量，并使出卷更加合理与科学化，此文通过遗传算法设计了一种新型的自动组卷系统，该系统首先介绍了遗传算法的基本思想与优势，其次利用随机搜索方法对自动组卷系统中各个功能模块进行了详细的设计，其中主要包括自动组卷系统中的编码方案的确定、自适应度函数的创建、选择交叉变异算子以及控制参数计算，最后，我们对基于遗传算法的自动组卷系统进行了成功的实现，整个系统运行正常。

关键词：遗传算法；自动组卷；成卷技术指标

中图分类号：P315.69 文献标识码：A 文章编号：1009-3044（2013）07-1626-04

1 概述

考试是用来考查人们学习程度的一种常见方式，传统的出试题的方式让老师有很大的负担，由于每个老师的理解不同，使其对学生的学习掌握程度的认识也有所不一样，这样就使得知识的覆盖面和试题难度难以被控制。为了达到考查的目的，提高老师的工作效率，避免不必要的重复劳动，我们有必要采用一种科学的组卷方式实现科学，高效，快速组卷。该文主要探讨遗传算法在自动组卷中的应用，研究遗传算法解决自动选题成卷的问题。

2 遗传算法

遗传算法起源于达尔文的进化理论与孟德尔的遗传学理论，它是一种新型的，模拟自然界生物进化过程的随机搜索方法。借鉴生物遗传学的方法，经过选择、遗传、变异等生物过程，提高个体的适应性，从而达到优胜劣汰的淘汰机制。遗传算法已经在搜索、优化、机器学习、图像识别等领域得到了广泛的应用，已经成为智能计算的重要技术。与传统的优化算法相比较，遗传算法具有如下优势：1） 遗传算法从解集中的串集开始搜索，不同于传统优化算法从单个初始值开始迭代得到最优解的方法。遗传算法搜索覆盖面大，容易搜索到全局最优解。2） 遗传算法通过适应度函数值来评价个体的优劣从而得到最优解，不涉及搜索空间的知识和其它辅助信息。由于适应度函数可以取任意的定义域，并且不受连续可微的约束。这样大大扩展了遗传算法的应用范围。3） 遗传算法根据概率的改变来确定搜索方向，经过比较得到最优解集，其概率并不是确定的。有效地防止了组卷失败的状况。4） 遗传算法遗传算法在进化过程中利用获得的信息进行自主搜索，使得优质个体能够以更高的概率被选中，从而得到更优质的基因结构。遗传算法的主要工作流程，如图1所示。

3 自动组卷

3.1 自动组卷的发展

在自动组卷试题库的创建方面，我们可以不断的更新与完善试题库的内容，在组卷时，对每题的内容进行分析，对出现过的缺点与不规范可以进一步修改，从而避免了传统出试卷时，考试结束后没有时间来进行总结与记录的缺点。自动组卷的产生，使得试题的内容具有了继承性，规范性，可以不断地积累出试卷的经验，并做好相应的记录与分析，丰富与规范试题库的内容，达到了开放性，实用性与交流性的特点。回溯试探法与随机抽取法是自动组卷中最常用的算法，回溯试探法记录每次操作的状态类型，然后分别与设定的条件进行对比，抽取满足条件的类型，一直循环到自动生成试卷或者重新开始组卷，它是基于随机抽取法基础上的。随机抽取法不考虑最优化，自动组卷生成的试卷只需要满足预先提出的各种约束条件，此试卷就为可用的了。随机抽取法算法结构简单，选取单一的试题时有较快的运行速度，但是应用于组卷的整个过程中，其抽取空间较大，会使得组卷时间很长，或者最后选取的试题不能满足要求，组卷失败。

3.2 自动组卷的技术指标与系统分析

试卷的评比中，会通过有几种曲线来考核试卷的好坏，如获取难度分数分布曲线LD，教学要求度分数分布曲线LR，题型分数分布曲线LT，内容分数分布曲线LC及其各自允许的误差，其中LR，LC及允许的误差都是用户给出的。曲线LD是很重要的曲线，大大地决定了最终成绩的分布。成卷的技术指标有难度，区分度，信度，效度这些方面，我们通常是用试卷的考试结果进行分析，但是在组卷时，我们了解这些指标的计算方法，然后进行科学合理地组卷。组卷系统中的试题库需要进行难度控制，能够生成符合测试要求，达到真正考查学生目的的试卷。

3.3 自动组卷试题属性

为了保证试题的质量，更好地考查学生对知识的掌握情况，我们通过控制以下属性来让试题规范化，科学化，最优化。

1）难度系数D：学生掌握试题内容的难易程度，D公式1确定

[Di=SiFi] （1）

其中，Di是指第i道题的难易系数值；Si是指所有考生在第i题的平均分数；Fi是i题的满分值。只有当Di适中，才能使得试卷达到检测学生对知识的真实掌握情况，当Di为0，则意味着，没有一个学生可以答对第i题，则该题的难度太大；当Di为1时，则意味着所有的学生都能答对第i题，则该题难度太低，这样的题目不能达到检测学生的目的。一份理想的试卷的难度系数应该在0.4—0.6之间，这样考试的成绩分布能够满足正态分布，也具有实际的参考价值。

2）区分度Q：为了区分考生的水平与能力，更好地考查考生各方面，试题需要设定一个区分度标准。区分度是根据考生的前35%高分组与后35%低分组计算出来的。如公式2

[Qi=Hi-LiFi] （2）

其中，Qi 为 第i题的区分度；Hi是前35%高分组在第i题的平均分数；Li是后35%高分组在第i题的平均分数；Fi是i题的满分值。当Qi = 0，表明低分组和高分组的平均分数相等，从而本试卷不能区分考生能力；当Qi < 0；则说明此试卷太难，考生都是胡乱猜测做题的；Qi > 0 ，才是正常的，但最好要大于0.3，这样才能有效区分考生能力。

3）时间T：是确定所有考生做完整套题所需要的平均时间。

4）分数S：确定此试卷的满分值。

5）曝光度E：曝光度是用来描述一道试题在前后两份试卷中出现的时间间隔。通过对曝光度值的大小来决定是否选用该题。

[Ei=Sa-SbG] （3）

其中，Ei 为第i题的曝光度；Sa 为第i道题在最近的那份试卷的出卷时间；Sb为第i道题在此次试卷的出卷时间；G为用户允许前后两份试卷出卷时间的最小间隔值。

4 基于遗传算法自动组卷的设计与实现

遗传算法应用于自动组卷中，首先要生成初始群体然后按照各约束条件对其中的个体进行选择与复制，再对其以一定的概率进行交叉与变异的操作，从而实现个体结构之间新的重组，不断迭代，知道搜索到符合条件的全局最优解。遗传算法应用于自动组卷中的算法如下：

1） 确定编码方案

自动组卷最终需要得到一份满足各约束条件的可行试卷，根据生物遗传学，我们可以将一份试卷对应一个染色体，而试卷中的每个试题对应染色体中的每个基因，我们可以用试题的题号来表示标记基因的值。染色体中的每个基因编码可以表示为：（R1，R2，R3，……Rn），其中Ri（n为试卷中的总题型数目，i = n -1）是试题的题号。

2） 建立适应度函数

在遗传算法中，群体中个体的优劣是通过适应值的大小来区分的。通常来说，适应值越大，就判断该个体越优秀，反之，则判断该个体越差劲。适应度函数就相当于是求解一个问题的评价标准函数。我们设某个体的适应度函数为f（x），在建立函数之前，我们要保证目标函数与适应度函数建立映射后，使得f（x）是非负的，并使其越大越好。

3） 设计遗传算子

Step 1选择算子。选择算子是用来确定进行交叉的个体，本身并不具有产生个体的能力，主要是为了达到提高群体平均适应度值的目的。通过选择算子，我们选择优异的个体，使其直接遗传给下一代或者让其通过交配产生新个体然后再遗传下一代，从而就淘汰了适应度值低的个体，也就是劣质个体被淘汰了。个体i在初始群体为n的情况下，其被选中的概率为

[Psi=fi/i=1nfi] （4）

其中n为初始群体的大小，fi 为第i个个体的适应值。

Step 2 交叉算子。交叉算子能够产生新个体，它主要操作是将父代个体的部分结构进行两两替换重组，从而产生新个体，这主要是在相同题型段内操作的。基本的遗传算法中，交叉概率是固定的。自适应的交叉概率是可以自己调整的，交叉概率越大，则搜索过程中更加容易保证群体的多样性。所以，在粗略搜索时，其交叉概率越大越好，最后细搜时，其交叉概率越小越好，这样能够加快其收敛速度。

Step 3 变异算子。变异算子也能够产生新个体，是产生新个体的一种辅助方法。它决定遗传算法在局部的搜索能力。采取最小的概率对满足约束条件的相同题型段的单点进行变异操作，并且先进行交叉操作再以变异概率Pm来进行操作。在确定每个题型的题号范围后，需要考虑该个体基因与其他基因是否被多次选中，有没有重复，如果被选中，就要重新开始产生，直到没有被选中的随机数，用它来代替此题型段中的任意一个题号。变异算子可以保证种群的多样性，防止出现早熟现象。

Step 4 選择算法的控制参数指标。遗传算法中需要考虑的参数有，群体规模n，交叉概率为Pe，变异概率为Pm。当群体规模过小时，能够提高运算速度，但是降低了种群的多样性，比较难得到最优解。但是当群体规模过大时，运算速度会下降，n的取值范围一般大于30且小于150。交叉概率决定了个体的更新与算法的全局搜索能力，当Pe取值过大时，容易导致群体的高适应度值得到破坏，取值过小时，其退化为简单的随机搜索，所以其取值范围为0.35～0.85之间。变异概率Pm过小时，会使产生的新个体较少，若过大，则会使其退化为简单的随机搜索，所以其取值范围为0.01～0.2之间较合适。P的值是经过多次的实验确定的。

Step 5 确定算法的终止条件。我们通过限制最大的迭代次数与既定的目标适应度值来判断是否终止算法，分别将个体的最大适应度值与目标适应度值进行比较，当期望值不大于最大适应度值时就停止迭代，否则对上述遗传操作进行反复循环，直到达到期望适应度值时，组卷才成功。

Step 6算法的实现

参数的确定，群体规模n，交叉概率为Pe，变异概率为Pm，最大迭代次数为MaxGene，实际迭代次数Gene；

确定用户的约束条件；

建立初始群体；

初始迭代的次数Gene = 0；

确定群体中每个个体的适应度值；

确定最好个体的编号，输出的指标值分别与用户的约束条件值进行比较。

5 结束语

随着计算机的普及，信息知识的发展，使得自动组卷技术被大家追捧。自动组卷技术能够减轻老师的负担，使老师们将更多的时间投入到科学研究中；使试题的形式更加规范化，能够更好地进行总结与分析，使试题更加科学化，更好地考查学生各方面的素质。该文主要是基于遗传算法在自动组卷中的应用，设置了几个变量，设计了遗传算法自动组卷的基本步骤，实现了简单的自动组卷功能。由于时间与能力有限，其运行过程中的细节问题还需得到完善。

参考文献：

[1] 王明川.基于遗传算法的组卷方法研究[J].基础科学，2011，35（2）：65-81.

[2] 朱大茗，马绍汉.算法设计与分析[M].北京：高等教育出版社，2009.

[3] 李敏强.遗传算法的基本理论与应用[M].北京：科学出版社，2003.

[4] 宋芝兰.基于遗传算法自动组卷问题的设计研究[J].商业科技，2011，2（上）：9-10.

[5] 王栋.自适应遗传算法的研究[J].科技前沿，2011，2（646）：175.

[6] 王小平，曹立明.遗传算法理论应用与软件实现[M].西安：西安交通大学出版社，2002.

[7] 钟宁，刘连浩.遗传算法在在线考试系统中自动组卷的优化设计[J].电脑知识与科技，2010，7（2）：397-398.

[8] 谢兴，秦前清.遗传算法在医学图像自适应融合中的应用[J].计算机工程与应用，2011，47（3）：181-183.

[9] Xiao Han-peng.Research of Test Paper System Base on Genetic Al-gorithm[J].Computer Knowledge and Technology，2010，27（056）：65-81.

[10] Guo Xiaolei.Design and Implementation of Paper System based onAGA[J].Computer Development &Applications，2010，8（027）：7569-7570.