基于改进遗传算法的智能组卷系统设计

王宣策　欧阳鑫玉

摘要：针对大学课程考核及题库建设需求，设计并实现了一种基于改进遗传算法的智能组卷系统。系统采用Word文档保存试题的内容和答案;在组卷策略上采用了改进遗传算法，详细设计了组卷问题的染色体结构、适应度函数和遗传操作等，克服了传统随机组卷方法存在的局限性，科学合理地解决了智能组卷问题。通过测试后发现，本智能组卷系统可操作性强、组卷效率高，可以显著提高组卷的质量，完全能够满足课程考核的实际需求。

关键词：智能组卷;遗传算法;系统设计;题库建设

中图分类号：TP11; TP391                    文献标识码：A

文章编号：1009-3044（2020）02-0065-03

Abstract： Aiming at the needs of university course assessment and item bank construction， an intelligent test paper generating system Based on improved genetic algorithm is designed and implemented. The system uses Word document to save the contents and answers of the test questions， and adopts improved genetic algorithm to organize the test papers. The chromosome structure， fitness function and genetic operation of the test paper problem are designed in detail， which overcomes the limitations of the traditional random test paper generation method and solves the problem of intelligent test paper generation scientifically and reasonably. After testing， it is found that the intelligent test paper generating system has strong operability， high efficiency， can significantly improve the quality of test paper， and can fully meet the actual needs of curriculum assessment.

Key words： intelligent test paper generating; genetic algorithm; system design; item bank construction

1 概述

隨着信息时代的发展，计算机已成为了人们日常生活和工作不可或缺的工具，在大学教学改革过程中，也成为重要的教学辅助工具和教学管理手段。随着高校教学改革不断推进，利用计算机进行大学课程的题库系统建设得到了广泛的重视和应用，各种类型的题库及其应用系统在日常教学管理中正发挥着越来越重要的作用。

在题库系统建设过程中，如何保障生成的试卷能最好地满足教学评价目标要求，是整个系统设计的一个难点和重点问题。传统的题库系统一般采用人工或随机组卷方法，在题库规模越大越大的情况下，很难保证所形成的试卷在质量、难度、广度等方面达到满意的效果;尤其是在约束性条件越多的情况下，越难组成满意的试卷。当前比较流行的组卷方法主要有回溯组卷算法、粒子群算法和遗传算法等[1-4]。回溯组卷算法是基于随机抽取算法，粒子群算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法[5-6]，这两种算法的缺点是随机性较强;而遗传算法是一种自适应全局优化搜索算法，具有全局优化强的特点，为多目标的优化问题提供了更好的解决方法[7]。

因而，本文将以《土木工程施工》课程为例，针对课程考核目标和要求，在遗传算法的基础上，通过适当改进后形成优化组卷策略，设计并实现一个大学课程智能组卷系统。

2 需求分析

本项目的目标是开发一个通用、易用、高效的试题库管理及自动组卷系统，要求围绕如何实现科目与题型的自定义、试题的重复检测、智能组卷等关键问题进行研究和设计。

2.1 系统主界面功能需求

要求主界面简洁美观，可以按照用户的要求隐藏或者显示，可以添加四个按钮供用户快速操作，分别是“隐藏章节目录”“隐藏功能区”“隐藏答案”“隐藏考点面板”。此外，还需在主界面下方添加状态栏，显示当前打开的题库和登录的用户名。

2.2 组卷系统管理功能需求

为了满足不同课程需要，本系统要求提供章节管理、考点管理、题型管理、试卷分类、组卷设置、试卷模板管理，使用户能够自定义题库结构。各个管理模块界面左侧采用树形控件显示题库的结构信息，并提供增加、删除、上移、下移、导入、导出等功能按钮。在章节管理中，提供章节导入导出功能。

2.3 试题模块功能需求

系统应提供单题录入功能，在录入时用户需把试题的章节信息、难度、类型、分值、考察的知识点以及试题的题目、简要答案、详细答案进行录入，点击保存即可把试题录入到系统中。为了让方便客户管理试题，系统应提供批量删除、批量修改、重复检测、转移试题等功能。

2.4 组卷的需求

