基于知识点的改进型遗传组卷算法的研究

吴敏宁

（榆林学院 陕西 榆林 719000）

随着计算机技术的快速发展，网络应用范围的不断扩大，教育领域与计算机技术的结合愈见紧密，无纸化在线考试系统已成为深化教学改革，推进教学创新，提高教务效率的重要平台[1]。自动组卷是无纸化在线考试系统中一个重要模块，自动组卷策略的研究也得到众多专家学者的注意。自动组卷是按照一定的组卷要求，由计算机自动从试题库中选择试题，组成符合特定总分、总时间要求和试题题型、试题数量、知识点、难度等约束条件要求的试卷。组卷问题是一个在一定约束条件下的多目标参数优化问题，采用传统的数学方法求解十分困难，自动组卷的效率和质量完全取决于试题库设计以及抽题算法的设计。由于自动组卷要求生成的试卷能最大程度地满足用户的不同需要并具有随机性、合理性，因此本项目就如何设计一个算法从试题库中既快又好地抽出一组最符合考试要求的试题进行了研究和设计。

总之，本项目将针对在线考试问题进行研究与实践，研究采用先进的开发技术，目的是设计出满足在线考试系统要求的，简单的、高效的、可行的、满足用户需求的自动组卷策略。

1 组卷系统需求分析

设计一个性能良好的组卷管理系统，明确用户需求非常重要。通过对用户传统卷面考试方式的业务流程进行调研，对用户生成试卷、组织试卷，管理试卷、输出试卷和安全问题等要求进行了详细的探讨，确定出用户目前的主要需求如下：

1）用户界面友好，使用方便。

2）组卷时，用户需要输入正确的用户名和密码进行身份验证，只有经过授权的用户才能登录组卷管理子系统进行操作。

3）组卷前，按试卷需求用户需给出考试蓝图，考试蓝图可修改。

4）组卷时，用户根据考试蓝图，设置组卷参数，组卷的各个属性指标如难度系数、区分度、知识点等可根据学生的水平来决定，用户可以确定各种题型的题目个数、难度、知识点、区分度、分值、时间等。

5）用户可以选择多种组卷方式，不同的组卷方式满足不同的要求，最终能生成满足用户需求的试卷。

6）用户通过一次参数设置，选择其中一种组卷方式，能组成多套满足用户的试卷，可供上机考试，并且要求试卷质量好，试卷知识点重复率低。

7）用户能根据设置的参数生成试卷，并能转换保存成word文档，可套入已有考试模板打印输出，供纸质考试使用。

8）能进行系统备份操作与系统恢复功能，避免由于系统崩溃导致信息丢失，需保证数据的安全性，防止试卷失密，具备有效的系统备份和恢复功能。

2 组卷系统总体设计

该组卷系统结构图如图1所示，为了保证试题质量及试题库的保密性，设置了用户登陆权限，严格控制用户登录，经过相关部门或领导审核批准后，用户可登陆题库进行组卷，通过审核方式，不仅加强了试题的保密性，还增强了教师的责任感，确保出题组卷的内容不被泄露。

组卷时，用户首先需要提供考试蓝图，考试蓝图可以添加、修改、删除、查询、审核。考试蓝图确定后用户需设置组卷参数，选择组卷方式，生成的试卷提供给上机考试，并将生成试卷存入套卷管理库，以便将来查询、分析。生成试卷有两种方法：手动组卷、自动组卷。手动组卷效率比较低，自动组卷主要取决于组卷算法，如果有好的算法支持，可以生成满足用户需求的较优试卷。

图1 组卷管理结构图Fig.1 Structure diagram of test paper and management

3 组卷系统详细设计

试题生成包括组卷参数设置和组卷策略选择。组卷方案的设置主要应用在自动组卷当中，可以预先设置好试题的组卷方案，在自动组卷的时候可以直接调用组卷方案，而不需要重新设置，用户可以对试卷方案进行新建、修改、删除、查询、浏览等操作。手动组卷是教务人员根据知识点，学生的实际情况，按照试题类型、难度系数等，在组卷向导的指导下生成试卷。用户在组卷过程中可以选择试题、浏览试题、查找试题、在试卷中添加、删除试题、生成试卷，浏览试卷、保存、删除试卷等操作。自动组卷是在自动组卷的向导下，根据考生蓝图进行参数设置，参数设置后，审查蓝图是否合理，如果合理，组卷，如果不合理，退出修改考生蓝图，用户也可以直接调用设置好的组卷方案进行自动抽取试题。在组卷过程中，用户可以对生成尚未存盘试卷进行调整（添加、删除、替换试卷中的试题），浏览、保存、删除试卷等操作。

