改进的混合遗传算法的组卷系统模型及算法.pdf

《改进的混合遗传算法的组卷系统模型及算法.pdf》由会员分享，可在线阅读，更多相关《改进的混合遗传算法的组卷系统模型及算法.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、?第 27卷 第 1期2009年 2月?贵州师范大学学报(自然科学版)JournalofGuizhou Nor malUniversity(Natural Sciences)?Vo.l 27.No.1Feb.2009文章编号:1004?5570(2009)01-0085-05改进的混合遗传算法的组卷系统模型及算法*罗?佳,张仁津*,张贵明(贵州师范大学 数学与计算机科学学院,贵州 贵阳?550001)摘要:在基本遗传算法基础之上,针对试题库组卷系统对算法进行改进,设计了一种运用于组卷系统的数学模型和混合遗传算法,从而提高组卷质量和系统的通用性。关键词:遗传算法;组卷系统;混合遗传算法;算法;模

2、型中图分类号:TP301.6?文献标识码:AResearch ofmodel and algorithms of test paper generationsystem of i mproved hybrid genetic algorithmsLUO Jia,ZHANG Ren-jin,ZHANG Gu-im i ng(School ofM athematics and Co mputer Science,GuizhouNormalUniversity,Guiyang,Guizhou 550001,China)Abstract:This article i mproved algorithm

3、s of test paper generation syste m on the basis of basic geneticalgorithms,and designed one kind of model of mathematics and hybrid genetic algorith m s applied ingeneration system of test paper.It can i mprove the quality of test paper and the versatility of systemconsequently.Key words:genetic alg

4、orithms;generation system of test paper;hybrid genetic algorith m s;algo-rithm s;model0?引言遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它非常适合解决多目标优化的群体搜索问题,具有简单、鲁棒性强、全局寻优等特点。组卷是从题库中抽取出满足用户要求的试题生成试卷,要求试卷在知识点、题型、难度等方面达到用户需求。而试卷各约束条件之间又是相互制约的,即组卷是一种多目标优化问题,因此用遗传算法实现组卷可取得良好的效果。用遗传算法进行组卷已不是一种新兴的技术,实际上一些学者已经

5、开发出基于遗传算法的组卷系统。这些系统普遍能在可接受的时间内成功生成具有一定质量的试卷。这些系统的实现为后人的研究奠定了基础,研究者功不可没,但笔者认为很多系统仍有一定缺陷。如文献 1中,作者提出的适应度函数公式 f=10?c+?t+50?q+40?r+85*收稿日期:2008-09-25基金项目:贵州师范大学学生科研基金资助。作者简介:罗?佳(1978-),女,贵州省贵阳市人,讲师,在读研究生,研究方向:计算机辅助教育、人机交互和智能计算等。*通讯作者:张仁津(1963-),男,教授,研究方向:计算机辅助教育,软件理论与应用等。0.25?ni=1Ei,其中的系数是在实验中获得。这类系统对试题

6、库的依赖性较大,若题量及难度等属性值分布改变,组卷效果不一定理想。又如文献 2中作者将试题属性设为题型、考查点、难度系数和题分,笔者认为较少的试题属性对提高组卷速度较有利,但试题属性太少又不能全面反映试题质量,从而影响组卷的客观性、科学性及试卷质量。为此,笔者考虑从增强系统通用性及生成试卷质量两方面建立组卷系统模型,以此来改进基于遗传算法的组卷系统。1?基本遗传算法(SGA)SGA首先生成一定规模的初始种群,接着个体以一定的概率进行交叉、变异,实现个体结构重组,再按预设的评价函数选择复制优秀个体组成新一代种群,循环该过程,直到找到满足条件的最优解。其算法如下:(1)群体编码;(2)生成初始群体

7、;(3)群体中个体适应度设计及计算;(4)对个体进行选择、交叉和变异操作;(5)计算新个体的适应度值;(6)判断是否满足退出循环的条件,若找到满足条件的解或达到最大循环次数则结束循环;否则转向(4)继续循环。因此基本遗传算法可定义为一个 8元组:SGA=(C,E,P0,M,?,?,?,T)其中 C为个体的编码方法;E 为个体适应度评价函数;P0为初始群体;M 为群体大小;?为选择算子;?为交叉算子;?为变异算子;T 为算法终止条件。2?组卷问题的数学模型已开发出的众多遗传算法组卷系统不具备通用性是因为,对遗传算法控制参数的选择目前还没有合理的理论依据,在遗传算法的实际应用中,需要经多次试算才能

