刘长骞
(淄博职业学院现代教育技术中心,山东淄博255314)
计算机智能组卷的实质是求解出满足用户输入参数的一套最优试卷,因此组卷问题是一个典型的约束满足问题的求解过程.遗传算法则由于自身具有全局搜索性、随机性、较好的编码方式和高度的并行性的特点,因此当前许多组卷算法都在考虑使用遗传算法进行求解.国内外已有许多学者进行了这方面的研究,D.B.Fogeol提出把遗传算法用于试题组卷,GordbergM.W应用遗传算法的寻优特性为组卷问题建立了寻优模型等.
遗传算法一般采用定长二进制串编码方式,问题的一个解对应一个长度为k的二进制串.从初始种群出发,采用一定的选择策略,在当前种群中选择个体,使用杂交和变异遗传算子来产生下一代种群.如此一代代遗传下去,直到满足期望的终止条件.
传统遗传算法可以从很差的个体逐渐搜索到较好的个体,对领域知识要求也很少,是一种通用的有效的解决方法,但它的求解质量和效率都不理想,计算时间也很长,还存在着以下几个问题亟待解决:
遗传算法用适应度作为选种的选择压力,如果群体的适应度变化不大或者过大,会引起选择压力不足或者波动,导致迭代过程过早收敛或发生振荡.
由于后代完全替换双亲,优良基因结构被交叉破坏的可能性较大,以致延缓群体性能的进化.
各代群体中的最优个体未得到保护,劣质个体有可能会取代优良个体.
求解的终止条件一般采用繁衍代数(迭代次数)作为准则,含有很大的人为因素,使算法可能收敛不到极值点.
鉴于传统遗传算法存在的不足,为提高遗传操作在组卷算法中的搜索能力,我们从遗传操作、控制参数等方面对其加以改进,使其功能更为强大.
遗传算法在很多具体应用中容易出现所谓“早熟收敛”现象,即在早期可以迅速地达到次优解接近最优解,但此后搜索到最优解的速度就慢下来了.其原因是遗传算法主要通过交换算子繁殖后代.由于交换算子所作用的两个个体相同时,不能产生有意义的新的个体,因此初始种群一般都要求具有广泛多样性.应用中一般都采用较大的交换概率和较小的变异概率,并且这两个概率参数在整个搜索过程中往往不变,算法可以迅速接近最优解.但在最优解附近,当群体进化到其中的各个个体均相同时,交换算子无效,此时仅靠变异算子产生新的个体,由于较小的变异概率缺乏较强的局部搜索能力,以致步长过大很难找到最优解,遗传迭代难以进行下去.
针对这种情况,采用动态参数自适应调整方法,即在算法开始执行时采用较大的交换概率pc,小的变异概率pm,算法搜索速度放慢时动态调整概率大小,使pc适当减小,而pm适当增大.
混合遗传算法是在传统遗传算法中将局部优化作为其辅助成分.在混合算法中,每一个新产生的后代在进入种群之前需要进行局部优化使其移动到局部最优点上,由于遗传算法和局部搜索方法的互补特性,所以混合方法的效果更好.
其中最典型的是Lamarckian进化[1-2],它的理论依据是环境变化引起的生物体生命过程中的结构变化可以传递到其后代去,因此算法中个体在整个生命过程(一代)中都进行学习(爬山),个体爬山后被重新放回到种群中.在这种混合方法中,人工生物体首先经历Darwin的生物进化,然后经历Lamarckian的智能进化.在Lamarckian进化过程中的评价阶段之前,用传统的爬山程序来将某种“知识”注入到后代生物体中.
通过让某些个体的经验传递到未来的个体中去,将遗传算法的搜索领域集中到最有希望的区域,改进算法的性能.采用了Lamarckian方法,传统的爬山程序可以采用后代作为初始点并对其进行快速的局部优化.个体学会在局部解空间中爬山后,其后代就可以经历评价和选择阶段.利用普通的杂交将其经验传递到后代中去.这种方式使优良基因结构得到保护,最大程度上避免了各代群体中的劣质个体取代优良个体.
爬山算法是基于邻域搜索技术的、沿着有可能改进解的质量的方向进行单方向搜索(爬山)的搜索方法.该方法的局部搜索能力很强,是常用的寻找局部最优解的方法.可以针对遗传算法这种全局搜索能力很强而局部搜索能力不足的算法形成互补.
通过以上的改进方法,可以得到如图1所示的算法流程。
图1 改进后的遗传算法流程
通过以上的改进方法,可以得到如图一所示的算法流程图.
利用上述改进后的遗传算法,采用asp.net技术开发了基于web的考试系统,并对淄博职业学院《大学英语》题库进行自动组卷实验.
将600道试题按要求存入题库,给出生成试卷的要求.组卷中决定一道试题,就要决定k项指标,这里我们考虑5维向量(知识单元a1,题型a2,难度,题分,区分度)相当于第i项指标,决定一份试卷,就决定一个n*k(这里k=5)的矩阵[3].其中n是试卷所含的题目数,k为试题控制指标的数目.其中(i=1…n,j=1…5)表示试题库中第i道试题的第j项指标.因此组一份n道试题的试卷就是从题库中抽取n道试题,每道试题的5个属性决定一个n*5的组卷参数矩阵S一行元素的值.
组卷参数矩阵S的列元素的分布分别满足用户指定的试卷的总体要求,即试卷中各种题型的题数、所有试题的分数总和、各种难度的试题所占的分数比例、各篇章所占的分数、各种区分度的试题所占的分数比例,这5个指标都应等于用户指定的要求,或者误差最小.在实际应用中,设定个体的整卷指标f来综合反映这5个指标与用户要求的误差,由于它们的重要程度不同,所以整卷的指标f就是5个指标的加权和,为了不至于各个误差相互抵消,这5个指标与用户要求的误差都取绝对值.用下式表示:
试题库中共有600道题X1,X2,…,Xm,组卷就是从这些题中选出n道题,使得整卷指标f最小.在此,用一个600位的二进制串来表示问题解.如果F1为1则表示该题被选中,若为0则表示该题未被选中.假设该套试卷要求有n道试题,则串中有n个1.这样,一份试卷可表示为形如0101110…10的600位的二进制串.问题解本身并不直接包含试题属性,第i(i=1…n)道题的试题属性可以在组卷参数矩阵S中找到,即Xi=[ai1,ai2,…,ai5] .
为了使系统在初始搜索时,对于每一个状态空间都有平等的机会,通过随机的方法生成初始化的串群体.对一个有n*5个基因的染色体,初始种群的产生方式为从试题库里随机抽题.初始种群的规模一般由实际问题的具体性质决定,按经验或实验给出.在实际组卷中,将群体规模设为n,每个个体都是通过random(m)这个随机函数在1至600中随机选择n道题,其中600为题库中试题的题量.
初始化过程如下:
fori=1topop_sizedo
random(600),随机生成第i个染色体形式的初始试卷
end
首先通过解码,得到个体的组卷参数矩阵S.具体过程如下:根据串F1F2…F600的值,可知试卷中包含的试题的题号,然后把这些试题的属性写到组卷参数矩阵S中,然后调用适应度评估函数计算个体适应度.这里通过计算个体的整卷指标f来反映个体的适应度.根据自动组卷的要求,希望组成的试卷各种性能指标最接近用户的要求,即整卷指标f越小,个体的适应度越高.
选用最优个体保留选择策略,即采用最优个体保留和轮盘选择的方式进行.根据适应度对群体中的个体排序,依据每个个体的适应度的高低决定个体进入到下一代的概率.种群中最优个体直接复制到下一代中,其他个体通过轮盘法进行选择.该方法既可以保证优良品种的个体得到更多的繁殖机会,又能在一定程度上防止少数几个优良品种由于过度繁殖而控制整个种群,使得算法陷入到局部最小.
采用列优先编码的单点交叉算子,交叉点的位置随机地在第三列到第五列之间选取,这样可以保持知识单元和题型属性不变.先在群体中随机地选择两个串,然后对每对串随机地在第三列到第五列之间选择一个交换点.如果交换概率pc满足random(1) 变异算子的选用上使用均匀变异.对交叉后种群中个体Xi随机产生一个0至1之间的随机数,若大于突变概率p600,则保留原染色体的性状不变;否则在组卷参数矩阵S中使用随机方式在试卷中抽选出一行,得到这道试题的题型属性.然后在试题库中随机选择一道同题型的题目,替代变异的个体.这里较小可小于0.001. 每个问题的解(个体)进行遗传操作以后,可能变为非法,比如串经过交换或变异后,串中1的个数可能大于或小于n,这时这个串对应的解就是非法的,须对解进行处理.这里采用拒绝方法[5-6],直接抛弃进化过程中产生的所有不可行解. g=g+1,g为进化的代数,并按照第3步的方法计算当前群体的每个个体的适应度,如果g等于指定的进化代数,或者某个个体的适应度达到要求就退出,否则转第4步继续执行.该算法要经过至少320次迭代算法才能生成满意的试卷,有时还会出现震荡,特别是最后收敛速度缓慢. 操作采用基因换位算子实现爬山操作的方法如下: ①在个体中随机选择两个基因交换它们位置. ②判断基因换位后其适应度是否增加,若适应度增加,则以换位后的个体取代原个体. ③重复步骤①②到达到一定的交换次数为止. 由于遗传算法不是自动终止,因此无法得知该算法是否已经收敛到极值点.为此可以修改终止条件为:①出现种群满足f=0要求的;②当第g代与第g+1代全体中最大适应度个体的适应度满足如下条件时说明遗传算法进化效果已不明显,停止遗传操作. 实验表明一般迭代250代左右就能生成满足符合要求的试卷.该改进的遗传算法实现了全局并行搜索,搜索空间较大,并且搜索过程中不断向可能包含最优解的方向调整搜索空间,从而易于找到最优解,能有效的解决试题库的智能组卷问题,它特别适合分A卷,B卷甚至C卷的情况. [1] 王小平,曹立明.遗传算法—理论、应用与软件实现[M] 西安:西安交通大学出版社,2002:69-87 [2] 杨路明,陈大鑫.改进遗传算法在试题自动组卷中的应用研究[J] .计算机与数字工程,2004,32(5):76-79 [3] 余胜泉,何克抗.网络题库系统的设计与实现[J] .中国远程教育,2000(9):53-57. [4] Gen M,Cheng R.遗传算法与工程优化[M] .予歆杰,周根贵译.北京:清华大学出版社,2004:83-86. [5] Michalewicz Z.Genetic algorithms,numerical optimization,and constraints[M] .1999:151-158. [6] 陆亿红,柳红.基于整数编码和自适应遗传算法的自动组卷[J] .计算机工程,2005,31(23):232-233.2.6 变异
2.7 非法解
2.8 判断终止条件是否满足
2.9 采用基因换位算子实现爬山
2.10 近似满足