基于遗传算法的信息技术类课程自动组卷应用研究

江军强

(泉州经贸职业技术学院 信息技术系，福建 泉州，362000)

0 引言

高职学院信息技术类课程的考试普遍处于人工考试的初级阶段，对于理论考试采用传统的纸质考试，对于上机考试则采用教师手动发卷、收卷、评卷的人工考试，考试效率低、考试工作量大、考试成本高。因此开发一个面向高职学院信息技术类课程的考试系统，以适用、够用、好用为目标，实现无纸化考试，降低考试的成本，提高考试的效率，非常具有现实意义。组卷问题是考试系统的关键问题，组卷质量的优劣关系着考试系统建设的成败。

组卷问题实质上是一个多目标优化求解问题，且满足条件的最优解不是唯一的[1-2]。如何保证组成的试卷最大程度地满足组卷的要求，并具有随机性、科学性、合理性是实现中的一个难点[3]。传统的数学分析方法难以直接应用于求解复杂的组卷问题。遗传算法是一种有效地求解多目标优化问题的算法，同其它优化算法相比，遗传算法在收敛和寻优方面非常有效，能有效地求解计算量大的问题，适合于求解复杂的组卷问题，本文采用遗传算法求解组卷问题[4]。由于遗传算法自身存在的不足之处，在有些情况下不能搜索到全局最优解[5]。本文通过改进标准遗传算法提高组卷效果，使组成的试卷能最大程度地满足组卷的要求。

1 遗传算法组卷研究

1.1 遗传算法简介

遗传算法是一种模拟自然界遗传进化机制形成的过程搜索多目标优化求解算法[6]。遗传算法求解问题是从多个可行解开始，按照自然界生物进化过程中优胜劣汰的竞争机制和交叉变异的遗传机制，对群体中的个体进行遗传操作，使得群体中的个体一代一代得以优化，最终得到问题的最优解。1975年美国密切根大学的Holland教授在其著作中第一次明确提出遗传算法的概念，并系统阐述了遗传算法的理论和方法。八十年代Goldberg在遗传算法研究中起着继往开来的作用，Goldberg在他的博士论文中第一次把遗传算法应用于实际的工程系统，从此遗传算法的理论研究更为深入、应用研究更为广泛。我国有关遗传算法的研究，从二十世纪九十年代以来，经过几十年的发展，遗传算法的应用在许多领域取得了令人瞩目的成果[7-8]，并且在算法的改进和理论研究方面也作出了成功的探索[9-11]。

1.2 组卷数学模型

计算机自动组卷是根据组卷的要求，计算机自动从试题库中抽取试题组成一份符合要求的试卷。组卷的目的是使组成的试卷尽可能满足组卷的要求。组卷要求是教师在组卷时对试卷质量提出的多方面要求，比如说试卷的题型、难度、认知等内容，因此组卷要求表示为试题的属性。根据信息技术类课程的组卷要求，试题属性定义为以下内容：

1) 题型：试题的题目类型包括了选择题、填空题、问答题和操作题四种。已知题型的分值和题型所占的分数可确定题型所包含的题目的数量。

2) 难度：试卷难度是试卷的一个重要指标，试卷难度是由试题难度决定的，试题难度是试题的一个重要属性。试题难度包括了易、较易、中、较难、难五种类型。

3) 认知：试题认知是试题在教学内容的要求层次，试题认知包括了解、理解、掌握和运用五种类型。

4) 知识点：试题知识点一般根据教学内容来分，如不好确定，可按章节来分，本文的知识点以章节来划分。

一份试卷由多道试题组成，每一道试题包含了多个试题属性。假设一份试卷由n道试题组成，试题的属性有6项：题号、题分、题型、难度、认知和章节，应用矩阵理论的方法一份试卷可用一个n×6的矩阵M来表示：

M是组卷问题求解的目标状态矩阵，矩阵的行表示试题，矩阵的列表示试题属性。求解组卷问题是使矩阵M最大程度地满足题型分值分布、难度分值分布、认知分值分布和章节分值分布等组卷的约束条件。

