计算机组卷算法的分析

杜向然，吴树锦，王文清

（天津海运职业学院，天津 300350）

计算机组卷算法的分析

杜向然，吴树锦，王文清

（天津海运职业学院，天津 300350）

计算机考试系统是计算机辅助教学的重要分支之一，它是评价和改进学生学习情况和教师教课情况的重要依据之一。计算机组卷算法是考试系统中重要组成部分之一，它决定了试卷的效果。本文介绍了几种常见的组卷算法，并对这些算法进行分析。

考试系统；组卷算法；人工智能

一、引言

计算机考试系统的研究已经有很多年的历史了，它的出现极大地改进和丰富了传统考试模式。计算机考试系统的组成部分中，组卷算法是最重要的部分之一，它对试卷质量的好坏起到至关重要的作用。

二、组卷算法

计算机组卷算法可以分成两大类：传统组卷算法和智能组卷算法。传统组卷算法主要是对抽题的方法进行相应的改进和优化，智能组卷算法则依靠人工智能技术实现组卷功能。下面将介绍这二类组卷算法中常见组卷算法。

（一）传统评估函数

常见的传统组卷算法包括随机组卷法、回溯试探组卷法和误差补偿法。这三个算法是通过对随即函数的优化实现的组卷功能。

1.随机组卷法

随机组卷法是按照试题类型、试题难度和试题区分度等组卷要求，不断地从试题库中随机地选择试题。算法具体实现时，既可以先从试题数据库中随机地抽取试题，再判断是否放入试卷中，也可以先从试题数据库中挑选出满足要求的试题，形成一个新的小试题库，然后再从这个试题库中随机抽取试题。两个过程没有本质的区别，算法描述（按照先搜后判方式）如下图所示。

随机抽取法是不断地搜索数据库，以期找到满足条件的试题集。当搜索到的满足条件的试题数达到目标要求时，组卷成功，否则算法失败。

该算法的优点是易于理解、实现简单和单次抽取速度快等；其缺点是组卷效率低，时间复杂度高，不确定性高和用户满意度差等。算法的缺点在小型试题库的应用中往往表现得更加明显。如果随机法运用于题量和约束条件较大的试题库中，算法可以避免组卷重复率高和成功率低下等缺点。

考试系统试题抽取算法的早期研究中，很多专家和学者针对随机法的缺点提出了改进。比如，王萌等实现了集合随机抽选法、曾一等提出了基于状态链表的随机组卷算法和金汉均分段随机抽选法等等。随着组卷算法研究的深入，由于随机法自身的缺点阻碍了其发展，因此，目前该算法已经很少会被应用到实际应用中。

图1 算法描述

2.回溯试探组卷法

回溯试探组卷法是在随机组卷法基础上，利用深度或广度优先搜索算法改进而来的。算法实现时，选取试题的方法还是采用随机抽取的原则。如果选取的试题满足试题要求，则将其按照先后顺序放入到栈中，并标记成功状态，否则，算法会返回到上一个成功状态，并按照新的状态继续随机搜索。表1描述了回溯试探组卷法的过程。

溯试探法继承了随机法的简单和易于实现等优点，避免了随机法重复搜索试题的缺点。理论上，回溯试探法可以搜索所有的试题组合，并组合成最优试卷。实际应用中，当试题库较小时，该算法成功率较高，但当试题库较大时，算法会占用大量的内存空间，组卷时间过长，成功概率低。因此该算法更多的是应用在试题库较小，且组卷约束条件较少的小型考试系统中。

3.误差补偿法

误差补偿法是指在试题抽取失败时，适当地放宽某些约束条件，使其在允许的范围内重新搜索满足要求的试题。该算法虽然可以在一定程度上减少组卷的时间，提高组卷效率，但在实际应用时，算法容易出现死循环和组卷效果差等问题。这种情况的产生，主要是由组卷要求之间相互牵连和试题属性间相互作用造成的。