4 基于知识点的改进型遗传组卷算法的研究

组卷算法是建立在遗传算法的基础上，结合随机数组卷算法的优点，以题型为单位筛选含有此题型的知识点，多次筛选知识点，筛选方式采用随机算法，得到的知识点更接近需求，根据筛选结果重新组合试卷目标，种群编码[2]采用分区分别编码，减少种群染色体编码长度，适应度函数充分考虑各参数对试卷质量的影响，采用分别定标和设定比重；用最佳个体保持法和适应度比例相结合的方法计算样本的选择概率[3]，交叉操作是用模拟三点交叉的方法进行两点交叉进行，为使算法尽快收敛，终止条件不单以遗传代数作为条件，增加了若干代内最优个体适应度的比较，并以比较结果作为条件[4]。

本系统自动组卷算法流程图如图2所示，主要有初始化参数、题库选题、按题型选题3大步。

图2 基于知识点的遗产算法流程图Fig.2 Flow chart of improved genetic algorithm base on the knowledge points

4.1 初始化参数

首先根据题型编码，从数据库选择考查范围中包含该题型的试题的知识点，并记录知识点总数；逐个检查并记录题型知识点分布状况的最小值，初始化题型返回信息，如题型名称等信息[5]。然后检查经过初始化参数的题型现有知识点总数，若总数与题型考查范围的知识点总数不一致，则按照划分等级相同或者相近的基本原则对知识点-难度，知识点分类进行合并[6]。

4.2 题库选题

以该科目全部题型和知识点作为查询条件，从试题库中选择试题集合。

4.3 按题型选择试题过程

主要运用遗传操作，同时结合随机数组卷算法试题选择的不确定优点，算法具体描述如下：

1） 检查题型的平均难度 Check（PJ），如果 Check（SM）为难度的最大值或最小值，则转到步骤2）；否则，转步骤3）。

2）选择该难度的所有试题，记试题总数为 M，设Q（N）表示题型要求的试题数，若M≤Q（N），转下面的步骤①；否则，转步骤②。

①选择这M道试题，然后从试题库中选择其他知识点该难度的试题，设总数 K，若 K≥Q（N）-M，则转到 a）；否则，转到 b）。

a运用随机数组卷算法选择Q（N）-M道试题。

b选择全部的K道试题，若Check（SM）为最低难度，则终止运算；否则，按难度梯度（从高到低）选择试题进行补充。原则是在保证试卷质量的前提下，优先考虑题型的考查范围内的试题。

②运用遗传算法求解。

3）设M表示当前试题总数，Q（N）表示题型要求的试题数，若 M>Q（N），则转到①；否则，转到②。

①运用遗传算法求解。

②选择这M道试题，并调整试卷指标，从试题库中选择该题型其他试题，

记录总数为K，若K

4.4 获得试卷编号

终止算法，获得试卷编号。

图中的 NZ（X）、NZ（Y）分别是过滤知识点后当前的知识点总数和预设要求的知识点总数的函数。Chech（PJ）、Chech（SM）分别是检查题型平均难度是否为最高值或者是最低值函数和检查题型现有试题数目和预设要求的试题数目的关系函数。

5 结 论

该组卷系统自动组卷策略采用的是基于知识点的遗传算法，首先按题型对知识点进行多次筛选，然后对试题难度进行判断，再按照遗产算法进行组卷，该自动组卷算法降低了试卷中知识点的重复率，提高了试卷的质量，使得无纸化考试系统的效率、可靠性、稳定性提高。

[1]李香英.高校题库建设与试卷生成系统[D].济南：山东大学，2007.

[2]刘艺.自动组卷算法的研究[J].渤海大学学报：自然科学版，2005（5）:124-128.LIU Yi.Research of automatic test paper generation algorithm[J].Journal of Bohai University： Natural Science Edition，2005（5）:124-128.

[3]潘中良，熊银根.一种基于小生境的遗传算法及其应用[J].中山大学学报：自然科学版，2001（5）:44-46，51.PANG Zhong-liang，XIONG Yin-gen.A method based on Niche Genetic Algorithm and its application[J].Journal of Sun Yat-Sen University： Natural Science Edition，2001，5:44-46，51.

[4]余红朝.基于遗传算法的组卷研究及题库系统实现[D].重庆：重庆大学，2008:32-33.

[5]陈宇，治平.发式遗传算法组卷模型研究[J].计算技术与自动化，2006（5）:39.CHEN Yu，ZHIPing.Research ofHair-style genetic algorithmtestmodel[J].ComputingTechnologyandAutomation，2006（5）:39.

[6]周敏.遗传算法的若干改进及应用[D].北京：中国科学院软件研究所，2001.