基于LT-backfilling算法的智能题库系统的设计与实现*

张舒虹，孙宏健，夏 锋，孔祥杰

（大连理工大学 软件学院，辽宁 大连 116620）

一、引言

本系统是运用可视化程序设计和数据库进行开发的一个基于Web的智能题库系统，包括系统管理，题库管理，组卷管理和试卷管理等功能。本系统在教学实践中的优越性体现在两个方面，一是教学管理上的，试题库具有高效、经济、灵活和保密的特点；二是教学测试上的，由题库生成的试卷具有质量高、可预控等特点。

二、系统设计

本智能题库系统采用模块化的设计方法，根据系统功能来进行模块划分，保证模块内聚性高、模块之间耦合性低。本系统的用户群包括四大类，即系统管理员、教师、助教和学生。本系统将核心业务大致划分为四个主要模块，分别是题库管理、试卷管理、组卷管理和系统管理。其中，题库管理模块主要满足了在校教师对试题库中各试题的试题属性的增加、修改和删除等管理，以及题库中试题的随时上传、适时更新、及时删除和数量统计等需求；组卷管理则同时兼顾了传统的人工式手动组卷和自动的智能组卷功能；试卷管理模块主要是基于对整套试卷上传存储和已考试卷下载预览的现实需求；系统管理模块主要保证了系统管理员对整个智能题库系统的用户审核、管理和日常的系统维护工作。其结构如图1所示，本章接下来会分模块介绍智能题库系统的设计及功能，以及用户的权限设置等。

图1 系统结构图

1.系统管理

系统管理模块的功能是管理系统用户和进行系统维护，只有管理员有权使用该模块。通过系统管理模块，系统管理员可以管理系统的所有用户，维护整个系统的安全性和完整性，提供系统帮助，保证系统正常运行[1]。

2.题库管理

题库管理模块的功能是管理试题库，用户需通过已注册的邮箱和密码进行登陆。教师有权限对试卷、试题、学科、题型、章节和知识点进行管理，助教仅有部分权限。主要功能如下：

（1）试题管理

试题管理模块包括添加、删除、修改试题，查看试题分布和试题详细信息，搜索试题，管理已删除试题等功能。考虑到试题的保密性，只有教师和助教两类用户可以管理试题，并且具有不同的权限设置。

（2）试题属性管理

教师有权限对试题属性，包括学科、章节、知识点、题型等进行管理，可以进行增加、删除、浏览和修改，同时也会对试题库中所属学科、章节、知识点、题型的试题进行统计和计算，便于了解当前试题库中试题的分布情况。在进行题型添加时，可以根据题型选择相应的试题模板，题型和模板是多对一的关系，以增加试题上传的灵活性。

3.组卷中心

只有教师有权限使用该模块，组卷管理模块包含两种组卷方式：自动组卷和手动组卷。组卷系统生成的试卷若是用于期末考试，则需要避免近三年考过的试题重复被使用，所以在组卷时，需要考虑去除出近三年考过的试题。

手动组卷按题型查询试题，在试题查询和浏览过程中，教师可以按照试题的各个属性选择符合要求的试题，添加到试卷中，最后组成一份试卷。在试卷预览时，若发现组成的试卷存在某些问题，可以通过试卷调整功能删除已选试题，并重新添加符合条件的试题或者重排试题顺序，调整层次结构。这种做法效率比较低，而且也不容易控制试卷的总体难度和试卷的知识点覆盖范围。当试题库中试题数量较多时，这种缺陷更明显。所以，这种方法只适合作为经验丰富的教师进行人工组卷的辅助工具[1]。

自动组卷是一种智能化的组卷方式，可以根据用户设置的试卷要求自动的进行组卷。用户对试卷的期望将以参数的形式通过系统提供的人机交互式界面输入系统并作为组卷的依据。

4.试卷管理

只有教师有权限使用该模块，试卷管理包括两个子模块：试卷上传和试卷下载。试卷上传是对组卷模块生成的试卷进行排版和编辑后，连同试卷答案和试卷信息概览表上传到服务器进行存档。试卷下载是从服务器上下载曾经考过的试卷。

三、系统关键技术实现

本系统的关键性技术问题是教师进行自动组卷时采用的智能组卷算法，该模块研究的主要难题是如何保证自动生成的试卷既能满足用户的需要，又能保证其科学性、随机性、客观性，以及远程网络交互式环境下的实时性。因此，高效、简单通用的智能组卷算法是实现自动组卷的关键技术和研究重点。

目前常用的智能组卷算法主要有随机抽取法、回溯试探法、遗传算法[2]。遗传算法可以用于求解智能组卷问题[2]，但基本遗传算法存在容易早收敛[3-4]、进化后期搜索效率较低的缺点，故无法得到真正最优解[5]。而随机抽取法、回溯试探法算法常因约束条件的局部满足而导致整体组卷失败，或选取试题缺乏随机性，组卷过程所需时间也较长，无法满足实时性要求。基于此，本文提出了一种基于LT-backfilling算法的智能组卷算法。

