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

刘召华?李建良

摘 要：随着计算机技术的发展，利用计算机存储大量的试题信息并结合数据库技术实现试题的自动组卷功能已成为一项实际可行且应用性广泛的课题。本文就试题组卷遗传算法进行了论述和总结。

关键词：自动组卷；遗传算法；试题库

随着信息技术不断发展，传统考试方式已经不能适应现代化考试需求，设计开发和应用计算机考试管理系统成为现代教育教学改革的一项重要任务。计算机技术不断发展，并结合现有成熟的数据库技术，为计算机考试管理系统开发提供了可靠保证。考试管理系统设计中，建立一个好的试题库尤为重要，而良好的组卷方法却是核心。如何保证生成的试卷能最大程度地满足用户的不同需求，并具有随机性、科学性、合理性；尤其在交互环境下，对组卷速度要求较高，而一个在理论上能搜索到全局最优的算法可能会以牺牲时间为代价，往往达不到预期的效果。因此，选择一个高效、科学的算法是自动组卷的关键。以往具有自动组卷功能的考试系统大多采用随机选取法和回溯试探法。在限制条件状态空间的控制下，随机选取法有时能够抽取出一组令用户满意的试题，但由于它随机选取试题的范围太大，有可能在无法抽取合适试题的区域内反复选题，进入死循环，最终导致组卷失败。回溯试探法组卷成功率高，却以牺牲大量的时间为代价。遗传算法（Genetic Algorithms）以其全局寻优和智能搜索技术，及收敛性好的特性能很好地满足自动组卷的要求。

1. 遗传算法原理

遗传算法（Genetic Algorithm，GA）是模拟自然界自然选择遗传机制进行搜索寻优的方法，通过模拟生物在染色体层面的各种遗传优化作用而设计人工寻优方法，GA本质上是一个群体迭代过程，从一个随机的初始群体出发，依据优胜劣汰原则.通过竞争、选择、繁衍、变异等遗传操作，产生性能更优的下一代群体。直到满足环境约束的优良体或合乎具体的应用准则为止。遗传算法的这种特点使其很适合解决多重条件最优解的问题。

2. 组卷问题的数学模型建立

通过实际组卷分析，组卷约束条件主要有知识点，题型，章节，认知层次，题量，分值，答题时间，难度，区分度，曝光度等10个方面。根据对上述组卷约束条件的分析，可以构建组卷问题的数学模型。由于一张试卷存在10个约束变量，所以针对于整个试卷所有的题目构成了一个10维度变量的空间：知识点，题型，章节，认知层次，题量，分值，答题时间，难度，区分度，曝光度。为了减小组卷算法的复杂度，提高组卷算法的效率，需要对这个10维空间进行化简处理。一般而言，要出一份试卷，我们总是先确定试题难度、试卷的满分值和所用的题型以及各种题型的题目和分数以及知识点分布，而且对一种考试而言，这种难度分布常保持相对稳定。不同难度试题的分数分布通常成正态分布，我们可以根据难度系数、各知识点分数、各题型分数来约束将要被选中的试题个数以及试题难度分布，计算出不同难度级别的题目在试卷中所占的比例。再结合各知识点、各题型的分数在试卷中所占的比例，可将10维空间简化为一个5维的空间——试卷（知识点，章节，题型，分值，难度），在这个5维空间里对试题进行操作来完成组卷。不同的计算机系统通常采用不同的二进制文件格式。

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

遗传算法模拟达尔文的自然界遗传学：继承（基因遗传）、进化（基因突变）和优胜劣汰（优的基因大量被遗传复制，劣的基因较少被遗传复制）。其实质就是一种把自然界有机体优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。运用遗传算法求解问题，首先需将所要求解的问题表示成二进制编码，然后根据环境循环进行基本的操作：selection（选择）、crossover（交叉）、mutation（变异），最后收敛到一个最适应环境条件的个体上，得到问题的最优解。算法步骤如下：

（1）染色体的编码：假设试题库中有m道题，可用一个m位的二进制串来表示，形式为：a1，a2，a3 ，...am，，其中若ai为1，则表示该题被选中；若ai 为0，则表示该题未被选中，即ai=1，第i道题被选中；ai=0，第i道题未被选中。

（2）初始化群体：通过随机的方法生成初始化的串群体，在串群体中，串的长度是相同的，群体的大小按需要根据经验或实验给出。

（3）计算当前种群每个个体的目标函数：本问题的目标函数可定义为

F=

Fi表示第i个属性指标与用户要求的误差的绝对值，Wi表示第i个指标对组卷重要程度的权值，F是所有指标与用户要求的误差绝对值之和。该目标函数越大，则适应度越小，被淘汰的概率越大。

（4）选择：按照一定的选择概率对种群进行复制，选择较好的串生成下一代（个体的适应度函数值越大，该串的性能越好，选择概率越大），去掉较差的串。

（5）交叉：交叉是两个串按照一定的概率（交叉概率P ），从某一位开始逐位互换。首先，对每个二进制串产生一个0～1范围内的随机数；若该数小于P ，则选择该串进行交叉，否则不予选择。然后随机地对被选择的二进制串进行配对，并根据二进制串的长度 ，随机产生交叉位置i，i为[1，n-1]上的一个整数。

（6）变异：变异是二进制串的某一位按照一定的概率（突变概率Pm）发生反转，1变为0，0变为1。这里Pm 较小，Pm 可小于0.001。但在实践中发现，在有些遗传算子中，Pm为0.1时更好。

（7）终止：记录进化的代数，并判断是否满足终止条件。若满足，则输出结果，否则转向步骤3继续执行。终止条件如下：（a）出现种群满足F=0；（b）某个个体目标函数值（个体适应度值）达到指定要求；（c）达到指定的进化代数；（d）当前种群中最大目标函数值与以前各代中最大目标函数值相差不大，进化效果不显著。

遗传算法在试题组卷中的应用可以将教师从繁重的考试出卷等工作中解放出来，最大限度地减少人为因素在组卷过程中的影响，最大程度地实现了组卷的自动化，有效提高试卷的质量。我们也可以对简单遗传算法改进，利用组卷过程中的误差对遗传算法中的随机性选择进行诱导，保证产生的新个体的误差相比对于同一个体的其他信息位的变异所产生的新个体而言，产生的误差最小。理论分析与实验结果表明，基于遗传算法的试题组卷算法具有较好的智能组卷性能。

参考文献

1.王小平.《遗传算法——理论、应用与软件实现》西安交通大学出版社，2002

2.张文修，梁怡.《遗传算法的数学基础》西安交通大学出版社，2003

3.乐光学，彭小宁，曾志峰.试题库自动组卷系统的算法与实现，计算机应用，2001；21（8）：198-200

4.孙勇，柏云.基于遗传算法的试题组卷策略.淄博学院学报（自然科学版），2002；（3）：27—28

5.刘彬，李勇，糜长军.智能组卷系统中专家知识的表示与实现.计算机工程与应用，2002；38（17）：229— 231

6.王慧，刘宝坤，曹明，等.一种改进遗传算法及应用.天津理工学院学报，1998；14（4）：62—65