智能在线考试系统中遗传算法组卷的设计和实现

吴 英

WU Ying

（上海政法学院，上海 201701）

0 引言

在计算机课程的教学中，把传统笔试与计算机技术结合到一起的考试方式越来越被师生所接受。智能在线考试系统研究主要是用来实现学生上机考试。软件系统通过网络服务器的设置，学生所用的计算机作为客户端来登录服务器获得试题，答题完毕后网上提交试卷，软件系统对学生的答卷按班级学号等进行分类、整理。然后进行智能化的判卷、给分（对部分题目类型能够实现）。其中，试题库系统的开发一直是教学改革中的重要方面，对改进教学方法和提高教学质量以及实现考试的公平性起到了很大的作用。其中全自动成卷模块是试题库系统的一个亮点。

1 在线智能考试系统的设计

1.1 系统的组成模块

学生考试部分：注册，登录，验证信息，试题下载…

系统管理部分：课程管理，试题管理，学生管理，成绩管理及查询，补考管理…

数据库部分：学生基本信息，学生选课信息，课程信息，教师信息，试卷信息，各题型信息…

1.2 系统各模块设计

1）用户登录和注册：根据用户所属的不同角色显示不同的操作页面。如考生登录时，显示生成试卷等待页面；教师登录时，显示题库管理页面；系统管理员登录时，显示系统维护页面。

2）角色管理：添加角色 修改用户、删除用户、角色权限管理。

3）用户管理：添加用户、修改用户、删除用户、分配用户的角色。

4）题库管理：（1）试题类别管理，主要实现试题类别的添加、删除、修改和排序功能；（2）考试试题管理，主要实现试题的添加、删除、修改和排序功能；（3）试题答案管理，主要实现试题答案的添加、删除和修改功能。

5）在线答题：（1）动态随机生成试卷，使用遗传组卷算法动态地从题库中取得试卷的题目，每次生成的试卷是不同的；（2）显示整套试卷。

6）成绩管理：……

2 在线智能考试系统的关键技术

2.1 ASP .NET技术

ASP .NET是当今最先进的开发平台，运行在服务器端。它不仅是Active Server Page（ASP）的下一个版本，还提供了一个统一的Web开发模型，其中包括开发人员生成企业级Web应用程序所需的各种服务，利用它可建立功能更加强大的Web应用。作为Microsoft .NET平台的一部分，ASP .NET提供了划时代的新程序设计框架，是创建Web应用的首选平台。ASP .NET开发速度快，并且为开发、部署和运行Web应用提供了最快捷并且可缩放性程度最高的方式。它可选择任何一种可用的.NET编译性程序设计语言，不需要重新编译，极大地简化了部署的过程，只需要将程序复制到Web服务器即可。此外，它还提供了一些对数据库访问的数据控件，比如DataList、Dat—aGrid控件，使得对数据库操作更加灵活、方便。鉴于ASP .NET的以上优势和目前远程考试存在的问题，采用ASP .NET技术结合B/S模式，设计远程考试系统。

2.2 使用ADO .NET访问数据库的方法

系统使用SQL Server 2000作为应用程序的数据库，考虑实际需要，主要包括七个表，基本结构如下：

1）角色表：角色ID，角色名称。

2）用户表：用户ID，用户名，密码，Email，角色ID。

3）考生表：考生ID，用户，考试时间，成绩。

4）问题种类表：问题类型ID，类型名称，问题顺序号。

5）图片表：图片ID，图片标题，图片存储地址。

6）问题表：问题表ID，问题标题，问题内容，添加试题的时问，问题类型ID，问题的图片ID，难度系数，成绩。

7）问题答案表：问题ID，答案标题，答案内容，图片ID，问题ID。

系统采用类DBConnection来封装访问数据库的某些基础属性和函数，如数据库连接字符串、添加数据库的参数等。

2.3 基于遗传算法的自动组卷技术

以往智能在线考试系统大多采用随机选取法和回溯试探法。随机选取法方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低，有时能够抽取出一组令用户满意的试题。只不过由于它随机选取试题的范围太大，无法确定目前条件下哪些区域能够抽取合适的试题，反而可能在那些已经证明是无法抽取合适试题的区域内反复选题，进行大量的无效操作进入死循环，最终导致组卷失败。即使组卷成功，花费时间也令人难以忍受。回溯试探法是种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，但在实际应用时对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，对于现今越来越流行的考生网上随机即时调题的考试过程来说，它已不符合要求。

我们从试题的数量及试题库结构两个方面分析，将遗传算法应用到该系统中，努力实现试卷的生成和考查的知识点尽可能地接近、并由教师控制试卷的难度系数等。遗传算法是模拟生物界适者生存、自然选择等生物进化机制发展起来的一种高度并行、随机和自适应的搜索算法，是解决复杂问题的一个有效途径。

2.4 遗传算法的一般结构

在设计遗传算法时通常按以下步骤进行闭：1）编码方案：遗传算法求解问题．一般不是直接在问题的解空间上，而是利用解的某种编码表示。2）确定适应函数：适应值是对解的质量的一种度量。解的适应值是演化过程中进行选择的依据。3）选择策略的确定：优胜劣汰的选择机制使得适应值好的解有较高的存活概率。4）控制参数的选取：控制参数主要包括种群规模、算法执行的最大代数、执行不同的遗传操作的概率及一些辅助性的控制参数。5）算子的设计：主要有杂交、变异和再生。6）确定算法的终止准则。