1.3 改进遗传算法

本文根据组卷问题的特点通过改进标准遗传算法求解组卷问题。在分析标准遗传算法基本原理和关键技术的基础上，针对组卷问题对标准遗传算法的编码方法、适应度函数、遗传算子和组卷策略等方面进行了设计和改进。

1.3.1 编码方法

标准遗传算法采用二进制编码，二进制编码对连续函数的优化存在映射误差，不能直接反映所求问题的特定知识[13]。改进遗传算法编码方法采用分段实数编码，一份试卷映射为一个染色体，试卷的试题映射为基因，基因由每道题的题号直接表示，并且同类型的试题放在同一个区间，按题型分段，如图1所示。分段实数编码直接对解进行遗传操作，减少了解码的过程，因而提高了算法的效率。

图1 试卷个体分段实数编码示意图

1.3.2 适应度函数

标准遗传算法对适应度函数的取值范围只要求非负，函数的取值范围不加限制，可能会影响算法的收敛。改进遗传算法采用指数比例变换方法将目标函数转换为适应度函数。适应度函数具体形式如下：F=e-α(100-f)，α取值为-0.03，f为组卷的目标函数。使用该适应度函数，对于初始组成的试卷，试卷的分值分布与组卷要求的分值分布差别较大，f值较大，F值则较小，F>0；随着试卷的优化处理，试卷的分值分布与组卷要求的分值分布差别逐渐减小，f值逐渐减小，而F值逐渐增大；当组成的试卷完全符合组卷的要求，f值为0，F值取最大值，Fmax=e3≈20。采用指数比例变换方法的适应度函数符合适应度函数的设计要求，能较好地衡量试卷个体的优劣程度，适合遗传算法的组卷应用。

1.3.3 遗传算子

标准遗传算法的遗传算子包括选择算子、交叉算子和变异算子。改进遗传算法根据组卷问题的特点设计遗传算子，选择算子采用锦标赛选择算子，交叉算子采用均匀交叉算子，变异算子采用均匀变异算子。选择算子是实现遗传算法优胜劣汰的关键算子，通过选择算子，使得适应度值高的试卷个体优先选择，而适应度值较小的试卷个体容易被淘汰。标准遗传算法采用的选择算子是轮盘赌选择算子，由于轮盘赌选择算子是基于概率选择，存在统计误差，无法保证算法的收敛性。因此本文采用锦标赛选择算子，每次从m个个体中选择适应度值最高的个体加入下一代，得到适应度值较大的下一代试卷群体。锦标赛选择算子具体操作如下：在当前群体随机选取m个个体，比较m个个体适应度值大小，选择适应度值最高的个体进入下一代，将上述过程重复n次(n为种群规模)，即可得到下一代群体[14]。交叉算子在遗传算法中起着重要作用，是产生新个体的主要方法，决定了遗传算法的全局搜索能力。本文采用均匀交叉算子，两个相互配对的个体的每一位基因都以相同的概率进行交换，从而产生两个新的个体。均匀交叉算子具体操作如下：在新一代试卷群体中随机选取两个相互配对的试卷个体，从基因位置1开始按照交叉概率对每一位试题基因进行交换，随机产生一个概率值，判断该概率值是否大于交叉概率，大于交叉概率则取消本试题基因位置的交叉操作，小于交叉概率先判断试题基因交换后是否会出现题目重复的问题，是则取消本试题基因位置的交叉操作，否则对本试题基因位置进行交叉操作。变异算子是产生新个体的辅助方法，决定了遗传算法的局部搜索能力。变异算子维持了种群的多样性，避免出现早熟问题。本文采用均匀变异算子，对变异个体的每一位基因都以相同的概率进行变异，从而产生新的个体。均匀变异算子具体操作如下：对新一代试卷群体的每一个试卷个体，从试题基因位置1开始按照变异概率对每一位试题基因进行变异，随机产生一个概率值，判断该概率值是否大于变异概率，大于变异概率则取消本试题基因位置的变异操作，小于变异概率则根据该试题基因的题型从试题库中随机选取一道相同题型的题目，判断该题目是否会与原试卷个体已有的题目重复，如重复再重新选择一道相同题型的题目进行判断，如没有重复则进行变异操作。

