（计算机软件与理论专业论文）基于改进遗传算法的智能组卷研究.pdf

摘要 随着计算机辅助教育研究的不断深入，计算机考试系统作为计算机 辅助教学管理的重要组成部分越来越受到人们的关注。在考试系统中， 自动组卷功能决定了系统能否有效地检验被试者的真实水平，是评价系 统好坏的一个重要因素。因此，组卷算法的研究也成为计算机辅助教育 中的一个重要课题。本文针对现有组卷算法组卷成功率低，耗时长，生 成的试卷难以满足实际考试需求等不足，对遗传算法在组卷问题中的应 用进行了研究。 首先，详细阐述了组卷问题的基本理论及原则，总结了组卷过程中 涉及的约束条件，在此基础上建立了组卷问题的数学模型。然后，针对 遗传算法本身易过早收敛的缺陷，介绍了遗传算法早熟的成因、常见预 防措施及种群多样性度量方法，在传统遗传算法的基础上，对算法中操 作概率的自适应调整方法及遗传操作过程中个体的替换策略进行了改 进，提出了基于种群多样性度量的自适应遗传算法，并通过对比实验对 改进算法的全局搜索性能、效率和有效性进行了验证。实验表明，改进 算法具有较好的克服早熟的能力，在全局搜索性能及收敛速度上较传统 遗传算法有显著提高。最后，将改进算法与组卷问题的具体情况相结合， 采用了一种符合组卷问题特点的分段实数编码方法，并提出了相应的交 叉、变异算子通过仿真实验表明，基于改进算法的智能组卷算法组卷 速度快，组卷质量较好，能够满足实际组卷需求。 关键词组卷算法，加权离差模型，自适应遗传算法，过早收敛，种 群多样性 a b s t r a c t w i t ht h e d e v e l o p m e n t o f c o m p u t e r b a s e d e d u c a t i o n , c o m p u t e r e x a m i n a t i o ns y s t e ma sa ni m p o r t a n tc o m p o n e n to fc o m p u t e rm a n a g e d i n s t r u c t i o ng e t sm o r ea n dm o r ea t t e n t i o n i nt h ee x a m i n a t i o ns y s t e m , t e s t p a p e ra u t o - g e n e r a t i o ni sa l li m p o r t a n tf a c t o ri ne v a l u a t i n gt h es y s t e ma n d d e c i d e sw e t h e rt h es y s t e mc a ne f f e c t i v e l yt e s ts t u d e n t s t r u t hl e v e l s s ot h e s t u d yo ft e s tp a p e rg e n e r a t i o na l g o r i t h mi sas i g n i f i c a n tt o p i co fc o m p u t e r b a s e de d u c a t i o n e x i s t i n gt e s tp a p e rg e n e r a t i o na l g o r i t h m sh a v es o m e d e f e c t s ，s u c h 雏l o ws u c c e s sr a t i o ，c o s t i n gl o n gt i m ea n dp o o rq u a l i t yo f t e s t p a p e r a i m e da t t h e s ed e f e c t s , t h ei n t e l l i g e n tt e s tp a p e ra u t o g e n e r a t i o n a l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m i sr e s e a r c h e di nt h i sp a p e r f i r s t l y , t h eb a s i ct h e o r i e sa n dp r i n c i p l e so ft e s tp a p e rg e n e r a t i o na r e e x p o u n d e da n dt h ec o n s t r a i n tc o n d i t i o n sa r es u m m a r i z e d b a s e do nt h e m , a m a t h e m a t i c a lm o d e lo f t e s tp a p e rg e n e r a t i o ni se s t a b l i s h e d s e c o n d l y , a i m e d a tg e n e t i ca l g o r i t h r a ss h o r t a g e , t h er e a s o nw h yp r e c o c i o u sc o n v e r g e n c ei s e a s yt oo c c l 珥u s u a ls o l u t i o n st op r e c o c i o u sc o n v e r g o n c ea n dm e a s u r e m e n t s o fp o p u l a t i o nd i v e r s i t ya r ei n t r o d u c e d a na d a p t i v ea l g o r i t h mb a s e do n e v a l u r a t i o no f p o p u l a t i o nd i v e r s i t ya l ep r e s e n t e d i nt h ei m p r o v e da l g o r i t h m , t h e r ea r et w oc h a n g e da s p e c t s o n ei st h ew a yt oa d j u s tt h ep r o b a b i l i t yo f g e n e t i co p e r a t o r sa n dt h eo t h e ri st h er e p l a c e m e n ts t r a t e g y t h ev a l i d i t yo f t h ei m p r o v e da l g o r i t h mi sp r o v e db ys i m u l a t i o nt e s t s 髓et e s t sr e s u l t ss h o w t h a tt h ei m p r o v e da l g o r i t h mc a ni m p r o v eg l o b a lo p t i m i z a t i o na b i m ya n dt h e c o n v e r g e n c es p e e d f i n a l l y , t h ei m p r o v e da l g o r i t h mi su s e dt os o l v et e s t p a p e rg e n e r a t i o np r o b l e m a c c o r d i n gt o t h ec h a r a c t e r so ft e s tp a p e r g e n e t a t i o np r o b l e m , ac o d i n gm e t h o dn a m e dp a r a g r a p h e di n t e r g e rc o d i n gi s u s e d d u et ot h ec o d i n gs t r a t e g y , c r o s s o v e ra n dm u t a t i o no p e r a t o ra r e d e s i g n e d t h es i m u l a t i o nt e s ti n d i c a t e st h a tt h ei n t e l l e g e n tt e s tp a p e r a u t o - g e n e t a t i o na l g o r i t h mb a s e d0 1 1i m p r o v e dg e n e t i ca l g o r i t h mc a ns a t i s f y t h en e e d sf o ra c t u a le x a m i n a t i o n s , t h es p e e di sf a s t e ra n dt h eq u a l i t yo ft e s t p a p e ri sb e t t e r k e yw o r d s c o m p o s i n g t e s t p a p e ra l g o r i t h m ，w e i g h t e dd e v i a t i o n s m o d e l ，a d a p t i v eg e n e t i ca l g o r i t h m ，p r e c o c i o u sc o n v e r g e n c e ，p o p u l a t i o n d i v e r s i t y m 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特j | i i j j n 以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在在论文中作了明确的说明。 作者签名：二啦日期：上丝乒旺月卫日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅：学校可以公布学位论文的 全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校 可根据国家或湖南省有关部门规定送交学位论文。 作者签名：j 蛆导师签名堡堕奎兰日期：丝翌年! 月日 硕士学位论文 第一章绪论 第一章绪论 计算机自从问世以来就在各种领域得到了广泛的应用。2 0 世纪5 0 年代末，在 美国心理学家b f 斯金纳教授的程序教学理论基础上，计算机辅助教育( c o m p u t e r b a s e de d u c a t i o n ，c b e ) 逐步发展起来近几十年来，随着计算机技术、网络技术、 人工智能、多媒体处理技术的高速发展以及信息论与教育科学的融合，计算机辅助 教育已逐渐发展成为一门集教育学、心理学、学习理论、信息论、控制理论、计算 机科学、数学等多学科知识于一身的新兴交叉学科并受到各国教育界的的广泛重视 计算机辅助教育包括两个重要的分支领域：计算机辅助教学( c o m p u t e ra s s i s t e d i n s t r u c t i o n ，c a i ) 和计算机管理教学( c o m p u t e rm a n a g e di n s t r u c t i o n ，例i ) c a i 是指用计算机帮助或代替教师执行部分教学任务，向学生传授知识和提供技能训练， 直接为学生服务。c w i 则是利用计算机来实施教育管理功能，主要包括教学管理， 学校行政管理、图书数据管理等啪在我国，计算机辅助教育研究起步较晚，但是 经过近二十年的努力，计算机已被广泛的应用于教育领域中，从教学、研究到管理， 计算机在整个教育活动中发挥着重要的作用，c b e 理论研究及实践取得了丰硕的成 果并得到长足发展。 1 1 智能组卷研究的目的及意义 考试是教学过程中的一个重要环节，是检验学生学习成绩和教学效果的重要手 段，在评价学生学习成绩、激发学生的创造力、提高学习效果等方面起着重要作用。 同时也为教师改进教学方法、提高教学质量提供了必要的信息传统考试主要采用 纸上做答的形式，教师在教学过程中需要花费大量的时间和精力进行试题收集、试 卷编制、批改试卷和考试分析等工作，不但工作量大而且效率低。随着计算机辅助 教育的推进，如何充分地利用计算机，使其代替人工去完成考试过程中的各种繁杂 的重复性工作成为计算机辅助教学管理中的一个重要课题，计算机辅助测验 ( c o m p u t e ra s s i s t e dt e s t ，c a t ) 系统也应运而生完整的c a t 系统主要包括组卷模 块、测验实旄模块、试卷评阅与分析模块以及题库管理模块四个部分，其中组卷模 块的功能是按照测验目的和有关组卷的具体要求在题库中挑选题目，组成一份或多 份等价的试卷。众所周知，试卷的质量决定了一场考试能否有效、准确地检验出答 题者的真实水平因此，组卷模块中的自动组卷功能是评价c a t 系统好坏的一个重 硕士学位论文第一章绪论 要因素，一个良好的组卷系统对于教学活动起着非常重要的作用，而如何保证生成 的试卷能最大程度地满足用户的不同需求，并具有随机性、科学性、合理性，是c a t 系统实现中的一个重点和难点 本课题是为了解决现有计算机考试系统组卷模块难以满足实际考试需求这一问 题提出的。有效的解决计算机考试系统中的组卷问题，对于合理、高效地利用现代 化手段进行教育、教学，实现考试现代化，规范化，减轻教师工作量，提高教学效 率和质量具有重要的实际应用价值。 1 2 自动组卷算法的研究现状 自2 0 世纪6 0 年代美国首先将计算机用于教育测验开始，3 0 多年来计算机辅助 测验系统发展迅速8 0 年代，人们将c a t 系统应用于大规模等级考试，形成了计算 机等级考试系统，典型的有美国的研究生入学考试( g r a d u a t er e c o r d e x a m i n a t i o n 。g 陋) 、工商管理类研究生入学考试( g r a d u a t ef o rm a n a g e m e n ta n d a d m i n i s t r a t i o nt e s t ，g 姒t ) 、t o f e l 等。近十几年来，为了顺应教育现代化的发展 趋势，我国也自主开发研制了一些计算机考试系统，其中具有代表性的有西安交大 等联合编制的“高等学校工科大学物理课程试题库系统”、清华大学等联合编制的 “高等学校工科高等数学课程试题库系统”、山东省高教自考办公室等联合编制的 “高等数学( 财经类) 题库系统”以及全国计算机等级考试系统等等嘲 组卷模块是计算机考试系统中重要的组成部分，组卷模块中的自动组卷功能是 考试系统自动化的核心目标之一，能否生成高效、科学、合理的试卷对于考试系统 至关重要上述考试系统中的组卷模块主要采用三种方式：一种是将试题库看做试 题集，组卷时由教师逐题筛选抽取；二是将试题库看做试卷集，将已经出好的试卷 存储起来，考试时随机抽取一份或多份试卷；三是有自动抽题组卷的功能，可以利 用某种组卷算法自动形成试卷。其中，第一种方法虽然以计算机作为工具，但实质 上仍然是人工组卷；第二种方法由于题库中试卷数量有限，组卷缺乏灵活性，往往 会在多次考试中出现完全相同的试卷；第三种方法生成的试卷灵活性大，但如果缎 卷策略不理想，生成的试卷效果往往不能满足实际考试的要求，仍需要人为对组卷 过程进行干预，以保证试卷的有效性因此，为了提高计算机考试系统组卷模块的 实用性及有效性，组卷算法研究成为计算机考试系统研究的一个重要方面 自动组卷是按照教师和教学的要求，由计算机自动从试题库中选择试题，组成 一份符合知识分布、题型分布、难度分布、区分度分布、认知层次分布、时问分布、 2 硕士学位论文 第一章绪论 分数分布等要求的试卷m 。它是计算机考试系统的重要组成部分 自动组卷问题涉及算法分析、数学建模、优化控制、人工智能等诸多领域2 0 世纪8 0 年代中后期，荷兰的林顿等人针对组卷问题的特点率先把随机线性规划法引 入测验编制领域，经过十几年的发展，产生了多种以线性规划为基础的自动组卷策 略其中具有代表性的有优先权策略、弱并行策略嘲、误差补偿策略旧、随机抽题法 及回溯试探法等。 1 动态优先权策略 在组卷的开始阶段，试卷各项属性有较大的取值范围，指标问的牵制问题不会 立即反映出来，但随着被选试题数的增加。取值范围逐步缩小，矛盾便会随之产生 该策略从试题数量、题型的平均分数、完成率和累计值与指标值差距四个方面综合 评价每道试题的优先权，并在根据组卷过程中上述因素的变化，动态调整试题的优 先权，以缓解各指标阃的矛盾 2 弱并行策略 组卷问题的难点在于指标间的相互制约需要同时满足的指标越多，实现起来 越医难。弱并行策略将组卷指标分为主并发指标和次并发指标。组卷过程中，先保 证主并发指标的平衡，再对已经满足主并发指标的试题组进行调整，使其满足次并 发指标。 3 误差补偿策略 误差补偿策略允许当组卷过程中无法完全满足指标约束条件时，适当地放松约 束条件，只要组卷结果落在允许的误差范围内，都认为组卷成功这种策略在允许 一定误差的前提下减少了不必要的循环搜索，提高了组卷的效率和成功率，解决了 在实际组卷过程中由于指标间的相互牵制、试题库题量有限而约束限制过严造成的 筛选陷入死循环的问题。 4 随机抽题法 随机抽题法是根据组卷问题的控制指针，由计算机随机地抽取一道试题加入试 卷中，此过程不断重复，直到组卷完毕，或已无法从试题库中抽选满足控制指标的 试题为止这种方法结构过程简单，对于单道试题的抽取速度较快，但是要完整地 组成一张试卷，需要搜索较长的时间，并且一旦选题进入死角将不得不从头开始常 常由于约束条件的局部满足而导致组卷失败。 5 回溯试探法 回溯试探法是在随机算法的基础上改进而来的，它将随机选取产生的每一状态 记录下来，搜索失败时，释放上次记录的状态类型，然后再依据一定的规律变化一 3 硕士学位论文 第一章绪论 种新的状态进行试探，通过不断地回溯试探直到试题生成完毕或回到出发点为止阱。 回溯试探法理论上可以遍历每一种可能的状态组合，但当试题库总题量较大，状态 组合是一个巨大的数字，而且算法不能知道矛盾发生的时问，回溯点通常不是前一 个选择，必将在回溯无效后再次回溯，因此，组卷时问长，并且内存空间占用量也 较大。当题库中题量较少，组卷指标简单时，回溯试探法往往较之以上四种方法更 为行之有效。 针对上述方法的不足，不少研究人员对随机抽取法和回溯试探法进行了改进， 如雷国雨等对组卷参数进行编码优化，将约束条件转化为屏蔽码和条件码完成随机 抽取过程嘲；张国才等提出的基于分割策略的随机组卷方法帆；王萌、王晓荣等提出 了一种集合随机抽选组卷算法，每次抽题均从满足抽取条件的试题集合中选取最优 试题”1 ；郝彦、陈丽燕等充分利用题库中试题的基本信息，通过对题量、试题历史 信息及知识点分布的调整和控制实现试题的智能筛选“o ；金汉均、郑世珏等将众多 试题数据进行分段处理，在各段内随机抽取“4 这些改进算法在一定程度上提高了 组卷算法的效率和组卷结果的有效性，对一些小规模的试题库有着较好的性能，但 是这些算法没有从根本上改变传统组卷算法的缺陷，对于大规模题库仍显得力不从 心，具有很大的盲目性，缺乏智能性，难以满足组卷需求。 i 3 遗传算法及其在组卷问题中的应用 面对传统组卷算法存在的不足，很多研究人员将遗传算法、模拟退火算法、禁 忌搜索算法等智能优化算法及其改进算法应用到组卷问题中，比如楼玉萍等提出的 基于p b i l 进化算法的自动组卷算法“”；刘仁金等提出的基于粒度合成计算原理的智 能组卷策略“”等，并取得了很好的效果。 1 遗传算法的产生与发展 在众多的优化搜索方法中，遗传算法是后起之秀。它是2 0 世纪6 0 年代末期到 7 0 年代初期由美国m i c h i g a n 大学的j - h h o l l a n d 教授及其学生和同事发展起来的。 六十年代初，i i o l l a n d 教授开始认识到生物的自然遗传现象与人工自适应行为的相 似性。提出了在研究和设计人工自适应系统时可以借鉴生物自然遗传的基本原理， 模仿生物自然遗传的基本方法。1 9 6 7 年，他的学生j d b a g e l e y 在其博士论文中首 次提出“遗传算法( g e n e t i ca l g o r i t h m ) ”的概念在b a g e l e y 的论文中，采用了双 倍体编码，发展了与目前g a 类似的复制、交叉、变异、显性、倒位等遗传操作，并 对g a 早熟机理进行了研究“目 4 硕士学位论文 第一章缮论 1 9 7 5 年是遗传算法发展史上十分重要的一年。h o l l a n d 教授总结了十几年的研 究思想，出版了第一本系统论述遗传算法和人工自适应系统的专著( a d a p t a t i o ni n n a t u r ea n da r t i f i c i a ls y s t e m s 。该书详细阐述了遗传算法的基本理论和方法， 发展了一整套模拟生物自适应系统的理论提出了对g a 理论研究和发展极为重要的 。模式定理( s c h e m at h e o r e m ) 一，从而奠定了遗传算法研究的理论基础。同年，d ej o n g 深入领会了模式定理并进行了大量的纯数值函数优化计算试验，建立了遗传算法的 工作框架，完成了具有指导意义的博士论文。a na n a l y s i so fac l a s so fg e n e t i c a d a p t i v es y s t e m ”。他还建立了著名的d ej o n g 五函数测试平台，定义了g a 性能 评价标准，并以函数优化为例，对六种遗传算法方案的性能及机理进行了详细的实 验和分析时他的工作为遗传算法的研究及广泛应用奠定了坚实的基础。 2 0 世纪8 0 年代以来，遗传算法进入了蓬勃发展时期，无论是理论研究还是应 用研究都十分活跃遗传算法被广泛应用于各种复杂系统的自适应控制及复杂优化 问题中，并取得了良好的效果1 9 8 5 年，在美国召开了第一届国际遗传算法会议 ( i c g a ) ，并成立了国际g a 学会。1 9 8 9 年，g o l d b e r g 出版了优秀著作( g e n e t i c a l g o r i t h m si ns e a r c h ，o p t i m i z a t i o n ，a n dm a c h i n el e a r n i n g ，总结了g a 研究的 主要成果，对g a 及其应用作了全面丽系统的论述，奠定了现代g a 的基础1 9 9 1 年， ld a v i s 编辑出版了( h a n d b o o ko fg e n e t i ca l g o r i t h m s ，其中包括了g a 在工程 技术和社会生活中的大量应用实例，对遗传算法的有效应用具有重要的指导作用 我国有关遗传算法的研究，从2 0 世纪9 d 年代以来一直处于上升时期，特别是 近年来，遗传算法的应用在许多领域取得了令人瞩目的成果“嘲，并且在算法改进 及理论研究d 删方面也作出了成功的探索。 2 遗传算法的基本原理及结构 遗传算法是模仿自然界生物进化进制发展起来的随机全局搜索和优化方法，它 借鉴了达尔文的物竞天选，适者生存的进化理论和孟德尔的遗传学说其本质是一 种高效、并行的全局搜索方法，它能够在搜索过程中自动获取和积累有关搜索空间 的知识，并自适应地控制搜索过程以求得最优解。 g a 模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群 出发，通过随机选择、交叉、变异等遗传操作。淘汰不适应环境的个体，使种群进 化到搜索空间中更好的区域，通过一代代的繁衍进化，最后收敛到一群更适应环境 的个体，求得问题的最优解完整的遗传算法运算流程如图l _ l 所示。 从图中可以看出，遗传算法主要由编码、个体适应度评价、遗传操作、新旧个 体替换等步骤组成，基本的遗传操作有选择、交叉、变异三种。g a 的每个步骤都有 ， 硕士学位论文 第一章绪论 图i - i 遗传算法运算流程 多种解决方法，比如编码方式可以根据实际问题的需要采用二进制编码、格雷编码、 实数编码等；选择操作可以采用轮盘赌选择、锦标赛选择、最优保留选择等；交叉 操作有单点交叉操作数、多点交叉操作数、均匀交叉操作数和算数交叉操作数等等。 遗传算法为各种复杂系统优化问题提供了一个通用的框架，具有很大的灵活性和通 用性。 3 遗传算法的特点及不足 大多数古典优化算法如最陡下降法、爬山法等，是基于一个单一度量函数的梯 度或较高次统计，产生一个确定性的试验解序列；与传统优化算法不同，遗传算法 是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，它通过模拟自然进化 过程搜索最优解。与传统优化算法相比，遗传算法具有如下特点噙硼： ( 1 ) 遗传算法是对变量的编码进行操作，而不是变量本身。传统的优化算法往 6 硕士学位论文 第一章绪论 往直接利用变量的实际值来进行优化计算，而遗传算法是以变量某种形式的编码作 为运算对象。对一些无数值概念或很难用数值表示的优化问题，编码处理方式显示 7 其优越性 ( 2 ) 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用 目标函数值，而且往往需要目标函数的导数及其它辅助信息才能确定搜索方向而 遗传算法仅使用由目标匾数值变换来的适应度函数值，就可确定进一步的搜索方向 和搜索范围。这一特性使得很多目标函数无法或很难求导的优化问题以及组合优化 问题可以方便地应用遗传算法求解。另外，直接利用目标函数值或个体适应度可以 把搜索范围集中于适应度较高的搜索空问，提高了搜索效率 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息传统优化算法往往是从解空间 中的一个初始点出发进行迭代搜索，搜索效率不高并且对初始点敏感度大，经常使 搜索过程陷于局部最优解而停滞不前而遗传算法按并行方式搜索一个种群数目的 点。可同时搜索解空问内的多个区域，并相互交流信息这种搜索方式虽然每次只 执行与种群规模n 成比例的计算，但实质上已进行了大约o ( n 3 ) 次有效搜索，这使得 遗传算法能以较少的计算获得较大的收益 ( 4 ) 遗传算法使用概率搜索技术很多传统优化算法使用确定性的搜索策略， 一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，初始解的选择对 最后的结果起着决定性的作用。而遗传算法是一种自适应概率搜索技术，其选择、 交叉，变异等运算都是以概率的方式来进行的，增加了搜索过程的灵活性，尽管这 种概率方法也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，适 应度不高的个体将逐渐被淘汰 作为一种优化方法，遗传算法也存在着自身的不足。由于计算机条件的限制， 遗传算法的种群规模是有限的，并且在算法运行过程中通常保持群体规模不变，而 遗传操作中的选择操作往往使优良个体呈指数级增长，因此，在进化初期。种群中 往往会出现大量相同的优良个体，种群多样性丧失，导致算法只能收敛于局部最优 解，引起“早熟”现象的发生另外，遗传算法中参数的确定没有通用的方法，通 常只能通过大量的实验来确定，而不恰当的参数又往往导致算法的搜索性能不高嘲 针对遗传算法存在的不足，众多学者致力于推动遗传算法的发展，改善遗传算 法的性能，提出了各种改进的遗传算法，比如：结合了精英选择、异物种重组，大 变异的改进遗传算法算法；采用变长染色体的m e s s y6 a 嘲；交叉，变异概率可变的 自适应遗传算法”；基于小生境技术的遗传算法；根据问题自身特点引入非标准遗 传操作算子嘲；与传统启发式算法相结合的混和遗传算法嘲以及并行遗传算法洲等 7 硕士学位论文 第一章绪论 等。这些改进算法不但在一定程度上弥补了遗传算法的缺陷，使遗传算法的性能和 效率得到了提升，而且为遗传算法的研究发展提供了新的思路。 4 遗传算法在组卷问题中的应用 正是因为遗传算法与传统优化算法相比具有简单通用、鲁棒性强、适于并行处 理、全局寻优等特点，较之传统组卷方法，遗传算法更适用于组卷问题。近年来， 已有不少研究人员将遗传算法及其改进算法应用于组卷问题，并取得了一定的成绩， 为智能组卷问题提供了新的解决办法王友仁、施玉霞等在系统分析组卷理论的基 础上提出了一种基于自适应多点变异混合算法的智能组卷方法眦1 ；焦翠珍、戴文华 等改变了传统的遗传算法编码方式，根据组卷问题的特点提出了十进制编码，试验 表明该方法取得了比传统= 进制编码更好的效果铷；董敏，霍剑青等将项目反应理 论与自适应遗传算法相结合。有效地解决了基于i r t 的智能组卷问题铷：管宝云、 尹琦将遗传算法与模拟退火算法相结合的混和算法应用于自动组卷系统的设计，较 好的发挥了两种算法的长处：陈宇、陈治平等将启发式思想应用于遗传算法。确 保进化过程沿着有利于最终问题求解的方向进行，有效地降低了非可行解造成的系 统开销嘲 将遗传算法应用于组卷问题仍处于研究阶段针对遗传算法自身存在着不足以 及组卷问题的特点，需要探索出更加符合组卷问题特点并能够克服遗传算法缺陷的 改进算法。 1 4 本文的主要工作 本文主要对计算机智能组卷的发展及应用现状进行系统总结，分析现有组卷算 法存在的不足；根据教育心理测量学理论及教师组卷心理，对组卷中涉及的参数指 标和组卷要求进行分析，建立组卷问题的数学模型；通过对遗传算法及其存在的问 题进行分析，提出一种基于种群多样性度量及小生境技术的改进遗传算法，对改进 算法进行仿真实验，证明算法的有效性，并将改进算法应用于组卷问题中主要篇 章内容如下： 第一章介绍自动组卷算法的研究现状，分析常用组卷算法的原理及存在的问题， 对遗传算法的基本理论及其在组卷算法中的应用进行概述并简要介绍本课题的研究 目的、意义及本文的主要工作； 第二章从教育心理测量学的角度对组卷问题的原理进行阐述，其中包括试卷及 试题的评价指标、各指标间的关系、组卷的基本原则，分析教师组卷活动并在此基 硕士学位论文 第一章绪论 础上建立组卷问题的数学模型； 第三章分析遗传算法早熟的主要原因，介绍克服早熟现象的常见措施以及种群 多样性度量的常用方法，在此基础上提出基于种群多样性度量的改进自适应遗传算 法，并对改进算法的有效性进行验证； 第四章详细介绍利用改进算法求解组卷问题的具体步骤，其中包括编码方式、 交叉、变异算子的设计，并使用模拟题库进行仿真实验； 第五章总结全文，对智能组卷研究进行展望。 9 硕士学位论文第二章组卷问题的基本理论及数学模型 第二章组卷问题的基本理论及数学模型 试卷编制是教学活动中的一个重要环节。编制不出高质量、可实用的试卷就无 法有效地检验学生对知识的掌握水平及教师的教学效果，教学活动就失去了有力的 指导。任何问题的有效解决都需要有坚实的理论作为依托，组卷问题也不例外。从 学科角度来看，组卷问题属于测验编制范畴，是心理和教育测量学的核心内容。在 心理与教育测量学中，存在着两种主要的测验理论：经典测量理论( c l a s s i c a lt e s t t h e o r y ，c t t ) 和项目反应理论( i t e mr e s p o n s et h e o r y ，i r t ) 。经典测量理论将测试 者的能力水平分布假设为正态分布，因此，测验后的成绩分布也应该呈正态分布， 只有测验分数呈正态，测试才可以认为是客观有效的。而且测验的编制也以追求测 验总分呈正态分布为最高目标田。经典测量理论是测验的最一般、最基本的理论， 应用极为广泛，现阶段大部分考试试卷编制及考试评估都是以经典测量理论为基础 项目反应理论是一种建立在潜在特质理论基础上的新兴的心理与教育测量理论目 前，也有少部分考试系统采用项目反应理论，考试时系统根据测试对象的答题馈况 给出下一道测试的题目，不同能力水平的测试对象测试的题目也各不相同鉴于项 目反应理论成立的假定条件较强，目前通用的考试规则不能很好的满足其假定条件 ，本文仍采用经典测量理论作为组卷问题的理论基础 2 1试题的基本属性指标 组卷就是从大量试题中选取一定数量的试题，组成一份合乎考试要求的试卷 不同的试题组合而成的多份试卷在质量上也不尽相同，试卷中试题的质量及其他属 性指标对试卷的检验能力起到了决定性的作用。因此，在组卷前，需要对试题进行 分析以确定每道试题的属性本节将对试题的基本属性指标做简要介绍 2 1 t 难度 难度是衡量试题质量的一个重要指标。试题的难度是指参加测试的学生群体在 该题上的失分率。根据试题的记分方式不同，难度计算公式也稍有不同。若试题为 采用“全或无方式”记分方式的客观题，难度的计算公式为； p ；1 一三 刀 ( 2 一1 ) 其中，为答对该题的人数，玎为参加考试的总人数。若试题为有错酌情扣分 i o 硕士学位论文第二章组卷匈题的基本理论及数学模型 的主观题，难度的计算公式为： p ；1 - 墨 k ( 2 _ 2 ) 其中，i 为参加考试的学生在该题上的平均得分，j 表示该题的满分分值。 由难度的计算公式可知，难度值pe 【0 ，1 】并且尸越大，试题的难度越大，答对 的人数越少一般情况下，我们把试题难度划分为五个等级，难度区间与难度等级 间的对应关系如表p 1 1 难度等级易较易中等 较难 难 i 难度区间 0 0 2 】( 0 2 。o 4 】( o 4 0 6 】( 0 6 。0 8 】( o - 8 1 】 2 1 2 区分度 区分度是衡量试卷质量的又一重要指标，用于反映试题对参加测试的不同能力 水平学生的区分程度，用字母d 表示区分度一般可采用高低分组法计算，计算公 式如下； d = 益一互( 2 - 3 ) kk d 为试题区分度的估计值，j 0 和玩分别为高分组和低分组在该试题上的平均 得分，k 为试题的满分分值 根据公式，试题区分度的取值范围在- 1 和l 之间，区分度过低表明该试题的 质量不佳，这种试题对测验总分起着不良的干扰作用。具体的区分度评价标准如表 2 - 2 所示 由难度和区分度的计算方法可知，试题的难度和区分度依赖于考生的答题情况， 同一道试题对不同能力水平的学生群体施测可能会得到不同的难度和区分度只有 考试实施后，才能准确地计算出对该批考生来说这两项指标的取值。但由于学生的 能力水平基本呈正态分布，尽管情况略有不同，但大体相似因此，编制试卷时， 试题的难度及区分度可由经验丰富的教师确定一个初始值，再根据学生的实际考试 情况进行适当的修正，作为下次组卷时试题质量的依据。 硕士学位论文第二章组卷问题的基本理论及数学模型 表2 - 2 试题区分度评价标准 区分度评价 0 4 0 以上优良 0 3 0 o 。3 9 合格 0 2 0 o 2 9勉强可用，需修改 0 2 0 以下应淘汰 难度和区分度是对试题质量的定量分析。除了这两项指标外。每道试题还有诸 如认知程度、题型、知识点等属性其中，认知程度用于反映学生对知识独立获取 和驾驭的程度，从低级到高级可分为识记，理解、应用、分析、综合、评价六个层 次这些指标是对试题的定性描述，对于科学评价试题、合理组卷起着重要作用。 2 2 衡量试卷质量的指标 2 2 1 试卷的信度与效度 在教育测量学中，衡量试卷质量的基本指标是试卷的信度和效度 试卷的信度是表示试卷作为测试工具的可靠性程度的指标试卷信度在很大程 度上决定了考试的信度，因此，试卷信度常用于代指考试信度。一项考试的信度就 是这项考试的一组成绩和对同一组考生实施等价考试所得的另一组成绩相比较的一 致性程度。一致性越高，试卷信度越大，考试越可靠。信度通常可以通过对测试群 体实施多个内容成分、试题形式、难度及区分度等指标相当的平行测试来计算。 试卷的效度是衡量一项考试实现其既定目标的成功程度的指标，它反映了试卷 内容与教学大纲或考试大纲的吻合程度。效度高的试卷，能够较准确地测试出学生 掌握和运用所学知识的真实度。根据教学大纲或考试大纲进行命题，且各单元试题 分数分配与学时数分配基本保持一致，成正比关系，这是保证试卷效度的基础。 2 2 2 试卷的难度与区分度 鉴于试卷的信度与效度须在考试实施后才能进行评价，无法作为组卷时判断生 成试卷质量的依据本文引入试卷的难度嘲和区分度作为组卷时衡量试卷质量的指 标。 试卷难度的计算公式为： 硕士学位论文第二章组卷问题的基本理论及数学模型 只k 。 p = 且j 广( 2 - 4 )鬈 坍为试卷的总题量，只为第j 道试题的难度，t 为第f 题的分值，k = 杰k ，即 试卷的总分。 试卷区分度的计算公式为： d ，毛 d27( 争5 ) 其中，日为试卷中第i 题的区分度 试卷的难度和区分度有着密切的联系。试卷过难或过易都无助于提高考试区分 不同能力水平考试的能力，试卷的区分度较低一般情况下，具有中等难度( 难度在 0 4 到0 6 之问) 的试卷，区分度较大。 2 3 组卷的基本原则及教师组卷活动分析 一份合格的试卷不是试题的随意堆砌只有按照一定的原则，精心选择内容、 难度、区分度等属性指标相匹配的试题，才能保证试卷的信度和效度，满足实际考 试的需求。 2 3 1 组卷的基本原则 为了生成具有高信度和高效度的试卷，组卷过程中应遵循以下几点原则嘲： ( 1 ) 试卷有适当多的试题数和较大的内容覆盖面，尽量避免同一试卷中出现过 多内容相近的试题，以保证试卷的信度一般情况下，认知层次较高、教学时间较 长的章节或知识点允许出现多个题目，但应尽量有难度及题型的差别 ( 2 ) 按教学内容的重要程度( 重要知识点、次要知识点和一般知识点) 、题型及 认知程度等指标合理地分配试卷分数，以保证试卷的效度 ( 3 ) 试卷的难度尽量适中，以保证试卷有较高的区分度根据考试的目的，可 适当对试卷难度进行调整，比如以检验知识掌握程度为目标的一般性考试，可设定 试卷难度在0 5 左右；选拔性考试可适当地加大难度，尽量避免试卷难度过高或过 低试卷中不同难度试题的比例也应合理安捧，试题难度应呈梯度分布 ( 4 ) 试卷有一定的总分及时间限制。一般试卷满分值为1 0 0 分，考试时间可为 1 3 硕士学位论文 第二章组卷问题的基本理论及数学模型 9 0 分钟、1 2 0 分钟、1 5 0 分钟等。 ( 5 ) 试卷中试题应避免连续多次出现在考试中，以防止押题、猜题现象的发生。 2 3 2 教师组卷活动分析 根据组卷的基本原则，我们可以总结出组卷问题的各项约束条件，大体上可以 分为以下几个方面：一是试卷质量约束条件，如难度、区分度等；二是试卷格式约 束条件，如题型分布、总题量、试卷满分值、考试时间等；三是测验内容能力约束 条件，如内容覆盖面、认知程度要求、所考内容的教学地位( 重点、次重点) 等；四 是其他方面的约束条件，比如同一知识点最多能允许出现的题数、试题连续出现的 最大次数等等以上这些约束条件，并非完全独立，它们相互交叉并在试卷中得到 统一删。然而，约束条件越多、越严格，组卷难度就越大过多的约束条件不但会 使组卷效果不理想，甚至会导致组卷失败 因此，在教师实际组卷过程中，并不是追求以上约束条件全部满足，而是主要 从以下几个方面对组卷问题进行考虑： ( 1 ) 确定考察知识点的范围；根据教学大纲的要求及学时数，决定哪些是重点 知识点，哪些是次重点知识点，哪些是一般知识点，并指定三个层次知识点的分数 分布； ( 2 ) 根据考试的目的，确定试卷的整体难度，并分析不同难度等级的试题在试 卷中所占的比例； ( 3 ) 组织试卷的结构，确定试卷- 中包含的题型、题数及其分值比例。 2 4 组卷问题的数学模型 通过前面的论述，我们可知组卷过程就是从题库中抽取一定量的试题，生成一 份或多份满足一定约束条件的试卷，组卷闯题实质上是一个多重约束目标优化问题， 弗且满足约束条件的最优解不是唯一的。本节将从试卷难度分布的计算方法、约束 条件、目标函数三个方面对组卷的数学模型进行讨论。 2 4 1 基于正态分布的试卷难度分布计算模型 一份试卷是由难度不同的各种试题组成的。试卷在难度上的合理性取决于各种 不同难度试题所占比例的合理性，即难度分布的合理性1 只有合理地分配各种不 同难度试题的比例，才能保证生成的试卷在难度上满足考试需求。 根据经典测量理论，学生的能力应该大体呈正态分布，考试的成绩也应服从正 态分布。正态分布z ，c r 2 ) 的分布密度函数为嘲； 1 4 硕士学位论文第二章组卷问题的基本理论及数学模型 m ) = 去e 簪一只 ( 2 - 6 ) 其中，口为随机变量x 的均值，它决定了正态分布曲线峰值的位置；矿为随机 变量的标准差，它反映了随机变量与的差异，决定了正态分布曲线的形态。z 一 定时，仃越大，随机变量的取值越分散，曲线越平坦，如图2 _ l 所示。盯一定时， 增大，曲线沿x 轴向右平移。在某一区间内，曲线与j 轴包围的面积等于随机变量 落在该区间内的概率，在卜吣，如。】上，面积等于l 。在学生考试成绩的正态分布中， 随机变量工代表考生的成绩， 表示考生的平均分，表示考生成绩的标准差。 塞 图2 - 1不变时，不同标准差的正态分布示意图 x 在经典测量理论中，测验的编制目标是追求测验总分呈正态分布针对学生中 中等水平学生占大多数的情况，试卷中的题目也应以中等难度试题居多，并应包含 部分难度较低和难度较高的试题，以形成难度台阶，保证考生成绩形成差距。因此， 试卷中各种不同难度试题所占的比例也应呈正态分布嗍 由于试题难度的取值范围为 0 ，1 ，要使正态分布有效地描述试卷中的难度分 布，必须使 o ，1 区间内正态分布曲线与石轴包围的面积足够大当试卷的整体难 度确定后，曲线在 0 ，1 区问内包围的面积由盯决定，口越大，曲线越平坦，区间内 曲线与x 轴包围的面积也越小为了确保正态分布的有效性，需要对口进行限制。 根据概率论中著名的。3 口准则”，即服从正态分布( 以c