（计算机软件与理论专业论文）一种基于遗传算法的智能组卷模型与系统设计.pdf

t ：d k ： 弋、 1 ， 4 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取 得的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文 中作了明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：王墨益宝 日期： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即： 东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编本学位 论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：舀盥， 日 期：勉f 么五。岁 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名：国垂垒 日 期：边么之= 6 兰厂 电话： 邮编： 1省 ，itj qj，。， 1 0 摘要 组卷问题是在一定约束条件下，多目标参数优化的问题。通过对各种传统的组卷算 法的分析发现其有组卷速度慢、成功率较低、试卷质量不高等缺点。智能组卷的效率和 质量完全取决于试题库设计以及抽题算法的设计。如何设计一个算法从试题库即快又好 的抽出一组最符合考试要求的试题，是本文研究的目的。 在对国内外大量相关文献分析研究的基础上，发现遗传算法非常适合解决这类问题， 因为，遗传算法具有自身的全局搜索性、随机性、较好的编码方式和高度的并行性，因 此本文使用遗传算法进行组卷问题的求解。本文提出了一种基于遗传算法的智能组卷系 统总体设计方案。该系统能够按照试题类型、试题数量、知识点、难度系数、区分度、 曝光度、最近出题时间、答题时间等约束条件进行快速搜索，从而找到最佳组卷方案， 组出理想的试卷。 遗传算法本身并不能直接解决智能组卷问题，其中还有一个关键问题，如何把智能 组卷问题映射为一个数学模型。只有在这个基础上，遗传算法才能发挥出作用。智能组 卷数学模型也是本文的一个研究重点。 论文分析了组卷目标要求，建立了智能组卷系统问题求解的理论模型，根据本论文 提出的系统设计方案和组卷数学模型成功实现了东师理想中小学智能组卷系统。通过系 统的运行，验证了系统具有一定的通用性、可扩展性和安全性，能较好的满足复杂的组 卷要求，有助于实现试卷质量的控制、提高教学效率、推行教考分离。 关键词：试题库；组卷模型；智能组卷；遗传算法 a b s t r a c t t e s t p a p e r i su n d e rc e r t a i n c o n s t r a i n t s ，m u l t i o b j e c t i v ep a r a m e t e ro p t i m i z a t i o n p r o b l e m s t h r o u g hav a r i e t yo f t r a d i t i o n a la n a l y s i so ft h ea l g o r i t h m i cf o u n dt oh a v et e s tp a p e r w a ss l o w , t h es u c c e s sr a t eo fl o wq u a l i t yp a p e rt h ed i s a d v a n t a g e s t e s tc o n s t r u c t i o ne f f i c i e n c y a n dq u a l i t yd e p e n d se n t i r e l yo nt h ed a t a b a s ed e s i g n 部w e l la sq u e s t i o n sa r i t h m e t i c d e s i g n h o wt od e s i g na na l g o r i t h mt h a ti sf a s ta n di t e mb a n kf r o mt a k i n gag r o u po fg o o dt o m e e tt h ee x a m i n a t i o nr e q u i r e m e n t so f m o s tq u e s t i o n si st h ep u r p o s eo ft h i ss t u d y i nt h ea n a l y s i so ft h er e l a t e dd o c u m e n t sa th o m ea n da b r o a d ，b a s e do ng e n e t i ca l g o r i t h m w a sf o u n dv e r ys u i t a b l ef o rs o l v i n gs u c hp r o b l e m s ，b e c a u s et h eg e n e t i ca l g o r i t h mh a si t so w n g l o b a ls e a r c h ，s t o c h a s t i c ，b e t t e re n c o d i n ga n dah i g hd e g r e eo fp a r a l l e l i s m ，s ot h i s t e s tp a p e r u s eo fg e n e t i ca l g o r i t h m st os o l v et h ep r o b l e m t h i sp a p e rp r e s e n t sag e n e t i ca l g o r i t h mb a s e d d e s i g no fi n t e l l i g e n tt e s ts y s t e mo ft h ep r o g r a m t h es y s t e mc a nb ei na c c o r d a n c ew i t ht h et y p e o ft e s tq u e s t i o n s ，t e s tt h en u m b e ro fk n o w l e d g ep o i n t s ，d e g r e eo fd i f f i c u l t y , d i s c r i m i n a t i o n ， e x p o s u r e ，r e c e n t l yo u to fq u e s t i o nt i m ea n da n s w e rt i m ec o n s t r a i n t sf o rr a p i ds e a r c ht of i n d t h eb e s tt e s tp a p e rp r o g r a m ，t h ei d e a lg r o u po f p a p e r s g e n e t i ca l g o r i t h mb yi t s e l fc a nn o td i r e c t l ya d d r e s st h ei s s u eo fi n t e l l i g e n c et e s tp a p e r , o f w h i c ht h e r ei sak e yi s s u e ，h o wt om a pt h ei n t e l l i g e n c et e s tp a p e ram a t h e m a t i c a lm o d e lo ft h e p r o b l e m o n l yo nt h i sb a s i s ，c a np l a yar o l ei nt h eg e n e t i ca l g o r i t h m m a t h e m a t i c a lm o d e lo f i n t e l l i g e n tt e s tp a p e ri sa l s oar e s e a r c hf o c u so f t h i sa r t i c l e t h i sp a p e ra n a l y z e st h et e s tp a p e rt h eo b j e c t i v e sa n dr e q u i r e m e n t s ，t h ee s t a b l i s h m e n to f a ni n t e l l i g e n tt e s ts y s t e mo ft h et h e o r e t i c a lm o d e lo fp r o b l e ms o l v i n g ，a c c o r d i n gt ot h e p r o p o s e ds y s t e md e s i g na n dt e s tp a p e rm o d e ls u c c e s s f u l l yi d e a ls c h o o li ne a s td i v i s i o n i n t e l l i g e n tg r o u p i n gs y s t e m t h r o u g ht h eo p e r a t i o no ft h es y s t e m ，v e r i f yt h a tt h es y s t e mh a s s o m ev e r s a t i l i t y , s c a l a b i l i t ya n ds e c u r i t y , t ob e t t e rm e e tt h ec o m p l e xr e q u i r e m e n t so ft e s tp a p e r , e x a m i n a t i o np a p e rw i l lh e l pt oa c h i e v eq u a l i t yc o n t r o l ，i m p r o v et e a c h i n ge f f i c i e n c ya n dt o i m p l e m e n ts e p a r a t i o no ft e a c h i n ga n dt e s t i n g k e yw o r d s ：i t e mb a n k ；t e s tp a p e r ；i n t e l l i g e n c et e s tp a p e r ；g e n e t i ca l g o r i t h m 1j馏 目录 摘要i a b s t r a c t - i i 目录i 第一章绪论l 1 1 课题研究的背景及意义1 1 2 国内外研究现状1 1 3 主要工作与组织结构5 第二章智能组卷的研究7 2 1 智能组卷的基本原则7 2 2 试卷的属性指标7 2 3 遗传算法介绍1 1 第三章基于遗传算法的智能组卷数学模型1 8 3 1 试卷的数学模型i 8 3 2 试卷指标的量化方法1 8 3 3 偏差计算2 1 3 4 适应度函数设计2 3 3 5 遗传算法2 3 第四章基于遗传算法的智能组卷系统设计2 7 4 1 设计原则2 8 4 2 系统难点分析2 9 4 3 系统功能分析2 9 4 4 系统结构3 6 4 5 数据库设计3 7 4 6 系统安全设计4 0 第五章结束语4 1 参考文献4 2 致谢一4 4 i i i 1，碰 东北师范大学硕士学位论文 第一章绪论 经过几十年的发展，计算机技术已经发生了重要的变革，在外观、体积、性能等方 面都有很大的提高。计算机的应用领域非常广泛，已经渗透到了生活的方方面面。那么 在计算机辅助教学方面，也逐渐发展成了一个新型的学科：包括心理学，教育学、控制 理论、系统论、电子、信息、计算机等基础学科，受到整个教育界的高度重视。 那么在计算机辅助教学领域中，应用计算机从题库中按照一定要求自动抽取试题， 然后形成试卷的这种智能组卷算法一直是一个比较热门的课题，它是计算机辅助教学的 一个必可或缺的部门。因此有很大的研究价值和应用价值，而且拓展空间很大。现在智 能组卷在自动化考生系统中也是一个核心的研究课题。 1 1 课题研究的背景及意义 智能组卷算法之所以在计算机辅助教学中比较重要，是因为它将现代的教育理论和 人工智能技术应用到组卷当中，能够智能的设计试卷的结构和内容，包括试卷的难易度， 知识点，题型和题量等，使生成的试卷质量比较高。与传统的人工组卷相比，智能组卷 系统具有如下特点卅： 1 要用智能组卷系统之前一定要建立一个具备广泛应用价值的试题库，那么这个试 题库不但具备完整的试题信息，而且试题都是经验丰富的老师总结归纳的试题，并由权 威部门统一维护和管理。 2 智能组卷系统可以代替人工来出题组卷，而且不会出现一些人为的低级错误，工 作效率高。完全把老师解放出来，不必在去为了准备一次考试而进行翻阅资料，选择试 题，权衡试卷各项参数等繁重的工作。 3 由于智能组卷是应用先进的人工智能技术和教育理论到组卷系统中的，那么自然 具有一定的科学性、合理性、智能性。 自从计算机开始出现以后，不论是什么功能、什么系统，它都是一个目的，让计算机 代替人来完成一些重复、繁琐的工作，那么智能组卷技术的发展也是以这个目标为宗旨 的。因此系统如何能够保证它所为人类完成的工作是能让人们满意的呢? 一份试卷要让 人满意，那么一定要满足人们对试卷的要求而且具备科学性、快速性和随机性等方面的 要求。对于减轻教师工作强度，使老师能够抽出更多的精力去搞教学工作，必然是会提 高教学质量，因此有着实际的应用价值和研究价值。 1 2 国内外研究现状 从上世纪六七十年代开始，美国等国家最先在测试系统中应用计算机。经过多年来 1 东北师范大学硕士学位论文 的研究，计算机辅助系统得到了迅速的发展。到八十年代，人们把计算机辅助系统应用 于大规模的考试系统，如各种资格考试，职称考试，升学考试等。还有g r e ，t o f e l 等 出国英语考试。在最近l o 年来，由于现代教育化事业发展很快，对计算机的智能性、 自动性需求增大，我国一些研究人员也自主开发了一系列的组卷系统，其中西安交大联 合推出的“高等学校工科大学物理课程试题库系统 和清华大学等联合编制“高等学 校工科高等数学课程试题库系统比较典型。对于一个能够生成各个方面的要求都达标 的试卷的智能组卷考试系统来说组卷模块是其核心功能。上述介绍的组卷系统一般用以 下方式来实现的：( a ) 把试题库看作试题集，老师在组卷时从中选取。( b ) 把试题库看成 是试卷的集合，每次需要时从中随便取出一份。( c ) 从试题库中随机抽取试题组成试卷。 从这几种方法来看第一种方法只是把计算机作为一个存储工具来用，还是由老师人为组 卷。第二种方式由于题库中的试题都以试卷的形式存放，这样就失去了灵活性，每套试 卷的题没有变化，如果重复抽取某一套试卷的话，那么所以题都是重复的。第三种方式 虽然它很灵活，但是很难满足试卷的实际要求，不能满足考生需要，那么还是要老师进 行调整才行。 所以，计算机考试系统研究的一个比较关键的问题就是组卷的算法问题。只有好的 算法才能提高考试组卷系统的可用性。那么智能组卷要做的是从题库中选择合适的试题 组成一套完整的试卷，但是要保证这份试卷满足老师的要求和教学的要求。一般的要求 包括难度，指定的知识点范围，题型，时间限制，认知层次，分数要求等等，使试卷能 够有很好的区分度。组卷问题设计的范围很广泛，如：算法分析，建模，人工智能等领 域。 现在我们要总结一下一般都有哪些方法被用来进行智能组卷运算。首先，我们要 了解一下组卷问题的本质问题。组卷实质上是一个在一个复杂的约束条件下的多目标求 优化解的问题。那么优化解就说明可能得不到这样的解，可能不止一个这样的解，或者 优化的程度不同的解，当然对于我们要的是最优近似解。那么这样的问题用传统的方法 是不行的。怎么能设计出一个算法来解决这个问题呢? 随着计算法技术的飞速发展，人 工智能理论的迅速发展，和数据库海量存储技术的不断更新。那么借助于计算机及相关 理论、技术来解决上述提出的问题成为可能。到目前为止，国内外许多研究机构做了大 量的研究工作，一般常用的组卷策略如下陌1 ： 其一，误差补偿算法 其二，随机抽取算法 其三，深度与广度搜索算法 其四，遗传算法 ( 1 ) 误差补偿算法嘲 生成一个比较好的试卷需要满足很多约束条件并达到某些目标，在多个方面限制 下，很难找到比较满意的答案，那么当算法进行一段时间后，大部分的限制条件都接近 约束目标了，但再继续下去也很难有更好的结果，这时采用误差补偿算法来处理这种情 况。那就是这种方法会在一定限度内放松限制条件和目标解的近似程度，让算法能够结 2 1 ， 0 东北师范大学硕士学位论文 束，并找到相对满意解。减少了无谓的循环和计算。 ( 2 ) 随机抽取算法嘲 基于这种方法的组卷算法逻辑比较简单，而且实现容易。因此在早期有很多的组 卷系统采用这种方法。随机抽取算法顾名思义就是从数据库中随意抽取一个试题，然后 看看这个试题是否满足试卷的需要，是否满足各项指标。如果满足那么放入试卷，如果 不满足就放弃，然后在此基础上修改约束条件，继续重新从题库中抽取下一个试题，然 后在判断，一直到算法结束。一种结果是失败，另一种结果是找到在一定程度上 满足要求的试题集合组成试卷。 随机算法的简单、易用的特点使组卷算法单次执行速度快，同时，它的特点也同 样是它的缺点，即极容易失败，重复率高，整个过程时间非常长，效率低下。 ( 3 ) 深度与广度搜索算法1 由于随机抽取算法的简单易用使很多应用找早期都在使用，但其耗时、低效、大 量的重复操作等缺点，使人们逐渐放弃了这种方法。找到了一个比随机抽取算法更好的 方法，即基于深度优先和广度搜索算法的组卷算法。这种算法是在随机抽取算法的基础 上进行的改进算法，那么改进的内容一定是随机抽取算法的不足之处。深度优先和广度 优先算法仍然是用随机抽取的方法从题库中抽取试题，但是如果在当前的条件下不能找 到满足要求的试题时，而且组卷没有结束时，就会采用深度优先于广度优先算法，丢掉 最近若干次搜索的结果，向上回朔到上一个节点处重新沿着另一个方向搜索。因此，深 度优先于广度优先算法也叫回朔试探法。通过放弃之前的部分重新向新的方向搜索组 卷，但是并不是放弃全部搜索成果，因此减少了随机抽取算法的大量的无效的循环，节 省了时间，提高了效率。这种方法实现也很简单而且方便实现口1 。 这个算法其实是一个深度优先与广度优先的递归遍历算法，理论上算法是可以搜 索每一种结果的。但是它的遍历次数会随着试题库的增大而迅速增加，那么就是说明这 种算法在比较小的试题库上应用的效果很好，成功率高。如果试题库太大的话，消耗的 时间相当长，由于要进行递归运算，因此要占用很多的内存资源。因此这种算法的应用 是受限的。 ( 4 ) 基于遗传算法的组卷算法 遗传算法是在m e n d e l 遗传学说和d a r w i n 进化论的理论基础上发展而来的一种具 有搜索功能的自适应全局优化算法。到目前为止遗传算法是比较适合应用到组卷算法 的，这也是有它自身的一些特点决定的。如聃1 ： 第一，遗传算法对可能解有广泛的表示性，这使得遗传算法应用的更普遍。 第二，遗传算法能够对种群进行全局搜索。 第三，遗传算法有自我纠正的特性。 第四，遗传算法能够在种群空间内的搜索具有随机性。 第五，遗传算法具有并行计算的能力，计算量大的问题迎刃而解。 与传统组卷方法相比，这些特性使遗传算法更适用于组卷问题。虽然现在有很多组 卷系统都应用遗传算法，并获得一定的成功。但是传统的遗传算法仍然存在很多问题， 3 东北师范大学硕士学位论文 例如成功率和效率、局部最优解和早熟等问题，尽管已经有很多学者一直在研究遗传算 法，并且在选择，编码，交叉，变异等环节做出了改善，而且在一定程度上克服了早熟 和局部最优解等问题，但是此算法仍然需要针对其缺点做进一步的研究和改进。 目前遗传算法在国内外的研究领域非常热门，过内外对遗传算法进行研究机构很多 而且有很多有关遗传算法的国际会议和活动，这些都充分映射出遗传算法在国际上受重 视的程度，也体现出它的理论价值和实际应用价值。到目前为止研究人员还没有找到一 种通用的方式去设置算法中需要的控制参数，都是人们通过实际检测并总结的经验数 据。 国内外对于遗传算法的研究现状已经进入应用阶段，虽然在应用中还有很多不足需 要改进，但是也取得了很大的成果。有关遗传算法的论文和研究成果等文章等在国际期 刊上越来越多。 那么遗传算法经过多年的研究，得到了快速的发展而且在理论和应用上也获得了不 错的成绩。但是，算法还不完美，仍然存在着一些不足需要更深入的探讨、在更深的层 次上挖掘。 这些不足之处有以下几点口3 ： ( 1 ) 个体的编码还需要进一步研究 ( 2 ) 种群规模、交叉和变异等的参数设定 ( 3 ) 算法方面的基础理论还有待遇提高 ( 4 ) 避免过早收敛的方法问题 ( 5 ) 增强局部的搜索能力问题 遗传算法的这些问题都会对算法产生很重要的影响。因此需要花费更大的投入去研 究和发展以上提出的问题。 模式理论全面、深刻、透彻地分析并阐述了遗传算法的基本原理。从模式角度出发 看待遗传算法的话，那么遗传算法其实就是对模式的运算。那么选择算子会把当前种群 中优秀的模式复杂到下一代种群；交叉操作对模式进行重新组合，产生不同的模式，也 就是搜索整个解空间；变异算子对模式进行突变，使种群增加新的模式，使保持模式的 多样性。通过不断遗传和进化，不好的模式慢慢消失，推出种群；而好的模式继续进化 使解空间的模式越来越优秀，同时使遗传算法向着最优解的方向进化，那么很可能搜索 到最优解。 那么从模式理论中我们知道，随着种群的不断遗传进化，模式的不断重组，更新和 推演，有些适应度很高的模式将在种群中大量增加，是种群中很多个体的基因比较相近 或相似，使群体的多样性减小。从理论上将种群的规模可以无限大，而且遗传操作都是 可靠的，那么种群中的优良模式一定会一代一代传下去。那么随着算法的不断收敛，多 样性不断减小，最优解慢慢浮出水面。但是，在实际应用中，在理论上可行的事情可能 行不通。比如，种群规模一定是有限的，时间和资源也是有限的，那么久会产生和理论 结果不一致的误差，这个误差的原因很简单，就是由于实际应用的种种限制，导致种群 的个体的多样性过早消失而造成的。通过对已有文献和资料分析得知只要初始种群中包 4 东北师范大学硕士学位论文 含足够的模式，那么标准的遗传算法就有能力找到最优解。种群的多样性越强，交叉算 子的搜索能力就越强。种群多样性过早消失，交叉算子的搜索能力就减弱了，甚至不起 作用。变异算子的操作几率很小，如果种群过早收敛，那么久很难在保持多样性，算法 缺乏跳出局部最优解的能力，导致早熟现象的发生。可见，早熟现象发生的根本原因是 种群多样性的过早丧失。 如果标准遗传算法中变异概率为零，即无变异操作，标准遗传算法总是收敛的，并 且在进化过程中种群的多样性是单调递减的。从这里可以看出交叉算子既要探索新的解 空间又要使算法收敛。然而，局部最优解，全局最优解，非极值解都可能是标准遗传算 法收敛的极限。因此，单纯的交叉操作不能摆脱种群过早收敛的趋势。 通过前面的总结分析，我们深刻认识到遗传算法的早熟原因。要避免早熟和过早进 入局部最优解并且保持种群多样性的话需要有效增加种群多样性，能够跳出最优解。那 么从早熟的原因入手，有以下几个可以避免早熟现象： ( 1 ) 适应度函数的尺度变换n 帕 在遗传算法中，适应度是一切遗传运算的基础，它更是识别个体好坏，进行个体选 择的依据。在进化初期，常常会出现非常优秀的个体，那么导致种群中好坏个体的适应 度相差很大，这些优秀的个体有很强的竞争优势而慢慢控制选择过程。此时需要对个适 应度值进行缩小。当种群的的好坏个体的适应度相差很小时，需要放大适应度值。总之， 一个好的适应度函数应该能够使种群中好坏个体的适应度值一直保证一定的距离。常用 的尺度变换方法主要有线性变换、指数变换、幂函数变换等。 ( 2 ) 控制参数的自适应调整u 们 在遗传算法中影响遗传算法行为和性能的关键是交叉概率和变异概率的选择。标准 遗传算法中的交叉和变异概率是固定值，对于不同的应用来说很难找到一个合适的值， 并且当早熟现象发生时，算法无法跳出局部最优解。现在，有一种自适应遗传算法，交 叉、变异概率能够随适应度的变化做出适当的调整，在保持种群多样性的同时，保证算 法的收敛性。 ( 3 ) 混和遗传算法n 叼 为了更好的提高局部搜索能力，有些遗传算法把一些其他的算法引入进来，通过对 算子的改进，形成混合算法。这些算法如：爬山法、梯度法、模拟退火法、禁忌搜索等 优化算法。这些算法具有很好的局部搜索能力遗传正是利用这种特性去维持种群多样 性，跳出局部最优解。 1 3 主要工作与组织结构 本文深入研究各种智能组卷算法，比较各种算法之间的优点及其不足。探索遗传 算法的各种改进措施对算法的影响，适当采用多方面的改进方法来提高算法的成功率， 以及算法中涉及的种群、染色体、基因、遗传算子等与试卷中试题的各种属性及约束关 系。将本文提出的这种改进的遗传算法应用到东北师范大学理想信息技术研究院的智能 5 东j b v i l i 范大学硕士学位论文 组卷系统，通过实际测试表明此算法表现较好。 论文的基本结构和工作内容： 第一章在绪论部分中，介绍了智能组卷系统在国内外的发展情况，总结智能组卷 现在应用的方法和理论。以及本课题研究的背景和意义。 第二章研究并分析了智能组卷基本原则和试卷的各项属性指标。深刻研究遗传算 法的关键技术，如算法基本流程、编码方法、遗传算子、种群和适应度函数。 第三章设计了一种基于遗传算法的组卷模型，并设计指标量化方法、指标偏差计 算方法和适应度函数。并根据前面的分析，分析各种的改进遗传算法，如在编码、适应 度函数计和遗传算子等方面进行改良。 第四章从系统的功能需求和非功能需求两方面分析了智能组卷的基本要求和目 标。从设计原则、系统体系结构、网络拓扑结构、系统功能、数据库和系统安全等方面 进行全面阐述系统的构建过程。 第五章对本论文进行总结并提出不足和希望，最后致谢。 6 东北师范大学硕士学位论文 第二章智能组卷的研究 考试是教学过程中的一个重要环节，考试的效果由试卷的质量来决定，一份好的试 卷不但可以检验学生的学习水平还能衡量教师的教学效果，教学活动就失去了有力的指 导。那么好的试卷要能够同时满足多个约束条件，同时还有掌握智能组卷的基本原则。 除此之外，一种既能兼顾试卷原则又能满足多个试卷目标的算法显得尤为重要。遗传算 法借鉴了生物进化理论和遗传学机理在理论上形成了一套比较成熟的算法体系，在智能 组卷算法上能够体现出比较优秀的性能。 2 1 智能组卷的基本原则 根据文献 1 1 - 1 2 ，本文总结了组卷的基本原则如下： 第一，每一个考试都有考试大纲，在大纲中明确规定了考试的内容，如考核对基本 理论。基本知识点的理解程度，以及考生的分析问题和解决问题的能力。因此考生大纲 是考试内容的依据，就是试卷必须能够体现出大纲的内容和基本要求，而且要球有足够 的题量，内容全面。 第二，既然是考试，那么考试的结果一定要符合正态分布曲线规律，就是说成绩分 布要有层次，不能分数都很高，或者分数都很低，那样就不能检验考试对知识的掌握情 况，同时也不能鉴别考生的能力。那么就要求试卷要有一定的难度，试题要有区分度。 第三，考试成绩是反映一个考生学习效果的一个重要指标，每个考试都会很重视， 必然回朝着考试的方向去学习、准备，那么考题就如同一个指挥棒，引导学生的学习偏 向。如果试题是记忆性的，那么考试就回去死背；如果是考怎么分析问题和解决问题， 那么考生就会在平时学习时注意多动脑、多思考。所有，考题能够引导学生的学习方向。 第四，试题表述要清楚，没有歧义，不能让考生去猜测题意，以提高考试的信度。 2 2 试卷的属性指标 试题的属性指标是对试题的内在属性和外在特征进行定性或者定量的刻画，在计 算时这些定量的属性是必不可少的。试题的属性和指标有很多，不同的标准之间略有差 别，综合各个标准，根据文献 1 3 - 1 5 ，本文总结以下主要试题的指标： ( 1 ) 题型 一般是指从试题形式上区分，具体的试题类型可分为：选择题( 包括单选、多选和不 定项选择) 、填空题、简答题、论述题等。 ( 2 ) 知识点：知识点是试题承载的考试核心内容。 ( 3 ) 难度 7 东北师范大学硕士学位论文 本文设计的试题难度分为五个档次，具体见表2 1 所示。 表2 1 试题的难度系数表 难度级别较易易中等较难难 难度系数 0 - 0 20 2 - 0 40 4 - 0 60 6 - 0 80 8 1 0 试题的难度值是指全体考生对该题的失分率。其计算公式为：d = l 一圭。式中，d 是题目的难度值：z 为全体考生在该题上得分的平均数：w 为该题的满分值。 ( 4 ) 区分度 试题的区分度可以测量某一题目对不同水平考生的心理特质的区分程度，是由考生 在该题上的得分与其实际能力水平之间的关系来确定的，就是用来区分不同能力的学生 的水平能力，也即鉴别力。对于区分度比较好的试题，能力强的学生得分高，能力差的 学生得分低，学生的能力很容易能够区分出来。 区分度是试题的分数与一组考试成绩的相关度，两者成正比关系，相关度高区分度 也高，相关度低区分度也低。区分度高的要保留在试题库中，区分度低的要丢弃。那么 区分度也是检验试题好坏的一个标准，如果不将其量化的话，没有办法应用到遗传算法， 下面是具体的量化方法。如果要对某个试题估算其区分度值，满分值为f 。那么先让一 组学生去做这个题，然后将成绩按高到低排序。把前2 5 0 5 的成绩列为高分组，再去平均 值，用h 表示；取后2 5 0 5 的成绩列为低分组，取平均值，用l 表示。那么区分度( q ) 的计算公式为： d ：h - l 。 f 本文设计的试题区分度分为四个层次，具体见表2 2 所示 表2 2 试题区分度表 区分度指数( q )评价 0 9 0 以上较好 0 3 0 - 0 8 9好 0 2 0 - 0 2 9一般 0 1 9 以下不好，必须淘汰 通过上面的分析我们知道区分度差的试题对于区分学生的能力水平是没有什么效 果的。因此，试卷不应该选择这样的试题。但是需要特别说明的是，区分度和难度是有 区别的，也有一定联系。如果试题很难，没有学生能够得分，那么有公式可知，区分度 很差；相反，如果试题很简单，所有学生都会，都能够拿满分，有公式得，区分度也很 些 z lo 在试卷难度指标中我们提到过，试卷的难度应该适中，才能使考试的成绩呈正态分 布。在这旱从区分度的角度来说，也要求考生的难度不能太极端，适当为好。 ( 5 ) 认知层次 在试卷中用认知层次来呈现学生对知识的理解和应用能力。一般认知层次如图2 - 1 ： 8 东北师范大学硕士学位论文 i 盔层 次 玖 建件 少 彩 图2 1 ( 6 ) 分值：试题的满分值。 ( 7 ) 时间：每个试题理论上需要的最大时间。 ( 8 ) 曝光度 曝光度指的是题库中的试题曾经被选中的次数，曝光度小，可以使试题更具不可猜 测性。 每套试卷都包含若干道题，每道题的难点不尽相同。那么一套试卷到底要包含多少 道难度较大的试题，包含多少道难度较小的试题，或难度适中的试题呢? 有什么方法来 判断? 有什么依据? 不论从经典测量理论还是根据实践经验我们知道，每个班的学生的 个人能力水平是不一样的，成绩当然也不一样，但是基本上都应该符合正态分布曲线。 其曲线方程为： 1 一! 三二生 f ( x ) = 2 a 2 ，x er式2 1 o 二死 结合本文的内容来说，x 表示每个学生的成绩；u 表示这些学生成绩的平均值，相 当于正态曲线最高点的坐标；万表示标准差，说明了平均成绩和每个学生成绩的差值。 下面图2 - 2 是u = 5 ，d = l 和u = 5 ，万= 1 5 的曲线对比图 图2 2 9 东北9 币范大学硕士学位论文 一份合理，科学的、难度适中的、区分度好的试卷一定会符合经典测量理论，也就 是说这分试卷的考试成绩一定会是呈正态分布的。这样的试卷一定是难度适宜的试题占 据试卷的大部分版面，难度较小的和难度较大的仅占据试卷的一小部分。这样不但试卷 的难度基本上是呈正态分布的，而且也符合学生的能力分布，学生的能力分布其实也是 呈正态分的。 虽然这种道理很好理解，也很好说明白，但是应用起来比一定那么如意。因为我们 还要知道怎么样才能使正态分布更加有效。根据概率论知识介绍，如果正态分布曲线满 足3 占原则，那么正态分布的有效性会达到9 9 7 。可以用正态分布去对应试题的难度 分布： i , t t - 3 0 _ j j 仃于詈，当仉5 时 式2 2 l t + 3 0 - _ 0 5 i t , j 表2 - 3 不同试卷难度下难度正态分布最大标准差 0 2o 30 40 50 60 70 8 万0 0 6 70 1 0 00 1 3 30 1 6 70 1 3 30 1 0 00 0 6 7 不同试卷整体难度下的难度分布曲线，如图2 - 3 ： 图2 3 如图所示，这时一个不同难度下，不同平均值和标准差的曲线对比图。对于每条曲 线来说，曲线和代表难度等级的x 轴的面积被分成4 份，每份就代表此难度的试题在试 卷中的比例。 下面是其计算公式 l o 东北师范大学硕士学位论文 p s i = k 上f ( x ) d x 尸s ：= k 厂( x ) d x p s 32 k 上。f ( x ) d x p s 4 = k f m ) d x p s 5 = k e 。厂( x ) d x 式2 - 3 2 3 遗传算法介绍 遗传算法是根据生物进化理论而得出的一种全局优化算法，通过全面模拟自然选 择和遗传机制，形成一种具有多条件全局搜索的算法。 算法的解空间就相当于个体的编码空间或者说是模式空间。遗传算法是通过不断 的进化迭代，反复进行遗传算法的选择、交叉和变异操作，每次迭代后都通过个体的适 应度函数来计算适应度值。 目前，遗传算法正在向其他学科和领域逐渐渗透，正在形成与遗传算法、神经网 络和模糊控制相结合，从而构成一种新型的、智能的、整体优化的结构形式。在人工智 能研究中，现在人们认为遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一 样，是2 1 世纪有关智能计算中的关键技术和研究热点。 遗传算法的创建过程有两个主要研究目的：一是严谨和抽象地解释自然界的适应 过程；一是为了将自然生物系统的重要机制运用到工程系统、商业系统或计算机系统等 人工系统设计中。遗传算法在计算机上模拟生物的基因的操作和进化过程，并不需要对 象的搜索空间是连续可微的，也不需要对象的特定知识，它具有全局寻优的能力。一些 用常规的优化算法不能有效解决的问题，采用遗传算法寻优技术却能得到比较好的结 果。 遗传是指父代与子代之间，在性质和形状上存在的相似现象。变异是指父代与子代 之间，以及子代的个体之间，在性质和形状上或多或少地存在的差异现象。由于变异得 到的特征经过遗传由后代继承。遗传能使生物性质和形状不断地传送给后代，因此保留 了物种的特性，变异能够使生物的性质和形状发生改变，从而适应新的环境而不断地向 前进化。选择是指具有精选的能力，它决定生物向前进化的方向。在进化过程中，有要 保留的，有要被淘汰的。通过不断的选择，有利于生存下了变异个体就会遗传下去，积 累起来，使变异程度越来越大，逐步产生了新的物种。 通过自然选择、遗传和变异，生物物种能够不断向前进化n 引。种群是由一个生活在 一起的集体生物组成的，其中每个生物叫做个体，相对于环境来说每个个体都有一个适 应度值盥叫。遗传物质的载体是染色体( c h r o m o s o m e ) ，染色体主要是由蛋白质和d n a ( 脱氧 核糖核酸) 组成，其中d n a 是最主要的遗传物质。d n a 由很多的基因构成，基因( g e n e ) 是遗传效应的片断，它储存着遗传信息，能够准确地复制，或者发生突变。在遗传过程 中经过复制和突变产生的基因的遗传和繁殖能力取决于它对环境的适应度，那么适应度 l l 东北师范大学硕士学位论文 大生物其繁殖能力就较强，适应度小的繁殖能力就交差。在自然界中适应度大的生物逐 渐进化成为更能适应周围环境的个体最终占据整个生物群体。那么适应度小的生物慢慢 的被淘汰掉。在自然界中这种物竞天择、适者生存的法制是物种一直朝着最能适应其生 存环境的方向前进，最终会进化出比较良好的种族。 在整个生物链中的这种自然选择机制逐渐被人们注意，而且人们开始研究这种生物 生存法制并进行效仿和实验，为遗传算法发展提供了广阔的前景。遗传算法所借鉴的j 下 是上面的自然选择( n a t u r a ls e l e c t i o n ) 学说，遗传算法就是用这种模拟生物行为取得 了令人瞩目的成果。 2 3 1 遗传算法的基本流程 根据文献 1 7 - 1 8 ，遗传算法的最终目的是要在这个解空间内搜索出一个适应度最 大的个体，虽然在选择个体进行交叉和变异操作是随机进行的，但是这种随机性并不是 漫无目的的随机，也就是说这种随机不是觉得的随机，而是根据之前积累下来的信息在 能够更好适应环境的方向上的随机。按着这机制向后推演，从而找到正解。图2 4 是典 型的算法描述图。 图2 - 4 1 2 东北师范大学硕士学位论文 2 3 2 遗传算法的编码方式 在遗传算法的运行过程中，主要是对解空间中每个个体进行遗传运算，无外乎选 择个体、进行交叉和变异操作。在概念上是这么说的，但具体的说，从算法实现的角度 看究竟怎么来完成个体的选择、交叉和变异等操作呢? 我们知道，这些运算都是建立在 对个体编码的基础上的，对每个个体基因位上的基因值进行交叉和变异运算的。通过操 作个体编码来完成进化，在可行解空间中搜寻最优解。因此，个体的编码及其及其编码 方式对于算法中的遗传算子的运算是非常重要的。这也正是在某个领域要应用遗传算法 的第一步工作，完成对问题的抽象、建模、转化成编码。然后再这个基础上应用遗传运 算。 通过分析研究，我们知道个体的编码对遗传算法是尤为重要的，是应用遗传算法 第一个要解决的问题。但是对于编码的方式、技巧也不能忽视。这会对接下来要进行遗 传算法的推演、运算造成很大影响。比如说，一个精心设计的编码形式，很可能遗传运 算的效率很高，而且成功率很大。同时还会使遗传算法本身实现起来很方便，占用很少 的内存和系统资源。然而，如果编码设计的很差的话，不但会增加遗传算法本身的实现 逻辑的复杂度，而且要花费更多的时间、消耗更多的系统资源，导致算法效率很低。还 有可能对编码和解码造成混乱，使得解空间内没有这个编码对于的个体。总之，编码及 其编码方式对算法会产生很大的影响，应该慎重考虑这个环节。 在实际应用中，由于不同的应用所面对我问题不一样，它的可能解空间也是不同 的，那么编码也不可能一样。因为编码很重要，我们希望能够找到一种放之四海而皆准 的方法，去解决所有应用的编码问题。这应该是遗传算法的一个关键研究内容。但是， 到现在为止还没有这样的理论方法可以遵循。从经验上来讲，设计一种编码时有几个建 议性的原则可以作为依据n 叼： 第一，编码长度尽量短，避免高阶。 第二，编码尽量能够自然的描述问题。 第三，编码尽量使用较小的字符集。 上面总结的编码规则只是一种在编码思想上的建议，可能还不能应用于所有问题。 当面对具体问题时，还是必须对编解码的方法和遗传算法进行综合考虑，找到一个既能 对问题表述清楚又能适合运算的编码方法。 现在，国内外的遗传算法已经进入应用阶段，因此已经有很多的编码方案，大多 数遗传算法采用固定顺序、固定长度的位串编码方式。最早出现的案是二进制编码，而 且有很多的应用实例，理论基础深厚，但是这种编码方法太长，使用不方便而且有些问 题不能使用。后来逐渐出现实数编码、多字符编码和有序位编码等。通过分析得知这种 实数编码或多字符编码确实能够改善算法的效率，但是它的设计过于依赖实际的应用和 算法的具体方法实现。那么，现在还不能说那种方法好哪种方法不好，都有各自的应用 领域和自身的特性。下面列举几种编码方式： ( 1 ) 二进制编码啪3 二进制编码使用的编码符号集由二进制符号0 和1 组成的，其优点在于编码、解码 1 3 东北师范大学硕士学位论文 操作简单，交叉与变异等遗传操作便于实现等。但是二进制编码是离散的，很难精确的 表示连续函数，如果用二进制编码来表示的话会存在着一定的误差。那么对于较短的编 码根本到不到很高的精度，