基于约束条件遗传算法的智能组卷策略研究

卢俊玮　付常军

摘要：随着教育教学信息化建设的日益深化，课程考试系统成为现代化教学评价环节的一个必须模块。通过学校资源的整合与积累，已构建了符合人材培养方案定位的试题库，并且对于试题的数量、知识点的覆盖度及试题库更新的常态化也达到考试系统的运行要求。但是，保证智能组卷的随机性、合理性及平衡性是实现难点。在交互式环境下用户对于组卷速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。该文结合遗传算法的原理，采取约束条件通过数学模型进行论证，表明了该算法的有效性和可行性。

关键词：遗传算法；智能组卷；数学模型

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）26-6172-02

Abstract： With the education of information construction increasing， the course test system is an important part of evaluation in modern education. The college was constructed test bank， through resource integration and accumulation. And the number of questions， coverage of the knowledge point， update normalization for test bank meets the operation requirements of examination system. But， it is a difficult problem to make sure randomness， rationality， balance of auto generating test paper. Because request high speed in interactive environment， however， a good algorithm usually spends a lot of time. In this paper， based on constrains of genetic algorithm theory， and reasoning by mathematical model， finally， the algorithm is proved effective， feasible and practical.

Key words： genetic algorithm； auto-generating test paper； mathematical model

随着办公自动化的发展，计算机辅助考试系统已被越来越多的机构使用。计算机辅助考试系统，是指系统根据用户出卷需求，在庞大的题库中随机地抽选试题，最终组成满足用户需求的试卷。而智能组卷是实现该系统的关键所在。对于在线考试系统必须保证其实时性。因此，寻找一个时间复杂度较低并能满足用户需求的算法成为实现智能组卷功能的关键。

遗传算法是一种新型的、模拟自然界生物进化过程的随机搜索、优化方法。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。非常适合组卷过程中多目标的逼近。该文根据智能组卷的需求，将遗传算法中的编码、初始种群、杂交步骤进行了一系列的改进，从而高效、智能生成平衡、合理的试卷。

3.3 后代产生算法

1） 由轮盘赌选择法生成选择算子，然后选择多个个体[2]。适应度越大的个体被选中的概率越大，这样能使遗传算法往好的方向进化，对提高解的质量有很大的帮助。

2） 将选择出的个体随机进行两两配对，针对每一对个体，进行杂交操作。杂交操作步骤如下：①确定交换点所属题型，算法：生成一个随机题型序号i，i∈[0，n-1]，n为题库题型的数目，如果约束条件中第i种题型的试题的需求量为0时，重复①操作；②确定交换点的在所属题型题库中的序号，算法：生成一个随机序号j，j∈[0，m-1]，m为题库中第i种题型的题目总数。若约束条件中该试题所属知识点不在考试范围内，则重复②；③生成一个随机数实数p，p∈[0，1]，若p∈pc，则将两个体的基因位b[i][j]进行交换（pc为交换概率）；④进行多次①②③操作，

3） 由于杂交后，新个体中某些题型的题量与用户需求不相等，这样的个体是不符合要求的，该文中称病体，因此需要对于杂交后产生的病体再进行修复操作。步骤如下：若病体中第i类题型不符合用户需求，设用户需求n道该题型，而病体中有m道该题型试题。当mn时，从已选的第i类题型中随机删除（m-n）道试题。对每个病体进行修复操作，使产生的所以新个体各题型对应的题量与用户的需求相等，因而试卷总分也符合要求，同时各个体包含的知识点在考试范围内。

5） 对变异后的个体进行3） 中的修复操作。

3.4 组卷结束条件

当初始群体或产生的后代中，有个体满足目标函数，即f为0，或者在用户允许的误差范围内，则组卷结束；否则，继续产生新的后代。若组卷的次数达到最大的系统预设执行次数或最大容忍生成时间时，将强制终止组卷。

4 结束语

本改进后的遗传算法，依据题型，进行十进制编码，以方便之后的各项操作，并在生产初始种群时便加以约束，从而减少组卷的冗余度，从而提高算法效率，对杂交、变异后的个体进行修复操作，使得生成的个体各题型对应的题量与用户的需求一定相等，因而试卷总分也符合要求，并且各个体包含的知识点在考试范围内。由于修复操作使得新个体必定满足上述约束条件，同时也提高了组卷效率。对于智能组卷的质量组卷系统应具备相应的检验模块及调优模块，检验模块主要包含对试卷结果整体的正态分析、信度分析等，从而对当次测评的合理性和平衡性进行评价；调优模块将影响到前置约束条件，是对试题个体产生调节。即对于在普适性测评中正确率严重偏离标准值时调优模块将自动调节该试题的难度影响因子[3]，从而，在以后的组卷过程中出题概率和试卷整体平衡性得以优化，更加真实的反映教学水平。

参考文献：

[1] 丁振国，郭海燕.一种基于CHC算法的自动组卷方法[J].计算机应用研究，2009，26（1）：134-136.

[2] 陈晓龙.遗传算法的多样性和收敛性[J].计算机工程与设计，2004，25（9）：1603-1605.

[3] 卢俊玮，陈杰.基于层次分析法的自动组卷评价模型的研究[J].电脑知识与技术，2014，10（19）：4457-4459.