1.3.4 组卷策略

组卷策略是组卷算法为提高遗传算法性能达到较好组卷效果采用的策略。本文采用的组卷策略包括了初始群体满足一定的约束条件、最优个体保存策略和迭代终止条件。初始群体满足一定的约束条件是指初始试卷群体不是随机产生的，而是根据题型分值分布随机产生，使得初始试卷群体满足题型分值分布的约束条件，这样做加快了遗传算法的收敛并减少了迭代次数。最优个体保存策略是指当前试卷群体不是直接进入下一代，而是比较当前试卷群体最优个体的适应度值和上一代试卷群体的最优个体的适应度值，如当前试卷群体的最优个体的适应度值下降，则用上一代试卷群体的最优试卷个体替代新一代试卷群体的最差试卷个体。最优个体保持策略保证了最优试卷不会被遗传操作所破坏，最优个体保持策略是保证遗传算法收敛的一个重要条件。迭代终止条件是遗传算法迭代处理的终止条件。本文采用的迭代处理终止条件有两个，一个是依据终止适应度值，当新一代试卷群体的最优试卷的适应度值达到了终止适应度值则终止算法，另一个是依据最大终止次数，当遗传算法迭代处理的最优试卷的适应度值一直达不到终止适应度值，为避免遗传算法的组卷时间过长，当试卷群体进化中连续若干代最优个体适应度值停滞不变所持续的代数超过了最大终止次数，则终止算法。

2 实验结果分析

遗传算法的组卷参数包括了群体规模、交叉概率和变异概率。组卷参数对遗传算法的组卷性能影响很大，组卷参数选择应具体问题具体分析，根据组卷的实验结果选择合适的组卷参数。本文在大量组卷实验的基础上分析组卷实验结果选择适合于本系统的组卷参数。

2.1 实验数据说明

本文以大学计算机应用基础课程为例，建立课程的试题库，应用组卷算法进行组卷实验，根据实验结果选择组卷参数。组卷要求是组卷的约束条件，假定试卷总分为100分，组卷要求如表1所示。组卷要求分为四种：题型分值分布要求、难度分值分布要求、认知分值分布要求和章节分值分布要求。给定各类题型的分值，根据题型分值分布可确定各种题型的题量，初始试卷满足题型分值分布的约束条件。

表1 组卷要求表

2.2 实验结果分析

根据文献15的实验结论，初始组卷参数种群规模设为40，交叉概率设为0.6，变异概率设为0.01，以此开始组卷实验，依次选择组卷参数。首先选择种群规模，依次设定种群规模为40、60、120、200、400进行组卷实验，同一组卷参数进行三次组卷实验，测试三次组卷实验的平均组卷时间和最大适应度值的平均值，实验结果如图2所示。

由图2可知，种群规模选择为400时，组卷的适应度值有明显的增大，而组卷时间影响不大。接下来选择交叉概率，依次设定交叉概率为0.25、0.45、0.6、0.85进行组卷实验，同一组卷参数进行三次组卷实验，测试三次组卷实验的平均组卷时间和最大适应度值的平均值，实验结果如图3所示。

图2种群规模选择组卷实验柱形图

图3交叉概率选择组卷实验柱形图

由图3可知，交叉概率选择为0.6时，组卷的适应度值有明显的增大，而组卷时间影响不大。再选择变异概率，依次设定变异概率为0.005、0.01、0.1、0.15、0.2、0.5进行组卷实验，，同一组卷参数进行三次组卷实验，测试三次组卷实验的平均组卷时间和最大适应度值的平均值，实验结果如图4所示。

由图4可知，交叉概率选择为0.1时，组卷的适应度值有明显的增大，而组卷时间影响不大。根据实验结果，组卷参数选择如下：种群规模为400，交叉概率为0.6，变异概率为0.1。设置该组卷参数，本组卷算法达到了较好的组卷效果，平均组卷时间11秒可组成一份符合组卷要求的试卷。

