基于遗传算法的网络考试系统的开发与应用

摘要：随着教育事业和网络技术的蓬勃发展，越来越多的课程选择在线进行练习或测试，因此如何设计和开发在线测试系统受到越来越多的人的关注。常用的组卷方法有许多种，本课题中主要研究基于遗传算法的组卷方法，实现组卷、测试、评分、试题管理、试卷成绩管理等功能，开发一套完整的网络考试系统。

关键词：在线测试；组卷策略；遗传算法

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)29-7217-02

Genetic Algorithm Based on the Network Test System Development and Application

GUO Shu-hua

(Guangsha College of Applied Construction Technology, Dongyang 322100, China)

Abstract: Along with the vigorous development of education and network technology, more and more courses are chosen online practice and test, so how to design and develop the online test system is paid more and more attention to. There are many commonly used test paper methods, but this paper mainly studies the test paper method based on genetic algorithm method. The purpose of this article is to realize the functions of testing paper, testing, scoring, test managing, test paper grade managing and other functions, and develop a complete set of network examination system.

Key words: online testing system; maneuvers of composing examination papers; genetic algorithm

如今，计算机技术和互联网技术的发展日新月异，它们越来越多地渗透到社会各个领域，对当代社会产生着重大影响。随着计算机等现代科学技术被越来越广泛地应用以及应用水平的不断提高，必将大大改变我们的工作方式、学习方式和生活方式。教育如何迎接现代科学技术，如何应用科学技术，以提高教学质量，培养高素质人才，已引起人们的普遍关注。近年来，我国的开放教育和网络教育正蓬勃发展，越来越多的课程选择在线进行练习或测试，因此如何设计和开发在线测试系统也受到越来越多的人的关注。

在线测试系统作为网络教育系统的一个重要组成部分，作为它的一个子系统，是体现网络教学质量的重要手段，也是实现网络教育的关键环节。而在线考试系统中最重要的一个组成部分就是系统的组卷算法了。随着信息技术和数据库技术的高速发展，利用计算机存储大量的试题信息并结合数据库技术实现试题的自动组卷功能已成为一项非常实际可行并且应用性极其广泛的课题。国外和国内的许多科研单位、学校机构等都在对组卷系统进行研究[1]。

本课题主要的研究遗传算法的思想，并开发一套基于遗传算法组卷的在线考试系统。系统通过遗传算法对题库进行编码初始化，并通过选择、交叉、变异的迭代过程进行组卷，同时实现学生测试，教师评分、成绩查询、试卷管理等功能。

1 算法分析

对于组卷系统来讲，生成符合系统要求的一套试卷是组卷系统中一项最根本的功能要求，而运用什么样的算法来实现抽题组卷对这个组卷系统的性能和质量来讲是关键。自动组卷不但能最有效地把客户的需求与计算机技术结合在一起，生成符合要求的试卷，且比较客观、规范，使用起来也最为方便[1]。 目前，自动组卷系统根据其所使用的组卷策略大致可以分为四类[2]：

1) 随机抽取法；2) 回溯试探法；3) 遗传算法；4) 定性映射算法。

随机抽取法根据状态空间的控制指标，由计算机随机抽取试题组成试卷。该方法实现最为简单，不需要很高的技术支持，但具有很大的随意性和不确定性，使生成的试卷缺少整体性和科学性，组卷的效率也比较低。回溯试探法记录随机产生的每一状态类型，如果搜索失败则将上次记录的状态类型进行释放,然后采用特定的规律运用新的一种状态类型进行回溯试探，直到试卷生成成功或退回到起点为止。回溯试探法不适合大型的题库系统，通常适用于题型和题量都比较小的考试系统。该算法程序实现相对比较复杂，出题的随机性比较差，试卷生成时间也比较长。定性映射算法提出了一种合理分配不同难度试题的方法[2]。这种算法首先要建立一个组卷的数学模型，同时采用多目标优化为选题依据。这种组卷算法在生成试卷的效率和成功率上有比较大的提高，是实现自动组卷的一种新途径。但是要求建立数学模型，对数学的基础要求比较高，同时程序结构比较复杂，算法实现比较困难。

遗传算法（Genetic Algorithm，GA）是Michigan大学的John Holland在20世纪60年代末期到70年代初期借鉴生物界的进化规律而提出来的随机化搜索方法，主要模拟生物进化论的自然选择和遗传学机理搜索出最优解的方法，遗传算法主要的特点有并行性、通用性、自适应性、全局优化性和收敛速度快等[3]。依据遗传算法的这些特点，将其应用到考试系统的进行自动组卷，组卷效率和质量有大幅度的提高。

2 遗传算法研究