表1 回溯试探组卷法描述

综上所述，这三种组卷算法都适用于试题约束条件少、试题数据库题量小和效率要求不高的小型考试系统中。对于题量较大的考试系统而言，随机组卷法的不确定性较高，组卷成功率低；回溯试探组卷法消耗的内存空间较大，试卷生成时间过长；误差补偿法常常出现陷入到布局最优的死循环，组卷效果不理想

（二）智能组卷算法

智能组卷算法是借助人工智能技术实现组卷的方法，常见的智能组卷算法包括基于专家系统的组卷法、基于项目反应理论的的组卷法和基于遗传算法的组卷法。

1.基于专家系统的组卷算法

专家系统是人工智能研究的一个重要方向，它是通过专家数据库和智能推理机制使计算机能够模拟专家的思维方式解决相关领域问题。基于专家系统的组卷算法的的实现也需要一个专家知识库，以及模拟专家思维方式的推理机制。专家数据库要包含某个领域的大量知识，以及这些知识的层次要求和掌握程度等知识属性。数据库质量的好坏直接决定了组卷效率的高低，质量好的数据库质量可以提升组卷效率，反之则会降低组卷效率。推理机制是利用人工智能的技术模拟人类的思维方式和处理问题的方法，它是专家系统智能化的充分体现。

目前，基于专家系统的组卷算法实现的主要难点是无法建立高质量的专家数据库，这主要有两方面的原因。一方面，由于知识的复杂性比较高，部分专家们在某些知识点的要求上无法达成共识。另一方面，专家数据库的建立不能仅靠某几个专家来完成，而是需要一个强有力的权威专家组的支持。因此，该算法还处于理论阶段，实际的应用还有很长的路要走。

2.基于项目反应理论的的组卷法

传统试卷是由专业领域专家和教育专家联合完成的。这样的试卷主要反应了出题人的主观想法，而忽视了被测试人的实际情况，换句说话，试题库中的试题不一定都适合每一个测试者。考试的目的是检测被测试者的实际能力，考试试卷要根据每个测试者的实际情况调整试卷内容。为了解决这个情况，Wiiliam W.T Urn Bull教授把项目反应理论首次引入到组卷测试中的应用中，提出了基于项目反应理论的组卷算法。

基于项目反应理论的组卷算法通过一个非线性数学模型评估考生的实际能力值，并根据该值调整考生的考试内容。该组卷算法以考生的实际能力为依据，不依赖于特定的试题库和测试人群。算法描述过程如下表所示。

表2 基于项目反应理论的组卷算法

基于项目反映理论的组卷算法的优点是考试出题是以学生的实际能力为基础，而不是以教育专家的主观意识为根据的。它充分地考虑到了学生的实际情况，体现了考试的目的是检验考生的实际能力。该算法的缺点是提出的这个非线性数学模型是否能够真实地验证学生的实际水平还有待进一步验证，而且如何建立一个权威的专家试题库以及试题的相关属性也是一项比较困难的任务。

3.基于遗传算法的组卷算法

遗传算法是模拟自然界优胜劣汰和遗传基因进化的优化算法。遗传算法是由美国Michigan大学的Holland在1975年次提出，经过了40多年的研究和发展，该算法已经成功地应用到很多领域中。基于遗传算法的组卷算法是用染色体表示试卷，多个染色体表示多套试卷。每个染色体中的基因表示组成试卷的试题，每道试题在染色体中占有一个独立编码位。染色体的编码有的算法采用的是二进制编码，也有的采用的是十进制编码。二进制编码的执行速度比十进制编码快，但十进制编码方式更加简单和直观。算法在进化过程中，依据试题的相关属性和评价函数决定染色体中的试题如何进行遗传、变异和变异等操作，从而实现计算机组卷的功能。

