基于遗传算法的自动组卷算法的研究

徐海东

基于遗传算法的自动组卷算法的研究

徐海东

自动组卷问题一直是计算机辅助教学领域中的一个研究热点，如何设计一个优良的算法让计算机更快更好地实现自动组卷是研究这个问题的关键点。遗传算法是现今比较智能的一种组卷算法，对通过对遗传算法进行改进，采用分组实数编码方案，通过证明了改进后的遗传算法在控制参数设置合理的情况下，能较好地实现自动组卷功能。

遗传算法；自动组卷；组卷算法

0　引言

遗传算法是一种新的全局优化搜索算法，相较于传统的组卷算法具有很多优点，如收敛速度快、并行处理能力强、应用范围广等等，在目前的计算机自动组卷算法有着极其重要的地位[1]。本文对通过对遗传算法进行改进，采用分组实数编码方案，通过试验证明改进后的遗传算法在控制参数设置合理的情况下，能较好地实现自动组卷功能。

1　遗传算法的改进

1.1染色体编码方案

目前在遗传算法中采用二进制编码算法处理的模式最多[2]。但是在组卷问题上，对于大试题量的试题库组卷，二进制编码的染色体长度太长，会造成遗传算法的搜索空间急剧扩大，计算量大，占用内存多等问题[3]。已有大量实验表明，在解决数值优化问题，实数编码要比二进制编码效率要好的多[4]。考虑到试题库的结构和试题特性，本文采用的是分组实数编码方案。分组编码就是把染色体按题型分组进行编码，每个编码表示一种题型。 初始化群体时根据各类题型的试题题量要求，从试题库中抽取满足条件的各类型试题组成一份试卷。这样保证了初始群体满足题型和题量的需求。

2.2目标函数设计

组卷问题是一个带约束的多目标条件下求最优解问题[5]。本文把各个试卷参数取值的限定作为组卷的多个目标。

如果假设难度级别为i的试题所占的分数为 ai（i=1,2,…,n,n 为难度级别的最高值），则组卷约束要求各难度等级的试题分值总和应该等于试卷总分，即。设Δai为试卷中难度级别为i的试题总分和实际要求总分之间的差值，所以试卷中各难度级别试题的实际分数与设定值的偏差的平均值f1可以用公式（1）：

类似的，如果假设知识点编号为i的试题所占的分数为bi（i=1,2,…,m,m 代表知识点的总数），则试卷总分可以用来表示。对于这一约束条件，也可以转换为目标函数的一部分。设Δbi为知识点编号为i的试题总分和实际要求总分之间的差值，f2为试卷中各类知识点的试题实际分数与设定值的偏差，则f2可用公式（2）：

同样的，f2越小说明选取的试题越符合用户的要求，误差越小；反之则说明选取的试题离用户的要求越远，误差越大。

将这些平均差值当作一个个目标分量，组合起来就可以作为组卷算法的目标函数。由于约束条件的多样性，这些目标分量往往很难被同时满足，而且它们之间的重要性根据用户的设定也有差异，所以可以给这些目标分量分配权值 ri来表示第i个目标分量的重要性，ri越大说明该目标分量越重要。所以目标函数f(x)可用公式（3）：

由上面的公式可以看出，f（x）越小，选出的试题就越符合用户的要求，因此组卷问题就变成目标函数f(x)最小化问题[5]。

1.3适应度函数设计

适应度函数的通常是将目标函数映射到适应度函数[6]。因为本文设计的目标函数是求最小值问题，所以在目标函数F(x)转换为适应度函数F(x)时采用如下公式进行转换如公式（4）：

上述公式将组卷问题从求目标函数的最小值问题转换为求适应度函数的最大值问题来求解[7]。

1.4遗传算子设计

1）选择算子

在遗传算法中，由选择算子来对试卷群体进行选择[8]。在选择时应该优先保留优秀的试卷个体，同时也要防止优秀的试卷个体控制整个群体。本文采用的选择算子为轮盘赌选择法，它是目前遗传算法中最常用的方法，选择操作过程如下：

1）依次累加试卷群体中试卷个体的适应值，得到相应的累加和Si；

2）在区间[0，Sn]上产生一个服从均匀分布的随机数 ；

