摘要：本文基于改进的遗传算法，通过相似个体淘汰和新个体补充扩大试题解的范围，稳定可能解的多样性，在此基础上建立了包含试卷知识点、难度系数、区分度等特征的智能组卷模型，在保证自动组卷精度的同时，提高了系统运算效率。
关键词：信息化；自动组卷；计算机辅助教学
考试作为衡量教学效果的一种有效手段，要求试卷内容能够真实、恰当地反映学生的水平。但如何才能对学生进行合理考核，一直是众多教师在思考与追求的目标。传统人工出卷方式存在很多不足，很难适应现代教学的要求。随着教学现代化步伐的加速和计算机辅助教学的广泛开展，智能计算机辅助教学系统的研究已经成为教育工作者和科研人员广泛关注的研究领域。而试题库技术和计算机辅助教学的发展，对计算机组卷系统的要求也越来越高。计算机组卷系统利用计算机完成试卷内容编制，可有效改变传统教师出卷方式中质量不稳定、范围狭窄、时间浪费等不足。智能组卷算法是实现试题库系统、考试试卷自动生成、远程在线测试的基础。但现有的智能组卷系统存在诸多问题，如试题库题量要求较高、题型分布复杂、组卷算法设计实时性差、误差大等。
如何保证试题库中自动组卷满足用户实际需要，是试题库组卷系统研究者长期追求的目标，其很大程度取决于组卷算法设计的优劣。而从题库中抽出一组最优解或近似最优解，涉及智能优化算法的全局最优解和收敛速度问题，其在一定程度上而言是一对矛盾的问题。当前常见的组卷算法主要包括：随机选取法、回溯试探法、遗传算法、蚁群算法等。其中随机选取法基本思想是根据状态空间的指标，由计算机随机抽取试题放入试题库，重复上述随机抽题过程直到组卷完毕，或题库中没有满足控制条件的试题为止。回溯试探法是记录随机选取法获得的试题状态，失败时则释放上次记录状态，再依据某种规律变换新的状态类型进行试探。遗传算法作为一种并行、能够有效优化的算法，以基因理论及间断平衡理论为依据，同时融合边缘物种形成理论和系统理论的一些思想，模拟达尔文的自然界遗传学，是当前较获认同的方法。蚁群算法作为新型的自然寻迹方式，根据单蚂蚁具有有限感知能力，并可进行简单推理，最终蚁群体现出智慧性和自适应性。
● 智能组卷系统设计
智能组卷是综合运用人工智能技术，基于已有的包含大量试题的题库，实现满足包括题型、题量、知识点分布、难度系数等约束条件的试题自动选取的系统，因此需要有合理的知识库、知识推理方法和模型的支持。除考虑用户需求特点之外，组卷时间、题目类型、知识点覆盖、平均分和及格率等需要综合考虑。因此智能组卷可看作典型约束满足问题的求解过程，命题者需事先约定考试内容、难度等级、题型和要求等，计算机自动合理地生成一份符合教学要求的试卷，使试题内容在各篇章分布上均匀合理，避免出现重题。
计算机自动组卷过程对应为在较大题量的试题库中搜索一个子集，使得该子集符合组卷目标要求。因此组卷中决定一道试题，就要取决于各项指标，包括题号、题型、题分、难度、教学要求等，本文考虑6维向量（d1,d2,d3,d4,d5,d6），其中di为第i项指标。一份试卷对应为一个m×6的矩阵，m是试卷题目数目。系统中，相关实体属性如下。
题号：标识题目的唯一数据；题型：各类题型的代号；题分：试题分数；难度系数：试题难易程度；教学要求：试题属于识记、理解、应用、综合之一的代号；估时：试题所需时间。
组卷系统数学模型所对应的矩阵D的行对应为试题的题号、章节、难度、题型等属性指标，采用常用的十进制编码方式表示，而矩阵列对应题库中该指标所有试题的取值，对应为：
组卷系统自动组卷可视为：对试题库中的试题，通过一定规则选取m道试题，且应满足如下约束：
（1）卷面总分=，由用户事先确定试卷分数要求，一般为100；
（2）试卷难度=，由用户给定，试卷难度约束由用户事先给定；
（3）答题总时间=，由用户给定，即试卷总时间约束；
（4）试卷教学要求的约束：
教学要求k取值为识记、理解、综合、应用等具体要求，所占分数由用户事先给定。这4个教学要求在组卷过程中需要满足输入难度下系统默认的教学要求的约束，其每个教学要求分值尽量与系统默认的相匹配。
自动组卷作为典型的多目标优化问题，需同时考虑k个目标，且要求目标函数在满足约束条件下值越小越好。常用的方法是将多个目标整合成单目标函数进行最优化求解。针对本文研究自动组卷问题，对应函数可设计为：
其中，wi为第i个因素的权重系数，对应为第个组卷因数的重要性；ei对应为第i格因素对应的误差；f越小，选出的试卷就越满足用户的要求。
● 基于改进遗传算法的组卷实现
1.编码改进
组卷系统中，每种题型数目一般都事先固定下来，且相同题型分数和答题时间一样，如选择题假定其分数均为2分，答题时间限制为1分钟。这样对所有的题目选取中，设选取的题目用“1”表示，而未选取的题目用“0”表示，因此整个试题库可以看成一个二进制数字串，并且，按照题型将整个二进制串分为不同题型的功能块，如填空题功能块、选择题功能块、判断题功能块、计算题功能块、解答题功能块、程序阅读功能块以及程序编写功能块等。
2.交叉运算
根据编码原则，初始种群各功能块对应某个题型，为保证题型数目不变，交叉点选择时仅限于从下一个功能块发挥作用，即当选择的交叉点在当前的第i个功能块内，则从第i+1个功能块开始逐位进行交换。
3.变异运算
功能块“1”的数目对应该题型试题数目，在变异过程中应保证整个种群所有功能块中“1”的数量恒定。执行如下过程：首先，对每一个题型功能块，由变异概率决定某位取反；然后，查看该位值为0还是1，如果为0，则在该题型段所有的1中随机选取一个设为0，并且将变异的位置设为1；如果为1，则在该题型段所有的0中随机选取一个设为1，并且将变异的位置设为0。将个体中被选中的试题的题号与未被选中的试题的题号分别存入两个数组中，这样在随机选取进行变异操作时更加方便。
4.选择运算
为保证好的字符串不流失，选择操作采用选取最优的解进行下一代的繁殖，将性能最好的一半对应的试题留下来，通过适应度排序，取整个种群中适应度排位在前一半的试题，再进行复制，以代替被淘汰的个体。
5.控制参数调整
遗传算法中交叉概率Pc和变异概率Pm对算法性能有重要影响，交叉概率和变异概率取值过大则优化算法退化到无任何遗传引导的随机搜索算法；而若对应的取值太小则会延长搜索过程，限制个体生成控件并导致算法早熟陷入局部最优。我们采用如下公式进行自适应调整：
其中，Pc对应交叉概率，Pm对应变异概率，fmax是种群的最大适应值， favg为种群的平均适应值，f是变异个体的适应值。
6.最优个体保存策略
为保存好的题解，每次遗传操作前记录本次迭代过程的最优解和次优解，若其优于全局最优解和全局次优解则用其替换全局最优解及次优解。每次遗传操作后，用全局最优解和全局次优解替换本代中的最差解和次差解。进行选择、交叉、变异操作后，比较新一代最好个体与上一代最好个体适应度值，若性能下降则用上一代最好解和次好解替换当前代的最差和次差个体。
● 仿真实验及分析
设计一个包含500道题目的试题库，包括选择题、填空题、判断题、简答题和编程题5种题型，各100道，将试题库中题目以题号方式映射至数组中，要求生成一份总分为100，总时间为100分钟，难度系数由用户输入的试卷。试验中设交叉概率Pc=0.7，变异概率Pm=0.1，迭代次数为200，初始种群为100。输入试卷难度系数为65.76，采用本文方案进行试题库的自动组卷结果得到的试题总体难度系数为65.44，和预设较好地吻合，系统组卷运行时间小于2秒，在保证整个试卷满足分数约束的前提下，适当允许部分难度系数的误差，可大幅减少组卷时间。
参考文献：
[1]张琦,郑河荣,刘志,陈云泽.基于优化遗传算法的智能组卷系统研究[J].浙江工业大学学报,2009,37(3):307-311.
[2]周红晓.遗传算法在试题库智能组卷中的应用[J].浙江师范大学学报,2003(4):374-377.
[3]罗毅.基于知识点-难度比例的组卷算法研究[J].武汉理工大学学报,2009,31(10):154-156.
[4]关淞云,刘大有,金第等.基于局部搜索的遗传算法求解自动组卷问题[J].吉林大学学报，2009,47(5):961-968.
基金项目：南京邮电大学教学改革研究基金(JG00409JX40、JG00410JX12)，南京邮电大学教育规划课题(GJS-XKT0914)
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文