8、确定这些参数合理的取值大小或取值范围,而开发者又是基于特定数据库进行测试获得控制参数值,因而不具备通用性。为了使系统具有一定的通用性,即组卷不依赖于特定题库,这就要求控制参数值和数据库中各种题型题量、试题属性值无太大关系。这也需要反复实验来确定控制参数取值大小,所不同的是,本系统的数据库构造要求试题具备一定规模和完备性(即题型、题量、各题型试题属性分布在一定范围内),且用户输入的约束条件与题库中试题满足一定比例,就可生成科学合理的试卷。为了生成高质量试卷,题库中的试题属性应尽可能包含影响组卷质量的属性。在此,我们给定以下的约束条件,包括:分值、知识点、难度、区分度、曝光度、最后一次抽题时间、答

9、题时间。这 7项属性就决定了一套试卷的属性分别用 a1 a7表示,若一套试卷有 m 道试题,则决定一份试卷的指标可用一个 m?7的矩阵表示如下:S=a11?a12?a17a21?a22?a27?am 1?am 2?am7这是问题求解的目标状态矩阵,该矩阵应满足如下约束条件:(1)试卷总分 sjzf=?TXi=1ti,应尽可能满足用户给定的试卷分数约束,其中 ti表示第 i种题型的实际分值,TX 表示试卷中的题型数;(2)试卷知识点 sjzsd=?ZSDi=1ai,其中 ai表示试卷中包含的第 i个知识点的实际分值,ZSD为试卷知识点的总数;(3)试卷难度 sjnd=1-?mi=1(1-ai3)

10、?ai1)/?mi=1ai1,应尽可能满足用户给定的试卷难度值。在此,试卷难度分成 5 个级别:容易(0 0?2),较容易(0.2 0.4),中等(0.4 0.6),较难(0?6 0.8)和难(0.8 1.0);(4)试 卷 区 分 度sjqfd=?mi=1(ai4?ai1)/?mi-1ai1,应尽可能满足用户给定的试卷区分度值。试题区分度一般是由该题的成绩与整个测验成绩之间的相关程度来表示。相关度高,表明区分度高;相关度低,表明区分度低。经过大量的研究,伊贝尔的分组法区分度指标提出了一种评价标准:区分度在 0.4以上的,评价最高,在 0.30 0.39为较好;在 0.20 0.29为尚可,使

11、用时需作改进;在86?贵州师范大学学报(自然科学版)?第 27卷?0.19以下的为劣,需要淘汰或加以修改。因此把区分度分成 3个级别:0.20 0.29、0.30 0.39和0.4以上。(5)试卷曝光度 sjbgd=?mi=1ai5/m,应尽可能小。曝光度用整数表示,试题库中试题曝光度初始值为 0,组卷选中的试题曝光度增 1,系统预设一最大曝光度值,当试题曝光度值达预设值时,曝光度值不再增加。(6)试卷中试题最后一次抽题时间 sjctsj=?mi=1ai6/m,该值应尽可能小。最后一次抽题时间用整数表示,试题库中试题的最后一次抽题时间初始值全为MT(预设的最大值),每生成一次试卷,被抽取的试题

12、该属性值被置为 0,其它未被抽取的试题该属性值通通增 1。若某试题该值已为 MT,则该题对应的曝光度值被置为 0。(7)答题时间 sjdtsj=?mi=1ai7,应尽可能满足用户给定的试卷答题时间约束。3?组卷问题的数学求解?遗传算法改进思想3.1?个体的编码纵观前人研究成果,利用遗传算法进行组卷常见的编码方案有两种:二进制编码和实数编码。利用二进制编码在进行交叉和变异时非常方便,但由于二进制编码串过长、搜索空间过大,在组卷中采用效率较低。本文采用分段实数编码方法,即将试卷按题型分别用实数进行编码。从前人的研究成果看,这种编码方案适用而有效。3.2?适应度函数适应度函数值是评判个体(试卷)优劣

