本站原创西南交通大学
本科毕业设计(论文)
智能组卷的数学模型和算法分析
专业:信息与计算科学
指导老师:赵海良
年级:2004级
学号:20043563
姓名:李莹芳
2016年5月
SouthwestJiaotongUniversity
BachelorDegreeThesis
MATHEMATICMODELOFTEST
PAPERAUTO-GENERATIONANDALGORITHMANALYSIS
Specialty:InformationandComputingScience
Supervisor:Prof.ZhaoHailiang
Grade:2004
AcademicDegreeAppliedfor:Bachelor
Candidate:LiYingfang
May.2016
院系数学系专业信息与计算科学
年级2004级姓名李莹芳
题目智能组卷的数学模型和算法分析
指导教师
评语
指导教师(签章)
评阅人
评语
评阅人(签章)
成绩
答辩委员会主任(签章)
年月
毕业设计(论文)任务书
班级计算一班学生姓名李莹芳学号20043563
发题日期:2016年2月10日完成日期:5月30日
题目智能组卷的数学模型和算法分析
1,本论文的目的,意义:随着当今教育的发展,现代考试对试卷的测量学特性要求越来越严格,不仅要在考核的内容范围,能力层次方面符合事先指定的要求,而且平均分,考试时间,区分度等方面也要符合要求.同时,如何做到高效,经济,灵活,及时编出需要的试卷也显得尤为重要.在试题编制过程中,组卷算法起着举足轻重的作用.它的优劣直接影响组卷的质量和成功率.从题库建设和组卷算法的发展来看,目前还没有一种比较完美的试题生成办法.设计一个算法从试题库既快又好地抽出一组最符合考试要求的试题,一直是有关科研工作者不断探索的课题.
本文应在详细分析组卷评价体系的基础上,拟提出一个智能组卷的数学模型,并结合当前存在的组卷算法,拟组建一个改进算法用于组卷问题.拟考虑以遗传算法所涉及的初始种群的优化,适应度函数的设计,个体编码的改进以及交叉算子和变异算子的自适应性等方面予以改进,缓解全局优化中容易出现早熟和收敛速度慢的问题,设计一种较优的算法用于组卷过程,提高组卷的成功率.
2,学生应完成的任务(1)掌握测量学相关知识,(2)学习组卷的相关知识,弄清组卷流程,(3)总结目前常用的组卷算法,了解它们的实现过程,归纳它们的优缺点,(4)解决组卷问题的建模方法,在此过程中,提高分析解决问题的能力,(5)学习遗传算法,熟悉算法的具体步骤和实现过程,详细说明对算法的改进方法,(6)查找相应的资料文献,完成论文.
3,论文各部分内容及时间分配:(共16周)
第一部分查阅资料及相关文献,进行整理.(2周)
第二部分学习测量学和组卷的相关知识.(3周)
第三部分构建组卷的评价体系和数学模型,学习遗传算法.(4周)
第四部分根据遗传算法的实现过程对它的几个步骤进行改进.(2周)
第五部分修改论文和制作答辩时文档.(3周)
评阅及答辩(2周)
备注毕业论文的内容可有所变动,但论文的主要方面应与本论文题目相关.
指导教师:年月日
审批人:____年月日
摘 要
组卷问题是一个在一定约束条件下的多目标参数优化问题,采用传统的数学方法求解十分困难,自动组卷的效率和质量完全取决于试题库的设计以及抽题算法的设计.如何设计一个算法从试题库既快又好地抽出一组最符合考试要求的试题,是本文研究的目的.
目前已出现多种算法用于自动组卷,如随机抽取策略,回溯试探策略,遗传算法等.这些算法在大的解空间,多峰值的问题上往往容易陷入局部最优或算法复杂度过高.由于自动组卷要求生成的试卷能最大程度地满足用户的不同需要并具有随机性,合理性.因此,必须寻找更加行之有效的算法.在对国内外大量相关文献分析研究的基础上,本文研究了一种改进的遗传算法及其在组卷中的应用.
本文首先对试题生成策略的研究背景进行了比较系统的总结,详细分析了试题生成过程中试卷的各项约束条件.文中重点分析了试卷的评价指标,各项指标的作用及几个重要指标间的关系.在这些知识的基础上采用各个评价指标的分布构建了成卷模式,并根据成卷模式定义了评价试卷质量的偏好关系,建立组卷数学模型,并对模型进行简化处理.
其次,详细介绍了改进遗传算法应用于组卷问题的解决步骤,涵盖了其中的各项关键技术:包括组卷策略,编码方案,适应度函数的确定,选择交叉变异算子,遗传算法的实现等.
最后,依据自动组卷问题的特点,本文采用分组自然数编码,减少了染色体长度空间,编码直接采用试题编号,省去了编码和解码的繁琐.利用这种方式,在编码时就可以解决在试题生成问题中题型及各题题量大小这两个约束条件,简化了求解的问题.将初始化的试卷随机抽取两份进行配对,采用有条件的"顺序交叉",在染色体交叉和变异改进中采用相同题型组内的单点交叉变异.
关 键 词:试题库组卷适应度函数改进遗传算法
ABSTRACT
Thetestpapergeneratingisanoptimizedproblemtomulti-objectiveparameterwithcertainrestriction.Theoptimizationisimplementedverydifficultlybytraditionalmethod.Thequalityandefficiencyofauto-generatingtestpaperisalldeterminedbythetestquestions-databasedesignsandgetproblems-termsalgorithm.Theaimoftheresearchistodesignanalgorithmthatcangetagroupoftestproblemtermsquickly,whichfittherestrictionoftestrequirement.
Severalalgorithmshebeenappliedintestpaperauto-generation,suchasrandomizationstrategy,traceandtrialstrategy,geicalgorithmandsoon.Whenencounteringwithbigsolutionspace,multimodalproblems,thesealgorithmsareusuallyinclinedtorunintolocalextremiordifficulttosolve.Sincegeneratedtestpaperneedstofulfillvariabledemandwithgreatrandomnessandrationality,amoreeffectivealgorithmisingreatdemand.Agreatdealofarticlerominsideandoutsideanalyzed,thethesisistodevelopanimprovedgeicalgorithm,andapplythealgorithminthetestpaperauto-generationproblem.
Aboveall,thisthesissystemicallysummarizestheresearchbackgroundofauto-generatingtestpaperstrategy,detailedlyanalyzesallkindsofconstraintconditionsduringtheprocessofauto-generatingtestpaper.Thisthesiocusesontheanalysisofthepapersofevaluationcriteria,indicatorsandtheroleofseveralimportantindicatorsoftherelationshipbetweenthem.Intheknowledgebaseontheuseofindicatorsconstructeddistributionmodelintovolumes.Accordinolumeandpatterndefinitionintotheevaluationofthequalityofthepaperspreferences,weestablishamathematicmodeltogeneratetestpaperandsimplifyit.
Secondly,thisthesisdetailsontheimprovedgeicalgorithmusedingeictestpaperstepstosolvetheproblem,coveringoneofthekeytechnologies,includingtheestablishmentoftestpaperstrategy,codingprograms,fitnesunctionidentification,choiceofcrossoverandmutationoperator,geicalgorithmrealization.
Finally,aimingatthecharacteristicofautomaticgeneratingtestpapersystem,thisthesiakesuseofthenationalcodewhichisusedinthegeicalgorithminordertodecreasespaceofchromosomes.Thiscodingstylecanresolvetwoconstraintconditionsofquestionsortsandquestionquantitiesduringcodingandsimplifytheproblemofdrawingtheresults.Theinitializationtestpaperwillbeselectedtwotomatchrandomization,usingthecondition"ordercrossover",andone-pointcrossovermutationofthesametopicgroupinthechromosomecrossoverandmutationimproved.
Keywords:itembank,paper-design,fitnesunction,improvedgeicalgorithm
目录
第一章绪论1
1.1研究的背景和意义1
1.2计算机智能组卷中要解决的重要问题2
1.3本文的主要工作3
第二章组卷的评价体系与建模5
2.1组卷的基本原则5
2.1.1试卷信度和效度5
2.1.2组卷的基本原则7
2.2组卷策略7
2.3组卷步骤8
2.4试题参数及其说明9
2.5组卷的数学模型12
2.6组卷过程的难点及其解决办法18
第三章常用组卷算法介绍20
3.1随机抽题成卷算法20
3.2自动成卷算法20
3.3倒塔式收缩成卷算法21
3.4回溯试探成卷算法21
第四章遗传算法在组卷中的应用22
4.1遗传算法22
4.1.1遗传算法概述22
4.1.2遗传算法的基本思想22
4.1.3遗传算法的特点23
4.1.4构成遗传算法的基本要素23
4.2采用传统遗传算法的组卷算法24
4.3改进遗传算法的组卷算法27
4.3.1个体编码的改进27
4.3.2优化初始种群28
4.3.3个体适应度函数的自适应改进30
4.3.4选择方法的改进31
4.3.5交叉算子的自适应改进31
4.3.6变异算子的改进33
总结与展望35
致谢37
就完成了任务,并没有考虑在组卷过程中由于算法的输入可能导致组卷的试卷质量比较差.在这种情况下,应考虑将试卷的组卷效果的真实情况反馈给计算机,以便计算机能够自动地对组卷算法中的各项参数进行适当地调整,以便在下次进行组卷的时候能够提高组卷的性能.1.3本文的主要工作
本文的主要工作是鉴于组卷中待解决的几个问题,根据教育测量学理论,制定符合教育测量学理论的试题属性,首先提出组卷的评价体系,对组卷过程进行建模,接着针对现有的计算机智能组卷技术进行了深入,系统地研究,最后综合现有算法的特点,提出了改进遗传算法的组卷算法,并对其实用性进行详细地分析.本文的具体章节安排如下:
第1章介绍了计算机组卷的背景与意义,简单说明了组卷过程中面临的重要问题.
第2章对组卷的评价体系与建模进行介绍,分别阐述了组卷基本原则,组卷策略,组卷步骤,详细对试题参数进行了说明,提出了组卷的数学模型.
第3章对常用的智能组卷算法进行介绍,并分析了它们各自的应用技巧与实现过程,指出了它们的优缺点.
第4章基于现有算法的基础上,提出了改进遗传算法的智能组卷算法,算法思想是把组卷问题的解表示成染色体,通过遗传算法的几个步骤,寻求问题最优解,即符合用户要求的试卷.
结束语部分对文章进行了总结,提出了智能组卷过程中还存在的其他问题,并对论文下一步的工作进行了展望.
第二章组卷的评价体系与建模
组卷是题库建设的核心环节,它的成功率直接影响试题的质量,从而影响考试质量.所以,组卷工作的科学性建设尤为重要.组卷的科学性主要体现在代表性和针对性.代表性是指试题取样能足够反映考试内容.针对性是指试题本身编制要合理,对不同的考试对象有不同的体现.本章目标是:先根据组卷的基本原则,提出组卷策略和组卷步骤,然后详细设计了试题参数,使之易于组卷算法的操作,最后提出了组卷的数学模型.
2.1组卷的基本原则
2.1.1试卷信度和效度
1,试卷信度
信度[1]指的是测量结果的稳定性程度,简单地说就是测量结果的可信程度.如果用同一测量工具反复测量同一特质对象,则多次测量结果间的一致性程度就叫信度.各种类型的测量,无论是物理测量还是教育测量,先后向同一对象施测后,所得数值很难做到绝对一致.每次测量结果实际上包含了被测量特质对象的实际水平和测量误差两部分.如果每次测量结果中误差部分都很小,那么测量结果必然是稳定的.由于考试中测试对象的特殊性,出现测量误差的可能性更大,如考试环境,完成时限,主被试的关系,被试的动机和情绪都可能影响到考试的结果.信度在这里就是指对这种随机误差的控制.
2,影响试卷信度的因素及提高试卷信度的方法
信度是测量过程中随机误差大小的反映.随机误差大,信度就低,随机误差小,信度就高.测量过程会引起随机误差的因素,例如被试,主试,测试内容,实测情景等都会影响测量信度.这些因素有些是难以改善的,如被试者个体差异的程度,试卷内容的同质性等因素,但有些因素却是可以通过被试,主试的努力,采取相应的对策而得以改善的.
被试个体差异的程度.
被试之间的差异是指被试水平的高低程度,它在每次测量中都是难以避免的.
试卷的长度.
试卷的长度主要指试卷所包含题目的多少.题目越少,则考试得分就越容易受试题抽样偶然性的影响,因而考试信度也越低.一般情况下,加大试卷的长度就能提高考试的信度.
试卷内容的同质性程度.
一般地,内容性质相同或相近的试卷,和内容性质不同或相差较远的试卷比,前者信度往往较高,后者信度往往偏低.
试卷的难度.
试卷难度对考试的分数分布状态发生直接的影响,当考试难度过高或过低时,分数呈偏态分布.此时得分大部分集中在低分段或高分段.分数分布的范围和分数之间的差异较小,信度也就小.大量实践表明,当试题难度取值在0.3至0.7区间时,使试题难度接近正态分布,较有利于提高考试信度.
5)考试中出现的各种偶然性因素.
考试中出现的各种偶然因素也是影响信度的一个方面.可提高考试的标准化程度,减少无关因素的干扰.
3,试卷效度
效度[1],就是一次测量的有效程度,是指一个测验或量表实际能测出其所要测量的特性的程度.测验或量表是测量使用的工具,如果测量能测出其所要测的特性,我们就认为这个测验或量表是有效的.效度指标是测量质量的一个重要方面,测量工具效度太低,就失去了存在的价值.效度是反映一项考试实现其既定目标的成功程度的指标.考试效度指的是根据考试分数做出推论或预测的准确性程度,是程度上的概念.评价试卷效度的高低,主要看它达到既定目标的程度.一般来说,影响效度的因素主要是系统误差,考试内容的同质程度,应考者差异程度,试卷的长度.
4,提高试卷效度的方法
1)精心编制试卷,题目样本要能较好地代表欲测内容或结构.题目的难易程度,区分度要适当,数量适中,避免系统误差.
2)严格控制随机误差.测验实施者一定要严格按要求进行操作,指导语要清楚,尽量减少无关因素的干扰.
3)提供标准的测试环境.让被试能正常发挥水平.
4)适当增长考试的长度.
5)适当控制试题的同质程度.提高考试内容的同质程度有助于提高考试的信度,但却使效度降低了.这就要求我们"彼此兼顾",妥善处理好信度与效度的关系.Tucher研究表明,当试题取中等相关时(0.1—0.6)时,可求得相对满意的效度(0.3—0.8)和信度(小于0.9).
2.1.2组卷的基本原则
根据对试卷信度和效度的分析,可总结出组卷过程的几个基本原则:
1)组卷必须全面反映大纲的广度和深度,既要反映考生对基本知识和技能的掌握程度,又要考核考生灵活运用所学理论去分析,解决问题的能力.
2)确定好一份试卷出多少道题才符合大纲要求.由于每门课程都有重点章节和非重点章节,在决定成卷时,重点章节应多出题,反之,应少出题.同时,要避免试题重复出现.
3)在组卷时,应考虑试题类型的多样化,以考查考生的综合能力.
4)试卷难度分配要恰当.难度太大或太小会降低试题的区分度.若试题太容易,难以激发考生的积极性,若太难,超出考生的能力,易使考生失去信心.对于不同类型的学生,试卷的难度也应有所不同.
总之,要按照用户指定的考试目的,考试范围,考试时间,考试期望平均分组卷.
2.2组卷策略
题库建成后,系统根据用户输入的参数抽出最适合参数要求的试题,组成试卷,定义这种查询参数以及对这些参数进行变换算法,称为组卷策略[15].组卷策略的实质是将直观明了的组卷参数变换成计算机能直接操作的试题属性项,然后根据这些属性项,在题库中抽题组卷.
组卷问题就是从题库中选择满足所有组卷要求的试题子集.从题库中组出满足要求的试卷,取决于题库的结构,组卷策略,成卷算法的优劣.组卷策略的优劣取决于所选取的抽题算法及相关的约束条件,前者是提高组卷速率的保证,后者是确保组卷符合用户要求的重要因素.
在组卷策略中,并不是随意输入参数,参数必须符合用户组卷目标中各个约束条件的要求.
2.3组卷步骤
组卷就是按照给定的组卷策略,从题库中抽取适当的题目组成一份符合要求的试卷.在一般的考试中,组卷的过程应遵循以下几个步骤来组成一份有效的试卷.
(图2-1)组卷步骤
根据上图组卷分为以下几步:
1)确定考试知识点的范围,即考的章节范围.分清哪些知识点是重点,哪些是只要求了解就可以的.
2)确定试卷包含哪几个题型.
3)确定各题型的题量和完成整个考试的时间.
4)确定试卷的结构,就是按章节的重要程度确定各章节在试卷中的比重,即各知识点在试卷中的分值比例.
5)确定试卷难度和区分度,这一步骤很关键,它们的选取会影响到整个考试的信度和效度.
6)确定与调整各题的分值,是指在试卷组卷允许的误差范围内进行调整,以使分数趋于合理化,以便于对学生的分数进行统计并做出合理的评价,同时满足用户的要求.
2.4试题参数及其说明
试题参数是对试题属性及其在考试中的功能进行的定性或定量的描述.它的设计应符合以下要求:(a)易于抽题算法的操作.(b)利于提高组卷效率.(c)全面反映试题的特征.题库用于存放各试题的参数,各字段为试题编号,题型,难度系数,所属知识点,区分度,度,分值,估计时间,选中时间,试题内容,试题答案,标志位.
(表2-1)试题参数结构
字段名类型说明试题编号整型每一道试题有唯一编号题型整型该题属于的类型难度系数浮点型该题的难度所属知识点字符型该题的具体考核内容区分度浮点型区分各水平的考生度整型试题被选中的次数分值整型该题的分值估计答题时间整型该题的答题时间选中时间日期型该题组卷时被选中年份试题内容指针型题目内容试题答案指针型题目答案标志位整型标记题目是否被选中
试题内容类型文字内容字符型图形内容指针型(指向图形文件)
试题答案类型答案内容字符型答案图形内容指针型(指向图形文件)下面分别予以说明:
1)题型
将试题类型划分为五种题型:①填空题.②判断题.③选择题.④简答题.⑤综合题.用0～4分别代替这五种类型的题型,在组卷初始化时,根据知识点的约束条件,从总题库中选出符合知识点条件的试题,并对不同的题型建立各自的成卷试题数据库表.这样在进行组卷时,每种题型的试题就会定位在自己的符合出题要求的库表中搜索,减小了搜索范围,加快了搜索速度.
2)试题编号
试题编号分为总库编号和成卷分库编号.在组卷初始化前,试题有一个编号,我们称之为总库编号.总库编号不参与运算,只作为试题标记,初始化时,在内存中生成DataSet数据库,并形成5个DataTable数据表,分别表示5种题型.试题在DataTable数据表中按顺序重新编号,我们称之为分库编号.分库编号具有与每一道试题一一对应的性质,在遗传算法中直接作为基因编码参与运算.
(表2-2)从总库中选出的填空题的数据表
分库编号题型难度系数知识点区分度度分值估计时间选中时间标志位000.6AAA0.81212016-4-231100.5ABA0.52222016-3-200200.2BBA0.4023Null0等等等等等等等等等等等等等等等等等等等等3)所属知识点
知识点即试题的具体考核内容.知识点的划分按章节和内容从上到下分为3个层次,每一层最多可划分为26个知识点,用字母A到Z表示.例如:AAB表示第一章第一节第二个知识点.BBC表示第二章第二节第三个知识点.当知识点编码不足3层时,后面用X表示.知识点数据以字符型存放在试题记录中.
4)难度系数
在试卷命题过程中,针对不同的考试对象,不同教学阶段的考试,命题难度也不同,根据成卷要求,对难度系数进行搜索,得到符合考核难度要求的试卷.试题难度是指全体被试者对该题的失分率,计算公式[1]:
(2-1)
其中,为试题的难度系数,为全体被试者在该题上得分的平均数,为该题题分.越大,越小,当等于,等于0,越小,值越大,当等于0时等于1.的取值范围是:.
由于难度系数对不同层次的考生及在不同的教学阶段相差很大(例如学习完立即测试和两个月后测试),为了使难度系数更客观反映考生的情况,可以设计出一种试题难度调整算法.该算法的思想是:题目入库时,由教师的教学经验预估试题的难度系数,以后,根据每次考试的反馈,及时调整试题的难度系数,使其更接近试题的真实难度[6].预估难度系数的四个层次:A类,容易,答对率在70%以上,难度系数小于0.3.B类,中等偏易,答对率50%~70%,难度系数处于0.3~0.5之间.C类,中等偏难的试题,答对率为30%~50%,难度系数处于0.5~0.7之间.D类,难题,答对率在30%以下,难度系数大于0.7.对于难度过高或过低的题,组成的试卷区分度低,所以一般考试试题平均难度应控制在0.5左右,这样的试卷成绩分布才能符合正态分布.而竞赛试题却适合抽取平均难度较高的试题.
5)试题区分度
题目的区分度也叫题目的鉴别力,它是由被试者在该题上的得分与被试者的实际能力水平之间的关系来确定的,是衡量题目对不同水平被试者的心理特质的区分程度的指标.试题的区分度一般是由该题的成绩与整个测验成绩之间的相关程度来表示.相关程度高,表明区分度高,相关程度低,表明区分度低.一般来说,求取试题区分度的方法,是计算被试在该题上的得分跟试卷总分的相关系数.其计算公式[1]为:
等于(2-2)
为试题i的区分度,为试题的答对率,为答错率为答对第i题的被试者总分的平均数,为答错第i题的被试者总分的平均数,为全体被试者总分的标准差.
为了给区分度的高低确定一个评定标准,经过大量研究,伊贝尔(R.L.Ebel)提出了试题区分度评价表:(表2-3)
区分度值对试卷的评价0.4以上优良0.3~0.39合格0.2~0.29勉强可以使用0.2以下应该淘汰6)度
度即试题被选中使用的次数.在题库中,它指该题最后一次被使用的试卷流水号.度值越大,下次该题再次被选中的概率就要越小.相反,度值越小的试题下次再次被选中的概率越大.我们还可通过试题难度的变化程度控制试题的度,如果题目难度明显向容易的方向变化,就会考虑停止使用该题.以一道题的率与总组卷数比较来决定是否选用该题.
7)最近出题时间
为避免相同试题在规定的时间内多次使用,抽取试题时,需要考虑题目最近使用日期..
8)估计答题时间
完成该题所需的时间.在该时间内大多数学生能完成并有时间检查该题,数据类型为整型,单位为分钟.该项数据可通过客观测试后由教师根据教学经验加以调整.
9)试题内容
表示试题的内容,它不参与组卷的运算.
10)试题答案
表示该试题的标准答案,不参与组卷运算.
11)标志位
用于组卷过程中区分可选与不可选试题,0表示可选,1表示不可选.
以上参数应在题库运行时自动生成.
2.5组卷的数学模型
组卷问题实际上是一个多条件的约束优化问题,这种问题通常被定义为一个目标函数和多个约束条件的组合.
为考核学生对所学内容的掌握情况,为每道试题定义如下指标:试题编号,题型,分值,难度系数,所属知识点,认知分类,估计答题时间,区分度.组卷中生成一份试卷,就是得到一个m×8的矩阵(m是试卷中试题总数).矩阵的每一行代表一道选中试题的相关信息,每一列是试题的某一控制指标的全部取值.
试题编号难度区分度知识点题型认知估时分值
S等于(2-3)
这就是问题求解中的目标状态矩阵.
由于计算机组卷是根据试题指标一道道试题进行处理的,教师一般都不可能对所有试题指标进行设置.因此,需要设置一些教师易于理解,容易操作,同时又能很好体现教师考试意图的组卷目标.设置组卷目标的主要依据是一套完整试卷的属性,具体有:试卷难度,试卷区分度,知识点,题型,认知层次,考试时间,试卷总分.
下面根据试题属性和组卷目标设计目标函数.
在文献[7]中,给出了试卷中各种难度试题的分配方法,运用该方法,可以根据用户期望的试卷难度计算出各种难度值的试题在所有试题中所占的比例及分数.同时,借鉴该方法,我们也可根据用户期望的区分度算出各种区分度值的试题的分数.在文献[8]中,提出了根据题型表,计算某知识点某类题型所出试题数的方法.借鉴该方法,我们可以计算出各认知层次所出的试题数.通过对这几种方法的分析,可以发现,组卷模式其实是一些分数分布.组卷的过程就是从试题库中选择出适当的试题去实现这些分布的过程.每一个分布可以看作是一个需要实现的约束,组卷过程就是一个实现多个约束的过程.
设试卷难度-分数分布,试卷区分度-分数分布,知识点-分数分布,题型-分数分布,认知层次-分数分布,考试时间,试卷总分的期望值分别为:,,,,
对于一套试卷,为试卷的总题数,为试卷中的第道试题,为试题的分数.
设为试题的难度级别,为试卷的第个难度级别的分数,为第个难度级别,为难度级别的个数,用表示试卷难度-分数分布的预估值,有:
其中,
(2-4)
设为试题的区分度,为试卷的第个区分度级别的分数,为第个区分度,为区分度级别的个数,用表示试卷区分度-分数分布的预估值,有:
其中,
(2-5)
设为试题的知识点,为试卷的第个知识点的分数,为第个知识点,为知识点个数,用表示知识点-分数分布的预估值,有:
其中,
(2-6)
设为试题的题型,为试卷中第种题型的分数,为第种题型,为题型数,用表示题型-分数分布的预估值,有:
其中,
(2-7)
设为试题的认知层次,为试卷第个认知层次的分数,为第个认知层次,为认知层次的个数,用表示认知层次-分数分布的预估值,有:
其中,
(2-8)
设完成试卷所需的预估时间为,预留检查时间为,则完成试卷所需的实际时间为:
(2-9)
其中,为试卷的试题的预估时间.
设组成试卷的总分数为,则:
(2-10)
其中,为试卷的试题的分值.
下面计算试卷各项期望值与预估值的偏差.
由于以上各项分布的期望值与预估值都不是一维向量,所以采用欧式距离来度量偏差,偏差越小则试卷越接近期望值.
设试卷难度-分数分布,试卷区分度-分数分布,知识点-分数分布,题型-分数分布,认知层次-分数分布,考试时间,试卷总分的偏差分别为.则有:
(2-11)
(2-12)
(2-13)
(2-14)
(2-15)
(2-16)
(2-17)
组卷目标就是从一个试题库中,寻找一个子集使得这个子集满足上面所述的成卷模式中的各个约束分布.其中,是试题库的总题量,为一套试卷中的总题量.
因此,目标函数就是要使实际得到的试卷中的各指标分布与理论要求分布的偏差最小.这里采用对各分布的所有偏差加权求和,取该和的最小的方法来定义组卷问题的目标函数.
令:
(2-18)
其中,为各指标的权重,且.
作为一个多目标优化问题,对各指标分布与理论要求分布的偏差的优化往往是矛盾的,不能期望它们的极小点重叠,即不能同时达到最优,甚至还产生对立,即对一目标是优点,对另一目标却是劣点,这就要在各目标的最优解之间协调,以取得整体最优.根据对组卷的7个目标的内在含义以及它们对组卷的重要程度的分析,可以发现,若使用式(2-18)的线性加权和法,若子目标数量级不一样,则次要目标会掩盖主要目标,影响优化效果,为解决此问题,可采用规范化加权平方和法[22].即在原来线性加权和法的基础上,找到各目标绝对值的最大值,将其与各目标相比,得到的各目标值将在[-1,1]间变化,为减小各目标差值较大对目标函数的影响,将各项平方后分权相加,目标函数改为:
(2-19)
我们可以将7个组卷目标按重要程度分成3类:1)难度,区分度.2)知识点,认知层次.3)题型,总时间,总分数.这样,组卷问题的目标函数就可以简化为:
(2-20)
其中,为各类指标的权重,,根据各类指标的重要程度,规定,这样可以加重第三类指标对组卷的影响,根据各类指标重要程度的大小将各类指标的偏差限定在1%—5%之间.
同时,为保证每道试题在连续份试卷中不重复出现,可增加一个约束来控制率[9].设试卷中任意试题上一次在试卷中出现,本次组卷中试卷的流水编号为.则得到求解组卷问题的目标函数:
(2-21)
至此,由上式的约束条件和目标函数已经建立了组卷的数学模型.
对组卷目标的分析,还有几点说明如下:
1)试卷难度和考试分数的关系
试卷的难度指一份试卷的总体难易程度,显然试卷的难度是由试卷中每道题目的难度来决定的.试卷的难度中等时,考生的分数呈正态分布.试卷难度较大时,考生的分数较低,低分区出现高峰,呈负偏态分布.试卷难度较小时,考生的分数较高,高分区出现高峰,呈偏态分布.试卷难度与平均分的关系:
(2-22)
其中,为所有考生的平均分,为试卷的满分,为试卷难度.
(图2-2)试卷难度与分数的关系
2)试卷区分度与试题难度的关系
试题难度和区分度有密切的关系[5],当难度过高或过低时,区分度将会很低,当难度在0.5左右时,试题的区分度将会很高,可接近最大值.
它们之间的关系式为:(2-23)
2.6组卷过程的难点及其解决办法
在组卷过程中,如何保证生成的试卷能充分满足用户的需要,并具有合理性,随机性,科学性是组卷系统实现的难点.
1,为保证随机性,使组卷过程不出现重复的题目,可以采用下面的方法[17]:(1)在试卷参数设计时,为每一道试题添加了标志位,数据类型为整型.在插入试题前标志位的值全部设置为0,然后每插入一个题目,就把该字段的值设置为1,若为1,则不进行任何操作,这样就保证了插入的试题不重复.当组卷结束之后,将标志位的值全部恢复为0.(2)在编制试题编号时,用7位代码表示一道题.其中最高位表示题目类型(如:1填空题,2选择题,3判断题,4简答题,5综合题),第2,3位表示题目所在的章,第4,5位表示题目所在的节,6,7位表示平行题的题号,即同一类型,同一章节,同等难度的第一题,第二题.(例如:1040302,1表示此题为填空题,04表示它在第四章,03表示第三节,02表示同类,同章节,同等难度的第二题).由于编码的唯一确定性,可确保在生成的同一份试卷中,不会抽到相同的试题.本文采用的是第一种方法.
2,为保证试题的合理性和科学性,试题分值根据试题难度,答题时间在试卷中所占的比例与试卷的满分值来确定,试卷的满分值可由出题人根据情况任意设定,满分值不受试题个数的约束.使试卷的试题个数摆脱试卷满分值约束,从而可通过增加试卷试题个数来增加测试效度和信度.
第3章常用组卷算法介绍
计算机自动组卷是按照教师和教学要求,由计算机自动从题库中选择试题,组成一份符合用户设置的知识点分布,题型,认知层次,难度系数,区分度,时间,分数等要求的试卷.组卷中的难点是:如何保证生成的试卷能最大程度地满足用户的不同需要并具有随机性,科学性,合理性.
组卷问题是一个结合了计算理论,算法分析,优化控制等知识的多目标优化问题.国内外的教育研究者针对此问题提出了许多算法,本章将简单介绍其中的几种.
3.1随机抽题成卷算法
该方法根据组卷状态空间的控制,由计算机抽取一道符合控制指标的试题放入组卷库,不断重复,直到组卷完毕或无法从题库中抽取满足要求的试题为止.该方法结构简单,对于单道题的抽取运行速度较快,但是对于整个组卷过程来说,组卷成功率较低,且要求试题库题量大,分布良好.
3.2自动成卷算法
该方法[2]采用动态地制定试题模式的方式,在组卷过程中,考虑到已产生试题的情况,采用某种推理算法逐题产生下一题.每当在题库中寻找到一道符合当前要求的试题并选中后,将其记入已入选试题题号组,从各指标限定的总分中减去该题分数,并且标记该题以防止它再次入选.当按某一模式找不到试题时,可按照题目控制指标需优先保证的顺序来逐个放宽条件.放宽条件的顺序是:题分,难度系数,章节,题型.该方法方便灵活,适应性好,随机性强.许多组卷算法都是将全卷分数分别分配到各章节中,这实际已将各章节在某题型,某难度系数上出几分的题作了确定的分配,然后按照这个分配到题库中查找,这样的静态分配对题库的要求非常高,一旦题库对该要求不能满足,就要重新修数分配模式,效率低且随机性差.
而本算法中,每一道试题的选择都是根据已入选试题的情况以及题库中现有试题的使用情况灵活处理的,而且是从所有尽可能严格地满足用户要求的试题中随机抽取的,保证了良好的随机性和适应性.但为了实现动态制定试题模式的方法,系统必须多次在试题特征库中查找所有满足当前状态的试题,故该方法在速度上不能保证.
3.3倒塔式收缩成卷算法
在组卷过程中,由于试卷参数间的相互制约,它们很难同时得到满足,通常是先随机抽题组卷,再判断试卷参数是否满足要求,不满足时调换试题这种成卷方法.在顺利的时候成卷速度较快,但往往是经过多次更换仍得不到理想的试卷,不得不重来.大体说来,这种成卷方法的速度是比较慢的.究其原因,主要是把问题留到了最后,也就是说等到问题成了堆才去解决.因此,文献[3]中采用了"倒塔式收缩"的成卷方式,先把各参数值放宽,以保证抽题的随机性,然后将各参数值逐步缩紧,最终收缩到允许的范围内.在组卷过程中,一旦参数值越界,立即强制返回.由于选题过程中先宽后严,并逐步收缩试卷数值范围,直至符合选题要求为止,故称为"倒塔式收缩法".按此种成卷模式,最后的试卷一定是一份合格的试卷,不会出现重来的局面.
3.4回溯试探成卷算法
回溯法[4]是一种"通用的解题法",属于有条件的深度优先算法.该方法是将随机选取产生的每一状态记录下来,搜索失败时,释放上次记录的状态类型,然后再依据一定的规律,变换一种新的状态类型进行试探.通过不断地回溯试探直到组卷完毕或回到出发点为止.按照上面提到的三种方法选取试题,随着选题数的增加,指标间的约束增大,选出来的试题可能不是最优的,此时回溯法往往是有效的.该算法对于试题类型较少和题量较少的题库以及组卷指标简单的试卷而言,成功率较高.但当总题量较大时,组卷时间长,占用的空间复杂度大,程序结构较为复杂,选取试题也缺乏随机性.
综合考虑以上几种组卷算法,发现上述算法对于小规模的考试来说,能够比较好地完成组卷,但对于中,大规模的考试来说,组卷时间长,而且,不一定能够满足所有的约束条件,对于用户来说,是不能令人满意的.
因此,结合以上几种方法的优点,寻找一种新的改进算法,不仅要具有智能搜索技术,并且要具备收敛速度快的特点.遗传算法以其具有自适应全局寻优和智能搜索技术,并且收敛性好的特性能够很好地满足自动组卷的要求.
第4章遗传算法在组卷中的应用
通过上章对常用的组卷算法的分析可知,将遗传算法应用于组卷是具有实际意义的.因为通过遗传算法强大的搜索能力得到的组卷参数表,可以保证根据此表抽题组卷时,题库中不会找不到满足所有属性的试题,从而使试卷的总体指标得到满足.
作为本文的重点以及难点部分,本章将首先阐述遗传算法的思想以及基本步骤,接着分析传统遗传算法用于组卷的可行性,最后针对遗传算法在应用时的一些弊端,将遗传算法进行了改进,使之更符合组卷问题的实际需求.
4.1遗传算法
4.1.1遗传算法概述
遗传算法[11]简称GA(GeicAlgorithm)是一种模拟自然选择和自然遗传机制的随机优化算法,它对目标函数没有可微的要求,可以用于解决传统搜索方法难以解决的复杂问题和非线性问题,可广泛应用于规划设计,组合优化,自适应控制等领域.
遗传算法的起源可以追溯到上世纪50年代初,最初是几个生物学家用计算机来模拟生物系统.到60年代后期和70年代初期,密歇根大学的JohnHolland从试图解释自然系统中生物的复杂适应过程入手,模拟生物进化机制构造人工系统模型,形成了较为完整的遗传算法理论和方法.在接下来的几十年中,人们对遗传算法的兴趣日益升温,在该领域也取得了理论研究的进展和丰硕的成果.近些年,随着人工生命研究的兴起,遗传算法的应用和研究也渐渐成熟.
4.1.2遗传算法的基本思想
遗传算法的基本思想[13]是把问题的解表示成染色体,在算法中就是经过编码的字符串.在执行遗传算法之前,给出一群染色体,作为检测设解.然后,把这些检测设解置于问题的"环境"中,按照适者生存和优胜劣汰的原理,从中选出较适应环境的染色体进行复制,再通过交叉,变异产生更适应环境的新一代的染色体群.这样,一代代进化,最后就会收敛到最适应环境的一个染色体上,这就是问题的最优解.可是,生物物种的进化是很缓慢的,要得到满意的结果,通常要经过上千次甚至上万次交叉,变异.为加快种群的优化速度,需根据实际情况对算法进行改进.
4.1.3遗传算法的特点
遗传算法是从某一初始群体出发,遵循进化原则,不断迭代计算,逐步逼近最优解,作为一种搜索和优化方法,它具有以下特点[12]:
遗传算法是一种间接的优化方法.它的搜索过程不是直接作用在问题的变量上,而是作用在将变量编码后的字符串上.对给定问题,它可以产生许多潜在解,有较大的选择性.
遗传算法的搜索策略不是穷举式的全面搜索,而是利用适应度逐步逼近目标值的搜索,目的明确.
遗传算法的搜索过程不是单点搜索,而是按并行方式搜索一个种群数目的点,是从一个群体到另一个群体,减少了陷入局部最优解的风险.它适合大规模并行,可同时搜索解空间的多个区域.
遗传算法的搜索过程只依赖于个体的适应度函数,不需要其它辅助信息,适用范围广泛.
遗传算法对搜索空间没有特殊要求,不要求可行域是连通的或凸的,对求解问题的数学模型没有特殊要求,不要求目标函数可导,可应用于离散问题和函数关系不明确的问题.
在有限次遗传迭代时,一般只能得到满意解而难以得到全局最优解.
4.1.4构成遗传算法的基本要素
1,染色体编码
遗传算法不能直接处理问题空间的参数,它只能处理以基因链码形式表示的个体[10].因而,使用遗传算法来求解问题的时候,就必须把问题解的参数形式转换成由基因编码按一定结构组成的遗传染色体即个体,这一转换叫编码,也称为问题的表示.从生物学的角度来看,编码就相当于选择遗传物质,它是研究遗传的基础.常用的染色体编码方式有:二进制编码,自然数编码,实数编码等.
2,适应度函数
在遗传算法中,衡量个体优劣的尺度是适应度.由适应度大小来评价群体中每个个体对环境的适应能力,决定某些个体是繁殖还是消亡.因此,适应度是驱动遗传算法不断寻优的动力.从生物学角度讲,适应度相当于"生存竞争,适者生存"的生物生存能力,在遗传过程中有重要意义.
一般而言,适应度函数由目标函数变换而成.标准遗传算法采用赌轮选择机制,按个体适应度来决定当前群体中每个个体遗传到下一代群体中的概率大小.由于要计算每个个体被复制的概率,所以个体适应度必须为非负数.
3,遗传操作
在遗传算法中,遗传操作就是对群体中的个体,按照它们对环境的适应程度施加一定的操作,从而实现优胜劣汰的进化过程.从优化搜索的角度来说,遗传操作可以使问题的解一代又一代地优化,并逐渐逼近最优解.
选择算子
选择染色体的目的是为了强调群体中适应性强的个体,并希望其后代也能具有较强的适应性.选择算子选择强度应该适中,选择强度太大将会使局部最优个体在群体中占优势,从而使群体的多样性减少,使群体陷入局部最优,影响群体进化.反之,选择算子选择强度太小,将极大地缓解群体进化过程.常用选择方法有:次序选择,竞争选择,适应度成比例选择.
交叉算子
遗传算法的主要特点就是使用交叉算子.一方面,它使得在原始群体中的优良个体的特性能够在一定程度上保持.另一方面,它使得算法能够探索新的基因空间,从而使新的群体中的个体具有多样性.常用的交叉算子有:单点交叉,多点交叉,均匀交叉等.
变异算子
变异算子的基本内容是,对群体中的个体串的某些基因位置上的基因值做变动.遗传算法中使用变异算子使得遗传算法具有局部的随机搜索能力,可使遗传算法维持群体的多样性.常用的变异算子有:自适应变异,均匀变异等.
4.2采用传统遗传算法的组卷算法
传统的遗传算法中,采用{0,1}k上的定长二进制串编码方式[13],将一群二进制串作为种群.问题的一个解对应一个长度为k的二进制串.从初始种群出发,采用基于适应值大小的选择策略,在当前种群中选择个体,使用杂交和变异来产生下一代种群.如此一代代演化下去,直到满足期望的终止条件.具体步骤如下:
染色体的编码和定义适应度函数
试题库由m道试题组成,则编码就用m位长的二进制编码表示:x1x2x3等xm,若xi为1,表示该题被选中,若xi为0,则表示该题未被选中.一份试卷有n道试题,x1x2x3等xm中就有n个1.
个体的适应度函数应能保证任何个体的适应度值都是非负的,且能反映个体的优劣,或能反映个体对环境的适应能力.在组卷算法中,选取的是各约束条件与目标值的误差值,见式(2-20):
(4-1)
所以越小的个体对环境的适应能力越强,被选择用来繁殖后代的机会越大.
产生初始群体
随机产生N份试卷个体构成初始群体.N为群体规模,它影响遗传算法的最终结果及其执行效率.若N取得太小,每一代处理的染色体数量不多,搜索效率不高,且易陷入局部最优解.若N取得太大,每一代的适应度值计算量太大,计算效率不高.
个体评价
计算群体中每个个体的适应度值,用组卷的目标函数作为适应度函数.
停机条件的判断
若群体中存在最优个体,或已经满足预先设定的停机条件则输出最优解后停机,否则转下一步.
选择
按照某种选择策略,从群体中选择出若干个体进入交配池.交配池中的个体通过遗传算子的作用产生新一代群体.选择策略应遵循的基本原则是:适应度值越小的个体被选中的概率应该越大.
交叉和变异
定义适当的交叉和变异算子.通过交叉,变异算子的作用,交配池中的个体产生新的个体,构成新一代群体.
跳转第(3)步
遗传算法就是这样不断进行个体评价,选择,交叉,变异,如此循环往复,使群体中的个体朝着最优解的方向不断移动,直到获得在误差允许范围内的试卷.
以上步骤可以简单表示为:
{GA等于(B,Q(0),N,S,C,P,f,T)
B:试卷个体的编码方法Q(0):试卷初始群体的大小
N:种群数S:选择算子C:交叉算子P:变异概率f:适应度函数T:终止原则
初始化种群Q(t):t等于0//t为当前种群代数
计算群中各个体的适应值
执行选择操作
while(不满足终止准则)do
{执行选择生成父代个体
执行交叉,变异
产生新一代种群
计算新一代种群中个体适应度值
保留最好解
执行选择产生新的种群Q(t+1):t等于t+1}
输出结果}
主要算法段用VC++语言描述为:
voidGA()//智能组卷的遗传算法
{intt等于0,
initialize(p(t)),//初始化,产生初始试题号集合
calcufit(t),//计算适应度
do{if(r<,等于Pm){select_parent,//选择父体
mutation,//变异}
else{select_parent,
crossover,//交叉}
}while(满足迭代终止条件)
cout等//输出最终的题号}
这种传统遗传算法解决组卷问题时,结构较为简单,遗传操作方便,具有较高的专家水平.但当题库比较大时,容易导致编码过长,解码繁琐,难以在遗传操作过程中处理约束条件,搜索耗时,而对于小规模的题库,有可能导致组出的试卷中试题重复率较高.
4.3改进遗传算法的组卷算法
设计遗传算法的一个原则[20]就是要在保持群体多样性以不断拓展搜索空间的同时,对群体施加一定的选择压力,以保证搜素过程是进化的.但这两者又是矛盾的,当增大选择压力时,就会使遗传搜索倾向于群体中的较好个体,从而降低群体的多样性,并使算法较快地收敛到局部最优解.反过来,为保持群体的多样性,就必须降低选择压力以拓展搜索空间,从而不得不进行大量的计算,使算法的搜索效率变低,这也是遗传算法计算量巨大的原因.因此,如此在这两者之间取得平衡,是改进遗传算法时必须考虑的问题.
根据前面部分的叙述以及实际过程中的操作,采用传统的遗传算法会出现以下问题:1)在传统遗传算法中,初始种群的每个字符串中"1"的数目等于试题的数目n,进行遗传操作后,字符串中"1"的数目可能大于或小于n,从而变成非法解,此时,必须对解进行修正,而修正过程很复杂,运算量大.2)组卷对生成试卷的各个属性指标要求不一样,对于考试分数,我们希望没有误差,而对于题型,章节,难度系数,区分度,认知层次等只要在误差允许的范围内就可以了,换言之,组卷工作仅仅为了组成一份误差在可接受范围内的试卷,并非要求试卷的整体指标一定是全局最优的.3)使用遗传算法求解多条件约束优化问题,初始种群可以随机生成.但若能使用已经满足一定条件的种群作为初始种群,定能极大加快遗传算法的计算速度.基于以上问题,我们可对传统遗传算法的个体编码,初始种群,杂交运算进行改进.
4.3.1个体编码的改进
使用二进制编码,虽然在组卷上取得过成功,但随着题库试题量的增多,染色体长度不断增长,计算复杂,导致组卷时间变长.针对这一弊端,同时利用标准化试卷中每种题型所占分数和题数相同的特点,采用分组自然数独立编码[14]的策略.独立编码就是将合成编码分解成几个相对独立的组,按各个题型分组编码,每一组编码反映一种题型,每组长度由题库内该题型题数决定.采用自然数编码就是用自然数编码策略,直接利用试题编号编码.为了加快遗传算法的收敛并减少迭代次数,试卷初始种群是根据各题型的题量要求,从初始化后的具有知识点约束属性的试题分库中随机产生,保证了初始种群既满足知识点约束又满足题型和题量的要求,并且染色体中的题目不会过多,为以后的染色体运算减少复杂度.因为编码长度由题库中的试题数决定,若题库中有种题型,每种题型的试题数分别为,而每一组编码的长度就是由题型数决定的.所以有:
,,等(4-2)
其中,是试卷所含的题目数,分别为试卷中各个题型所出的题目数.
检测设各代表一种题型,分别表示对应题型的题目数,,,表示对应题型中选中试题的题号,这样每个染色体就可以表示为:.
由于采用了自然数编码,可以克服采用二进制编码搜索空间过大和编码长度过长的特点.同时,按题型分段编码,在随后的交叉和变异操作时也按段进行,保证了每种题型的题目总数不变.以题号编码所表达的意义清楚,明确,不需解码,能有效改善遗传算法的复杂性,提高运算效率.
(表4-1)两张试卷的染色体编码
填空题选择题计算题综合题1236152645561519215258311182251829362125333966191121415911192129916314.3.2优化初始种群
初始种群的特性对遗传算法的计算效率有很大影响,要实现全局最优,初始种群在解空间中中应该尽量分散.而传统遗传算法中,随机产生的初始种群可能在解空间中分布不均匀,从而影响算法的性能.所以,应设法在产生初始种群时,使它们尽量均匀分布在整个解空间中.
一种方法[19]是,为初始种群中的个体之间设置一个距离限制,要求入选初始种群的各个体之间的距离必须大于这个限制距离,这样就能保证初始种群的个体之间有较明显的差别,使它们能较均匀地分布在解空间中,保证了初始种群含有较丰富的模式,从而增加搜索收敛于全局最优解的可能.
另一种方法是,首先将解空间分割成若干个子空间,对每个子空间进行初始种群选择,然后将每个子空间的初始种群进行合并,生成总的初始种群,那么这个种群中至少包含了来自不同子空间的个体.本文采用的是第二种方法.
根据本文前面部分对组卷步骤的分析,组卷要先确定知识点章节范围和试题类型,这一步就是试题的初始化操作,根据知识点的约束条件,从总题库中选出符合知识点条件的试题,然后对不同的题型建立各自的成卷试题数据库表.
(图4-1)具体实现过程
下一步,为了组卷方便,我们可以设置题型表[18],用于表示各题型出题数量和考核的知识点.(表4-2)
题型填空题判断题
选择题
简答题
综合题
出题数量20102052题分2015401510考核知识点1,3,25,72,3,68,5,93,6,1116,22,31根据从题型表中得到的各题型包含的题量,在各自的题型数据库表中抽题,抽题时采用随机函数法.这样抽取的一组题目,为一个个体样本,满足题型,题量与知识点的要求.按照这种方法选取多个样本,便可作为遗传算法的初始种群.
(图4-2)个体样本的抽取过程
4.3.3个体适应度函数的自适应改进
算法对适应值的调整是通过适当控制群体适应值的分布,进而控制个体的被选择概率[21].为此,引入一个自适应常数,算法运行过程中根据群体中各个个体的适应值分布情况加以启发,进行自适应调整,改变群体适应值的分布,从而有效地对算法加以引导,使算法快速向全局最优解靠拢.具体方法是,令适应度函数为:
(4-3)
(对于函数极小值问题,只需要一个简单的变换:,在起始时刻,可以给定一个较大的正数.在计算过程中,可以根据群体适应值的分布来自适应调整).
传统遗传算法解决组卷问题时,用组卷目标函数作为适应度函数,很好地反映了染色体与成卷要求之间的差别.但在遗传算法中,一般是适应值越大的个体越好.组卷问题是最小化问题,可取等于100,将目标函数转换为适应度函数:
(4-4)
依据组卷原则,目标函数是越小越好,而适应度函数是越大越好.指数比例既可让非常好的个体保持多的复制机会,同时又限制其复制数目以免其很快控制整个群体,提高相近个体间的竞争,采用指数比例变换方法将转换为:
(4-5)
其中取0.03,它决定了复制的强制性,它越小,复制的强度就越趋向于那些具有最大适应度的个体.
4.3.4选择方法的改进
使用传统的赌轮选择时,在遗传迭代早期,群体中个体适应度差别很大,适应度低的个体生存机会很少,低适应度个体淘汰太快容易使算法收敛于局部最优解.在遗传迭代的晚期,群体中个体适应度差别不大,"优胜劣汰"的作用不明显.本文选择自适应的选择方法.
先计算种群中所有个体的适应度总和,每个个体都有自己的选择概率(为第个个体的适应度).找出种群中所有个体的最大选择概率,对每个个体产生一个的随机数,如果则表示该个体被选中.显然,个体适应值越高,被选中的概率越大.但是,适应值小的个体也有可能被选中,这样有助于增加下一代群体的多样性.
4.3.5交叉算子的自适应性改进
遗传算法的交叉概率影响着算法的收敛性.越大,新个体产生的速度就越快,而遗传模式被破坏的可能性也越大,使得具有高适应度的个体结构可能被破坏,过小,会使搜索过程缓慢,以致停滞不前.为了加快遗传算法的搜索效率,保护优良试卷个体,在本组卷系统中根据种群的进化情况采用自适应函数来动态地调整交叉概率Pc:
(4-6)
其中,是交叉概率,为群体适应度的最大值,为群体适应度的平均值,为两个交叉个体中的适应函数值较大的一个,为概率系数从公式可以看出,越大时,越小,越小,小于群体适应度的平均值时,则趋于相同的概率系数.即对于适应函数值大于平均值的个体,其受破坏的可能性较小,而对于小于平均适应函数值的个体,其受破坏的可能性较大.这样便达到了好的个体尽量被保留,差的个体尽量被替代而淘汰.
在进化之初,各染色体之间的适应度差别较大,种群的多样性较强,取较大值,以加快进化速度,随着进化的发展,各染色体之间的适应度差别变小,此时,取较小值,减缓进化速度,避免陷入局部最优.因此,自适应函数能够为每个试卷个体提供一个较为合适的值.这种自适应交叉算子在保持试卷群体多样性的同时,保证遗传算