浅议在线考试系统中基于遗传算法的自动组卷算法的设计

曹鑫+韩莉+韩红彩+张亚娜

遗传算法在考试系统的自动组卷方面具有其他传统组卷算法所不能比拟的优点，通过交叉、变异等操作来产生新的个体，扩大了搜索范围，使得优化的结果是全局最优解而不是局部的最优解，适合于大规模、复杂问题的求解，其计算简单但功能强大。

【关键词】组卷；遗传算法；操作

在线考试系统的设计与开发中，组卷是实现考试系统自动化的核心问题之一。组卷是指由用户先输入对试卷试题的要求，然后系统自动地从试题库中选出符合用户要求的试题，组成一份试卷的过程。

1 遗传算法

遗传算法是将孟德尔的遗传变异理论与达尔文的“优胜劣汰，适者生存”自然进化学说进行模拟，实现的一种迭代式的搜索算法。遗传算法的步骤如下：

1.1 初始化

先产生足够数量的个体，然后将这些个体组成一个种群。

1.2 迭代的执行下面操作

在种群中，将每个个体的适应度值计算出来，根据某个规则，选出一个能进入到下一代的个体，产生一个新的种群。在这个新的种群中，按照交叉概率Pc进行交叉操作，按照变异概率Pm进行变异操作；如果不能满足任何一个停止条件，那么就转到第（1）步操作。

1.3 输出适应度值最优的染色体作为最优解

把问题的解用“染色体”来表示，把这染色体放到某个具体 “环境”中，根据适应度函数值选出适应度较高的“染色体”，并复制这些染色体，按照这个过程，将进化工作一代一代的进行下去，必将产生一个最适应环境的 “染色体”，从而获得问题的最优解。

2 自动组卷算法的实现

根据前面所介绍的有关遗传算法的相应知识，下面就对自动组卷的算法进行设计：

2.1 编码

遗传算法进行优化问题是通过编码来實现的，因此编码和解码是遗传算法的一个主题。首先是编码算法的确定。由于标准化试卷每种题型所占的分数、试题的个数和每题分数的乘积是相同的，所以采用独立的编码策略。具体来讲就是编码的依据要结合题目的类型，在每种题型的内部应用常规编码策略，也就是0-1编码。这种方式的编码使组与组之间的编码是相互独立，每一组的编码都反映一种题型，试题库中该题型的题目数量决定每一组编码的长度，一份试卷的编码长度就是总的编码长度，这是由试题库中所含的试题总数决定。

2.2 生成初始群体

在初始群体产生的时候，首先将各个个体的所有位上均设置为“0”，然后参照每种题型题数的限制，随机产生与试题数目相同的“1”位，这样可以保证初始群体各个个体都满足试卷的标准格式和满分都为100分的特点。另外，这也解决了因试题数目过多而造成编码长度过长的问题。种群规模n较大则进化较慢，但是对全局最优解的搜索会较为容易，而n较小时，则进化速度快，但对全局的最优解的搜索灰较为复杂。

2.3 计算初始群体适应度

由于采用独立编码方式，所以在初始种群产生时，题型、题数和题分都是满足要求的，因此在组卷过程的实际操作中，只需要考虑知识点的难度系数、范围、试题区分度和教学要求等因素即可。在此可将知识单元的权值取1.0，试题区分度的权值取1.0，教学要求的权值取0.9，难度系数的权值取1.1。以上这些权值是在模拟组卷过程中使用的，而实际权值的确定应该根据考试的要求或目标进行设定。

2.4 选择

首先根据适应度对群体中所有的个体进行由小到大的排序，然后将排在最前面的一半染色体选取出，在对这些选取出的染色体进行下面的操作。

2.5 交叉遗传

交叉遗传是针对编码进行的，此方法必须得保证试卷编码中的各段1的位数恒定不变，否则将会引起试卷中每个题型的题数发生变化，导致生成的试卷不符合标准化试卷的要求。因此在组卷过程中，采用单亲遗传法，这种方法可以避免两条染色体在进行交叉时，所引起的试卷中不同类型的题数发生变化的情况。交叉操作是各段分别通过随机数随机产生交叉位，它是一种以染色体中点为轴心进行的对称交叉。

2.6 变异

为了使各题型组内题目数量不会受变异操作而发生改变，可以采用一种一次变异操作，使组内可同时变异两位的方法，即一位0到1（1到0），而在该位所在的组内，应采用先向前、再向后的搜索方式，将与该位最近的1变为0（0到1）。

2.7 算法终止条件

遗传算法中的优化准则，是一种依据问题的不同而有所不同的确定方式，可以采用如下准则之一来作为判断的条件：种群中个体的平均适应度基本上达到了用户预先设定的值；用户输入的值要大于种群中个体的最大适应度；世代数超过预先设定的值。这里的终止条件是：设置遗传最大代数为200，那么进化到200后就会终止进化过程。

为了防止组出相同的试卷，还需要对试题库进行一定的修改，即修改从试题库中抽取的试题的使用次数和最近使用的时间，以便保证在连续生成的几份试卷中或在某一段时间内不会重复出现同一试题。

3 基于遗传算法的组卷流程

在实现自动选题时，可以采用父辈挑选与生存选择两种选题的方式。父辈挑选的方式是将每次选出的随机抽样不再返回，这种方式使得试题库中的每道题目都有可能被选中；生存选择的方式是指父辈与子代之间进行竞争，能进入到下一轮竞争环境的是二者中的优良者，这是一种择优选择。这两种方法共同作用于试题的选择，可以保证顺利完成选题。在选题的过程中，题目的选择是随机的，而且哪一道题目被选中是一个非均匀的随机事件，题目被选中的概率要依赖于上一次选题的过程。

遗传算法在考试系统的自动组卷方面具有其他传统组卷算法所不能比拟的优点，通过交叉、变异等操作来产生新的个体，扩大了搜索范围，使得优化的结果是全局最优解而不是局部的最优解，适合于大规模、复杂问题的求解，其计算简单但功能强大。

参考文献

[1]刘彬，金涛，陈太平.遗传算法在试题组卷中的应用[J].燕山大学学报，2002，26（03）：193-195.

[2]王娜.多目标组卷模型及其算法研究[J].沈阳师范大学学报（自然科学版），2006，24（02）：189-191.

[3]管宝云，尹琦.基于混合智能算法的自动组卷问题研究[J].天津工业大学学报，2006（04）：97-100.

[4]曾一，一冉忠，郭永林.试题库中自动组卷的算法及试卷测评策略[J].计算机工程与设计，2006，27（06）：3024-3027.

作者简介

曹鑫（1981-），女，现为石家庄信息工程职业学院讲师，研究方向为信息系统开发。

韩莉（1977-），女，现为石家庄信息工程职业学院讲师，研究方向为数据库应用于开发。

韩红彩（1980-），女，现为石家庄信息工程职业学院讲师，研究方向为数据库应用于。

张亚娜（1979-），女，现为石家庄信息工程职业学院讲师，研究方向为信息系统开发。

作者单位

石家庄信息工程职业学院 河北省石家庄市 050035