一种基于遗传算法的智能组卷策略优化研究∗

贺建英 王光琼 唐青松

（1.四川文理学院智能制造学院 达州 635000）（2.达州智能制造产业技术研究院 达州 635000）

1 引言

随着高校人才培养模式的不断改革，“一科多考”的考核方式顺理成章的被提出。在考核中提出从多维度进行考核，如考试内容、命题、评价等，且能得到多元动态考试评价体系。然而“一科多考”的提出无形中加大了教师的工作量，一门课程多次出题，多次阅卷、多次对试卷进行评价分析。繁琐的工作让大家不约而同想到在人工智能高速发展的今天，在线考试系统带来的优势。当前智能组卷技术及其相关算法是现今高校信息化建设中研究的热点技术之一，通过高质量的试题库和优秀的组卷策略生成满足多种约束条件的试卷，然后使用终端设备同步在线考试。考试系统的另一个优势在于可减少教师阅卷和评卷工作量。系统的阅卷工作可以采用机器阅卷和人工阅卷相结合的方式。试卷的评价则根据系统的各项参数设置及学生的最终考试成绩自动生成试卷评价信息。通过信息化建设达到无纸化考试的目的。

当前自动组卷策略主要分为四类［1］：1）随机组卷算法；2）回溯组卷算法；3）演化式计算方法；4）遗传算法。随机抽取组卷算法非常简单，对单个题的抽取速度快［2］，但因有相应的控制指标，使得组卷的成功率较低；而回溯算法是基于随机抽取方法的算法，是基于它的一种改进方法。对少量题目和题量的自动组卷来说，组卷成功率很高。但它是基于随机抽取算法的，故存在随机性，导致组卷时间长，内存消耗大，难以满足用户实时的抽题需要；演化式计算方法主要包含遗传算法和粒子优化算法这两种演化式算法。遗传算法（Genetic Algorithm，GA）是一种模拟自然界的进化规律，通过选择、交叉、变异从上一代种群中产生下一代个体并组成新的种群，逐渐把适应度低的个体淘汰掉，达到最优的搜索查询结果。遗传算法在自动组卷中应用的好坏主要取决于如下几个因素［3］：1）最大进化次数及停止进化的条件；2）评价个体质量的适应度，以得到最优秀的个体；3）通过选择来得到优秀个体从而产生下一代，通过选择来决定种群的进化方向；4）通过交叉算法得到两个个体繁衍的下一代，实现基因重组；5）通过变异实现种群个体的多样化。

本文在传统遗传算法的基础上，从试题的编码方法、建立加权目标函数来优化适应度函数、交叉算子的选择、变异的设置以及到采用保优策略和轮盘赌相结合进行选择操作等方面进行了优化设计。取得了很好的适应度，并能快速成功组卷，提高了组卷效率。

2 相关工作

当前许多学者对遗传算法在自动组卷中的应用进行了研究，取得了一系列的研究成果。Gorgdberg M.W［4］建立了基于遗传算法的智能组卷的寻优模型。陈国彬等［5］对组卷使用快速动态粗粒度并行遗传算法，采用基于SVM（支持向量机）方式建立适应度函数对遗传算法进行改进，取得了显著的效果。焦翠珍等［6］提出使用十进制编码方式来代替遗传算法中的二进制编码，大大缩减了组卷时间。陈宇等［7］对遗传算法组卷过程中的约束条件的误差进行优化，提出一种启发式的遗传组卷算法策略。任学惠等［8］提出一种基于遗传算法的小生境技术，有效地约束了相似个体的繁殖。赵荟［9］提出一种优化组卷的各种约束条件来提高组卷质量和效率。肖庆理等［10］提出一种在组合遗传算法的基础上，对精英策略进行改进，与单个的纯粒子算法、遗传算法及其改进算法都有一定的优势。周艳丽［11］提出使用分段交叉和变异算子，采用加权误差的适应度函数快速收敛的方式，有效解决了组卷中的问题。路宽等［12］将群体中的所有元胞按照一定的演化规则演化之后再进行遗传，提出一种新的元胞遗传组卷算法。

3 组卷理论及数学模型

3.1 组卷理论

自动组卷实质上是一个目标函数和多个约束条件的组合。一般需要满足如下指标要求：1）试题所包含的知识点；2）试题所属的题型；3）试题在教学中的层次要求；4）试题对学生能力的要求；5）试题的难度级别；6）试题对学生能力的区分程度；7）学生完成试题所需要的时间；8）试题的难度系数；9）试题的分数；10）试题在题库中的选中率。对生成的试卷还需要包括：1）试卷总分；2）知识点分布；3）试卷难度；4）考试时间；5）知识点；6）题型分数；7）能力层次；8）试卷区分度等多个约束条件。下面首先给出相关属性的定义［9，13～14］：

定义1（试题难度）是指参与考试的学生群体在某一题上的失分率，如式（1）所示：

其中r是答错该题的人数，n是做过该题的总人数。该值在系统中是动态变化的。

