基于改进遗传算法的智能组卷系统的研究

石慧升+韩志丽+刘沛叶

【摘要】针对传统的组卷算法具有组卷速度慢、成功率低、组卷质量不高等缺点，本文提出了改进的遗传算法组卷问题的新方法。实践证明，在这种结构下的数据库能很好的配合改进的遗传算法实现智能组卷，组卷的成功率和收敛速度都得到了明显的提高，并且较好的克服了未成熟收敛现象，取得了较满意的组卷效果。

【关键词】遗传算法 智能组卷 数学建模

1 引言

随着计算机在教学领域的应用和发展，试题库的编制和应用也越来越显示出其重要性，而智能组卷是试题库系统研制的一个难点。一个自动组卷系统的性能评价主要取决于组卷算法和相对于算法的试题库的库结构。因此，试题库的库结构设计和组卷算法的设计是智能型试卷自动生成系统的重要内容。遗传算法是一种模拟自然界生物进化过程的计算模型。它的求解问题是从多个可行解开始，然后通过一定的法则进行迭代以产生新解，直到得到最优结果。本文提出了一种用改进的遗传算法来求解试题库组卷问题的方法。

2智能型试卷自动生成系统的组卷问题

2.1智能型试卷自动生成系统中试题库结构的设计结合遗传算法的特点，系统所采用的试题库结构要全面客观反映试题的本质，并且易于遗传算法操作，使组卷实现智能化，组卷效率高、速度快、数据冗余度小。因此，所确定的试题结构如下：（1）章节：试题内容所属的篇章；（2）试题编号：试题编号具有与每一道试题一一对应的性质。（3）试题类型：可分为判断题、选择题、填空题、操作题、综合题。为了在生成试卷时能够快速选取指定类型的试题，和减少冗于度，在建库时可为每种题型建立一个库文件；（4）试题难度：在试卷命题过程中，针对不同的考试对象，不同阶段的考试，命题难度也不同，所以应在数据库中增加难度系数。（5）试题的内容：不参与组卷运算的过程。

2.2智能型试卷自动生成系统中组卷的功能要求

（1）考试内容由用户决定，可以按篇章为单位决定。

（2）考试时间由用户指定。

（3）整卷的难度系数由用户根据学生的水平决定，一般取0.2～ 0.5。

（4）每份试卷满分由用户指定，其中主观题、客观题所占分数比例由用户指定。

2.3智能型试卷自动生成系统中组卷的数学模型

组卷中决定一道试题，就决定它的上述13个属性，也就是说决定一个13维的向量（α1，α2，α3，… α13）决定一份试卷有n道试题，实际上就是决定一个n× 13阶矩阵。

3改进遗传算法在智能型试卷自动组卷系统中的应用

3.1遗传算法的基本思想。大自然的生物进化中，一个生物群体要经过交配、变异、自然选择的过程，形成下一代群体，如此循环下去，不断进化，最后生存下来的总是最优的。将这种思想运用到算法中去，就形成了遗传算法。 经典的遗传算法存在搜索后期效率低和易形成未成熟收敛的情况。为此，人们尝试了许多改进方法，包括设计不同的选择、交叉及变异算子，改变算法结构，设计自适应交叉和变异概率，将遗传算法与其它优化智能方法相结合等。

根据遗传算法，在采用遗传算法寻优时，通常按以下主要步骤进行：

①基因编码；②初始群体生成；③群体中个体适应度值的计算；④对群体中个体进行遗传操作（即选择、交叉和变异）；⑤适应度值的再次计算；⑥如果满足终止条件，叠代停止，输出问题的最优解；否则，转向步骤④。

上述遗传算法的每一步都对优化搜索的收敛速度和解的质量有影响。

3.2改进遗传算法在智能型试卷自动生成系统中的应用针对试题组卷的具体情况，我们对简单遗传算法进行改进后应用于智能型试卷自动生成系统中，下面给出具体的解决方案：（1）确定编码方案。（2）适应度函数的确定。（3）组卷问题中对遗传算子的改进。（4）对遗传算法控制参数

4实验结果及分析

实验条件：将《计算机基础》中800道试题按要求分别建立5个库文件，其中判断、填空、操作题各200道，选择、综合题各100道。为了使试题的各种属性分布合理，可用随机函数产生试题的各种属性值。遗传算法的控制参数为：种群规模N= 200；最大代数Maxgen= 500；初始交叉概率pc= 0.6；变异概率pm=0.1；智能型试卷自动生成系统中组卷约束条件：总分为100分；估时为120分钟；题型分数比例为：判断、填空各占10%，选择占20%，综合题占40%，算法设计题占20%；能力层次为：识记：20%，理解：30%，应用：35%，综合：15% ；难度为：容易：20%，中等：30%，较难：40%，难：10%。

由于在建库时为每种题型建立了一个库文件，故每种题型可各自独立编码。因此，编码方案可采用分组实数编码策略，就是根据各个题型各自进行实数编码，然后对每一个题型再采用传统二进制编码策略进行处理，但题型组之间的编码是独立的，每一组编码反映一种题型。这样，可以克服以往采用二进制编码搜索空间过大和编码长度过长的缺点。

为了加快遗传算法的收敛并减少迭代次数，试卷初始种群p（0）完全随机的方法产生，而是根据题型（或各篇章内容或各考查点）所占分数比例、总分的要求随机产生，使得初始种群已经满足了题型（或篇章或考查点）和总分的要求。

适应度函数是用来评判试卷群体中个体的优劣程度的指标，遗传算法利用适应度值这一信息来指导搜索方向。

5结束语

一个自动组卷系统的性能主要取决于组卷算法，一个好的组卷算法既要保证组卷的成功率，又要保证数据运算的时间效率。在传统的组卷算法中，组卷成功率较低，时间和空间开销都比较大，适合于小型题库系統。将遗传算法应用于组卷中，使组卷的成功率和收敛速度都得到显着提高，适合于较大型题库系统。由于求解精度和收敛速度是相互矛盾的，要使组卷的误差精度和收敛速度进一步得到改进，还需要做出更深入的研究。

参考文献：

[1]李小勇，王瑛.题库管理系统中的自动化组卷算法[J].西北师范大学学报（自然科学版），2002，38（4）：41- 43

[2]涂振华，王勇等.智能组卷算法研究[J].江西教育学院学报，2002，23（6）：51- 52

作者简介：石慧升 男 石家庄工商职业学院 高级工程师 硕士 ；韩志丽 女 石家庄工商职业学院 助理工程师 学士；刘沛叶 女 石家庄工商职业学院 工程师 硕士。