系统的核心是要求具有智能组卷功能。通过实际分析，本系统采用基于题目编号编码的改进遗传算法进行智能组卷。利用该功能，用户确定试卷整体架构后，系统会给出默认的组卷约束条件，用户也可以对约束条件中的试题总分、难度系数、考察的知识点进行重新设置，然后点击开始抽题，系统便可以按照设置和模板自动组成若干套试卷。

2.5 浏览需求

浏览分为三种浏览方式，分别是试题浏览、收藏夹浏览和回收站浏览。在试题浏览时，必须先选中一个章节，然后可以一次浏览该节的所有试题。在浏览收藏夹和回收站时，会先判断是否为空，如果为空则提示为空，否则则打开对应的题目。系统应提供浏览录入卷和试卷库的功能，并可以对试卷进行属性查看和试卷导出。

2.6 权限控制的需求

要求在用户设置里面，根据用户级别的不同赋予不同的系统权限，对系统进行精细化的管理，同时也能保障系统的安全性，在用户设置里面，可以对用户信息进行管理，同时可以对系统中的每一种权限进行管理。

2.7 系统设置的需求

在系统设置中，系统需提供试题难度的五级模型，用户可以自定义每一级的难度名称，并能自定义系统的标题，给用户最大的自由。此外，用户还可以自由的设置遗传算法的初始化参数，以及开机自启动等功能。

3 总体设计

根据需求分析，本智能组卷系统的设计内容主要包括如下16个方面：

1） 系统主界面的设计;

2） 新建题库;

3） 最近打开;

4） 章节管理;

5） 考点管理;

6） 题型管理;

7） 试卷分类;

8） 组卷设置;

9） 单题录入;

10） 重复检测;

11） 转移试题;

12） 批量删除和批量修改;

13） 智能组卷的设计与实现;

14） 查看试卷库和录入卷;

15） 收藏夹和回收站的实现;

16） 系统设置和用户设置。

4 基于改进遗传算法的智能组卷设计

本系统的智能组卷采用改进遗传算法来实现，具体算法流程如图1所示。

4.1 染色体编码方式设计

遗传算法首先要进行染色体的编码设计，其实就是构建属于自己的一套编码方案。在一般情况下，使用二进制编码对特征值进行抽象比较普遍，但是对于组卷系统的实际情况来说，这样的设计会导致基因序列会非常的冗余，而且在编码和解码的过程中耗费大量不必要的时间，从而导致系统的运行效率非常的低。因此，本系统在设计的时候，每道题目的命名用一个实数进行命名，并且保存到试题的属性中，这样就可以把试题的名字作为染色体的基因，然后许多的试题构成一个染色体，每一个染色体就代表一套试卷，他们建立了一种对应关系，并且把相同题型的试题编号放在染色体的相邻位置，以便于后期进行各种分段操作。

4.2 初始化种群设计

初始化种群的时候涉及种群的大小，这个参数应该在系统中有相应的设置，用户可以根据自己的需要设置为自己想要的种群大小，这个参数的大小直接影响算法最终的结果，设置一个适当的值会让结果更加的合理。另外，为了让算法尽快地收敛，在初始化种群的时候，应该让个体满足一些约束条件，本系统在初始化种群的过程中，让每个个体满足题型、题目的数量和试卷的总分这三个约束条件，这样在后期的遗传操作过程中，可以减少迭代的次数，提高系统的效率。

4.3 适应度函数设计

在遗传算法中，通常用适应度来表示个体的好坏，一个个体的适应度越高，表明它的进化过程中更加的适应环境。而适应度的计算要根据具体的适应度函数来决定，所以适应度函数是设计是决定遗传算法最终结果的关键。所谓的适应度，就是判断种群中的个体和预期想要的结果的一致性，因为在初始化的时候，已经达到了一些要求，所以在后期判断的时候主要考虑难度系数是否满足设置的要求，还要把知识点的涵盖范围作为一个参考，总的来说，就是难度系数尽量和预期的一致，知识点涵盖的范围越广越好。

通过分析，可以设计出组卷系统的适应度函數。例如用户希望得到的试卷考察[N]个知识点，但是把个体中所有题目含有的知识点放在一起，总数是有[M]个，则这套试卷的知识点分布率为[MN]。用户希望试卷的难度系数为[P]，一个个体经过计算后的难度系数为[p]，则适应度函数如下：