定义2（试题区分度）是指把该试题学生的得分从高到低排序，从前后各取一定比例的考生得分的平均值分别作为高分组h和低分组l。如式（2）所示：

其中d∈[0,1]，k为该试题的实际分值。

定义3（试题的知识点覆盖率）设N为该试题所包含的知识点个数，M为一套试卷中要求应该包含的知识总数。此时其覆盖率表示为式（3）所示：

其中N应是去重后的知识点个数即N≤M。

定义4（试题选中率）指试题被选中的频率，可通过规定在某一段时间内使用过的不能再次使用，或者通过试题选中的频率来控制。如式（4）所示：

其中Xc为试题被选中的次数，P为总的选中试题的个数。实际操作时，在条件都满足的情况下优先考虑选择选中率低的试题。

定义5（试卷的信度）指试卷测试结果的可靠程度。由试卷的真实方差和成绩方差的比值进行定义，受测量偏差的影响。如式（5）所示：

其中Pn为试卷总的题数为第i题的方差，S2是组成的该套试卷的方差。当C＜0.7时，说明该试卷不可信。

定义6（试卷的效度）即试卷测试结果的正确性。如式（6）所示：

其中r＞0.4，Yi和Zi分别为第i个考生在本次测试与校标测试中的成绩。Yi、Y'、Zi、Z'分别表示两次测试的标准差与均值。Pt为参考考试的总人数。

定义7（试卷难度）指每个试题的难度与其分值相乘后的累加结果与总分值的比值。如式（7）所示：

其中Qi为第i题的试题难度，ki为第i个题的分值，n为总的试题数量，K为总分。

定义8（试卷区分度）通过试卷中每个试题的区分度与该试题分值相乘后的累加值与该套试卷总分的比值。如式（8）所示：

其中di为第i个试题的区分度。

3.2 智能组卷问题数学模型

智能组卷的实质就是满足用户的需求，通过用户给定的初始值生成满足多种条件约束的试卷。本文以《大学英语》为例建立试题库。总共包含570道试题，题型包括听力（单选）、单选题、阅读理解（单选）、完型填空（单选）、翻译、英文写作。试题分布数分别为50、350、70、30、30、40。从试题库中生成试卷时，假定需要组成一份试卷的试题数目为m，而对从试题库中抽取的每一个试题都要符合选择试题的指标属性等相关条件。所生成的一套试卷用矩阵则可以表示为一个m*7的矩阵，如式（9）所示。

通过矩阵得到如下生成一套试卷的约束条件［6～7］：

1）试卷总分约束条件：

K值由用户确定。

2）知识点层次分数分布约束条件：考试中根据大纲要求，有些知识点需要重点掌握，有些只要求理解，有些知识仅仅只是了解。故在知识点的考察方面就需要有侧重点进行考核。设三个层次的知识点集合分别为Z1、Z2、Z3，对应的分数范围为[S1,H1]，[S2,H2]，[S3,H3]，得到式（11）的约束条件：

其中 f1i、f2i、f3i分别为该试题在三个层次上的的知识点分布覆盖率。其中试卷三个层次总的知识点覆盖率约束为

表明生成的试卷中实际包含的知识点数与期望包含的知识点数的比值。已有研究表明该值大于80%时该生成的试卷达到要求。

3）试卷区分度分数约束条件：

其中 f4i为每题的区分度。

4）试卷难度系数对应的分数分布约束条件：

其中 f5i为每题的难度。

5）试卷的试题选中率分数条件约束：

其中 f6i为每题的选中率，其值越低，则生成的试卷间的差别越大。

6）试卷完成时间约束条件：

T的值应该小于等于用户需求设定的考试时间。

7）试题题型分数分布约束条件：

其中 f7i为每题的题型。

3.3 目标函数的建立

根据生成试卷的多种约束条件，在组卷中均希望对每一个个体试题能得到最为理想的值，即期望值。然而往往真实值和期望值之间会存在一定的偏差。根据多种约束条件，设L表示试题层次知识点，D表示试题的区分度，O表示试题的难度，C为试题知识点。则试题的期望值与真实值的偏差分别表示为 EL、ED、EO、EC、EB，分别由式（18）～（21）所示［15］。

其中Lj表示第 j个层次中知识点的目标分数，j=1,2,3。m1为生成的试卷中知识点的总个数。

其中Di表示试卷中区分度为i的目标分数。m2为生成的试卷中区分度的总个数。

其中Oi为难度系数为i的目标分数。m3为难度级别的总个数。

其中Ci为选中率为为i的目标分数。

大学英语考试试题有一特点，当题型为听力题时，根据同一场考试，听力试题相同的原则，只要探测到某一个试卷个体中已经生成满足条件的听力试题部分，则在后续的遗传中对该组试题直接遗传，不再做任何操作使其进化。通过相关条件的约束，最后得到在组卷过程中的目标函数为式（23）所示：

其中ωi是各个约束条件在组成试卷时所占的权重，且

4 基于遗传算法的自动组卷策略

