用自适应多点变异混合遗传算法实现智能组卷

2022-09-11

在计算机辅助教学中,采用计算机实现无纸化考试是非常重要的组成部分。而在网络化考试系统中,如何采用合理、科学的方法来实现试卷的自动生成,又是非常重要的环节。传统的实现自动组卷的方法包括:随机抽取法、回溯试探法、遗传算法[1,2,3]。这些方法或缺少随机性,或组卷时间过长,或由于约束条件的局部限制,常导致组卷失败,无法满足需要。本文根据组卷问题中试卷构成知识、专家设计试卷时的选题思路,提出一种基于自适应多点变异混合遗传算法的智能组卷方法。

1 自动组卷的数学模型

通常,全部试题按内容分为若干篇章、题类和多个细目,每一道试题又包含多个属性。属性主要有:(1)知识范围,试题内容所属的知识篇章范围;(2)题型,试题的题型,有选择题、填充题、计算题、问答题、判断题等等;(3)认知程度,反映该题对教学内容的要求层次,分为a.掌握b.理解c.知道;(4)难度,分为容易、中等、较难和难题;(5)能力要求,试题对学生知识能力的要求;分为a.学会b.比较熟练c.熟练;(6)区分度,试题对考生的知识能力水平鉴别和区分程度的指标;(7)估时,估计答题时间;(8)题分,试题的分数。

组卷中决定一道试题,就是决定它的上述8个属性,也就是说决定一个8维的向量(a1,a2,a3,a4,a5,a6,a7,a8)(ai相当于第i个属性),那么一个具有n道试题的试题库,实际上就是一个n×8的矩阵:

根据用户的组卷要求,在矩阵A中寻找满足组卷目标要求的行组合,即搜索确定矩阵A中全部行状态的多变量优化组合(F1,F2,…,Fn)。其中Fi为第i行的状态变量(即第i道题),若Fi=1表示第i题被选中,而Fi=0表示第i题没有被选中。

整套试卷应满足的约束条件包括:

1)试卷总分S:完全正确回答所有题目所获得的分数,默认S=100。

2)答题时间T:控制试题数量的约束。

3)题型R:设全卷有r种题型,第r种题型的总分为Sr,那么S=S1+S2+…+Sr。

4)试卷难度D:试题难度的确定,得分率d=1-(平均分/该题满分);难度级别分四级:容易题(得分率0.8-1)、中等题(0.6-0.8)、较难题(0.3-0.6)、难题(<0.3)。试卷的平均难度(AD):

其中,pi和di分别是第i道题的难度和分数。可以要求所抽取试卷的平均难度为某一确定值,由用户给定。

5)知识范围K:设全卷有k种知识范围,第k种范围的总分为S k,那么S=S1+S2+…+Sk。

6)教学要求度A:设全卷第a种教学要求度的总分为Sa,那么S=S1+S2+…+Sa。

7)试卷的区分度F:其中ai8为第i题的分数,ai6为第i题的试卷区分度。

自动组卷就是从试题库中随机选出一组试题,使得它们所有的属性变量在取值范围内都满足用户指定的约束条件或要求误差最小,这样可以把自动组卷描述成一个约束满足的问题。在实际应用中,设定整卷指标f来综合反映这些个指标与用户要求的误差,由于它们的重要程度不同,因此整卷的指标f就是这些指标的加权和,同时为了不至于各个误差相互抵消,这些指标与用户要求的误差都取绝对值。

2 自适应多点变异混合遗传算法的智能组卷

传统的遗传算法有两个严重的缺点,容易过早收敛,以及在进化后期搜索效率较低。过早收敛主要表现在群体中所有个体都陷于某一极值而使进化停止,或者接近最优的个体总被淘汰,这使得最终搜索得到的结果往往不是全局最优解,而是局部最优解。为此,提出表1实验结果

传统的遗传算法有两个严重的缺点,容易过早收敛,以及在进化后期搜索效率较低。过早收敛主要表现在群体中所有个体都陷于某一极值而使进化停止,或者接近最优的个体总被淘汰,这使得最终搜索得到的结果往往不是全局最优解,而是局部最优解。为此,提出一种基于自适应多点变异混合遗传算法的智能组卷方法。具体方法如下。

2.1 编码

