（计算机科学与技术专业论文）遗传算法的改进及在智能组卷系统中的应用研究.pdf

摘要 近年来，随着信息社会的高速发展，计算机考试系统已经逐步代 替传统的考试，计算机考试系统正以其特有的优势在现代教育中扮演 着重要的角色，能否利用考试系统对被检测者进行有效的检测成为考 试成功与否的关键因素。本文针对目前组卷系统存在的成功率低，组 卷周期长，生成试卷不能满足教育测量要求等不足，对组卷系统进行 了研究。 根据对考试的要求，首先对试卷的各个性能指标及相互间约束条 件进行了分析，根据试卷性能评价指标建立了组卷数学模型。然后针 对遗传算法产生早熟的原因以及对现有的预防措施进行分析后提出 了改进遗传算法，改进遗传算法的主要思想是从染色体调控和染色体 库两个方面进行改进：一方面根据种群中优秀染色体位出现的活跃度 的评价方式来引进新个体；另一方面引进染色体库，染色体库在保留 优秀个体的同时也与种群中的个体进行选择、交叉和变异以产生新的 个体。通过与其他遗传算法进行测试对比，验证了改进遗传算法的全 局寻优能力。实验表明，改进遗传算法能有效的预防早熟，并且在收 敛速度上相对传统遗传算法有明显提高。最后，将改进遗传算法应用 于组卷系统，对系统进行实现后通过实例进行验证，结果表明基于改 进遗传算法的智能组卷系统的组卷速度快，试卷质量较高，能够满足 实际组卷的需求。 关键词组卷算法，种群多样性，改进遗传算法 a bs t r a c t i nr e c e n t y e a r s ，w i t ht h ed e v e l o p m e n to fi n f o r m a t i o ns o c i e t y , c o m p u t e r - a s s l s t e dt e s ts y s t e mh a sb e e ng r a d u a l l yr e p l a c i n gt h et r a d i t i o n a l e x a m i n a t i o n c o m p u t e re x a m i n a t i o ns y s t e mw i t hi t su n i q u ea d v a n t a g e si n t h em o d e me d u c a t i o np l a y e di m p o r t a n tr o l e s t h eu s eo ft h ee x a m i n a t i o n s y s t e mc a nb ed e t e c t e dt oc a r r yo u ta ne f f e c t i v ee x a m i n a t i o no ft h et e s t i n g h a sb e c o m eak e yf a c t o ri nt h es u c c e s s i nt h i sp a p e r , w es t u d i e do nt h e p a p e rs y s t e mf o rt h ef o l l o w i n gp r o b l e m s ，t e s tp a p e r sf o rt h ec u r r e n t s y s t e mi nt h el o ws u c c e s sr a t e ，t h el o n g - t e r mt e s tp a p e r s ，a n dt h et e s t g e n e r a t i o nc a nn o tm e e tt h em e a s u r e m e n tr e q u i r e m e n t so fe d u c a t i o n ，e t c f i r s to fa l l ，p a p e r si n v a r i o u si n d i c a t o r sa n dc o n s t r a i n t sw e r e a n a l y s e d ，a n dt h e nam a t h e m a t i c a lm o d e lf o rt e s tp a p e r sw a se s t a b l i s h e d a c c o r d i n g t ot h e p e r f o r m a n c eo fp a p e r s h e r e a f t e r , b a s e do nt h e r e g u l a t i o no fc h r o m o s o m ea n dt h ec h r o m o s o m el i b r a r y , t h ea d v a n c e d g e n e t i ca l g o r i t h mw a ss e tu po nt h ea n a l y s i so ft h er e a s o n sf o rp r e m a t u r e o fg e n e t i ca l g o r i t h ma n dt h e e x i s t i n gp r e v e n t i v em e a s u r e s t h eg l o b a l o p t i m i z a t i o na b i l i t yo ft h ea d v a n c e dg e n e t i ca l g o r i t h mw a sv e r i f i e db vt h e f u n c t i o nt e s t sw i t ho t h e rg e n e t i c a l g o r i t h m t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tg e n e t i ca l g o r i t h mc a n e f f e c t i v e l yi m p r o v et h ep r e v e n t i o no f p r e c o c i o u sp u b e r t y , a n dt h es p e e do fc o n v e r g e n c eo fw h i c hh a sb e e n g r e a t l y i n c r e a s e dt h a nt h et r a d i t i o n a l g e n e t i ca l g o r i t h m f i n a l l y , t h e a d v a n c e dg e n e t i ca l g o r i t h mw a sa p p l i e dt ot e s tp a p e rs y s t e m ，a n dt h e r e s u l t sa f t e rt h er e a l i z a t i o no ft h es y s t e ms h o w , t h r o u g ht h ee x a m p l e s ，t h a t t h ei n t e l l i g e n tt e s tp a p e rs y s t e mb a s e do na d v a n c e dg e n e t i ca l g o r i t h m w a sw i t hh i g hs p e e do fp a p e rt e s t ，w i t hh i g h q u a l i t yp a p e r s ，a n dm e tt h e n e e d so ft h ea c t u a lt e s tp a p e r s k e yw o r d s ： a l g o r i t h mo ft e s tp a p e r ，d i v e r s i t yo fp o p u l a t i o n ， a d v a n c e dg e n e t i ca l g o r i t h m l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：至尘：望 日期：4 年月2 日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者虢地导师签名且垫嗍年年月旦日 硕十学位论文第一章绪论 1 1 研究背景及意义 第一章绪论弟一早三百下匕 随着信息社会的发展，我国科技与教育得到蓬勃的发展，而高校作为社会中 非常重要的一部分，其所产生的影响和作用也越来越大。高等院校是传播知识的 主要媒介，其本身只有更好的掌握科学技术和文化知识才能更加适应激烈的竞 争。 教学是高等院校培养学生的主要途径，而计算机正逐渐成为教学中的有效工 具【l 】。计算机对于教学的影响主要是使教学手段、教学方法产生深远的影响，从 而产生了一门新的研究领域计算机辅助教学( c o m p u t e ra s s i s t e di n s t r u c t i o n ， c a i ) 。c a i 是指用计算机帮助或代替教师执行部分教学任务，向学生传授知识和 提供技能训练，直接为学生服务。计算机管理教学( c o m p u t e r m a n a g e d i n s t r u c t i o n ，c m i ) 则是利用计算机来实施教育管理功能，主要包括教学管理、 学校行政管理、图书数据管理等【2 】。计算机辅助教学在理论上涉及教育学、心理 学、哲学、信息论、控制论、计算机科学、数学等多个研究领域。其影响的范围 也越来越广阔，已融入到学校教学、网络教学、家庭教学等各个方面。 与教学对应的是考试，考试一直是我国高校对教学成果进行验收的标准。通 过考试，老师可以更加直观的了解学生对于知识的掌握情况，并通过考试的反馈 信息更改其教学手段、教学侧重点以提高教学质量。学生通过考试也可以更清楚 的认识到自己的不足，对于学习内容做到有的放矢进而提高自身的学习质量。 在以往的考试中，组卷方式存在不少问题。在一次考试中，从出题到考试一 直到最后的阅卷评分是一个复杂繁琐的过程。而随着教学的改进，对于考试本身 的要求也越来越高，教师的工作量也相应的增大。传统的组卷方式主要凭借教师 对知识点的侧重方向收集选取试题以完成试卷的编制，试卷的效度和信用度较 高，但也存在着一些不足：教师人为因素比较大，知识点分布相对狭窄，对于教 师精力耗费巨大，不同科目之间的出题者无法分享出题方法和成果【3 1 。因此，产 生了与计算机辅助教学对应的另一个重要分支：计算机辅助测试系统( c o m p u t e r a s s i s t e dt e s t i n g ，c a t ) 。计算机辅助测试系统近年来在我国发展很快，在教学 评估及考试上起到重要作用。目前c a t 一般包含以下几个部分：题库模块、组卷 模块、测试模块、阅卷模块。这其中组卷系统又是整个c a t 的核心部分，同时也 是题库模块的组成部分。 对于一个组卷系统而言，最根本的要求是能够生成符合要求的试卷，其中对 硕士学位论文 第一章绪论 试题抽取的组卷算法是能够保障最终试卷质量和性能的关键。自动组卷系统可以 非常高效的将出题教师的经验知识与计算机技术相结合，生成客观的具有良好规 范性的试卷，且试卷能满足考试要求。而自动组卷系统操作方便，使用简单，对 使用者不要求太多的专业技能。但是，组卷系统的实现并不简单，这其中主要的 困难是生成的试卷对多约束条件的满足问题，一般而言，一张高质量的试卷需要 同时满足多项约束条件，其中包括：试卷难度、区分度、知识点分布、题型分布、 考试时间、试卷题量和总分等方面。综合而言，试卷需要满足指标要求性、规格 多样性和试卷的严肃性三个方面。需要同时满足这三点，必须要有一个好的组卷 算法，然而在试题的抽取过程中要做到无法预知、随机、不重复及快速组卷并不 容易。因此，组卷系统必须要有一个优良的组卷算法，组卷算法是自动组卷系统 研究实现的核心部分。 目前，人工智能技术在计算机辅助教学领域的应用，很大程度上推进了组卷 系统向智能化方面的发展，即在满足用户组卷需求的自仃提下，同时控制好试卷的 难度、知识点章节分布和区分度等性能指标。 利用计算机进行组卷，可以大大节省教师的时间，使得考试更加标准且更完 全的反映教学成果，从而有效的提高教学质量。因此，组卷系统的出现更是一种 必然。 本课题的提出是为了解决计算机考试系统中的组卷模块对实际考试难以满 足的现状。解决计算机组卷问题，对于提高教学质量以及合理的利用资源有着重 大的意义，因此本课题具有重要的实际应用价值。 1 2 国内外研究现状 目前，计算机和网络的应用在各行各业已经很广泛，尤其是在高校。校园网 的建设己逐步完善，大多数学生也己经具备了利用网络进行交流和学习的能力。 但是在教学这个环节中，我们仍然过分依赖于传统的教学模式，对于网络的开发 和应用程度远远不够。即使是网络教学系统，也是大多为静态、无反馈的系统， 很少提供在线考试的功能【4 j 。 自动组卷系统的研究最早是美国首先于上世纪6 0 年代展开的。计算机辅助 考试( c a t ) 自诞生以来，经历了近5 0 年的发展，在国外已经得到了非常广泛的应 用。国外已经有很多教育和考试机构采用计算机辅助测试进行考试。其中著名的 有美国思而文学习系统有限公司( s y l v a nl e a r n i n gs y s t e m si n c ) ，在全世界五 大洲一百多个国家和地区有其2 0 0 0 多家考试中心。现在大部分的授证机构均通 过思而文公司对参考者进行测试、评估。这其中有信息产业中绝大部分计算机公 司的认证考试，还有其他专业的认证考试如医护人员认证考试，美国飞行员考试 2 硕士学位论文第一章绪论 等1 5 1 。8 0 年代，考试系统的应用更一步加大，如美国的t o e f l 、g r e 和g m a t 等考 试均采用了计算机考试系统。在国内对组卷系统也有相当的研究，这其中包括： 南京大学计算机科学与技术系研制了p a s c a l 题库系统，高教司的重点项目基于 知识点的成卷系统统用外科软件【6 l 等系统。 遗传算法是霍兰德( h o ll a n d ) 于1 9 7 5 年在他的著作 a d a p t a t i o ni nn a t u r a l a n da r t i f i c i a ls y s t e m s 中首次提出。遗传算法是模仿生物遗传学和自然选择 机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数 学仿真，是进行计算的一种最重要的形式【7 l 。其算法起源于达尔文的物竞天择、 适者生存规律。随后在世界范围内引起了广泛的注意并掀起对其的研究热潮，其 中g o l d b e r g 成果最为显著。他建立了完整的g a 体系，且成功的在搜索、优化及 机器学习等多领域展开应用。特别是基于遗传算法的智能组卷系统已经成为计算 机辅助测试的一个重要组成部分。 国外对于自动组卷问题主要采用随机线性规则的组卷算法【8 1 ，这种方法在算 法上采用结构化设计，实现简单，速度快，但应用不灵活。 国内经常采用的是以下几种策略1 9 i ： 1 、优先权策略 优先权策略从数量、题型的平均分数、完成率和累计值与指标值差距四个方 面综合解决了选题组卷开始阶段，由于各项属性都有较大的取值范围，指标间的 牵涉问题反映缓慢，伴随着试题增加取值逐渐缩小的矛盾。 2 、随机抽取策略 随机抽取策略是根据组卷指标随机的抽取试题到试卷，此过程不断重复，直 到组卷完毕或己无法从题库中抽取满足指标的试题为止。这种方法结构简单，对 于单道题的抽取运行速度较快，但这种方法的效率不高，最主要的问题是要求试 题库题量大，且要分布良好。用随机法组卷通常需要搜索一段较长的时间，这对 于网络考试是不可忍受的。随机策略有两种情况，一是从试题库中随机抽取试题， 然后判断是否符合试卷的约束条件。二是从符合试卷某项要求的试题库子集中随 机抽取试题，然后判断是否符合试卷的其它约束条件。 3 、误差补偿策略 误差补偿策略就是在试题生成过程中当不满足约束条件时，适当地放松约束 条件，让试题生成在允许的误差区域内完成。这种策略在允许一定误差的前提下 减少不必要的循环搜索，提高组卷的效率和成功率，解决在实际组卷过程中由于 指标问的相互牵制和试题库题量的有限性容易使计算机的筛选陷入死循环的问 题。 硕十学位论文 第一章绪论 4 、回溯试探策略 回溯法是一种“通用的解题法”。属于有条件的深度优先算法，对于约束集r 维数小的组卷模型( 即组卷指标简单的试卷) 而言，组卷成功率较高。但是这种算 法对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组 卷时间长。按照上面提到的三种方法选取试题，随着选题数的增加、指标间的约 束增大，选出来的试题可能不是最优的，此时回溯法往往是行之有效的，充分利 用这一方法一般都能成功地生成试卷。但是其组卷速度慢，而且难以满足所有约 束条件【l o 】。在上面介绍的四种策略虽然对小规模的试题库有着比较好的性能，但 是对于有上万道试题的大型题库存在很大的缺陷，这种缺陷使选题工作具有很大 的盲目性；对组卷指标比较复杂的情况，也不能满足要求。 5 、并行策略 解决组卷问题的困难之处在于对指标问进行相互制约。组卷要求同时满足的 约束指标越多，实现起来就越困难。并行策略是将组卷指标按层次分为主并发指 标和弱并发指标。在组卷过程中，优先保证主并发指标的平衡，然后对已经满足 主并发指标的试卷进行调整，使其同时满足弱并发指标。但也存在着试卷生成后 不能同时满足多项约束条件的问题。 针对以上各种方法存在的不足之处，有大量学者对上述算法作出了部分改 进：例如雷国雨等对组卷参数进行编码优化，将约束条件转化为屏蔽码和条件码 完成随机抽取过程i 川；张国才等提出的基于分割策略的随机组卷方澍2 1 ；王萌、 王晓荣等提出了一种集合随机抽选组卷算法，每次抽题均从满足抽取条件的试题 集合中选取最优试题1 1 3 1 ；郝彦、陈丽燕等充分利用题库中试题的基本信息，通过 对题量、试题历史信息及知识点分布的调整和控制实现试题的智能筛选i 1 ；金汉 均、郑世珏等将众多试题数据进行分段处理，在各段内随机抽取i i 。上述的改进 算法在组卷的效率和成功率有了一定程度的提高，且在一些小规模的组卷系统有 较好的性能表现，但对基于大型题库的多约束条件下的组卷问题仍显得力不从 心，缺乏智能性，不能很好的满足选卷需求。 1 3 本文研究的主要内容 本文主要针对智能组卷算法的发展和应用进行了分析总结，在对传统遗传算 法不足进行研究并提出了基于染色体调控和染色体库技术的改进遗传算法，并对 改进遗传算法和其他遗传算法一起进行了试验验证。主要篇章内容如下： 第一章介绍了目前组卷算法的研究现状。对现存的一些组卷算法进行了分析 研究。并简要介绍本课题的研究目的、意义及本文的主要工作； 4 硕士学位论文 第一章绪论 第二章从教育度量学角度介绍和分析了试卷的几个评价指标，确定了组卷遗 传算法的目标函数，并建立了组卷问题的数学模型； 第三章分析了传统遗传算法早熟问题的产生原因及常见预防措施，并在此研 究基础上提出了基于染色体调控和染色体库技术的改进遗传算法，并对算法进行 了有效性验证； 第四章将改进遗传算法与组卷问题相结合，实现了智能组卷系统，并进行了 实例验证； 第五章总结全文，对未来进行展望。 硕士学位论文第二章遗传算法及组卷系统的基本理论 第二章遗传算法及组卷问题的基本理论 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 借用了生物学中物竞天择的观点，通过 选择、遗传、变异等作用机制，对种群中的个体进行筛选，保留适应度高的个体。 遗传算法自诞生到现在时间并不长，但已有很多人对其展开了广泛的研究，目前 遗传算法所涉及的领域很广，在优化、搜索、机器学习等方面都起了非常重要的 作用。组卷是计算机辅助考试系统的核心部分，从科学角度来看，组卷问题属于 测验编制范畴，是心理学和教育测量学的核心内容【1 6 1 。近年来，已有广大学者将 遗传算法应用于c a t 的组卷系统中。 2 1 遗传算法基本机理 1 、遗传算法的数学模型及优点 遗传算法的数学模型可以表示为【1 7 1 ： g a = ( c ，e ，e o ，m ，f ，甲，t )( 2 - 1 ) 式中：c 个体的编码方式，g a 中一般使用定长的二进制编码方式； e 个体适应度函数； 只初始种群； m 种群中的个体总数； 选择算子； r 交叉算子： 甲变异算子； t g a 算法的结束条件。 遗传算法相对其他优化算法具有如下优剧i s l ： ( 1 ) 遗传算法是对参数集合的编码而非针对参数本身进行进化： ( 2 ) 遗传算法是从问题解的编码组开始而非从单个解开始搜索； ( 3 ) 遗传算法利用目标函数的适应度这一信息而不是利用导数或其他辅助信 息来指导搜索； ( 4 ) 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机 操作； ( 5 ) 具有智能性，利用进化中获得的信息自行组织搜索，适应度大的个体具 6 硕士学位论文第二章遗传算法及组卷系统的基本理论 有较高的生存概率，并获得更适应环境的基因结构。 2 、遗传算法的主要流程 完整的遗传算法如图2 1 所示，其中g e n 为当前代数。 ( 开始 ) i l g f , n ：；0 l j r l 产生韧始种群 否 图2 - 1 基本遗传算法流程图 同时，遗传算法的一般结构也有如下的表示形式： 7 硕士学位论文 第二章遗传算法及组卷系统的基本理论 p r o c e d u r e ：g e n e t i ca l g o r i t h m s b e g i n t 一0 ： i n i t i a l i z ep ( t ) ： ”初始化种群 e v a l u a t ep ( t ) ： ”对种群中的个体进行适应度计算 w h i l e ( n o tt e r m i n a t i o nc o n d i t i o n ) d o b e g i n r e c o m b i n ep ( t ) t oy i e l dc ( t ) ： ”对种群进行遗传操作 e v a l u a t ec ( t ) ： ”对新个体进行适应度计算 s e l e c tp ( t + 1 ) f r o mp ( t ) a n dc ( t ) ：”选择个体进入下一代种群 t t + 1 ： e n d e n d 通过遗传算法流程图可知一般遗传算法的主要流程如下： ( 1 ) 生一个单个个体长度固定的字符串组成的初始种群。 ( 2 ) 对个体字符串迭代以下过程和过程，直到满足目标适应度函数要求： 分别计算当代种群中所有个体的适应值； 根据一定规则对种群内个体应用复制，交叉，变异规则获得下一代个体。 ( 3 ) 找出后代中个体适应度最高的个体作为遗传算法的最优解。 3 、遗传算法的主要运算操作 通过以上流程可以看出遗传算法最基本的操作有三个：选择( s e l e c t i o n ) 、 交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 。 ( 1 ) 选择运算 选择运算的作用是挑选出种群中优良的即适应度相对较高的个体，可以作为 父体繁殖到下一代中，使得优良基因得以存活下来。根据各个个体的适应度并按 照一定的规则从上一代种群中挑选出一批优良的个体遗传到下一代。遗传算法通 过选择运算可以让更多的优良个体有更大的概率保留下来，并淘汰部分适应度低 的个体，这也体现了达尔文的适者生存规则。选择运算发生的概率称为选择概率。 ( 2 ) 交叉运算 交叉运算也是遗传算法中最主要的操作。通过交叉运算可以通过两个父辈个 体产生一个新的个体，每一个新的个体合并了父辈个体的特性，按照一定的概率 将种群内部个体随机交换他们之间的部分基因，交叉运算体现了信息交换的思 想。交叉运算发生的概率称为交叉概率。而交叉运算又包括以下几种交叉方式【9 1 ： 8 硕士学位论文第二章遗传算法及组卷系统的基本理论 单点交叉：随机设置交叉点，两个父体以交叉点为中心轴交换对应另一部 分以产生两个新的后代个体。 多点交叉：每次选取多个交叉点，两个子体对应的按照奇偶间隔的顺序继 承父辈的基因串。 均匀交叉：按与染色体长度相同的随机码交叉。 算术交叉：按照线性规则组合而成两个新的子个体。 ( 3 ) 变异运算 变异运算发生的概率同生物界一样很低，变异运算是在种群中选择某一个个 体，对其数据串编码中的一位或多位进行突变，变异运算为新个体的产生创造了 机会，变异运算发生的概率称为变异概率。 2 2 组卷问题的评测和建模 组卷是计算机辅助测试系统的核心部分，考试效果依赖于考试质量和考卷质 量。考卷质量又依赖于组卷工作的完成质量。组卷工作的主要作用体现在考试的 代表性和针对性。所谓代表性是指试题抽取能够代表考试内容。针对性则是指考 试本身的编制要合理，对不同的考试能有不同的体现作用。因此，建立标准化试 题库对于组卷工作来说起着非常重要的作用。本节将介绍组卷的基本原则、考卷 的评价指标和各指标间的关系等相关知识，并以此为基础构建组卷问题的数学模 型。 2 2 1 试题评价指标 考试的目的主要有两点：一是检验学生自己对学习的掌握情况；二是教师通 过考试反馈的信息来调整教学方式和知识侧重点。这两个目的对考试本身提出了 目标，即通过考试来知道学生学到了什么，能做什么，因此属于目标参考测试范 畴。 对于目标参考测试，组卷的基本依据主要体现在1 2 0 1 ： 组卷的主要依据是考纲，组卷需要全方位反映考纲的深度和纵度。 组卷要有利于考核学生能力和激发学生自身能力的发展。 组卷要有难度层次，才能体现出学生相互之间的差距。难度过大或过小都 会降低考试的区分度，不仅如此，考试难度过低还会让考生觉得太容易，失去了 积极性；而过高的难度也会让考生失去信心，影响学生对学习的兴趣。组卷的难 度应该体现出大多数中等考生的水平，考试最好的结果是考生分数服从j 下态分 布。 考题需要对考生的学习方法有指导作用。大多数学生都会根据考点的分布 而偏重相应知识点部分的学习。在实际教学中，教师也需要有轻重的对知识点进 9 硕士学位论文 第二章遗传算法及组卷系统的基本理论 行侧重教学。而考题同样也能指导学生对各个知识点进行有目的性的学习，从而 花更多的精力去掌握更重要的知识点。 一道试题的好坏有其评价方法，同样，整套试卷也有相应的评价方法，试题 评价包括下面这些重要的参数指标： l 、试题难度 试题的难度值f 2 l 】是全体考生在该题上成功率的反应，难度越低意味着更多的 考生能答对本题；相反，难度越高答对的考生就越少。难度可以用符号d 来表示， 计算公式为： y d = 1 一竺( 2 2 ) 式中，牙是全体考生在该题上的平均得分，形为该题分值。d 的取值范围 为 0 ，t ，当难度等于0 时试题最容易，难度值等于0 5 时为中等难度，当难度 等于1 时则为最难，也意味着所有考生都不能答对该题。我们通常将难度划分为 五个等级，各等级的区间和定义如表2 1 所示。 表2 - 1 试题难度的等级 难度等级难度区间 易 0 ，0 2 较易( o 2 。0 4 中等( 0 4 ，0 6 较难 ( 0 6 ，0 8 难 ( 0 8 ，1 2 、试题的区分度是指每个试题对考生的水平( 或能力) 区分丌来的程度。 一场测验的区分能力越大则区分度就越高。一般说来难度适中的题目区分度较高 2 2 1 。一般我们将全体考生划为两组，前5 0 为高分组，后5 0 为低分组，则区分 度的计算公式： d ：= 2 ( x h - x ，) 缈 ( 2 - 3 ) 式中，x 。为高分组的平均分，x ，为低分组的平均分，w 为总分。为了给区 分度的高低确定一个标准，在经过大量研究后，对区分度指标提出了如表2 2 所示的判断的标准。 1 0 硕+ 学位论文第二章遗传算法及组卷系统的基本理论 表2 - 2 试题区分度的评价标准 区分度指数评价 o 3 9 以下差，需要淘汰 0 4 - 0 5 9 尚可，需改进 0 6 - 0 7 9 较高 0 8 以上 高 3 、认知程度 认知程度用于反映学生对知识独立获取和驾驭的程度，依次划分为：识记、 理解、应用、分析、综合和评价六个等级。如图2 - 2 所示： 最高层次 最低层次 图2 - 2 认知程度教育i f l 标分类和层次结构图 共同性最少 共同性最多 上述指标是对试题的定性描述，对这些指标的分析有助于我们进行更科学、 合理的组卷。 2 2 2 试卷评价指标 考试的科学性包括考试形式与考试内容的科学性两方面。考试科学与否，需 要用评价指标来进行度量。对于试卷的评价主要有试卷难度和区分度以及试卷的 效度三个参数： 1 、试卷难度 试卷难度计算公式为： p t k ， p = 型f ( 2 4 ) k 、 硕士学位论文 第一二章遗传算法及组卷系统的基本理论 式中以为试卷总题量，p f 与k ，分别为第f 题的难度和分值，k 则为试卷的总 分。 2 、试卷区分度 区分度是对学生能力差异的一种客观反映。学生能力强学习情况好，则在考 分上应该是高分；学生学习能力差且学习不认真则相应的考分会偏低，一套好的 试题应该能够比较准确的区分出学习好的学生和学习差的学生。对于客观题的区 分度评价公式为： 现：旦历( 2 - 4 ) d 盟。可、 o 式中，i 为答对。 慨- - 憋e l 于 t 工- 总分的平均分，百了为答错题目学生总分的平均分， n 。为所有学生总分的标准差。为答对该题学生所占学生总数的比例，y 为答 错该题学生所占学生总数的比例。 同样对于主观题也有相应计算区分度的公式： 芝( e ，一百) ( p 一f ) d = 1 亍焉一 ( 2 - 5 ) 、( e ，- e ) 2 ( p f ) 2 y ，_ l- l 式中，e ，为测试总分，p 为该题得分，e 、p 分别为对应的平均分，n 为考 生总人数。 3 、试卷效度 所谓效度则是反应考试准确性和有效性的指标，表示学生掌握基础知识的能 力和水平。如果考试的结果与学生平时的学习情况一致，那么这样的考试具有较 高的效度，效度有如下的计算公式： d ：善( e ，一百) ( p ，一a( 2 - 6 ) z n 。n 。 式中，e 是e j 的平均值，p 是p 的平均值，n 。和n 。分别为e ，和p 的标准差。 测试过程中，效度的取值范围为e - 1 ，1 。当效度最大值为1 时表示考试结果符合 考试目的。一般的考试效果应该在0 4 - - 0 7 之间比较合适。 2 2 3 组卷的基本准则 为了保证试卷的高信度和高效度，在组卷过程中应遵循以下原则【2 3 1 ：首先， 试卷应该有足够多的题目数量以及较大的知识点覆盖面，避免试卷中重复出现过 1 2 硕+ 学位论文第二章遗传算法及组卷系统的基本理论 多知识点相近的试题，以保证试卷的信度。在一般情况下，认知层次较高且教学 课时较多的知识点允许出现多个题目，但应保持试题难度以及在题型上显现差 别。其次，应该按教学内容的重要程度、题型及认知层次等指标合理的分配试题 分数，从而保证试卷的效度。再次，保持试卷的难度适中，以保障试卷的区分度 在一个较高的水平。根据不同的考试目的，可以对试卷难度进行不同的调整。一 般的知识掌握程度考试可以将难度设定在o 5 左右，而选拔性考试可以适当的提 高难度，但也要避免试卷整体难度过高。同样试卷中各种难度试题也要合理安排， 使试题难度呈阶梯分布。最后还要注意考试总分以及考试时间安排。通常试卷总 分为1 0 0 分，考试时间可为9 0 、1 2 0 分钟。且同一试题不能重复出现在多次考试 中，以防止考生猜题和押题。 根据组卷的基本准则，以及组卷过程中存在的各项约束条件，大体上可以将 对试卷的要求分为以下几个方面【2 4 】：一是试卷质量的约束条件，如试卷难度、试 卷区分度等；二是试卷格式的约束条件，如总题量、题型分布、试卷满分值以及 考试时间等；三是测试内容能力约束条件，如知识点覆盖面、认知层次要求、考 题的内容在教学上的地位( 重点、次重点) 等；四是来自其他方面的约束条件，比 如同一知识点在统一试卷中允许出现的次数、试题在多张试卷上出现的最大次数 等等。以上这些约束条件，并非完全独立，它们相互交叉并在试卷中得到统一2 引。 然而，以上约束条件越多越严格，组卷的难度也就越大。过多的约束条件不但会 使组卷效果不理想，甚至会导致组卷不成功。 基于以上分析，在实际组卷过程中，并不是强调完全满足以上所有约束条件， 而是分轻重的主要考虑以下方面。 ( 1 ) 确定知识点的范围，根据教学大纲要求和学时安排，将知识点分成重点 知识点、次重点知识点以及一般知识点，并指定这三个层次知识点的分数分布： ( 2 ) 确定试卷的整体难度，以满足不同考试的目的，并分布好不同难度等级 的试题构成试卷的比例： ( 3 ) 组织试卷的结构，确定试卷中包含的题型、题数及其分值比例。 2 2 4 目标函数 组卷目标是从试题库中挑选出一定数量的试题并组成最终试卷。实际上组卷 问题是一个多重约束条件下的目标优化问题。通常情况下，并非所有的约束条件 总是能够同时得到满足，人们追求的是最大限度的满足尽可能多的约束条件，也 就是将不满足约束条件的因素减到最小。一般为了满足某些主要的约束条件，可 以放宽对其他次要的约束条件的要求。为了解决多重约束条件下的目标优化问 题，我们借助于加权离差模型来对组卷问题进行建模1 2 6 j 。所谓加权离差模型就是 对各约束条件给定一个权值，优先满足权值大的约束条件，而权值较小者可以相 硕士学位论文第二章遗传算法及组卷系统的基本理论 应的放宽约束条件。 结合以上各约束条件及加权离差模型可得到组卷问题的适应度函数计算公 式： 厂( x ) = w l d l + w 2 pl i + d 。+ d ，：+ d f ，2 ) + w 3 d 3( 2 7 ) 式中d 。、d ：和d ，分别为三类约束条件下的离差，、心和w 3 分别为三类 约束条件的权重值；具体雹为试卷在知识点覆盖面约束上的离差， 吼。+ 吃，+ 噍+ 呸，：为知识点分数的离差，这其中包括重点分数离差和次重分数点 的离差，d 3 为各难度试题分数的离差。d 。、d 厶+ 以。+ 西：+ 4 ，：和d ，的具体计算 方式如下： d 。= 苫一1 。尺r r 。0 8 8 ； d 厶= ， 厶一c ：，b ，： ，= l o 胛， c ：，b ，： 上2 ，= 1 5 l 埘 i d ，= 旧- zc l f b ，：i ，= li7 ；1l d ( ，l = d 2 = d f ，2 = 辫埘 c 2 ，b ，：- u ，c 2 ，b ，2 u 。 - l，- l 0 c ：，b ，2 u ， j - l 卅 三：一c ，b ，： 1 0 卅 c 3 f b ，2 - u 2 ，= l o c ，b ，2 1 ，z 1 ；而种群规模n 比”肯定也要大于1 ，可得 至蛞1 ，从而可得出结论：新的个体引进策略比随机引进策略而言，一阶个体 模式再现的概率要更大。 而引进新个体的数量也是改进算法需要考虑的问题：数量太小，不能保障种 2 5 硕士学位论文第三章基- 丁染色体调控和染色体库的遗传算法 群的多样性；数量太大，也会降低算法的收敛性。结合本文所采取的编码方式， 新个体引入的规模设定为种群规模的十分之一。 3 5 改进遗传算法的流程 通过对本章的面部分的研究，提出了新的改进遗传算法：基于染色体库及染 色体位调控的遗传算法，算法流程如下： ( 1 ) 随机产生一个由确定长度的特征字符串所组成的初始种群。 ( 2 ) 对该字符串种群迭代的执行下面的步骤和，直到满足停止准则为止： 计算种群中每个个体的适应值： 结合染色体库和基于染色体调控的新个体引入策略对个体进行选择操作： 应用单点交叉策略进行交叉运算；以基于染色体位活跃指数的微变异算子进行变 异运算。 ( 3 ) 把在后代中出现的最好的个体字符串指定为算法的执行结果，作为最优 解进行输出；或者因为不满足条件输出失败。 改进遗传算法的流程图如图3 1 所示，其中g e n 为当前代数。 3 6 仿真试验设计与分析 3 6 1 测试函数 为了进一步研究改进算法对解决优化问题的能力，本文采用以下几个测试函 数对算法进行试验。 1 、s c h a f f e r sf 6 函数3 1 1 厂g ，y ) = 0 5 一面s i n 2 而f f - 矿+ y 2 硼_ 0 5 - 1 0 0 _ x , y _ 1 0 0 ( 3 1 1 ) s c h a f f e r sf 6 函数有无数个局部最优解，只有一个全局最优解，最优解为 ( 0 ，0 ) ，全局极大值为1 ，而在最优解( 0 ，0 ) 附近有两圈脊，其值与最大值l 非常 接近，分别为0 9 9 0 2 8 4 和0 9 6 2 7 7 6 ，图3 - 2 给出了s c h a f f