13、的指标,也是指引遗传算法搜索方向的信息。为方便衡量个体优劣,我们将上述试卷各指标与对应目标值求差值分别得到 x1、x2、?x7如下:x1=?TXi=1(|ti-Ti|/Ti)x2=?ZSDi=1(|ai-Ai|/Ai)x3=|(1-?mi=1(1-ai3)?ai1)|/?mi=1ai1)-ND|x4=|?mi=1(ai4?ai1)/?mi-1ai1-Q|x5=(?mi=1(ai5/BG)/mx6=?mi=1|ai6-MT|/(m?MT)x7=|?mi=1ai7-DT|/DT其中 Ti表示试卷的第 i类题型的目标分值,Ai表示试卷第 i个知识点的目标分值,ND 表示试卷难度目标值,Q 表示试卷区

14、分度目标值,BG 表示试卷规定的最大曝光度值,MT 为系统设定的最后一次抽题时间的最大值,DT 表示试卷答题时间的目标值。于是适应度函数 fi可以定如下:fi=1/(1+?7i=1xi?di)?其中 di表示第 i项指标的权值。由 fi的定义可得到,fi越大,个体适应性越强,试卷越接近组卷目标。3.3?遗传算子根据个体编码方案,为不破坏种群已满足的题型、题量等约束条件,在交叉时,我们采用段内交叉方法。简单遗传算法中,交叉后的两个子代个体取代两个父代个体,没有考虑子代个体与父代个体的优劣情况。为此,我们进行改进,在交叉后的个体选择上,我们采用最优保存策略和比例选择(赌盘选择)相结合的方式进行。比

15、例选择操作如下:(1)计算群体总的适应度 F=?Nk=1eval(Fk);(2)计算每 个个体 Fk的选 择概率 Pk=eval(Fk)F;(3)计算每个个体的 Fk的累计概率 QK=?Kj=1Pj;j=1,2,?,K=1,2,?,N;(4)产生一 0 1之间的随机数 r,若 Qk?r Qk+1,则选择 Fk进入下一代群体。(5)重复(4),直到生成 N 个个体结束选择。3.4?最优保存策略最优保存策略模型 3操作如下:(1)找出当前群体中适应度最高个体和适应度最低个体;(2)若当前群体中最佳个体的适应度比总的迄今为止的最好个体适应度还高,则以当前群体中的最佳个体作为新的迄今为止的最好个体。8

16、7?第 1期罗?佳,张仁津,张贵明:改进的混合遗传算法的组卷系统模型及算法?(3)用迄今为止的最好个体替换掉当前群体中的最差个体。这种策略能保证保留迄今为止最优个体,可保证算法的全局收敛。而对当前群体的产生,可以有两种方法:(1)迄今为止最优个体不参与交叉和变异操作;(2)迄今为止最优个体要参与交叉和变异操作。最优个体在参与交叉和变异时,可能破坏掉较优模式,从而减慢收敛速度,也可能更加靠近局部最优解。因此,本算法将父代群体暂时保存的同时(包括迄今为止最优个体),将父代群体的所有个体进行交叉和变异操作得到当前群体。比较当前群体的最优个体和迄今为止最优个体,若当前群体的最优个体比迄今为止的最优个体

17、更优,则交换两个体位置。这样做既保证算法最终得到的是历代的最优个体,同时可防止算法早熟和搜索缓慢。3.5?小生境遗传算法基于预选择机制(Preselection)的小生境方法的基本思想是只有当新产生的子代个体的适应度超过其父代个体的适应度时,所产生的子代个体才能替换其父代个体而遗传到下一代群体中,否则父代个体仍保留到下一代群体。因此本文只对父代个体与子代个体进行比较,将编码结构相似的个体替换,从而有效维持群体的多样性,并造就小生境的进化环境。计算父代N 个个体与当前代的 N 个个体两两组合的海明码距:?xi-yj?=?ChromLenk=1(xi-yj)2?其 中i=1,2,?,N,j=1,2

18、,?,N,xi为父代第 i个体,yj为当前代第 j个体。当?xi-yj?L(L为最小海明码距)时,比较个体 xi与 yj的适应度大小,并对适应度较低个体处以罚函数:Fm i n=penalty,其中 penalty为一很小正数,使其适应值变小,遗传到下一代的概率减小;3.6?遗传-突变算法 4为进一步有效防止在进化过程中,局部最优解迅速占据种群,本文采用遗传-突变算法,即在连续数代的最佳个体没有任何进化时,实施灭变,对其处以罚函数;同时,将父代与当前代的所有个体按适应度值从大到小排序,将中间个体(第 N+1个)的适应度值与第一个体适应度值进行比较,若中间个体适应度值小于第一个体适应度的千分之一

19、,则对第 N+1 2 N 个个体实施突变,增大其变异概率并实施变异操作,得到新的 N 个个体。3.7?遗传算法的控制参数文献 3中表明种群数量一般取 20 100,终止代数一般取 100 150,交叉概率一般取 0.40?99,变异概率一般取 0.000 1 0.1。在此基础上,本文作如下改进:(1)交叉变异算子遗传算法中的交叉概率 Pc和变异概率 Pm对算法性能有重要影响,若 Pc与 Pm过大,可能使算法变为随机搜索;若 Pc太小,会使搜索过程缓慢,Pm太小,则不易产生新个体,可能使算法早熟,陷入局部最优。为加快算法的搜索效率并防止陷入局部最优,应根据个体的优劣动态调整 Pc与 Pm,于是本

20、文采用自适应交叉、变异概率,公式 6如下:Pc=Pc1,f?favgPc1-(Pc1-Pc2)(f?-favg)fmax-favg,f?favgPm=Pm 1,f favgPm 1-(Pm1-Pm 2)(fmax-f)fm ax-favg,f?favg其中,fmax为群体中最大适应度,favg为群体的平均适应度,f?为要交叉的两个个体中较大的适应度值,f 为要变异个体的适应度值,Pc1=0.9,Pc2=0.6,Pm 1=0.1,Pm2=0.001。根据公式,适应度高于群体平均适应度的个体,有较低的 Pc与 Pm,该个体受到保护;对低于平均适应度的个体,有较高的 Pc与 Pm,使该个体交叉变异可

21、能性增大。(2)循环终止条件满足以下条件之一即可终止循环:?达到最大循环次数;?群体中最优个体适应度与目标值之间的误差小于某一个极小的阈值;?连续几代个体平均适应度的差异小于某一极小的阈值。4?基于改进遗传算法的组卷算法设计仿照自然界生物遗传,父代群体生存下来就有交叉、变异的权利,本算法采用先交叉、变异,后根据父代及子代的适应度值选择生成下一代群体。同时,为有效防止进化初期生成适应度较高个体及88?贵州师范大学学报(自然科学版)?第 27卷?与该个体模式相似的多个个体,而迅速占领搜寻群体规模并产生早熟,在此,本文引入小生境技术及遗传-灭变算法形成混合遗传算法。改进遗传算法如下:确定参数:最大代

22、数MaxGen,群体规模 N,交叉概率 Pc,变异概率 Pm;接受用户的组卷要求;产生初始群体;当前代数 gen=0;计算群体中各个体 F 的适应值 eval(Fk),k=1,2,?N,按适应值从大到小排序为 F1、F2、?、FN,并记录下最大适应值及对应个体;W hile(gen M axGen&迄今为止最优个体的适应度值未达到要求)将 N 个个体两两配对,进行交叉操作得到群体 F?;将 N 个个体实施变异操作得到群体 F?;计算 F?中个体的适应度值并按降序排列;比较迄今为止的最优个体与 F?中的最优个体,若 F?的最优个体更优,则交换两者位置,将 F?中的最优个体视为新的迄今为止的最优个

23、体;i=0;j=0;W hile(iN)?While(jN)?If(hai m ing i+1,j+1 L)?比较 Fi与 F?j的适应度大小,对其中适应度较低的个体处以罚函数;?j+;i+;将 2 N 个个体按适应度大小降序排列;If(第 N+1个个体的适应度值小于第 1个个体适应度值的千分之一)对第 N+1 2 N 个个体实施突变操作;If(连续几代的最优个体没有任何进化)将当前代最优个体实施灭变;将新的群体视为 F?k(k=1,2,?,2 N),并按适应度值大小降序排列;选择 2 N 个个体中的N 个生成下一代群体;输出当前代数,群体的平均目标函数,及迄今为止的最优个体;If(连续几代个

24、体平均适应度的差异小于某一极小的阈值)跳出循环;Gen+;输出迄今为止的最优个体的编码,计算各章节分数、各难度级别的分数等指标,输出这些指标的值与用户的要求值相比较。5?结束语组卷是组成一份误差在可接受范围内的、各项属性允许有一定误差的试卷,而并非要求试卷一定全局最优。本文在构建了组卷问题的数学模型之后,根据组卷实际问题对遗传算法进行了改进,设计了一种基于混合遗传算法的组卷算法。该算法能避免早熟和搜索缓慢现象,并可提高组卷效率及试卷质量。参考文献:1 周文举.基于遗传算法的自动组卷系统研究与实现D.山东师范大学硕士学位论文,2006.2 周红晓.遗传算法在试题库智能组卷中的应用 J.浙江师范大

25、学学报(自然科学版),2003,26(4):374-378.3 周明,孙树栋.遗传算法原理及应用 M.北京:国防工业出版社,2002.4 雷英杰,张善文,李续武,等.M atlab遗传算法工具箱及应用 M.西安:西安电子科技大学出版社,2005.5 王淑佩,易叶清.基于改进自适应遗传算法的组卷研究 J.科学技术与工程,2006,6(4):468-473.6 陆亿红,柳红.基于整数编码和自适应遗传算法的自动组卷 J.计算机工程,2005,31(23):232-233.7 魏平,熊伟清.求解标准化组卷问题的单亲遗传算法 J.计算机工程与科学,2004,26(12):57-60.8 赵金帅,鲁瑞华.一种用于防止早熟收敛的改进遗传算法 J.西南大学学报(自然科学版),2008,30(1):156-159.89?第 1期罗?佳,张仁津,张贵明:改进的混合遗传算法的组卷系统模型及算法?