其中，[k1]为知识点在评价适应度中的比例系数，[k2]表示难度系数在评价适应度中的比例。当[k1=0]时表示试题难度系数占有全部的权重，不考虑知识点的影响，当[k2=0]时表示适应度只考虑知识点。

4.4 遗传算子的设计

（1） 选择算子。在遗传算法中，肯定有的个体要被淘汰，淘汰就是通过选择进行的，在这个过程中被选中则留下，否则就不能进行下一步的操作。选择算子从当前进化群体中选择适应度高的个体，交叉算子只能从选择算子选择的个体中选取个体执行交叉操作。遗传算法中有很多的选择策略，本系统采用了基本遗传算法的选择策略——轮盘赌方法，其具体设计为：通过适应度函数计算出每个个体的适应度[Fi]，种群的大小为[N]，则每个个体被保留的几率为[Fii=0NFi]。

（2） 交叉算子。由于在设计编码方案时每道题目的文件名称作为一个基因，文件名称都是一个整数，而且按照题型的不同分了几个部分，所以在进行交叉时可以在每一段选择一点交叉，这样从整体来看的话染色体就实现了在多个地方交叉。交叉的具体步骤：每两个染色体组合为一对，然后随机产生一个数[r]，交换[r]位置及之后的共两道题目，这样就得到了下一代，但是还要判断总分是否还能满足要求。交叉后可能会使新生成的子代包含题号一样的情况，此时可以将一样的题号中的一个换成没有出现过的题号，这样就可以满足要求了。

（3） 变异算子。在遗传算法中，变异概率都比较小，考虑到这种情况，本系统就不再在每一段上都进行变异，而是随意选择一个片段中的一个基因进行变异。变异的步骤如下：在染色体长度范围内产生一个随机数P，这个数就是基因将要变异的位置，然后从试题库所有题目中找一个各个属性值和[P]位置基因差不多的题目替换掉即可。

5 系统实现

本智能组卷系统以课程题库数据为基础，采用C#语言开发，开发环境是Visual Studio 2017：社区版，运行环境是Windows XP以上。

系统登陆界面如图2所示;系统主界面如图3所示;组卷成功界面如图4所示。

本系统实现了以Word形式存储的智能组卷功能，能够增加、删除、编辑课程目录和对应的题目;根据组卷设置自动生成一套试卷;方便快捷地完成目录导入和导出，还提供了重复检测的功能，能够准确定位重复的试题。

6 結束语

本文设计并实现了一个智能组卷系统。该系统提供了便捷的工具栏和信息丰富的状态栏，使操作更人性化;开发遵循了传统Windows应用的布局方式;采用Word文档保存试题的内容和答案，解决了课程题目中的图片、表格、公式等传统组卷系统很难解决的问题。在组卷策略上采用了改进遗传算法，解决了科学合理的智能组卷问题。该系统可操作性强、组卷效率高，显著提高了组卷的质量，很好地满足了用户的实际需求。

参考文献：

[1] 贺建英， 王光琼， 唐青松. 一种基于遗传算法的智能组卷策略优化研究[J]. 计算机与数字工程，2019， 47（1）：130-135.

[2] 郭竑晖. 智能组卷试题库系统的设计与开发探讨[J].时代农机， 2017， 44（10）：128.

[3] 高凌洁. 基于改进遗传算法的智能组卷系统设计[J]. 计算机与数字工程，2017， 45（10）：1910-1913.

[4] 李川，杨俊清，张少茹. 一种基于回溯试探法组卷的优化算法[J].兵工自动化，2019，38（2）：60-63.

[5] 崔星华，郭秀娟. 粒子群算法在智能组卷中的应用[J]. 吉林建筑工程学院学报， 2013，30（6）：46-48.

[6] 王菲. 基于改进粒子群算法的组卷系统[J]. 信息与电脑， 2017，（14）：55-61.

[7] 马小姝，李宇龙，严浪. 传统多目标优化方法和多目标遗传算法的比较综述[J]. 电气传动自动化， 2010，32（3）：48-50.

【通联编辑：梁书】