（计算机应用技术专业论文）基于改进遗传算法的组卷策略的研究.pdf

学位论文的主要创新点 一、在算法中引入了自适应技术，使交叉概率和变异概率己能随适应度的不 同做动态调整。使遗传算法在保持群体多样性的同时，保证遗传算法的收敛性。 二、在算法中引入小生境技术，基于小生境技术的遗传算法能够更好的保持解得 多样性，同时具有很高的全局寻优能力和收敛速度，特别适合组卷这样的复杂多 峰值问题。 摘要 随着计算机技术与教育理论的不断融合促进了计算机辅助教育的发展，计算 机辅助测试作为计算机辅助教育的重要部分而受到越来越多的关注。在计算机辅 助测试系统中，组卷模块的设计是否合理直接决定了试卷的质量，而试卷质量的 高低直接决定了考试的信度和效度，因此组卷策略的研究成为了计算机辅助教育 中的一个重要课题。本文针对现有的组卷算法组卷效率低、试卷质量不够理想、 难以满足实际考试需要等情况，在传统遗传算法的基础上，提出了基于改进遗传 算法的组卷策略。 本文分析了当前各种组卷算法的优缺点。遗传算法在解决组卷这样的多约束 条件下的寻优问题方面存在诸多优势。但是，传统的遗传算法在解决组卷问题时， 存在盲目搜索、局部搜索能力不强、容易得到局部最优解和搜索效率低等不足， 很难满足实际考试的需要。本文对传统遗传算法产生上述弊端的原因进行了研究 和分析，在此基础上提出改进方案。 本文在教学测量学中的经典测量理论的基础上，建立了试题的指标体系和组 卷的数学模型，确定了组卷问题的目标函数，并将组卷问题转化为1 7 标函数的最 小化问题。 本文采用实数编码方法，大大降低了染色体的长度，提高了组卷效率；对目 标函数进行线性变化，使其更准确的反映出种群和个体的质量；引入了自适应交 叉变异，根据当前种群的情况动态的调整交叉和变异概率；引入了小生境的技术， 不仅提高了算法收敛速度，而且增加了种群的多样性；引入了抗早熟运算，防止 算法进入局部收敛等。为了检验效果的实际组卷效果，本文用模拟题库对算法进 行了性能测试，实际的测试效果表明改进后的算法在试卷质量、组卷效率、稳定 性等方面都有很大程度的提高，具有较强的实际应用价值。 关键词：智能组卷；遗传算法；小生境；自适应； a b s t r a c t a l o n gw i t h t h ec o n n e c t i o nb e t w e e nc o m p u t e rt e c h n o l o g ya n dt h e o r yo f e d u c a t i o n s b e c o m em o r ea n dm o r ec l o s e l y , t h i sp r o m o t ec o m p u t e ra i d e de d u c a t i o n ( c a e ) d e v e l o pq u i c l y c o m p u t e ra i d e dt e s t i n ga sa l li m p o r t a n tp a r to fc a ea m a c k m o r ea n dm o r ep e o p l e s a t t e n t i o n i nc o m p u t e ra i d e dt e s t i n gs y s t e m ，t h ed e s i g no f t e s tm o d u l ei sr e a s o n a b l ed i r e c t l yd e t e r m i n et h eq u a l i t yo ft h et e s tp a p e r , a n dt h e q u a l i t yo ft e s tp a p e ri sh i 曲o rl o wd i r e c t l yd e t e r m i n et h ev a l i d i t ya n dr e l i a b i l i t yo fa e x a m i n a t i o n ，s os t r a t e g yo fp a p e rm a k i n gi sb e c o m eai m p o r t a n ts u b j e c to fc a e b a s e o nt h ee x i s t i n ga l g o r i t h mh a v el o we f f i c i e n c y , t h eq u a l i t yo fp a p e r si si n s u f f i c i e n t i d e a l ，c a n tm e e tt h ea c t u a la c q u i r e m e n to ft e s t ，t h r o u g h f u r t h e rs t u d yi ng e n e t i c a l g o r i t h m ，t h i sa c t i c a lp r o p o s eat e s ts t r a t e g yb a s e do ni m p r o v e dg e n e t i ca l g o r i t h m t h i sa r t i c l ea n a l y s i so ft h ea d v a n t a g e sa n dd i s a d v a n t a g e so fv a r i o u sg r o u p s a l g o r i t h m ，g e n e t i ca l g o r i t h mi ss u i tt os o l v et e s tm a k i n gp r o b l e m b u tw e f o u n dt h a t t r a d i t i o n a lg e n e t i ca l g o r i t h mt os o l v ep r o b l e m si ne x i s t e n c eo fb l i n ds e a r c h i n g ，a n d l o c a ls e a r c hc a p a b i l i t yi sn o ts t r o n g ，e a s yt og e tl o c a lo p t i m a ls o l u t i o na n ds e a r c h e f f i c i e n c yi sl o w , i ti sd i f f i c u l tt om e e tt h ep r a c t i c a ln e e d so fe x a m i n a t i o n b ys t u d y a n dr e s e a r c hw of o u n dt h er e a s o nw h yt h e s ed i s a d v a n t a g eh a p p e n e d ，a n dp r o p o s et h e i m p r o v e m e n tp r o j e c t i nf u r t h e rs t u d yo fc l a s s i c a lm e a s u r e m e n tt h e o r y , w ee s t a b l i s ht h ei n d e xs y s t e mo f q u e s t i o na n dt h em a t h e m a t i c a lm o d e lo ft a r g e tf u n c t i o n ，r o l lt h et e s tm a k i n gp r o b l e m i n t ot h et a r g e tg r o u po ff u n c t i o nt om i n i m i z ep r o b l e ms u c c e s s f u l l y i nt h ei m p r o v e m e n to fa l g o r i t h mw ea d o p t e dr e a l n u m b e r - c o d i n gg r e a t l yr e d u c e s t h el e n g t ho fc h r o m o s o m e s ，i m p r o v i n gt h ee f f i c i e n c yo ft e s tm a k i n g ；l e tt h et a r g e t f u n c t i o nm a k eal i n e a rt r a n s f o r m ，m a k ei ta c c u r a t e l yr e f l e c tt h eq u a l i t yo fi n d i v i d u a l a n dp o p u l a t i o n ；i n t r o d u c i n gt h es e l f - a d a p t i v ec r o s s o v e r - m u t a t i o n ，a c c o r d i n gt ot h e c u r r e n ts i t u a t i o no fd y n a m i ca d j u s t m e n to fc r o s s o v e ra n dm u t a t i o np r o b a b i l i t y ； i n t r o d u c i n gt h en i c h i n gt e c h n i q u e ，i tn o to n l yi m p r o v e st h ea l g o r i t h mc o n v e r g e n c e s p e e d ，a l s od i v e r s i t yo fp o p u l a t i o n ；i n t r o d u c i n gt h ep r e c o c i o u so p e r a t i o n s ，p r e v e n t a l g o r i t h mi n t ol o c a lc o n v e r g e n c e a f t e rd o i n gt h e s e ，w en e e dt ot e s tt h ee f f e c to f i m p r o v e m e n ta l g o r i t h m ；w eu s et h es i m u l a t i o nt e s tl i b r a r yt ot e s tt h ea l g o r i t h m s p e r f o r m a n c e t h ea c t u a lt e s tr e s u l t ss h o wt h a tt h ea l g o r i t h mi m p r o v et h ep a p e r s q u a l i t y , e f f i c e n c ya n ds t a b i l i t yo b v i o u s l y , s ot h ei m p r o v e m e n ta l g o r i t h mh a v eas t r o n g p r a c t i c a lv a l u e k e yw o r d s ：i n t e l l i g e n tt e s tm a k i n g ；g e n e t i ca l g o r i t h m ；n i c h e ；s e l f - a d a p t i v e ； 2 目录 第一章绪论1 1 1 引言1 1 2 研究的背景及意义1 1 3 国内外研究现状2 1 4 各种组卷算法优缺点的分析5 1 5 本文的主要工作6 第二章组卷问题的基本理论和数学模型7 2 1 组卷问题的理论基础7 2 1 1 经典测量理论8 2 1 3 项目反应理论( i r t ) 1 1 2 2 组卷问题的原则1 2 2 3 试题的重要属性指标1 3 2 4 衡量试卷质量的指标体系1 5 2 4 1 试卷的信度与效度1 5 2 4 2 试卷的平均难度1 5 2 4 3 试卷的区分度1 5 2 4 4 难度与区分度、认知层次之间的关系1 6 2 5 组卷的数学模型1 6 2 5 1 基于正态分布的试卷难度分布计算模型1 7 2 5 2 组卷的约束条件1 9 2 5 3 偏差的计算2 2 2 5 4 解的偏好关系计算2 5 2 6 目标函数2 6 第三章基本遗传算法介绍及其改进2 7 3 1 基本遗传算法简介2 7 3 1 1 遗传算法的基本概念2 7 3 1 2 遗传算法的特点2 7 3 1 3 遗传算法的基本操作2 8 3 1 5 遗传算法的步骤3 0 3 2 遗传算法的改进3 1 3 2 1 传统遗传算法的缺陷3 1 3 2 2 传统遗传算法的改进3 1 3 2 2 1 编码方式的改进3 1 3 2 2 2 适应度函数的变换3 3 3 2 2 3 交叉变异概率的自适应调整3 5 3 2 2 4 结合小生境的替换策略3 7 第四章智能组卷的遗传算法设计3 9 4 1 问题的描述与转化3 9 4 2 改进遗传算法在组卷中的具体实现3 9 4 2 1 组卷编码方案的确定3 9 4 2 2 初始群体的产生4 0 4 2 3 适应度函数的设计及其线性变换4 2 4 2 4 交叉算子设计4 6 4 2 5 变异算子设计4 8 4 2 6 结合小生境的选择策略5 0 4 2 7 抗早熟运算5 2 4 2 8 终止条件判断5 3 4 3 智能组卷算法的流程图5 4 第五章改进算法参数的确定及性能测试5 5 5 1 算法的测试环境5 5 5 2 模拟试题库的建立5 5 5 2 1 试题库的基本组织要求5 6 5 2 2 模拟试题库的建立5 6 5 3 实验数据及讨论5 8 5 3 1 组卷参数设定5 8 5 3 2 组卷的结果5 9 5 3 3 讨论组卷参数对算法的影响6 3 第六章总结与展望6 9 参考文献7 l 发表论文和参加科研情况说明7 4 致谢7 5 i i 第一章绪论 1 1 引言 第一章绪论 上世纪5 0 年末，美国著名的心理学家b f 斯金纳教授提出了程序教学理论， 伴随着计算机和信息技术的飞速发展，以及信息论与教育理论的不断融合，计算 机辅助教育( c o m p u t e rb a s e de d u c a t i o n ，c b e ) 逐步发展起来。通过几十年的发展 完善，计算机辅助教育已发展成为一门集教育学、心理学、学习理论、信息论、 控制理论、计算机科学、模式识别等多种学科知识于一身的新兴交叉学科，对教 育事业的发展变革起到了巨大的推进作用。 虽然计算机8 0 年代才进入中国，但由于我国经济的快速发展，科技水平的 不断提高，计算机在我国得到飞速的普及与应用。当前，计算机已经广泛的应用 到教育领域，并已经成为有效的教学媒体和教学管理的得力工具。计算机技术的 融入大大改变了原有的教学手段、教学形式和教材的观念形式，如何通过教学实 践和理论研究，更好的将计算机科学技术与教育实践结合起来，已经成为我国教 育教学改革的热点。 1 2 研究的背景及意义 教育领域中，考试评价学生对知识掌握程度和衡量教师教学效果的核心手 段，通过考试学生可以评价自己在一定时期内的学习效果，激发学生的学习动力， 根据考试的结果的有针对性的进行学习；教师则可通过考试成绩评价课堂的教学 效果、及时调整教学形式。当前大部分考试还采用传统的考试形式，不仅在命题、 组卷、组织考试和统计成绩等方面耗费很多人力物力，而且命题的内容、评分标 准等容易受到人为因素的影响，降低了考试的效度和信度。 随着计算机技术和教学理论的不断发展融合，计算机辅助教育( c b e ) 应运而 生，如何更好的利用现有计算机技术改进传统的考试形式，已经成为计算机辅助 教育最关注的问题。计算机辅助测验( 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 系统的一个重点和难点。 天津工业大学硕士学位论文 通过近二十年对组卷策略的研究，产生许多比较成熟的理论和算法，有些已 经成功的应用到大型考试系统中。但由于组卷问题本身是一种多约束条件下的搜 索寻优问题，尽管当前的组卷算法取得了较为理想的组卷效果，但还是无法满足 c a t 系统的实际需要。本课题通过对现有组卷策略的研究，在此基础上提出了 一种基于改进遗传算法的智能组卷策略，该组卷算法对提高试卷的质量，保证考 试信度与效度等方面具有非常重要的实际应用价值。 1 3 国内外研究现状 众所周知考试系统在c a t 中是必不可少的，而组卷模块既是考试系统的核 心，又是题库系统的重要组成部分。自上世纪6 0 年代出现计算机辅助教学系统 ( c a t ) 和智能计算机辅助教学系统( i c a t ) 以来，4 0 多年来组卷系统发展迅速，计 算机技术、信息处理技术、人工智能和数据库系统等技术的迅猛发展也给组卷系 统的发展提供了强大的发展动力。 上世纪6 0 年代美国首先将计算机技术用于教育测验，4 0 多年来计算机辅助 测验系统发展极其迅速。上世纪8 0 年代，人们就已经开始将c a t 系统广泛的应 用于各种大规模在线考试，典型的计算机考试系统有t o f e l 、工商管理类研究 生入学考试系统( g r a d u a t ef o rm a n a g e m e n ta n da d m i n i s t r a t i o nt e s t ，g m a t ) 、 美国的研究生入学考试系统( g r a d u a t er e c o r de x a m i n a t i o n ，c r e ) 等。通过最近十 几年的摸索实践，我国也自主研发了一些成功的计算机考试系统，典型的有全国 计算机等级考试系统、南京大学计算机科学与技术系开发的p a s c a l 题库系统、 清华大学等联合研制的“高等学校工科高等数学课程试题库系统”和高教司的组 卷系统外壳软件等考试系统。 组卷模块是计算机考试系统中极其重要的组成部分，组卷模块中的自动组卷 功能又是考试系统智能化的核心目标之一，能否生成快速、高效、合理、科学的 试卷对于考试系统的评价至关重要。上述考试系统中的组卷模块主要采用下面三 种方式：一种是将试考试系统中的题库看作试题集，实际组卷时由教师逐题筛选 抽取；二是将试题库看作试卷集，将已经出好的质量较好试卷存储起来，考试时 随机抽取一份或多份试卷；三是具备自动抽题组卷的功能，利用某种组卷算法自 动形成试卷。其中，第一种方式虽然以计算机作为工具，但只是做题库管理，实 质上依然是人工组卷：第二种方法由于题库中试卷的数量有限，组卷缺乏灵活性， 不可避免会在多次考试中出现完全相同的试卷；第三种组卷方法生成的试卷灵活 性大，但如果组卷策略不合理，生成的试卷效果往往满足不了实际考试的要求。 因此，为了提高计算机考试系统组卷模块的可用性及有效性，组卷算法的研究已 经成为计算机考试系统研究的一个重要内容。 2 第一章绪论 虽然已经有一些组卷系统取得了较为理想的效果，但由于组卷问题的复杂 性，目前的组卷系统还是无法满足用户的需求。通过近十几年来对组卷策略的研 究，先后出现了基于项目反应理论的组卷算法、基于优先权策略的组卷算法、基 于遗传算法的组卷算法、基于随机的组卷算法、基于数据挖掘和知识发现的自动 组卷算法和基于回溯试探组卷算法等，下面简略介绍各算法的特点。 一、基于优先权策略的组卷算法 在组卷开始阶段，试卷各项属性一般有较大的取值范围，指标之间的牵制问 题不会立即反映出来，但随着被选试题数的不断增加，取值范围逐步的缩小，矛 盾便会随之产生。该策略从试题数量、题型的平均分数、累计值和完成率与指标 值差距等四个方面来综合评价每一道试题的优先权，并根据组卷过程中上述因素 的变化情况，动态调整相应试题的优先权，以缓解各指标间的矛盾。 二、基于随机的组卷算法 随机组卷算法实现比较简单，因此得到广泛的应用，常用的随机的策略有以 下两种： 1 随机的从试题库中抽取一道试题，然后根据抽出试题的属性判断是否满 足试卷的约束条件，若满足则继续抽取题目，直到达到试卷要求的题目为止；若 不满足，则抛弃该题继续抽取题目。 2 算法将试题库根据难度、知识点和认知层次等分成若干个子集，接着根 据试卷的约束条件计算出各约束的指标分量，依据指标分量随机的从相应的题库 子集中抽选试题，然后判断该试题是否满足当前的指标约束。若满足，则将该试 题放入当前试卷，同时修改对象约束条件的指标；若不满足，则继续根据各约束 的指标分量抽题，假如所有可供选择的试题试探后不符合要求，则会导致该算法 组卷失败。 实际上随机抽取策略就是在试题库相应的子集中随机搜索满足指标分量的 试题，不断的重复搜索过程，直到完成试卷生成操作或搜索不能到满足约束条件 的试题为止。虽然该算法结构简单，单次组卷效果较快，但从整个组卷过程来看， 存在重复率高、成功率低和组卷时间长等缺点。 三、基于回溯试探测组卷算法 由于随机抽取算法的试卷容易存在过多的无效试卷，而导致组卷的效率比较 低，因此许多研究人员在基于随机抽取算法的基础上，提出了基于深度或广度搜 索的自动组卷算法。该算法在组卷过程中仍然采用随机的方法抽取试题，但在试 题的抽取过程中通过验证所选择的试题是否满足系统给定的约束条件来决定是 否抽取该试题，当发现目前没有任何试题符合要求而组卷的过程又没有完成时， 则采用回溯试探法，通过放弃前面一段时间所做的组卷操作来重新进行组卷。由 天津工业大学硕士学位论文 于这种方法是在组卷的过程中通过放弃部分工作而不是放弃本次组卷过程中的 全部操作，从而有效地较少了无效组卷的次数，使得自动组卷算法性能得到较大 提高。 基于深度与广度搜索算法将记录随机选取法产生的每一状态，当搜索失败时 便释放上次记录的状态类型，然后再依据一定的规律变换某种新的状态类型进行 试探，通过不断的回溯试探直到组卷完毕或退回出发点为止。在理论上基于深度 与广度搜索算法可以遍历所有可能的状态组合。这种有条件的深度优先法，对于 状态类型和出题量都比较小的题库系统来说，组卷成功率较为理想，但在实际到 一个应用时，你会发现这种算法对内存的占用量极大，程序结构比较复杂，而且 选取的试题缺乏随机性，组卷效率低。当试卷总题量比较大时，可能的试卷组合 数将会是一个天文数字，因此该组卷算法的时间开销非常巨大，故在实际应用中 单纯的基于深度与广度搜索算法应用比较少。 四、基于遗传算法的组卷算法 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文的自然淘汰和遗传选择的生物进 化过程的计算模型，它是由美国m i c h i g a n 大学的h o l l a n d 2 0 世纪6 0 年代末、7 0 年代初最先提出，其本意是为人工智能系统的设计提供一种基于自然演化原理的 搜索机制。它模拟达尔文“优胜劣汰、适者生存”的原理以激励产生好的结构， 通过模拟孟德尔的遗传变异理论，在搜索的过程中，保持己有的好的结构的同时 寻找更好的结构。遗传算法作为一种全新的全局寻优搜索算法，以其鲁棒性强、 适合大规模并行处理以及应用领域广等特点，使其成为了2 1 世纪最重要智能计 算方法之一。 遗传算法作为一种智能搜索算法，它采用“生成+ 检测 ( g e n e r a t ea n d t e s t ) 的迭代过程。遗传算法是一种群体性操作算法，它以当前群体中的所有个体为遗 传操作对象，选择( s e l e c t i o n ) 、交x ( c r o s s o v e r ) 和变异( m u t a t i o n ) 是遗传算法的三 个最主要操作算子，它们组成了所谓的遗传操作( g e n e t i co p e r a t i o n ) ，这些操作的 引入使遗传算法具备有了其他搜索方法所没有的特性。 在基本遗传算法的组卷策略中，它将每道试题独立编码作为基因放在染色体 的相应位置，利用遗传算法的三个基本操作：选择、交叉与变异来完成试题的搜 索寻优，进而得到满足各种约束条件的试题集合，完成一次组卷过程。由于这些 操作策略的引入，使得到试卷具有相当高的专家水平。 五、基于项目反应理论的组卷算法 基于项目反应理论的自动组卷算法是由适应性测试发展而来的，适应性测试 这一概念是由w i i l i a m w t 在1 9 5 1 年率先提出的。适应性测试含义就是说，算 法针对被试个体的先前经验或者被试先前的历史信息中中得到信息，并依据得到 4 第一章绪论 的信息选取适合被试的题目进行组卷测试。被试作答完该题后立即评分，并以当 前题目的作答情况决定下一道被选中的测试试题的难度层次，直到整个测试结束 为止。事实上，整个测试的过程就是根据被试者的答题情况来判断被试者的能力 水平，然后据此从题库中选择符合被试者水平的题目进行测试的过程。 六、基于数据挖掘和知识发现的组卷算法 数据挖掘和知识发现是当前比较前沿的一门学科，它涉及到机器学习、统计 学、模式识别、人工智能和数据库等科学。他也被看作是机器学习和数据库理论 等学科的交叉学科。它可以广泛的应用于商业管理、智能决策、故障诊断、科学 研究等方面，当然也可以被应用于自动组卷系统中。虽然有不少学者在这方面进 行了研究，但至今，如何提高算组卷法的效率，仍然是关联规则发现问题需要解 决的问题。虽然数据挖掘和知识发现在组卷寻优中具有一定的先进性，但这方面 的研究目前还停留在理论上，缺乏比较成熟的技术和理论。 1 4 各种组卷算法优缺点的分析 通过对上述几种算法优缺点的对比分析，不难发现，在限制条件和状态空间 的情况下，随机选取法有些情况下能够搜索出一组令用户满意的试题。但是由于 它随机选取试题的范围是整个题库，因此无法明确哪些区域能抽出符合要求的试 题，极有可能在那些已经证明是无法抽取合适的试题的区域内反复选题，该算法 具有很大的随机性和不稳定性，大大降低了求解效率，最终导致组卷失败。 基于回溯探测的组卷算法尽管在一定程度上缓解了随机选取算法性能比较 低的问题，由于这种方法缺乏专家知识的启发性引导，当试题库的题量比较庞大 时，同样无法避免耗时大、系统性能低的问题。它是以牺牲大量的时间为代价换 取组卷高成功率，这不符合现在网上考试即时调题的要求。基于项目反应理论的 主要是根据各个单元试题的性能指标做出一个比较标准的衡量，由于组卷算法的 目标是通过对试题库中各试题单位进行排列组合，使组合出来的试卷能够最大程 度的满足给定的各项约束条件，因此存在多个可行的解。对于用户来说不存在所 谓的最优解，因此在试卷的寻优过程中如何有效地减少无效试卷在组卷过程中出 现的频率，又能确保可接受的可行解出现是解决自动组卷算法的关键问题所在。 遗传算法的操作对象是一群被称作种群的编码化个体。它通过种群个体之间 的遗传操作来搜索全局最优解。种群的迭代过程是通过对个体的选择、杂交和变 异等具有生物意义的遗传操作来实现的。在h o l l a n d 的提出的遗传算法的最初模 型中，固定种群规模大小，对个体的编码采用的是二进制定长编码，遗传算法的 遗传操作采用比例选择、单点杂交和位变异。 正是由于遗传算法本身的特点，使得它非常适合解决多约束条件下的最优化 天津工业大学硕士学位论文 问题，所以很多学者尝试把其应用到自动组卷系统的研究中，d b f o g e o l 在神经 网络进化学习方法的研究过程中首次提出将遗传算法应用于自动组卷， g o r d b e r g m w 依据遗传算法的寻优特性，结合组卷问题的实际，为组卷问题建 立了寻优模型等。国内的遗传算法的对研究与应用较晚，并且主要应用于建立各 种神经网络，直接将它应用于组卷系统的并不多见。 基于这种思想，采用遗传算法的概念，将每道试题作为一个独立的编码位， 利用遗传算法的三个基本操作：遗传、交叉与变异并最终完成试题的选取，得到 满足各种约束条件的试题集合。遗传算法以其具有自适应全局寻优和智能搜索技 术，并且收敛性好的特性很好满足自动组卷的需要。 1 5 本文的主要工作 本文在对当前组卷算法发展及其应用的现状学习总结的基础上，深入分析现 有组卷算法的优缺点。通过对遗传算法的深入学习，研究遗传算法容易过早收敛、 盲目搜索、局部搜索能力不强的原因，提出解决上述弊端的改进方案。结合组卷 问题的实际，根据经典教育测量理论建立组卷的数学模型，在上述基础上提出一 种基于自适应和小生境的改进遗传算法进行仿真实验，验证算法的组卷效率及选 优效果。主要的篇章如下： 第一章介绍了课题的研究背景，当前组卷系统的发展现状。介绍了几种当前 比较流行的组卷算法，对比分析各个算法的优缺点。着重介绍了遗传算法在组卷 问题应用的优势。最后介绍了本文的主要工作。 第二章介绍了组卷的基本原理以及原则，着重介绍了试卷的指标体系，及各 指标之间的关系，并在此基础上了建立了组卷的数学模型。通过目标函数的确定 成功的将组卷问题转化为目标函数的最小化问题。 第三章详细介绍了传统的遗传算法，分析其在组卷应用中的优点及缺陷，并 在此基础上提出改进方案。 第四章具体介绍改进算法的设计，包括编码方案、适应度函数的变换、自适 应交叉变异、小生境和抗早熟等技术的引入，并确定了智能组卷算法的流程。 第五章介绍了算法的仿真环境，题库的建立，组卷参数的确定以及组卷结果 的对比分析。 第六章对全文进行了总结，并对组卷算法的发展做出展望。 6 第二章组卷的基本理论和数学模型 第二章组卷的基本理论和数学模型 组卷模块是c a t 系统的核心组成部分，如果c a t 系统无法编制出高质量、 可实用的试卷，那它就无法对学生知识的掌握程度及教师的教学效果做出有效的 检验，也就失去了对教学活动的指导。任何实际问题的有效解决都需要有坚实的 理论作为支撑，组卷问题自然也不例外。从学科角度来看，组卷问题隶属于测验 编制的范畴，同时也是心理学和教育测量学的核心内容。在心理学与教育测量学 领域中，有两种重要的测验理论：项目反应理论( i r t ，i t e mr e s p o n s et h e o r y ) 和 经典测量理论( c t t ，c l a s s i c t e s tt h e o r y ) 。 试题质量一定程度了决定了考试质量，试题质量高低又依赖于组卷工作的是 否科学。组卷工作的科学性主要体现在针对性和代表性两个方面。针对性的含义 是指试题本身编制要合理，能对不同的考试对象有着不同的呈现。代表性是指试 题取样能准备的反映考试内容。因此合理的试题评价指标、试题的科学性，建立 完善的计算机管理的标准化试题库，对组卷问题的解决具有极为重要的作用。本 章将根据测试理论、组卷的基本原则、试卷的评价指标及各指标间的关系等基本 组卷知识构建组卷模型，并在此基础上确定遗传算法的目标函数。 2 1 组卷问题的理论基础 在心理学与教育测量学中，有两种重要的测验理论：项目反应理论( i r t ， i t e mr e s p o n s et h e o r y ) 和经典测量理论( c t t ，c l a s s i ct e s tt h e o r y ) 。经典测量理 论假设测试者的能力水平分布呈正态分布，因此，测试后的成绩分布也应该呈正 态分布，只有当测验分数呈正态分布时，才认为该测试是客观有效的，而且测验 总分呈正态分布是所有测验的编制人员追求的最高目标。经典测量理论是测验领 域最基本的理论，应用非常广泛，现阶段绝大多数考试试卷的编制以及考试结果 的评估都是以经典测量理论为基础的。项目反应理论则是一种建立在潜在特质理 论基础上的新兴的心理学与教育学测量理论。目前，也有一小部分考试系统采用 项目反应理论作为测试理论，考试过程中系统根据被测试对象的当前的答题情况 给出抽取下一道测试的题目，不同能力水平的被测对象的测试题目也各不相同。 由于项目反应理论成立的假定条件较强，而且目前通用的考试规则一般无法满足 其假定条件，因此本文仍采用经典测量理论作为解决组卷问题的理论基础。 7 天津工业大学硕士学位论文 2 1 1 经典测量理论 经典测量理论( c t t ) 最早是在2 0 世纪初提出来的，发展到5 0 年代后逐步形 成了比较完整的体系。各种测验的参数必须从考生样本中求得是经典测验理论的 特点之一，经典测验理论以真分数模型作为理论基础。所谓的真分数模型，它在 数学上的定义为：测量上被试者的真分数是测验实际得到的分数与测验整体误差 之和。 显然，是无法通过直接测量得到真分数的，因此是根据公式( 2 1 ) ，真分数 t 是被试在无数次独立重复测量的基础上获得的平均观测分数。 薯 即t = l i m 上l 月- o 刀 公式( 2 - 1 ) 任何一组信息都由真正的信息和噪音组成。教育测验的真正目的是获得被试 的真正信息，去除无效信息。教育测量上将真正的信息称为真分数，无效的信息 称为误差。由于在测量过程中误差不可避免的存在，直接测量得到的观测分数便 会在误差范围内波动。经典测量理论的真分数模型对此进行了简单而又有效的描 述，以下是它提出的基本定义及推导。 ( 1 ) x = t + e 公式( 2 2 ) 公式( 2 2 ) 定义：观测分数( x ) 是真分数( t ) 与误差分数( e ) 之和。 ( 2 ) t = x 公式( 2 3 ) 公式( 2 3 ) 定义：真分数( t ) 与观测分数( x ) 的各自平均数( x ) 相等。 ( 3 ) 占e = 0 公式( 2 4 ) 定义：误差分数( e ) 的期望值( 占e ) 为0 。 ( 4 ) 所e = 0 公式( 2 4 ) 公式( 2 - 5 ) 公式( 2 5 ) 定义：真分数( e ) 与误差分数( e ) 的相关度为0 ，由于真分数是用来 测验被测个体稳定性的心理特征，故不会随测验的误差( e ) 而变化。 ( 5 ) 见l 。2 = 0 公式( 2 - 6 ) 定义：不同的测验误差之间不存在相关。 ( 6 ) 一= 露+ 仃三 公式( 2 6 ) 公式( 2 - 7 ) 公式( 2 7 ) 定义：测验观测分数的方差( 听2 ) 等于真分数方差( 听2 ) 和误差分数 8 第二章组卷的基本理论和数学模型 方差( 仃：) 之和。该真分数模型是以弱假设作为理论基础的，也就是说这些假设很 容易验证并能被绝大部分测验数据所满足。经典测量理论在上述假设的基础上建 立一整套理论及统计分析的方法。对于教育测验来说，经典测量理论要求被试完 成一定的试题或作业，然后依据被试的作答的情况来推论和评价其能力水平。 经典测量理论包含的主要内容有成绩分析、项目分析和整体分析等。 1 成绩分析 1 ) 平均分数 平均分数是一种用得最广泛的集中量数。集中量数的有多种表现形式，如算 术平均数、众数、中位数等。算术平均数则是最常用的一种。一般用j 来表示。 j ：苎羔：叠 疗 其中五，而，。吒表示第刀个被试在某次考试中的成绩， 算术平均值。可将公式( 2 8 ) 简记为： 2 - - ! 兰置 刀智 公式( 2 - 8 ) 用j 表示这次考试的 公式( 2 - 9 ) 2 ) 方差与标准差 对于一批分数，不但要了解它的集中量数，还要知道分数的离散程度，可以 用方差和标准差来衡量。若有1 1 个学生的成绩为而，而，毛，8 2 表示方差，则 一 s 2 = 圭( 置- 2 ) 2 刀智一 公式( 2 - 1 0 s 2 的值越大分数的离散程度就越大。 2 、项目分析 除了对成绩进行分析外，还要依次对试卷中的试题进行分析评价。在教育测 验中，对考试的分析与评价通常分两方面进行。一是对各个试题进行单独分析， 称为“项目分析；二是对整份试卷或考试进行的分析或评价，称为“整体分析一。 学习成绩测验既可以衡量学生的相对能力水平，也能衡量出学生的实际能力 水平。在教育测量中，把测量学生相对能力水平的测验称为常模参照测验：把衡 量学生实际能力水平的测验称为目标参照测验。由于常模参照测验和目标参照测 验的存在，故对项目分析和整体分析也提出了不同的要求。常模参照测验的项目 分析主要包括难度分析和区分度分析。 ( 1 ) 难度分析 9 天津工业大学硕士学位论文 难度是试题的难易程度的指标，有多种方法可以确定试题的难度，最通用的 方法是利用公式( 2 一1 1 ) 计算： n o , = 1 一詈 公式( 2 1 1 ) ，f 其中：n d , 、4 、e 分别表示第f 题的难度、该次考试第，题的平均分和第f 题的满分分数。假设有刀个学生，则可用公式( 2 1 2 ) 表示，根据考生在第f 题上 的得分直接求得该题的难度。 如 悃卅一苛 公式( 2 1 2 ) 其中：瓦表示第m 个学生在第i 题上的得分。 ( 2 ) 区分度分析 区分度也被称为鉴别度，是指测验项目对被试者的区分程度或鉴别能力。有 多种计算区分度的方法，最通用的一种方法是两端分组法。它是比较成绩在高、 低两端的被试者答对该题的比率。 假设s 和s ，分别为高分组和低分组通过某道题目的百分比，则公式( 2 1 3 ) 提供了该题目的区分度的指标： q = 品一 公式( 2 1 3 ) q 是区分度指数，q 的值在一1 和+ l 之间。当d = l ，表示高分组全部答对该题， 而低分组全部答错该题；当d = 一l 时，则表示低分组的全部答对，高分组的却全 部答错；当d = 0 时，则表示高低两个分数组的通过率相等。 3 、整体分析 整体分析是指依据测验的结果对试卷进行综合的分析与评价。它是通过效度 和信度这两个数量指标来描述的。 ( 1 ) 信度 信度表述的是考试结果是否真实反映考试的实际水平。测量误差是影响信度 的主要因素。一个考生的实得分数由反映学生能力水平的真实分数和测量误差两 部分组成，用方差的大小来表示这些影响的小小。因此，将成绩方差分解成真实 方差与误差方差之和，则信度就是真实方差与总方差的比。信度定义为： 1 0 第二章组卷的基本理论和数学模型 f 一椰一磐c = 幽生 ( n - 1 ) 公式( 2 - 1 4 ) 公式( 2 一1 4 ) 中是第墨是第i 道试题的方差，而s 2 则是整个试卷的方差。上述 可信度的定义描述了在排除了各题的误差后，剩下的部分在总方差中所占的百分 比，若各题的误差小，则试卷的可信度较高，反之则可信度较低。一般信度系数 在0 8 5 左右，如果信度小于0 6 ，那么可以认为该测验不可信。 ( 2 ) 效度 效度表示测验的有效性，即指测验结果的正确性程度。效度是衡量考试达到 目的程度的指标量，只有符合考试的目的考试，才是有意义的考试。计算效度通 常采用相关系数法，即先选取以前的一次与当前的考试目的一致的考试作为效度 指标，然后根据公式( 2 1 5 ) 计算这两次考试成绩的相关系数。 ，：妻业二譬望 公式( 2 - 1 5 ) 急 n s v s f 一1 式中咒和刁分别是第i 个考生在当前考试与效标考试中的取得的成绩；y 、 z 、s 一最分别是两次考试成绩的均值和标准差；n 为参加考试的人数。 2 1 3 项目反应理论( i r t ) 项目反应理论( i r ti t e mr e s p o n s et h e o r y ) 是一种新兴的心理学与教育学测 验理论，它是在改进经典测量理论的局限性的基础上发展起来的。在这些理论中 较有代表性的有逻辑斯蒂模型。 一、项目反应模型 柏恩鲍姆于1 9 5 7 年提出逻辑斯蒂模型，他假定的项目特性曲线如图2 - 1 所示。 l 答 对 饭 阜 图2 - 1 逻辑斯蒂模型 天津工业大学硕士学位论文 项目特性曲线描述的是各种特质水平的被试( 通常用秒表示) ，对某一项测验 的正确反应概率( p ( 口) ) 。该正确反应概率只与该项目的质量有关。 二、项目的测验信息函数 信息函数是项目反应理论中提出来用于描述一个测验或一道试题有效性的 工