2.1 遗传算法概述

遗传算法是是近几年发展起来的一种崭新的借鉴生物界自然选择和自然遗传机制的全局优化算法，它借用了生物遗传学的观点，是基于群体进化的一种方法，通过自然选择、遗传、变异等作用机制，来提高各个个体的适应度。其思想是从一组随机产生的初代种群中开始搜索，按照适者生存以及优胜劣汰的原理，根据问题域中个体的适应度挑选个体，并运用遗传算子进行组合交叉、变异，产生出符合要求的种群或者达到预先设定的迭代次数为止。

遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域[3]，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，如函数优化，组合优化。此外，也在生产调度问题、自动控制、图像处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。遗传算法作为一种有效的强大的随机搜索方法，有着重要的理论和实际价值。遗传算法组卷流程图如图1所示。

2.2 约束条件

本系统中，编码方式采用标准的二进制编码，二进制位串的长度为题库的题目数，染色体上的每一个基因代表对应的试题是否被挑选：1为该试题被挑选，0为该试题没有被挑选，那么每一个染色体代表一组选题结果。同时在编码的过程中将基因按题型有序排序。在初始化编码时，通过随机函数产生相应数目的界于1和题目数之间的不同随机数，再将序号和随机数相符的基因设置为1，以实现初始编码。

算法的适应度函数主要通过章节比例约束、难度比例约束、区分度比例约束、时间约束四个约束来实现。

1）章节比例约束的计算公式为：f1= （i为章数，z为应选题目数，Z为总题数）。

2）难度比例的约束公式为：f2= （i为题型数，j为题目数，n为题目难度，N为试卷总难度）。

3）区分度比例约束公式为：f3= （i为题型数，j为题目数，q为题目区分度，Q为试卷总区分度）。

4）时间约束公式为：f4= （i为题型数，j为题目数，s为题目参考时间，S为试卷总时间）。

最后得出目标函数为：f=w1f1+w2f2+w3f3+w4f4（1≤wi≤10）。

2.3 算法实现

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。本系统的选择算子运用的是基于排序的选择方法，将群体中的个体按照计算出的适应度排序，并按序分配各自的选择概率[4]。

算法中交叉算子采用单点交叉算子[4]。所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。单点交叉的实现方法是在基因串中随机设定一个交叉点并互换该点的前后两个个体的部分结构，生成两个新串。随机交叉占用时间比较多，当题库较大时，组卷时间可能偏长。

算法的变异算子采用的是基本位变异算子。所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索[5]。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。本算法中设定Pm为0.1。

3 系统实现

3.1 模块划分

根据课题研究分析后，对网络考试系统的模块划分如图2。

3.2 功能概述

学生访问考试平台，需要通过登录界面，学生进入考试平台后默认的是浏览历史考试记录，查询历史考试的答题及成绩信息。

教师以教师身份登录考试平台，系统自动切换到考试评分模块，教师可以根据需要设置题型题库，对题库进行添加、修改、删除等管理操作,也可以通过考试系统中的“试题组卷”功能进行批量组卷。组卷前需要对试卷名称、考试时间、试卷份数、题目数、分数、难易度及区分度等试卷参数进行设置，设置完成后点“开始组卷”按钮系统会自动生成考试试卷并保存在数据库中。测试后续，教师能对试卷做后期管理，主要有成绩查询、试卷存档、浏览已存档试卷三个功能模块。

4 总结

在线考试系统的实质是利用先进的现代计算机技术，用计算机组卷来代替人工活动，解决在传统的人工考试环境下不能解决的问题，达到提高工作质量和工作效率的目的[5]。

在线考试系统具有降低考试成本，解决繁重的考务工作的优点。利用计算机建立题库并对其进行管理，是实现教考规范化、标准化的一个重要措施。一方面计算机参与管理题库、组卷节省了教师的宝贵时间，另一方面使考试更加标准化，更加客观真实全面地反映教学成果，从而促进教学质量的提高[5]。

参考文献：

[1] 吕盈.基于B_S架构的远程考试系统的设计与实现[D].大连:大连理工大学硕士论文,2006.

[2] 刘丰.在线考试系统的设计与研究[D].北京:北京师范大学,2000.

[3] 邱少明.基于ASP的网上考试系统的设计与实现[D].大连:大连理工大学硕士论文,2006.

[4] 夏爱月.基于遗传算法的自动组卷系统研究与实现[J].电脑编程技巧与维护,2008(10).

[5] 伞晓丽.基于B/S 模式的网上考试系统的设计与实现[J].福建电脑,2009(1).

[6] 王小平,曹立明.遗传算法――理论、应用与软件实现[M].西安:西安交通大学出版社,2002.