遗传算法实现试题库智能组卷方法研究

吴　迪　龚启军

【摘 要】智能组卷方法是当今各大高校及相关单位试题库系统中的核心内容。本文提出了一种基于遗传算法解决组卷问题的改进方法，该算法以其具有的自适应全局寻优和智能搜索技术且收敛速度快的特点解决了传统组卷中编码太长、适应度函数值计算困难等问题，建立和描述了组卷问题的染色体结构和适应度函数，设计了问题的遗传操作，为进一步完善网络试题库的建设奠定了坚实的基础。

【关键词】试题库 数学模型 遗传算法 智能组卷

一、引言

本文对组卷方法进行了研究，使用遗传算法建立自动组卷的数学模型，并将遗传算法具体应用于试题抽取。

本文采用遗传算法的概念，将每道试题作为一个独立的编码位，利用遗传算法的三个基本操作：遗传、交叉与变异并最终完成试题的选取，得到满足各种条件的试题集和。遗传算法以其具有自适应全局寻优和职能搜索技术，并且收敛性的特性很好满足自动组卷的需要，具有较高的性能。

二、遗传算法的基本概念及设计步骤

1.遗传算法基本概念

遗传算法的基本思想是基于Darwin进化论的Mendel的遗传学说的。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，因此在这个算法中要用到各种进化和遗传学的概念。

2.遗传算法基本步骤

三、自动组卷算法设计

1.组卷策略分析

组卷就是从试题库中抽取试题，实现根据用户组卷要求生成的组卷模式。组卷的过程就是从试题库中选择合适的试题去实现这些分数分布。由于选题是有一定限制的，不是所有的试题库中的试题都有参与选题的资格，只有那些满足一定条件的试题才能参与选题。所以，选题组卷是在一定的约束条件下进行的。根据上述对组卷步骤地分析，组卷的约束条件基本上有以下十个方面，即知识点约束、题型约束、章节约束、认知层次约束、题量约束、分值约束、答题时间约束、难度约束、区分度约束、曝光度约束等。

针对整个试卷所有的题目构成如下的一个十维度变量的空间：

试卷（知识点，题型，章节，认知层次，题量，分值，答题时间，难度，区分度，曝光度）。为减小组卷算法的复杂度，提高组卷算法效率，对一份试卷，确定试题难度、试卷的满分值和所用的题型，以及各种题型的题目、分数和知识点分布；而对一种考试而言，难度—分数分布曲线LD常保持相对稳定，需要用到难度—分数分布曲线和数学模型即可计算出不同难度级别的题目在试卷中所占的比例，再结合各知识点、各题型的分数在试卷中所占的比例，将十维空间简化为五维空间——每一个试题（知识点，章节，题型，分值，难度）。

根据上述过程，首先解决“确定试卷知识点范围”、“章节范围”和“试卷包含的题型”三个步骤。

下一步，根据各题型所包含的题量，在各自的题型库表中抽题，抽题采用随机函数法。称这样抽取的一组题目，为一个“个体样本”。这就似乎最初建立的试卷样本。

这个样本至少满足了前三个步骤的要求，即知识点范围、章节、题型和题量上得到满足，但在“知识点分布”、“难度”、“区分度”、“曝光度”等维度上的约束条件可能存在或多或少的偏差，但这样做已经具备很好的应用遗传算法的可能性。

我们可以选取多个样本，然后按照遗传算法，使个体样本进行演化，得到满足章节、知识点、难度、题型和分值这五个约束条件的个体样本，而曝光度约束一般不限制为一个固定值条件，而是在寻优过程中选择曝光度之和最小的一组解，作为最后组卷的结果。

2.自动组卷算法的研究

试卷模式各参数实现之后，得到的是满足当前试卷模式的各道试题的具体指标要求值。下面关键的步骤就是从试题库中寻找具有这些特定属性指标的试题，组成试卷。

用遗传算法求解问题，首先要将问题的解空间映射成一组代码串。采用二进制编码，用1表示该题被选中，0表示该题未被选中，这种编码简单明了，但在进行交换等遗传操作时，各题型的题目数难以精确控制，而且当题库中题量很大时，编码很长。本文在确定编码方案时，采用了分组自然数编码策略。

每一组编码反映一种题型，各个题型各自进行自然数编码，即每一个题型根据组卷要求从初始化后的题型库中选出试题组成染色体。每一被选中的试题代表一个染色体编码，编码直接利用试题的编号。染色体采用变长编码策略进行处理，染色体中编码的个数就是试卷中试题的个数，题型组之间的编码是独立的。

在组卷中所得的可行解就为一份试卷，所以本文将一份试卷映射为一个染色体，组成试卷的各个试题映射为基因，基因的值直接用试题的题号表示，这样染色体的编码可表示为：(G₁,G₂,G₃,…,G_n)，其中G_i(i=1,2,…,n，n为试卷的总题目数)为试题的题号。

四、自动组卷算法的实现

确定参数：最大代数MaxGen，群体规模PopSize，交叉概率Pc，变异概率Pm；

接收用户的组卷要求；产生初始群体；

当前代数gen=；计算群体中各个体的适应值；

while(gen

{

根据个体适应值及选择策略从当前群体中选择生成下一代的父体；

执行交换操作和变异操作生成新一代群体；

计算新一代群体中各个体的适应值；

比较新一代的最好个体与上一代的最好个体的适应值，如下降，则以上一代最好个体替换新一代的最差个体；

输出当前代数，群体的平均目标函数，最好个体的目标函数值；

gen++；

}

输出最好个体的编码，计算各章节分数、各案难度级别的分数等指标，输出这些指标的值并与用户的要求值相比较。具体源代码略。

五、结束语

自动组卷系统是计算机辅助教学的重要组成部分，综合全文可见，本文主要工作是将遗传算法引入自动组卷问题，并在理论和实验中验证了基于遗传算法自动组卷的可行性。

参考文献：

[1]丁振凡.基于WWW的远程教学软件的设计.华东交通大学学报,1999,16(3):10-15.

[2]王宽全,符云清.基于WWW的计算机辅助教学环境.重庆大学学报(自然科学版).

[3]JR Quinlan.Induction Of Induction Of Decision Tress.Machine Learning,1986,(1):81-106.

基金项目：重庆工程职业技术学院科研基金资助项目（07YB009）厅级课题。