改进的遗传算法在智能组卷中的应用研究

唐玲 尹珧人

摘 要：该文提出分段二进制编码，对遗传算法的选择过程进行改进，并采用独立题型题库存放的方法来求解组卷问题。实验结果表明，新方法的组卷成功率和收敛速度都得到明显提高，较好的克服了早熟收斂现象，组卷质量明显提高。

关键词：改进遗传算法 智能组卷 数学模型

中图分类号：TP18 文献标识码：A 文章编号：1674-098X（2013）03（c）-00-02

随着我国信息技术的飞速发展，计算机在教学领域有了广泛应用，用计算机进行网上考试已经成为一种趋势，因此怎么才能快速从试题库中选出一份满足用户各项要求的试卷成为一个问题。目前常用的组卷方法有随机选题法、回溯试探法、遗传算法三种，而传统的遗传算法主要通过交叉算子繁衍后代，容易造成早熟收敛现象。因此目前已经有很多人为提高组卷效率，将遗传算法的算子改进后再应用到智能组卷系统中。该文为加快算法的收敛速度，将遗传算法的算子进行了改进，并应用于智能组卷系统中。

1 智能组卷的数学模型

将智能组卷问题视为从一定题量的数据库中抽取满足组卷要求的一组试题组合，就能够将组卷问题转化为一个多重约束目标问题。求解一份由m道试题且每道试题有n个属性的试卷，相即构建一个m×n的目标矩阵S。

S=

试题常有如下属性：⑴难度系数a1、⑵分数a2、⑶能力层次a3、⑷预计答题时间a4、⑸题型a5、⑹已出题次数a6。目标矩阵应满足以下约束条件：

⑴试卷难度系数=1-/总分（由用户给定）；

⑵试卷总分=（一般为100分）；

⑶答题总时间=（由用户给定）；

⑷（为第p能力层次题分），能力层次类型和所占分数由用户给定，即能力层次约束，其中

⑸题型题分=，第j题型题分，其中：c={，j为题型要求约束。题型分别为：判断、单选、填空、多选等，具体组卷题型类别和每题分值由用户给定。

组卷过程中，试题要根据数学模型中给出的各项指标来决定，即表示第i道试题中的第j项指标，其中i=1，2，…，m；j=1，2，…，n。

2 题库建设

该文试题在存储时采用各题型独立试题库的存储方法，为了避免经常抽取同一道试题，我们将各题型题库中试题根据已出题次数（a6）排序（初次抽取试题时，试题顺序随机产生），使a6小的试题下次被抽中的机率更大，以提高每次组卷产生的试卷

质量。

3 改进的遗传算法在智能组卷中的

应用

3.1 编码方案

将二进制数分段编码，每段代表一个题型，k表示题型数量，题库中试题数量决定了编码的长度。设各题型题库中共有t道试题，则编码形式为b1b2…bt，随机产生初始化种群（假设串长度是相同的）。

其中：bi={ i=1，2，…，t，且满足=m，其中m是试题所含的题目数。=m1，=m2，…，=mk，=m，=t其中m1，m2，…，mk表示在试卷中各题型的试题数量，r1、…、rk表示各题库中该题型的试题数量。

3.2 生成初始种群p（0）

为了降低问题难度，提高求解效率，我们随机产生试卷的初始种群p（0），使初始种群满足试卷总分的要求。

3.3 确定适应度函数

我们采用以下形式的适应度函数[1]：

F=1/（1+） i = 1，…，n

其中ei表示第i组卷因素对组卷目标造成的误差，ki表示权值系数，且ki>0。

3.4 遗传算子的改进

3.4.1 选择算子

该文中每个个体的适应度值由适应度函数计算得来，并将种群代数t的初始值设置为0，将每代种群按其适应度值的降序进行排序，依次计算相邻个体之间的广义海明距离H，广义海明距离[2]是指相同长度的两个串中对应位不相同的数量，例如，某种群的某代进化种群中第i个个体和第j个个体分别为：

xi（t）=1111001010001，xj（t）=1100101011001

它们间的广义海明距离H（x（t），xj（t））==4。比较H和参数d的大小，若H小于d，则依次用父代群体中的优秀个体替换适应度小的个体；否则保留这两个个体，将其加入到新一代群体中，执行交叉操作。

3.4.2 交叉算子和变异算子

该文的交叉概率和变异概率是根据种群的进化情况用自适应函数来控制的，这样可以加快遗传算法搜索效率，有效防止算法陷入局部最优，从而保护优良试卷个体，所使用的适应度函数如下[3]：

pC=

式中：f取参与交叉的两个个体中适应度值较大的一个；fmax、favg为上代群体中个体的最大适应度值、群体的平均适应度值；pc1=0.9，pc2=0.6。

pm=

式中：fmax、favg分别取上代群体中个体的最大适应度值、群体平均适应度值；f为要变异个体的适应度值；pm1=0.1，pm2=0.001。

该文交叉操作过程如下：随机产生交叉位置i，该位置由挑选出的两个个体的长度t决定，其中i取整数且1≤i≤t-1，按下面方式交叉：

为了避免交叉在基因段内进行导致同一题型试题重复的情况，我们限定交叉点位于第i个基因段内，前i个基因段保持不变，从第i+1个基因段开始逐位进行交换。并且在交叉后立刻评价新产生个体的适应度，将其与父代两个体比较，如果适应度值相同，则将新个体视为无效个体删除；否则将其连同父带个体保留，使新个体直接执行变异操作。

为了保证各个题型、题数的要求，变异过程我们利用变异率决定随机到哪位并将该位的值取反，同时在该位所在的基因段内，向前或向后搜索与该位最近并且值相反的位，将该位值也取反。

3.5 终止条件

我们将种群规模设置为200，算法执行的最大代数设置为500，当出现如下情况时算法终止：①达到要求的进化代数；②当进化中种群最大适应度值与之前各代种群最大适应度值近似时；③得到满足用户的组卷约束要求的种群或得到用户满意的试

卷时。

4 仿真试验结果分析

为了验证本算法可行，我们分别采用该文算法和传统遗传算法针对智能组卷系统进行了仿真。针对《C语言程序设计》的1000道试题进行组卷实验，将试题按照单选、多选、填空、判断题型分别建立4个库文件，并规定每个库中有250题，每类题型有5种难度。试卷满分设置为100分；预计答题时间为120 min；试卷总体难度系数设置为0.8。仿真结果如图1、图2所示。

通过上面比较可以看出，该文算法能够得到最优解，并且在进化代数和收敛速度上明显优于传统遗传算法，提高了问题的求解效率，能有效地解决智能组卷问题，充分验证了本算法可行。

参考文献

[1] 杨路明，陈大鑫.改进遗传算法在试题自动组卷中的应用研究[J].计算机与数字工程，2004（5）：77-78.

[2] 王丽芳，王楠，李新华.基于一种改进遗传算法的智能组卷的研究[J].中北大学学报（自然科学版），2006（4）.

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

[4] 路景，周春艳.基于遗传算法的混合优化策略研究[J].计算机技术与发展，2007，17（3）：144-146.

[5] 吴飞.自适应遗传算法解决组卷问题的探讨[J].重庆科技学院学报（自然科学版），2007（2）.