首先获取用户对试卷的整体期望，用户选择试卷学科，输入试卷总分，选择试卷章节并设置对应分值，选择题型并设置对应分值（总分及每道题的分值），以及设置试卷的难度系数。在获得试卷期望后，系统会自动按照相应条件进行试题筛选。为了使每次选出的题目在满足条件的同时保证随机性，本文参考了CPU在进行系统调度时的LT-backfilling算法[6]。

LT-backfilling算法的基本思想是均衡系统的负载，按照作业的优先级对作业进行排序插入到待调度作业队列中，在节点中选取满足作业所需资源的节点分配给作业，在选取节点的时候要考虑到该节点的负载，如果该节点的负载>最大负载，则此节点此时不再分配作业，如果该节点的负载≤最小负载，则将作业分配给此节点，如果此节点的负载在最大负载与最小负载之间，则根据节点上最长作业的结束时间为依据，找出作业结束时间最早的节点，将作业派发到该节点。如果任何节点的资源都无法满足该作业的需求，则该作业的优先级将动态地增加，直到该作业增加到最高优先级。

系统中的每个作业在提交时都由用户指定一个优先级，该优先级影响着读作业的执行顺序，而作业优先级不是固定的，在作业等待执行期间优先级是动态增加的，直到增加到最高优先级。

将上述理论运用到题库选题中，把对题目的选择当作CPU为每个进程的调度。把每个作业当作题目，节点的负载当作题目的分数，作业的优先级当作题目被选择的优先级。

下面再把优先级的标准具体化：第一个优先级的影响因素是该类型（章节、题型、知识点）所占的分数，分数高的优先级高。第二个优先级的影响因素是它出现的次数。对于每一个出现过的类型，为了防止“饥饿”现象，会适当的降低它的优先级（即在它原有优先级的基础上乘一个小数0.5～0.7），为在分数上处于劣势的类型创造提前被选择的机会。第三个优先级的影响因素是它被选出，而数据库中不存在此类型，这种情况发生的次数。这种情况被视作选题失败，会对优先级造成很大影响，此时需要降低该类型的优先级，并由此重新组织对试卷的选择。

依据以上优先级的设置标准进行选题，直到按照要求选出和总分相同的试题，则选题成功。或者在经过一定次数的循环后仍无法选出满足条件的试题，则返回用户一个提示，说明由于题库的限制，根据用户设置的试卷期望无法生成符合要求的试卷，并要求用户重新设置试卷期望。该智能组卷算法的程序流程图，如图2所示。

图2 智能组卷算法的程序流程图

本系统使用的智能组卷算法每次按照特定步骤生成满足条件的题目列表，然后去数据库中进行选择，这保证了每次选出的题目都是符合要求并且最小限度地去操作数据库，在一定程度上节省了时间和系统消耗，具有成卷快、客观性好、难易度可控、能同时生成多份试卷的特点。

四、系统运行情况

在自动组卷过程中，教师用户选择试卷学科，输入试卷总分，选择试卷章节并设置对应分值，选择题型并设置对应分值（总分及每道题的分值），以及设置试卷的难度系数。通过对以上试题属性的设置，用户对试卷的期望将作为参数输入系统并作为生成试卷的依据。系统运行过程中试卷章节设置如图3所示。

根据用户设置的试卷期望，系统会自动生成一份符合需求的试卷，并在每题题末注明分值，也可同时显示试卷信息概览以了解试卷的详细信息。

五、结语

图3 试卷章节设置

智能题库系统改变了传统的人工组卷方式，减少了主观因素对试卷的影响，有利于实行教考分离，提高教学效率。这种新型考试模式的构建和投入使用，可以极大提高考试的灵活性和考试的效率、公正性以及考试的可信度，是未来实现数字教学的基础。

[1]祝建中,陈丽燕.智能题库系统的研究与实现[D].2005.

[2]王友人,张岩,施玉霞,姚睿.题库系统智能成卷理论和组卷方法研究[J].电子科技大学学报,2006,35(3):363-366.

[3]Mei Yue,Tao Hu,Baoping Guo,Xuan Guo.The research of parameters of genetic algorithm and comparison with particle swarm optimization and shuffled frog-leaping algorithm [C].Power Electronics and Intelligent Transportation System(PEITS),2009,Volume 1:77-80.

[4]Genglie Zhou,Bo Chen,Chibing Hu,Wuyang Feng.Improved Adaptive Genetic Algorithm Based on Non-ferrous Metals Warehouse Routing Problem Stacker[C].Emerging Computation and Information teChnologies for Education Advances in Intelligent and Soft Computing(ECICE),2012,Volume 146:441-448.

[5]陈晓敏,梁静,葛宇.基于改进遗传算法的智能组卷研究[J].西南师范大学学报(自然科学版),2012,37(5):98-101.

[6]张果桃,赵金雁,白中英.基于 LT-backfilling算法的集群作业调度系统[J].计算机工程,2007,33(21):69-71.