4.1 编码方案

研究表明遗传算法是对基因的优胜劣汰。基因的长短决定了搜索效率的高低，基因过长导致搜索空间太大，遗传效率低下。本文采用实数的编码方式。每一个个体试题都有一个编号，该编号不会存在重复，把该编号作为遗传算法中的编码。按照不同的题型分段放在一起。大幅度减少了基因的长度，有效提高了搜索效率。本文中按大学英语课程考试的要求，设置六类题型。分别用L、C、R、S、T、W来表示，每类题型所生成的试题数量为m1、m2、m3、m4、m5、m6。则所生成的试卷编码可表示为图1所示。

其中的 li、ci、ri、si、ti、wi都是不同的实数。

图1 基因编码方式

4.2 相关操作的建立

在前面的分析中已经得知应满足的因素中包括适应度函数、进化次数、结束条件以及变异的相关操作（选择、交叉、变异）等。

4.2.1 适应度函数

适应度函数是用来评价一个群体中的单个个体优劣程度的值，该值越高其解越优，也能很好地控制搜索方向。已有研究表明，适应度的值与目标函数成反比，其目标函数的值越小，则适应度的越大。故适应度函数表示为式（24）所示［16～17］，这里t=2。

4.2.2 选择操作

选择操作的目的是对种群中的个体进行优胜劣汰，把优秀的个体进化遗传到下一代。在遗传过程中，有可能存在非常优秀的个体被淘汰的情况，故本文采用保优策略和随机轮盘赌相结合的方式。即把种群中优秀的个体不需要做任何操作而直接遗传到下一代，而剩下的个体则采用随机轮盘赌的方法，通过判断每一个个体可能被选择的选中率来判断是否被遗传到下一代中。选择率的计算可通过单个个体的适应度值与种群中每个个体的适应度值总和的比值Ci来确定。最后在［0，1］的区间上随机生成一系列数组，如果随机数组中的值大于个体被选择的概率值Ci，则该个体被选中进入下一代。否则直接把该个体抛弃。Ci的表示方式如式（25）所示［4］：

其中g(xi)表示第i个个体的适应度的值，t表示种群的大小。

4.2.3 交叉操作

交叉操作是在种群中对两个个体进行交叉操作。因听力试题的编码放在第一段内，根据分析，该部分题型在迭代过程中将直接遗传到下一代。本文采用随机在一个个体基因串的后面k-1段内和段间设置交叉点（k为基因的总段数），交叉后将生成两个新个体。若交叉后出现相同的基因序列，则取消该交叉操作。

4.2.4 变异操作

因采用的是实数分段进行染色体编码，不同的题型有不同的分段。故在变异操作时，对后k-1个分段内随机选择一个值进行变异，若变异之后的值在该段内已经存在，那么重新选择变异点进行变异，否则直接把变异后的值替代原值。一般情况下设置基因的变异率在0.01左右。

4.2.5 结束操作

本文采用最简单的遗传代数达到规定的值时结束算法。

5 实验与分析

系统采用MyEclipse10.0平台进行设计实现，数据库为MySql数据库（包含570道试题）。为验证上述算法的有效性，实验部分采用仿真方式对本文算法和SGA算法进行比较。根据分析设置组成一套试卷的约束条件要求如下［18］：1）试卷总分100分；2）考试时间120分钟；3）六种试题的题量和分值如表1所示；4）知识点层次分布在试卷中的比重为 60、25、15；5）试题知识点、区分度、难度、选中率、完成时间所占的权重分别为0.5、0.1、0.2、0.1、0.1；6）试卷难度0.6；7）试卷区分度0.7；8）变异率为0.01；9）交叉概率 0.6；10）初始种群规模数 30；11）种群数量15；12）最大迭代次数100。

表1 试卷结构设置参数

使用SGA算法和本文算法的仿真结果比较如图2、图3所示。

图2 算法收敛速度的比较

图3 所耗费时间比较

两种算法均能成功执行，对两个算法在执行过程中的收敛速度和执行时所耗费的时间两个方面进行对比。从图2可以看出，本文算法的收敛速度优于SGA的收敛速度，且随着迭代次数的增加SGA的收敛速度一直比较缓慢，而本文算法的收敛速度增加的较快。从图3可以看出，在迭代相同的次数时本文的算法在速度方面优于SGA，但迭代次数较少时，这种优势并不明显，随着迭代次数增加才被明显的表现出来。

6 结语

本文根据遗传算法的基本原理，从试题生成的约束条件、优化适应度函数的改进方面进行研究，并对在遗传过程中优化交叉算子的选择、变异的设置以及到使用保优策略和轮盘赌相结合进行选择操作等。在适应度函数中采用阈值t的方式来得到最优的适应度函数值。通过实验可知，但t=2时可以得到最优的值。本文最后通过本文改进的遗传算法与传统的遗传算法进行仿真结果比较，得到本算法有一定的优势，能得到更优的组卷策略和效率，组卷的成功率也有所提高。