2.5 基于遗传算法的组卷问题的设计

1）染色体编码

编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到GA算法的编码空间。如何将问题的解转换为编码表达的染色体是遗传算法的关键问题，即先要将问题的解空间映射成一组代码串。编码方案的选择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。常见的编码方案有二进制编码、十进制编码、实数编码等。采用二进制编码，用l表示该题被选中，O表示该题未被选中。这种编码简单明了，但进行交换等遗传操作时，各题型的题目数难以精确控制。而且，当题库中题量很大时，编码很长。我们采用实数编码，将一份试卷映射为一个染色体，组成试卷的各个试题映射为基因，基因的值直接用试题的题号表示。这样染色体的编码可表示为（G1，G2，G3，…Gn）。其中Gi（i＝l，2，…n，n为试卷的总题目数）为试题编号。比如要组成一份选择题5道、填空题5道、简答题2道的一份试卷，则染色体编码可以是：

编码时将同一题型的题目放在一起，同时为保证一份试卷中考查点不重复，每条染色体中各基因的考查点编码必须各不相同。由于不同的题型是从不同的题型表中取出，有可能在同一个基因串中会出现相同的试题编号，它们属于不同题型，考察的知识点也未必相同。故这种情况很正常的，不影响我们进行组卷。

在实际组卷过程中，假设在试卷中每种题型的数目是固定的，且相同题型的分数和答题时间是相同的。这样我们将整个编码串按照题目类型划分为不同的功能块，每个功能块可以认为是独立的编码。也就是说每个功能块对应一种特定的题型。显然按这种规则产生的群体已经满足了试卷对题型、分数和答题时间的要求。

2）群体的初始化

根据用户选定的考试内容及各种题型的题目数，按同一试卷中考查点不重复的原则，从相应题型表中随机抽取试题。生成初始群体，群体的大小按经验或实验给出由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索。因此初始的候选解群体的选择会对得到最终解的速度和质量有影响，初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。

3）适应度函数

在遗传算法中，以适应度大小来区分群体中个体的优劣。设di（i＝1，2，… ，m，m为试卷的总题目数）表示基因串中所选试题的考查点，用集合表示用户要求试卷中应包含考查点的集合，生成的试卷满足用户关于各考查点要求的程度可以用f1的大小来评价：

可见，f1的取值范围为：0≤f1≤1，f1的值越小，生成的试卷越接近于用户关于各考查点的要求。

4）遗传算子

遗传算法的交叉概率Pc和变异概率Pm是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性。Pc和Pm越大，算法产生新个体的能力就越强。个体之间的适应度波动比较大，产生新的超平面的能力比较强：Pc和Pm越小，算法使个体趋于收敛的能力越强。个体的平均适应度比较平稳，有可能产生早熟现象。所以我们采用自适应的思想，在算法的运行过程中对Pc和Pm进行调整。让它们随着个体适应度值的增加而变小，随着个体适应度值的减小而增加。由于种群中每一个功能块对应着一个题型，所以，为了保证每个题型的数目不变，交叉点的选择不能破坏功能块的完整性。假设交叉点位于第i个功能块内，则前i个功能块不变，从第i+1个功能块开始逐位交换。（交叉如果在功能块内也发生的话，可能会出现同一模块中有重复试题的情况）。普通的变异操作可能会使用户指定范围外的题目出现在染色体中，也会使各题型的题目数难以保证，采用有条件的变异算子。即每个个体的每一个基因座上的基因都按设定的变异概率Pm，在一定范围内（与该基因题型相同且考查点与本个体其他题的考查点不重复）变异。通过变异算子可以达到局部搜索的目的。

5）最优保存策略

进行了选择、交叉、变异操作后，比较新一代的最好个体与上一代的最好个体的适应度，如下降。则以上一代最好个体替换新一代的最差个体。此策略可以保证迄今为止的最优个体不会被交叉、变异等遗传运算所破坏。它是遗传算法收敛性的一个重要保证条件。

3 结束语

我院上机考试系统在实施过程中存在的问题也是显而易见的。例如：试卷的生成和考查的知识点如何尽可能地接近；交叉概率和变异概率波动度有限，导致某些个体产生早熟现象，未能满足计划中的考查点的要求等。如何改变由管理员控制试卷的难度系数，而由系统提高自适应性，最终到达根据学生在考试过程出现的错误给予相应的调整是我们需要进一步研究的。

[1]尹红卫,等.一种改进的遗传算法及其在组卷系统中的应用[J].现代计算机,2006,05.

[2]陈蕾,等.基于遗传算法的自动组卷系统的技术实现[J].成都航空职业技术学院学报,2007,03.

[3]张爱文.自适应遗传算法用于自动组卷中的数学模型设计[J].哈尔滨理工大学学报,2006,05.

[4]白云飞.基于自适应遗传算法的智能组卷的研究[J].河北工业科技,2006,04.