采用试卷个体由组成试卷的试题题号构成的方式进行编码,试题库中没有包含在试卷中的试题题型不出现在试卷个体编码串中,假定每种题型的试题数是固定的,且同一题型中试题的分数和答题时间是相同的,把群体中个体对应的串按照题型分为若干段,称这些小段为功能块,即每个功能块对应一个题型,以功能块为单元彼此独立编码。具体而言,就是根据各个题型各自编码,然后对每一个题型再采用传统编码策略进行处理,但组与组之间的编码是独立的。采用这种编码方式,可以克服常规采用二进制编码搜索空间过大和编码长度过长的缺点,提高了求解速度和精度,同时减少迭代次数加快算法收敛到理想解。

2.2 初始化群体

一般方法是随机生成m个二进制编码串,这m个个体形成遗传群体。在群体中,个体串的长度都是相同的,群体的大小需要按经验或实验给出。但这个方法存在着一些缺点,如果遇到问题解空间很大的情况,在搜索初期很难生成一个有意义的试卷,甚至在搜索的开始就陷入随机漫游的状态。在组卷问题中可以使个体的部分功能块满足部分组卷约束条件,例如初始化生成的个体满足组卷约束中对单选题数目的要求。但是这样生成初始群体一定要注意保持群体中个体多样性,防止算法过早收敛于一个次解。

2.3 确定适应度函数选择算子

用适应度函数计算每个个体的适应度,按适应度比例复制后遗传到下一代,再去掉适应度低的个体,但保持群体的大小不变。遗传算法利用适应度值这一信息来指导搜索方向,根据约束条件,建立目标函数为误差函数其中,wi表示相应误差权值系数,fi表示个体满足第i项组卷约束程度的归一化相对误差。根据实际组卷经验,对不同的约束条件可给定不同的允许误差(1%-5%),只要试卷个体满足第i项组卷要求的误差在容差范围内,即可认为fi=0,这样可以加快搜索到合理解的速度。由目标函数,可设计适应度函数F=1/(0.1+E)。该适应度函数可以很好地进行遗传运算。

采用期望值模型选择机制,即先计算群体中各个个体期望被选中的次数Ni,(M为群体的规模,Fi为第i个个体的适应度),用Ni的整数部分作为个体i被选中的次数,这样,选出个个体,然后对Ni的小数部分作为概率进行贝努利试验,若试验成功,则该个体被选中,不断重复,直至选满为止。显然,个体适应值愈高,被选中的概率愈大。但是,适应值小的个体也有可能被选中,这样有助于增加下一代群体的多样性。

2.4 交叉算子

在搜索初期,采用单点交叉算子,即交换作用发生在整个编码串上,这样可以保持群体的多样性;在搜索后期,改变普通的交叉算子为带约束的交叉算子,使交叉操作作用在功能块内部,即多点交叉算子。

在简单遗传算法中,交叉率是个常数,而实际上,优良的交叉率与遗传代数的关系较大。在迭代初期,交叉率选的大可以造成足够的扰动,从而增强遗传算法的搜索能力;在迭代后期,交叉率选的小可以避免破坏优良基因,加快收敛速度[4]。本文选择的交叉概率Pc是能自动适应演变变化的函数。

其中h1=h2=0.9,fmax为群体中最大适应度值,favg为每代群体中平均适应度值,f为要交叉的两个个体中较大的适应度值。

2.5 变异算子

采用分段多点变异操作,对染色体中各个独立编码段依次进行段内自适应多点基本位变异操作。基本位变异操作是对段内编码串以概率1随机指定的某一位基因座上的基因进行变异,在进行段内某基因位变异后,再在该变异位所在段内,随机向后或向前搜索寻找与该变异位基因值相反的基因座(将基因位值取反)。染色体中各段内多点基本位变异数为:M=wk(fmax-f)/fmax,其中k为题库中题型种类数,wk为k段代码的最大变异位数,fmax为群体中最大适应度,f为要变异个体的适应度值。同样选择的变异概率Pm也是能自动适应演变变化的函数。

其中h3=h4=0.1,fmax为群体中最大适应度值,favg为每代群体中平均适应度值,f为变异个体的适应度值。2.6最优解保护策略[5]

采用最优解保护策略,就是保证父代的最优个体总是可以生存到下一代,为了保持群体规模不变,该最优个体将替换掉子代中的最差个体,这样可保证在进化过程中父代的最优试卷个体不至于丢失,有利于加快进化进程。它是遗传算法收敛性的一个重要保证条件。