3）依次用Si和 R 进行比较，第一个出现Si ≥ R的个体i 被选择为复制对象；

4）重复步骤2，3直到选出满足试卷所需要的个体数目为止。

2）交叉算子

交叉的操作过程：先将种群中的试卷染色体进行两两配对，假设种群规模为M，则配对试卷染色体的个数为 M/2。在每对试卷染色体中随机选择一个交叉点进行交叉，交叉过后该对试卷染色体的基因进行互换，形成一对新的试卷个体。以分组实数编码方案为例，交叉操作的过程如表1、表2所示：

表1　交叉前的父代试卷染色体A和B

表2　交叉后的子代试卷染色体A'和B'

交叉操作生成子代试卷染色体可能存在两个问题：一个是基因重复[9]；另外一个是顺序混乱[10]。如果出现这两个问题中的任意一个，那么该染色体就是非法的。为了避免出现这两个问题，本文采用如下方法：在相同的编码段内，将处在交叉点的基因依次与交叉点前的基因从后向前依次做比较，遇到第一个小于交叉点基因的基因则停止判断，记录该基因的编码 m，然后再将交叉点前一个基因与交叉点之后的基因从前向后依次做比较，遇到第一个大于交叉点前一个基因的基因就停止判断，并记录该基因编码 n。所以交叉之后的重复和排序问题就是在区间[m，n]内做判断。假设交叉点基因编码为 p，那么两层循环就在区间[m，p-1]和[p，n]内判断是否重复，如果有重复，就将[p，n]内的重复基因替换成该段中没有出现过的基因，替换的方式是随机抽取一个没有出现过的试题编码。最后将 B'中的基因重新排序。比如对 B'中的第二段基因编码，只需重新排序即可；对 B 中的第三段编码，可以将后一个编码为 37的基因进行替换，然后再重新排序即可。

3）变异算子

在遗传算法中，变异算子一般采用小概率对某个试卷染色体的某一段基因里的基因值做变动，变异点采用随机的方式生成[11]。并不是所有的试卷染色体都会采用变异操作，而是根据变异概率来确定变异[12]。假设变异概率为pm，pm的取值在区间[0，1]内。如果pm过小，则不利于新的试卷个体的生成，从而使遗传算法过早陷入局部最优，产生“早熟”现象；如果pm过大，遗传算法就变成了随机搜索算法。

为了解决上述问题，本文根据试卷群体的进化情况设计了适应度函数，以自适应的方式来动态地调整变异概率pm。变异概率计算公式如公式（6）：

其中km为变异概率系数，取值区间为[0.01， 0.05]， F为变异试卷个体的适应度值，Fmax为试卷群体中所有试卷个体的适应度最大值， ¯为试卷群体中所有试卷个体的适应度的平均值。

2　.实验结果及分析

本文为了验证上述遗传算法的可行性和有效性，以《数据库结构》课程为例，通过上面实现的基于安卓的自动组卷系统对算法进行了性能测试。

本次实验模拟题库中共有 400道题，其中选择题 150题，填空题 150 题，问答题50题，综合题50 题。期望生成的试卷中包含 33道题，这4种类型的题目在试卷中数量比例为 15：10：5：3，试卷题型数量结构如表3 所示：

表3　试卷题型数量结构

题目难度-分数分布情况如表4所示：

表4　题目难度-分数分布情况

知识点-分数分布情况如表5所示：

表5　题目知识点-分数分布情况

测试过程：

固定最大迭代次数 MaxGen=200，群体规模PopSize=80，最佳适应度阈值 Fitness=0.85[14-15]。算法的终止条件是迭代次数达到 MaxGen 或者最好的试卷适应度值大于或等于 Fitness。调整交叉概率pc和变异概率pm，观察它们对组卷效率和算法收敛性的影响。 当pc = 0.3时，对pm取不同的值分别运行组卷程序 20次，实验结果如表 6所示：

表6　变异概率pm对组卷成功率和算法收敛性的影响

由实验数据可以看出当pm > 0.5和pm < 0.0001时，组卷效率和算法收敛性都明显下降，因为变异率取值太大虽然可以增加试卷群体的多样性，但同时也会破坏群体中的优秀试卷个体；变异率取值太小则新的试卷个体产生的速率又太慢。所以pm的取值最好在区间[0.01，0.05]之间。

