考试系统组卷算法研究：一种启发式算法

　　摘要：在线考试已经成为一种流行的考核方式。自动组卷是在线考试系统的核心，改进组卷算法，提高组卷质量和组卷效率具有重要的现实意义。本文在建立一个多约束的数学模型基础上，提出了一种启发式算法求解组卷问题，并用仿真结果验证了该算法进行自动组卷的可行性和有效性。
　　关键词：考试系统；遗传算法；启发式算法
　　中图分类号：TP391.6 文献标识码：A 文章编号：1007-9599 （2012） 21-0000-02
　　1引言
　　在线考试已经成为一种流行的考核方式，正在逐步取代传统的纸质考试。组卷系统是在线考试系统的核心，其生成的试卷结构、内容是学员对知识掌握程度的具体体现，直接影响到考核的效果[1]。因此研究如何高效率、高质量地自动抽取试卷具有重要的现实意义。但多数网络考试系统所采用的智能组卷方案均为传统组卷算法，即随机抽题算法和回溯试探算法。由于这两种方法分别存在受约束条件少和抽题时间长的缺点[2]，对于约束条件较多和题量大的大型试题库来说，无疑会影响智能组卷的抽题质量和抽题时间。近些年，随着启发式算法的发展，有人将遗传算法用于计算机自动组卷中[3-7]，由于其具有全局寻优和收敛速度快的特点，组卷质量和效率明显提高。但是在实际应用中，遗传算法由于变异过程会产生大量的无效试题，从而影响组卷的效果。因此必须结合组卷的特点加以改进，更好地满足要求。
　　2 问题陈述
　　自动组卷是根据教师提出的各种要求由系统自动从题库中抽取题目形成试卷的过程。生产试卷的质量依赖于试题的质量和组卷的科学性。因此，在建立数学优化模型之前，首先要研究组卷原则和试题的属性指标。
　　2.1 组卷原则
　　组卷基本原则是建立优化目标的基础，即组卷的约束条件。组卷的约束条件包括硬约束和软约束。常见的硬约束包括：（1）试卷总分约束；（2）试题不能重复出现；（3）试卷必须符合指定的题型和题量。通过恰当的编码，硬约束可以自动满足。因此我们更关心软约束，业务软约束满足与否会影响试卷的质量。软约束包括：（1）组卷必须能全面反映考试大纲的广度和深度；（2）组卷必须有层次性和难度台阶，分数上要拉开距离，能测量考生的不同知识水平和智能差异。
　　2.2 试题的基本属性
　　试题的属性取决于约束条件。基于上述组卷原则建立的试题属性如下：分值、题型、难度、区分度和知识点（章节）。因此，一个5维向量就可以表征一道试题Ti （分值ti1，题型ti2，难度ti3， 区分度ti4，知识点ti5）。下面就重要属性进行说明。
　　（1）难度。试题难度值由教师事前根据经验指定。所有试题难度的平均值可以反映试卷内容的深度，试卷平均难度的计算公式为：