遗传算法组卷的优点：一方面，计算机组卷不是过于依赖人类专家的经验和能力；另一方面，算法可以实现并行和大规模组卷。算法的最大缺点是执行时间过长。当试题库中的试题和试题属性较多时，算法的时间花费会呈指数增长趋势。

4.基于粒子群算法的智能组卷

粒子群算法是计算机专家从生物学家常年观察和追踪群的迁移和觅食等生活现象的基础上，提炼出来的优化算法。算法实现的过程模拟了鸟群觅食时发生的种种现象，并参考了鸟群捕食过程中，头鸟对鸟群中其他鸟的影响作用。粒子群算法与遗传算法都属于优化算法，但粒子群的优化速度高于遗传算法的速度。这主要是由于粒子群算法中每个粒子通常采用相对简单的十进制编码方式，而且算法优化时不需要经历繁琐的遗传、交叉和变异等操作，它仅仅是需要改变每个粒子的速度信息和位置信息。因此粒子群算法已经被很多专家应用到很多遗传算法的应用领域。台湾的Peng-Yeng Yin博士利用粒子群算法实现了多目标的智能组卷算法，该算法可以从大型试题库中抽取出中近似满足优化目标的试卷。实验表明，算法可以有效地提高抽卷的速度和准确率，抽出的试卷能够准确地评测出学生们的进步程度。

除了上述所述的这些智能算法以外，免疫算法、蚁群算法和分布估计算法等也都被用于到智能考试系统的组卷中。试验表明，这些算法虽然可以一定程度上起到优化组卷效率和提高组卷质量的作用，但其距离高质量和高效率的组卷还有一定的距离。

三、总结

本文详细地介绍了计算机考试系统构成中常见的组算算法，并分析了这些算法的工作原理和各自优缺点。随着教育教学改革的深入，考试系统正朝着规模化、智能化和并行化的方向发展，传统的组卷算法已经无法适应考试发展的趋势，而智能组卷算法凭借其自身的优势和特点，正逐渐地成为主力的组卷算法。目前，虽然计算机考试系统智能化的研究处于初级阶段，但其发展速度很快，随着研究的深入，大规模智能化考试系统必将应用到教育教学实践中。

[1]袁桂霞.自动组卷的建模和仿真研究[J].计算机仿真,2011，（11）.

[2]金汉均,郑世珏,吴明武.分段随机抽选法在智能组卷中的研究与应用[J].计算机应用研究,2003,（09）.

[3]朱明,王俊普.一种智能组卷方法的研究与实现[J].微小型计算机开发与应用，1997，（05）.

[4]罗毅.基于知识点-难度比例的组卷算法研究[J].武汉理工大学学报，2009，（10）.

[5]王萌,唐培和,李春贵.基于改进遗传算法的智能组卷研究[J].计算机应用与软件,2008,（02）.

[6]Kennedy. J and Eberhart. RC. Particle Swarm Optimization, In: Proceedings of the IEEE International Conference on Neural Networks. Piscataway, NJ: IEEE Service Center; 1995, （04）: 1942-1948.

[7]Peng-Yeng Yin and Kuang-Cheng Chang. A Particle Swarm Optimization Approach to Composing Serial Test Sheets for Multiple Assessment Criteria. Educational Technology & Society, 9（03）,3-15.

Analysis on Algorithm of Computerized Exam Paper Generation

DU Xiang-ran, WU Shu-jin, WANG Wen-qing

（TianjinMaritimeCollege,Tianjin, 300350）

As an important branch of the computer assisted instruction, the computerized test system provides an important basis for evaluation and improvement of students’ learning and teachers’ teaching. As an important part of the test system, the algorithm of computerized test paper generation determines the effect of the test paper. This paper introduces and analyzes several common algorithms of test paper generation.

test system; algorithm of test paper generation; artificial intelligence

2015-03-16

杜向然（1982-），男，天津人，天津海运职业学院信息工程系助教，硕士研究生，主要研究方向是人工智能与机器博弈。

TP312

A

1673-582X（2015）05-0078-04