3）当pm = 0.03时，对pc取不同的值分别运行组卷程序 20次，实验结果如表7所示：

表7　交叉概率pc对组卷成功率和算法收敛性的影响

数（次）数（次）（秒）适应度值0.2　16　179.1　1.965　0.85 0.4　20　162.2　1.632　0.87 0.6　20　162.5　1.636　0.85 0.8　19　161　1.651　0.86 1.0　17　180.6　2.013　0.86

由实验数据可以看出当pc在区间[0.4，0.6]之间时，组卷效率和算法收敛性比较好。

4）控制交叉概率pc为 0.4，变异概率pm为 0.02，组卷系统的组卷算法分别使用传统的遗传算法和改进后的遗传算法进行 20 次组卷实验。实验结果如表 8所示：

表8　传统遗传算法和改进后的遗传算法实验结果

3　总结

上述实验结果证明，只要适当控制算法的参数，改进后遗传算法具有较好的组卷效果，并且比传统的遗传算法组卷成功率更高，收敛速度更快。

[1] 张建国. 智能教学系统中的自动组卷算法研究[D]. 河南:河南大学.2009:12-14.

[2] 秦金亮. 标准化题库建设的数学模型建构[J]. 山西师范大学学报,2000,14(2): 21-22

[3] 周文胜,潘中柱. 一种实用的随机组卷算法的设计思想[J]. 湖南科技学院学报,2005,11(2):115-116.

[4] 管宝云,尹琦. 基于混合智能算法的自动组卷问题研究[J]. 天津工业大学学报,2006,4(1):32-33.

[5] S.S.Guttormsen & H.Kruemut. Using New Learning Technologies with Multimedia[J].IEEE Multimedia July-September,2000,36(7):40-51.

[6] 陈熙,吴成秋,贺栋梁.试卷分析与评价的指标体系及其应用[J]. 微处理机,2006,14(5):31-32.

[7] 柳国杰,陈军. 教育测量中难度与区分度的计算方法[J].信阳师范学院学报,2003,3(2):5-7.

[8] 赵立新,陈文艺,郭子君. 试卷质量的定量评价[J]. 华南农业大学学报,2004,3(4):21-22.

[9] 林雪明,张钧良,蒋伟钢. 基于知识点的试题库组卷算法的建立[J]. 微机发展,2001,11(2):77-80.

[10] 田茁,李太浩. 遗传算法在试题组卷中的应用[J]. 长春师范学院学报,2005, 24(3):555-557.

[11] 陈宇,陈治平. 启发式遗传算法组卷模型研究[J]. 计算机技术与自动化,2006,25(1):11-12.

[12] 刘明明，许勇.基于Web的在线考试系统分析与评价[J].管理观察,2009,3(5):235-238

[13] 王琪，张冬梅.试论在线考试系统的设计与实现[J].教育信息化,2002,5(11):37-38

[14] 沈建强，张宝明，邹轩.组卷系统的优化与实现[J].计算机应用,2003,6(S1) : 25-28

[15] 路平，王敏娟，万昆.试题库白动组卷策略研究[J].电脑开发与应用,2001,2(02) : 56-58

Research on Automatic Test Paper Based on Genetic Algorithm

Xu Haidong
(Mechanical and Electrical College,Xiangyang Vocational and Technical College,Xiangyang 441050,China)

The problem of auto-forming test paper has become a research hotspot in the computer-assisted instruction field. How to design a better algorithm to help the computer realize an auto-forming test paper has become the key point of this problem. The genetic algorithm is a kind of intelligent test paper algorithm,which can be used to solve that kind of problems of optimization about multi restrain conditions and multi objectives. In this paper,the genetic algorithm is improved based on the deeply research on the genetic algorithm,and according to the lots of experiment results,the improved genetic algorithm is verified that it can realize the auto-forming test paper better under the reasonable control parameters.

Genetic Algorithm; Automatic Test Paper; Test Paper Algorithm

TP311

A

1007-757X(2016)03-0060-03

徐海东 （1975-11），上海人，男，襄阳职业技术学院，机电学院，硕士，助讲，研究方向：计算机科学，襄阳，441050

（2015.07.15）