图4 变异概率选择组卷实验柱形图

3 结束语

本文研究了遗传算法在组卷中的应用。组卷问题是求解符合组卷要求试卷的问题，组卷问题实质上是一个多目标优化求解问题。遗传算法提供了一种求解复杂系统优化问题的通用框架，能有效地解决计算量大的问题，适合处理复杂组卷问题，因此本文采用遗传算法求解组卷问题。本文应用矩阵理论的方法建立组卷的数学模型，用矩阵表示试卷，矩阵的行表示试题，矩阵的列表示试题的属性。矩阵是组卷问题求解的目标状态矩阵，矩阵应满足组卷的约束条件。标准遗传算法不能直接应用于求解组卷问题。本文在分析标准遗传算法基本原理和关键技术的基础上针对组卷问题应用对标准遗传算法的编码方法、适应度函数、遗传算子和组卷策略等方面进行了设计和改进。遗传算法组卷参数对遗传算法的组卷性能影响很大，组卷参数选择应具体问题具体分析，根据组卷实验结果选择合适的组卷参数。以大学计算机应用基础课程为例，建立课程的试题库，应用组卷算法进行组卷实验，在大量组卷实验的基础上分析组卷实验结果选择合适的组卷参数。实验表明，选择组卷参数提高了遗传算法的组卷效果。本文组卷算法在今后的工作中还要进一步改进，提高组卷算法的性能，使得组卷算法能比较稳定地在较短的时间内完成组卷。该算法仅考虑了题型、难度、章节、认知等组卷约束条件，在今后的工作中还要进一步完善组卷的约束条件，使得组卷算法适应性更好、使用起来更灵活。

[参考文献]

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

[2] 路平,王敏娟,万昆.试题库自动组卷策略研究[J].电脑开发与应用,2001(2):10-12.

[3] 赖松兆.在线考试系统关键技术的研究与实践[J].闽西职业技术学院学报,2009,11(3):117-121.

[4] 何蓉、李支尧、刘翠英.试题库智能组卷算法研究[J].福建电脑,2009,11:10-11.

[5] 贾兆红,倪志伟.改进型遗传算法及其在数据挖掘中的应用[J].计算机应用,2002,22(9):31-33.

[6] 葛继科,邱玉辉,吴春明,蒲国林.遗传算法研究综述[J].计算机应用研究,2008,25(10):2911-2915.

[7] 陈刚,万自明,胡莹等.基于遗传算法的RLV再入轨迹优化设计[J].系统工程与电子技术,2006,28(8):1240-1243.

[8] 阳春华,杨旭坤,王雅琳等.一种用于氧化铝生料浆优化调配的改进遗传算法[J].中南大学学报：自然科学版,2006,37(4):775-779.

[9] LI Mei-yi, CAIZi-xing, SUN Guo-rong. An Adaptive Genetic Algorithm with Diversity-guided Mutation arid its Global Convergence Property. Journal of Central South University of Techology,2004,11(3):323-327.

[10] 陈一虎,刘淳安.基于实数编码的遗传算法收敛性研究[J].西南民族大学学报：自然科学版,2006,32(4):666-668.

[11] 苏小红,杨博,王亚东.基于进化稳定策略的遗传算法[J].软件学报,2003,14(11):1863-1568.

[12] 王小平.遗传算法-理论,应用与软件实现[M].西安:西安交通大学出版社,2002.

[13] ZOU Xiao-bing, CAI Zi-xing, SUN Guo-rong. Non-smooth Environment Modeling and Global Path Planning for Mobile Robots. Journal Central South University of Technology[J].2003,10(3): 248-254.

[14] 李会民,张仁津,马桂英.基于遗传算法的交规考试自动组卷方法研究[J].计算机工程与设计,2009,30(18):4333-4335.

[15] 卢莉.基于遗传算法的在线考试自动组卷方法研究[J].计算机时代,2009(3):67-69.