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

摘要 摘要 随着网络教育的流行，智能组卷问题也得到了广泛的关注。智能组卷问题( t h e p r o b l e mo fg e n e r a t i n gt e s tp a p e ri n t e l l i g e n t l y ) 是一个多目标优化问题。传统的随机选取法 和回溯试探法在组卷时间和组卷成功率上，都存在着明显的缺陷，很难得到一个较为满 意的解。如何在已有研究的基础上，针对智能组卷问题的实际特点，提出一些行之有效 的算法来解决智能组卷问题，已经成为大家关注的一个热点。 本文以“大连交通大学软件学院计算机等级考试网”的建设为背景，目的是研究如 何将组卷算法与现有的题库系统相结合，从题库中提取出符合用户要求的试题组成试 卷，使该试卷能客观反映用户的实际能力水平。通过对组卷算法和基本原理的研究，开 发了基于改进遗传算法的智能组卷模块。以改进的遗传算法为基础，根据用户对试卷难 度的要求，以及试卷总分等重要试题属性的需求动态生成试卷。 通过对遗传算法等几种常用智能组卷算法的分析比较，本文提出了一种改进的遗传 算法。该算法的思想是采用分段实数编码方式，克服了传统二进制编码搜索空间过大和 编码长度过长的缺点，省去了个体的解码时间，有效提高了算法的运行效率。并提出了 一种新的变异概率的计算方法，引入了呈指数变化的系数k m ，使变异概率随进化代数呈 递减趋势变化，保证了个体的进化能力，有效防止算法陷入局部最优。针对分段实数编 码的特点，采用段内基本位变异操作，在变异过程中，对种群的每个个体，产生一个长 度为编码串长度的随机数列，通过对数列中每个随机数与变异概率的比较结果，来判断 该位是否执行变异操作，从而改善了遗传算法的局部搜索能力，保持了群体的多样性， 保证了遗传算法的收敛能力。 本算法已应用于实际的在线考试系统中，理论分析和实验结果表明，与基本遗传算 法相比，改进的遗传算法更能满足组卷的实际需求，有较好的克服早熟的能力，在全局 搜索性能及收敛速度上较基本遗传算法有显著提高，证明了改进算法的有效性和优越 性。 关键词：改进遗传算法：智能组卷；数学模型 大连交通大学1 i 学硕十学何论文 a b s t r a c t b e i n gp o p u l a rf o r t h en e t w o r ke d u c a t i o n ，t h ep r o b l e mo fg e n e r a t i n gt e s tp a p e r i n t e l l i g e n t l yh a sb e e nw i d e s p r e a dc o n c e r n t h ep r o b l e mo fg e n e r a t i n gt e s tp a p e ri n t e l l i g e n t l y i sa c t u a l l yam u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m t h et r a d i t i o n a lm e t h o di ng e n e r a t i n gt e s t p a p e r ，s u c ha st h er a n d o ms e l e c t i o na n db a c kt r a c k i n g ，h a so b v i o u sd e f e c t so nt h et i m ea n d t h es u c c e s sr a t eo fg e n e r a t i n gt e s tp a p e r t h e r e f o r ei ti sd i f f i c u l tt of i n da i le f f e c t i v es o l u t i o n a c c o r d i n gt ot h eo l dr e s e a r c h ，h o wt of i n dau s e f u lm e t h o dt os o l v et h ep r o b l e m ，w h i c hc a n a i ma tt h ea c t u a lc h a r a c t e r i s t i c so fg e n e r a t i n gt e s tp a p e r i n t e l l i g e n t l y ，h a sb e c o m eah o ts p o to f c o n c e r nt oe v e r y o n e i nt h i sa r t i c l e ，b a s e do nc o m p u t e rr a n de x a m i n a t i o ni ns o f t w a r ei n s t i t u t eo fd a l i a n j i a o t o n gu n i v e r s i t y ，w er e s e a r c ho nh o wt oc o m b i n ea l g o r i t h mo fg e n e r a t i n gt e s tp a p e rw i t h t h ee x i s t i n gi t e mb a n ka n dh o wt oo b t a i nq u e s t i o n sw h i c hs a t i s f yt h eu s e r sr e q u e s tf r o mi t e m b a n k ，s ot h a tt h i st e s tp a p e ri sa b l et oo b j e c t i v e l yr e f l e c tt h er e a lc a p a c i t yl e v e lo ft h eu s e r a c c o r d i n gt o t h er e s e a r c ho fa l g o r i t h ma n db a s i cp r i n c i p l eo fg e n e r a t i n gt e s tp a p e r ，w e d e v e l o po n em o d u l eo fg e n e r a t i n gt e s tp a p e ri n t e l l i g e n t l y ，w h i c hi sb a s e & o ni m p r o v e d g e n e t i ca l g o r i t h m a c c o r d i n gt od i f f i c u l t ys u p p l i e db yt h eu s e ra n ds c o r e so ft e s tp a p e r , w h i c ha r ei m p o r t a n ta t t r i b u t e so fq u e s t i o n s ，w ec a ng e td y n a m i cg e n e r a t i n gt e s tp a p e r t h r o u g ha n a l y s i sa n dc o m p a r i s o n 、析t l lt h eg e n e t i ca l g o r i t h ma n dc o m m o na l g o r i t h mo f g e n e r a t i n gt e s tp a p e ri n t e l l i g e n t l y ，i nt h i sa r t i c l e ，an e wm e t h o do fg e n e r a t i n gt e s tp a p e r i n t e l l i g e n t l yb a s e do nt h ei m p r o v e dg e n e t i ca l g o r i t h mi sg i v e n t h i sm e t h o du s e st h ep a r t i t i o n r e a ln u m b e rc o d i n g ，i tc a l lg e to v e rs o m es h o r t c o m i n g so ft r a d i t i o n a lb i n a r yc o d i n g ，s u c ha s s e a r c h i n gs p a c ei st o ol a r g ea n dt h el e n g t ho fc o d i n gi st o ol o n g t h i sm e t h o da l s oc a ns a v e t h et i m eo fd e c o d i n ga n di m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h mo p e r a t i o n i nt h i sp a p e r ， t h e r ei san e wm e t h o do fm u t a t i o nr a t ec o m p u t a t i o n t oe n s u r ei n d i v i d u a la b i l i t yo fe v o l u t i o n a n de f f e c t i v e l yp r e v e n tt h ea l g o r i t h mi n t ol o c a lo p t i m a ls o l u t i o n ，t h i sa r t i c l ei n t r o d u c e san e w c o e f f i c i e n tk mw h i c hc h a n g e se x p o n e n t i a l l ya n dm a k e sm u t a t i o nr a t er e d u c ea l o n gw i t ht h e e v o l v i n ga l g e b r a f o rt h ec h a r a c t e r i s t i co fp a r t i t i o nr e a ln u m b e rc o d i n g ，i nt h ep r o c e s so f m u t a t i o no p e r a t i o n ，w eu s eb a s i cm u t a t i o no p e r a t i o ni nt h es e c t i o n , t h e nr a n tas e q u e n c e w h o s el e n g t hi se q u i v a l e n tt oc o d i n gl e n g t h t h r o u g hr e s u l to ft h ec o m p a r i s o nb e t w e e ne a c h n u m b e ri ns e q u e n c ea n dm u t a t i o nr a t e ，w ej u d g et h i sp o te x e c u t em u t a t i o no rn o t t h i s m e t h o di m p r o v e dt h ec a p a b i l i t yo fl o c a ls e a r c h i n go ft h eg e n e t i ca l g o r i t h m ，m a i n t a i n e dt h e m u l t i p l i c i t yo fc o m m u n i t y ，a n de n s u r e dt h ec o n v e r g e n c e o ft h eg e n e t i ca l g o r i t h m t h i sa l g o r i t h mi sa p p l i e dt ot h ea c t u a lo n l i n ee x a m i n a t i o ns y s t e m b o t ht h et h e o r e t i c a l a n a l y s i sa n dt h ee x p e r i m e n t a lc o m p a r i s o ns h o wt h a ti 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 i m p r o v e dg e n e t i ca l g o r i t h mh a sm o r ea b i l i t yt og e to v e r p r e m a t u r ec o n v e r g e n c et h a nt h et r a d i t i o n a la l g o r i t h m s m o r e o v e r ，i m p r o v eg e n e t i ca l g o r i t h m c a no b v i o u s l yi m p r o v et h ea b i l i t yo fg l o b a lr e s e a r c ha n dt h ec o n v e r g e n c e s p e e dt h a nt r a d i t i o n g e n e t i ca l g o r i t h m i tp r o v e st h a tt h ei m p r o v e da l g o r i t h mi se f f e c t i v ea n d s u p e r i o r k e y w o r d s ：i m p r o v e dg e n e t i c a l g o r i t h m ；g e n e r a t i n g t e s t p a p e ri n t e l l i g e n t l y ； m a t h e m a t i c a lm o d e l 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太整褒通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太整交通态堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太蓬塞通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太蓬銮通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 、 又。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：常硷 导：锄 日期：2 0 0 8 年1 0月2 5日日期：2 0 0 8 年1 0 月2 5 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱：上i n 9 - 2 9 船 f ) ，6 伽价 电话：13 0 t z h 2 1i 弓口 邮编： 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太蓬塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名： 霭臻 日期：2 了年i o 月玎日 绪论 绪论 一、智能组卷问题 1 、智能组卷研究的目的及意义 考试是教学过程中的一个重要环节，是检验学生学习成绩和教学效果的重要手段。 传统考试主要采用纸上做答的形式，教师在教学过程中需要花费大量的时间和精力收集 试题、编制、整理、批改和分析试卷，不但工作量大而且效率非常低。随着计算机和i n t e m e t 的普及，远程网络教学逐渐成为研究的热点。作为一种新兴的教学方式，远程网络教学 比传统的教育方式更具有自主性、交互性和个性化的特点。随着远程网络教学的流行， 网上考试也应运而生。而网上考试的试卷是根据用户的需要由计算机自动生成的，这不 仅使考试更加具有规范性，客观性，也节省了大量的时间。网上考试还使考试时间更加 灵活，让学生可以根据自己的时间，在任何时间段内参加考试，能更加全面的考察教学 的实际效果，对学生以后的学习起到指导性的作用，极大地促进教学质量的提升。 本文是为解决已有计算机考试系统中组卷模块难以满足实际考试需求这一问题提 出的。找到有效解决计算机考试系统中组卷问题的方法，对合理、高效利用现代化教育 教学手段，实现考试现代化，减轻教师工作量，提高教学效率和质量有重要的实际应用 价值。 2 、国内外智能组卷的研究现状 随着网上考试的发展，考试的形式发生了显著的变化，在传统考试中所有的被测试 者都使用同样的试卷进行测试，而现在可以在保证考察效力相同的f j 提下，在同一场考 试中使用不同的试卷对被试者进行单独的测试。 在国外，一些教育相对发达的国家对题库建设理论和模式研究的比较早，发展的也 比较快。他们建立的一些大型题库，在一些标准化考试系统，如美国的t o e f l 、g r e 、 g m a t 等已经成功运行了几十年，一直都能科学地测试出学生的实际水平。这证明智能 组卷是可能的并且行之有效的。 在国内，对题库建设理论的研究起步比较晚，直到9 0 年代题库建设才引起了一些 考试机构和大学的注意。现在，虽然一些高校也开发出了自己的在线考试系统，其中比 较有代表性的有西安交通大学等联合编制的“高等学校工科大学物理课程试题库系统”、 清华大学等联合编制的“高等学校工科高等数学课程试题库系统、山东省高教自考办 公室等联合编制的“高等数学( 财经类) 题库系统”以及全国计算机等级考试系统等等 【l 】，但这些系统都存在着这样那样的局限性问题，特别是在组卷算法方面还有很多不完 善的地方。 大连交通人学t 学硕十学位论文 目前，网上考试的组卷方法大体可以分为三种：一种是将试题库看作试题集，组卷 时由老师选题；二是将试题库看作试卷集，将已经出好的试卷存储起来，考试时随机抽 取份或多份试卷；三是有自动抽题组卷的功能，可以利用某种组卷算法自动形成试卷。 其中，前两种组卷方法的实质没有变化，对现在的研究没有任何意义：第三种方法生成 的试卷灵活性比较大，但如果组卷策略不理想，生成的试卷往往不能满足考试的实际要 求，还需要人为对组卷过程进行干预，来保证试卷的有效性。 3 、智能组卷问题的主要研究方法 经过多年发展，对于智能组卷问题的研究有了一定成果。国内常用的组卷方法有以 下三种： 随机抽题法：从题库中随机抽取试题，然后判断是否符合试卷的约束条件，或从符 合试卷某项要求的试题库子集中随机抽取试题，然后判断是否符合试卷的其他约束条 件，这样随机的抽取一道试题放入试题库中，此过程不断重复，直到组卷完毕，或己无 法从题库中抽取满足约束条件的试题为止。该方法结构过程简单，对于单个试题的抽取 运行速度较快，但是对于整个组卷过程来说组卷成功率低，即使成功，花费的时间也令 人难以忍受。 回溯试探法：将随机选取法产生的每一状态类型记录下来，当搜索失败时，释放上 次记录的状态类型，再依据一定的规律( j 下是这种规律破坏了选取试题的随机性) 变换 一种新的状态类型进行试探，通过不断回溯试探直到试卷生成完毕或退回出发点为止【2 】。 这种有条件的深度优先算法，在遇到状态类型和出题量都较少的题库系统时，组卷的成 功率较好，但对于实际应用选取的试题缺乏随机性，且组卷时间也过长。 遗传算法：是模拟生物在自然环境中遗传和进化过程形成的一种自适应全局优化搜 索算法，它利用一定的编码技术和繁殖机制来处理复杂的现象，适用于处理传统搜索方 法难以解决的组合优化问题。以遗传算法的基本思想为指导，设计的智能组卷算法，能 较好的解决组卷中的多约束组合优化问题，组卷成功率高，组卷时间也较短。 二、遗传算法概述 生物进化是一种特殊的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产 生适应环境变化的优良物种。而遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 就是通过模拟自 然界的生物进化和自然选择机制形成的一种易于操作的、并行的全局优化搜索算法，它 将问题的求解过程表示成“染色体”适者生存的过程，通过“染色体 群( p o p u l a t i o n ) 的一代代不断进化，包括选择( 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 ) 等操作，最 终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。 一般认为，遗传算法有5 个基本组成部分( 这是由m i c h a l e w i c z 归纳的) ： 2 绪论 ( 1 ) 问题的解的遗传表示。 ( 2 ) 创建解的初始种群的方法。 ( 3 ) 根据个体适应度对其进行优劣判定的评价函数。 ( 4 ) 用来改变复制过程中产生的子个体遗传组成的遗传算子。 ( 5 ) 遗传算法的参数值。 三、本文主要工作及意义 遗传算法是模拟大自然生物进化过程的计算模型，它以简单、鲁棒性强、全局寻优、 收敛速度快以及不受搜索空间限制性条件约束等特点，日益受到人们的关注。这些特点 都有利于解决组卷问题，遗传算法首先生成一定规模的初始群体，然后使其中的个体以 一定的概率进行交叉与变异，实现个体结构的重组，再按预定的适应度函数选择复制优 秀个体，组成新的一代，如此循环迭代，以期最终找到满足寻优条件的全局最优解。但 传统的遗传算法存在搜索后期搜索效率低和易形成早熟收敛的情况，为此，人们尝试了 许多改进方法，包括设计不同的选择、交叉及变异算子，改变算法结构，将遗传算法与 其它优化智能方法相结合等。针对组卷的具体情况，本文提出一种利用改进的遗传算法 来求解组卷问题的方法，这种方法具有较高的效率，在组卷中取得了良好的效果。 本论文研究课题来源为大连交通大学软件学院“计算机等级考试网”。 本课题的主要研究任务是： ( 1 ) 研究调整变异概率的计算对变异操作的影响； ( 2 ) 提出一种改进的遗传算法： ( 3 ) 针对智能组卷问题，改进了传统遗传算法中的随机交叉操作和选择、交叉、变 异操作的基本步骤； ( 4 ) 研究基于这种改进的遗传算法对于解决智能组卷问题的有效性； ( 5 ) 应用于实际项目中测试； ( 6 ) 论证算法在理论上和实际上的正确性和优越性。 本章小结 在本章中，主要介绍智能组卷问题的研究方法和现状。详细介绍了智能组卷问题的 基本理论和研究方法。同时，本章中还简单介绍了遗传算法。最后介绍了本文主要工作 及意义。 火连交通大学。1 j 学硕十学何论文 第一章题库建设概论 考试是用于较正式场合下的测试，作为一种教育测量与评价的术语，完全适用测试 理论。目前常用的测量理论主要有两种：二十世纪初提出的经典测试理论( 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 ) 。 1 1 经典测量理论 1 1 1 经典测量理论的基本内容 经典测量理论( c l a s s i c a lt e s tt h e o r y ，简称c t t ) 也被称为真分数理论，起源于2 0 世纪s p e a r m a n 的研究工作，是由基本假设、信度、效度、标准化等基本概念构成，其 中基本假设是经典测量理论基础【一5 】。 经典测量理论一直被题库系统建设所采用，是提供试卷分析和成绩分析的依据，是 估计测验中实得分数与真分数之间的关系程度。经典测量理论具体是指每个个体都有某 些无法直接观察的心理变量，被称为“真分数( t ) ，我们可以用实际得到的、具有 一定测量误差( e ) 的“观察分数”( 或称“正确应答分数) ( x ) 作为真分数的估 计值。真分数在数学上的定义为：测量上被测试的真分数是观测分数的期望值，即 t = e x 。其中，x 为实际得分，代表期望值，t 为被测试的真分数。但是仅仅根据这 个公式是不能直接测量得到真分数的。所以t 可以被解释为：在无数多次独立重复测量 上获得的平均观测分数。其数学模型为：观察分数真分数+ 误差，即x = t + e 。这是一 个线性模型，表示在观察分数和真分数之间存在着线性关系。 经典测量理论建立在如下三条假设的基础之上： ( 1 ) 实得分数x 和误差分数e 之间存在线性关系，即：x = t + e ；其中t 为真分数； ( 2 ) 大量测验中的误差分数统计平均值为零。 ( 3 ) 真分数和测量误差是相互独立的。 经过八十多年的发展历程，经典测量理论有了很大的发展，很多现代测量理论得到 了广泛的应用，例如题目反映理论、动态评测理论、潜在等级分析理论等。这些理论的 提出和应用，都提高了我国的教育水平。 1 1 2 经典测量理论的优点 经典测量理论计算公式简明易懂，建立了一系列对试题进行分析的方法，广泛的应 用于教育测试中，有如下比较明显的优点： 4 第一章题库建设理论 ( 1 ) 它建立在弱假设条件上，对实施条件要求不严格，适用性广。 ( 2 ) 它具有系统的理论与方法体系。 ( 3 ) 在实际应用经典测量理论的实践中，大家已经慢慢积累和完善了一些更为适合 自身的方法和应用原则。 ( 4 ) 经过几十年的发展，经典测量理论有着较为完善的理论基础和对测验进行统计 分析的方法，它建立在较简单的数学模型之上，易于被人理解和接受，容易推广。 传统的考试都是以经典测量理论为指导的，教师根据学习内容制定试卷的结构、考 试内容、试卷难度( 反映在考试平均分上) 等，并据此组织试题对学生进行考评。对于 经典测量理论来说，测试样本的选择很重要，必须选择难度适中、区分度好的试题，才 能有效地区分考生的学习水平。对于学生来说，试卷中的题目，只有一部分符合自己真 实能力，其余题目要么难度太大、要么过于简单，所以这样的考试存在着明显的弊端， 不能快速地测试出考生的真实水平。 1 1 3 经典测量理论的不足 经典测量理论虽然有了较长的历史并取得了相当的成果，但因其自身的局限性，还 存在着许多无法克服的问题，表现如下： ( 1 ) 测试参数过分依赖具体样本； ( 2 ) 测试结果的可比性差； ( 3 ) 题目的参数和所得的结果直接受制于具体测试和被测情况，被测试水平和测试 题目参数之间没有明确的关系，不同测试间所得的分数可比性差； ( 4 ) 不能适应各种被测试的具体情况，缺乏个性。 经典测量理论的问题在于该理论的各个基本概念之间的相互依赖、相互制约。测量 专家认为，经典测量理论中最基本的四个概念是项目难度、项目区分度、信度和正确应 答测试分数。项目难度和项目区分度、信度都依赖于考生组的能力水平分布，即正确应 答测试分数；而考生的j 下确应答测验分数又依赖于项目信度，这种基本概念之间的相互 依赖、互为前提，不可避免的为该理论带来许多难以克服的困难。这些问题都是经典测 量理论难以解决的问题，因此专家开始研究其他方法避免这一问题的发生。 1 2 项目反映理论 1 2 1 项目反映理论的基本内容 项目反映理论( i t e mr e s p o n s et h e o r y ，简称i r t ) 也称为潜在特质理论，又称为题 目特征曲线理论，起源于2 0 世纪三四十年代，是一种基于非线性概率模型的能力测量 大连交通大学t 学硕十学位论文 理论，能对被试者能力进行正确的评估。为了准确地测量出学生的真实能力水平，在实 施目标参照测验过程中，计算机必须能根据学生对题目的具体反映情况进行相关数据的 分析，及时调整适合该学生实际能力水平的题目。在实际测验的操作中，如果先给考生 的一道难度系数为中的试题，考生答对，则下一道试题的难度加大，否则，减小下一道 试题的难度，这样，就能够在比较短的时间内通过比较少的试题测量出考生的真实能力 水平。项目反映理论就是数学模型的建立和对模型中各个参数的估计，它主要基于以下 三条假设： ( 1 ) 局部独立性( l o c a li n d e p e n d e n c e ) ：被测者对于试卷中某个题目的反应只与本题 有关，不受其他题目的影响。任何一道题目的内容不会对其他题目的作答提供有用的信 息。 ( 2 ) 能力单维性：被测结果只取决于一种能力，其他能力的影响可以忽略不计。 ( 3 ) 项目特征曲线( i t e mc h a r a c t e r i s t i cc u r v e ) ：是指把一个题目的答对率和包括这个 题目的整份试卷测量出来的能力值相联系的数学函数。题目的正确概率是其能力的数学 函数。 目前，项目反应理论已经在欧美等发达国家中得到了发展和应用，应用领域涉及教 育、军事、工业等部门。近年来，项目反映理论也得到了国内学者的重视，在理论研究 的同时，也逐渐的开始尝试实践应用【6 】。 1 2 2 经典测量理论( c t t ) 与项目反应理论( i r t ) 的比较 c 1 v r 经过长期发展，在理论与实践上都有公认的成就，但仍存在许多无法克服的技 术问题；在这些方面，i r t 有较大的突破。 在c t t 中，根据项目分析法所得的项目统计量受样本的抽样变动影响，即项目统 计量依赖于测试所实施的被试样组；而在i r t 中，采用局部独立性假设与样本独立项目 较准的方法，能很好地解决抽样变动这一问题。在c t t 中，被试者测验分数依赖于项 目的难度，使得进行不同测验的被试者难以比较；为此，i r t 提出了一种测验等化方法 来解决这一困难，即根据每个被试者的不同水平，对不同的被试者实施不同的测验项目， 并使这些项目的难度和被试者的水平相适应，在此基础上，通过只要求测验数据和模型 是拟合的，使对被试者能力的测量不依赖于所选择的测验难度，即不管什么难度的测验 项目，根据其项目特征曲线都可以估计出相应的能力值。c 1 v r 假设所有被试者的测量标 准误差都相等，这是不太可能的；而i r t 理论没有这种等测量标准误差的假设，它采用 信息函数( 包括测验信息函数、项目信息函数、分数信息函数，其中测验信息函数量是 各项目信息量的总和。) 来说明这一问题。 6 第一章题库建设理论 另外，在题库建设中i r t 和c t t 的基本思路也有细微的不同，主要区别在于项目 参数的获得、标准参照测验项目的选择、常模的建设方面。c t t 提供项目统计量、项 目难度和鉴别力，但这些依赖于被试样组。而i r t 项目参数具有不变性，因此各被试团 体所得的项目参数具有可比性，对题库建设很有用。在项目的选择上，c 1 v r 往往根据 内容效度与项目统计量选择测验题；而i r t 则可以根据各项目在临界分数附近的信息 量，选择能够提供最大信息量的项目。在常模的建立上，根据i r t 所得的能力估计值具 有不变性，因此运用某一样组的实测结果建立的常模可用于解释题库其它项目样组的测 验结果。总之，以i r t 为基础，用计算机建立题库是比较省时省力的方法。 1 2 3 项目反映理论的优点 目前，项目反应理论的理论和方法在应用中体现了如下优点： ( 1 ) 对被试者能力的估计不依赖于特定的测验题目。项目反应理论将被试者的能力 和试题难度放在同一量尺上进行估计，无论测验的难易，被试者能力的估计值都不变， 不同的测验结果可直接比较。 ( 2 ) 难度和区分度的估计值与被试者能力无关。同一个测验项目，将高能力和低能 力的被试者的反应，拟合在同一条项目特征函数曲线( i c c ) 上，同一条i c c 所对应的项 目参数是唯一的。 ( 3 ) 测验信息函数的概念代替了信度理论，用测验对能力估计所提供的信息量的多 少，表示测量的精度。这避免了平行测验的假定，并能给出对不同能力被试者的测量精 度。 ( 4 ) 根据项目信息量的大小选择对能力估计精度最有增益的项目，使测验达到预先 规定的满意精度。对不同能力的被试者实施不同试题测试。这样既提高了测量精度又缩 短了测验长度。 ( 5 ) 采用非线性模型，建立了被试者对项目的反应( 观察变量) 与其潜在特质( 潜 变量) 之间的非线性关系。 显然，经典测量理论是不具备上述优点的，迄今为止能够同时具备这五条优点的也 只有项目反映理论1 7 1 。这些优点能够满足广大测试使用者的要求，也正是由于这些优点， 才使项目反映理论成为了当前教育和心理测量学中的前沿理论，吸引了大量的测量专家 和测试使用者。本文中的智能组卷问题，也是基于项目反映理论进行设计和实现的。 本章小结 本章介绍了经典测量理论和项目反映理论知识的原理，及优缺点，并对经典测量理 论和项目反映理论做了比较。针对本文的需要，对项目反映理论做了较为详尽的描述。 7 大连交通人学_ 1 ：学硕十学位论文 第二章智能组卷算法 2 1 随机组卷法 随机组卷算法的基本思想是通过组卷控制指标随机的选取试题放入试题库，此过程 不断重复，直到组卷完毕或已无法从题库中选取满足指标的试题为止【8 】。随机组卷算法 方法简单，对单道试题选取的速度快，但因为要求题库试题量大，而且要分布良好，导 致使用这种方法的组卷整体效率不高。 随机组卷法在组卷过程中根据当前各种约束条件分量，随机地从题库中挑选一道试 题，检查该试题是否满足当前目标函数的约束，如果不满足，则重新选择一道试题进行 新的试探，直到生成满足用户需求的试卷。若不能满足用户的需求，则组卷失败。 随机组卷算法的具体步骤如下： s t e p l ：将当前各种状态变量赋初值。 s t e p 2 ：随机从题库中选择一道试题，若无试题可选，则组卷失败，退出算法。 s t e p 3 ：检查该试题是否满足各种约束条件。 s t e p 4 ：试题若满足条件，修改各约束条件，转至s t e p 6 。 s t e p 5 ：试题若不满足条件，则该试题为不可满足的试题，转至s t e p 2 。 s t e p 6 ：检查当前试卷是否完成，若未完成，转至s t e p 2 。 s t e p 7 ：输出试卷，算法结束。 随机组卷算法结构简单、单次组卷过程的运行速度比较快，但是试题的重复率高， 组卷成功率非常低，即使成功，所花费的时间也令人难以忍受。因此人们对随机组卷 算法进行了改进，产生了回溯试探法。 2 2 回溯试探法 回溯试探法属于有条件的深度优先算法，其基本思想是将随机组卷法产生的每一状 态都记录下来，当搜索失败时释放上次记录的状态类型，然后再根据一定的规律变换另 一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为 止。这种方法对内存占用量比较大，程序结构比较复杂，选取试题时缺乏随机性，组卷 耗费时间比较多。但回溯试探法可以保证只要试题库中存在满足条件的解则一定可以找 到一个可行解。 回溯试探法的组卷算法原理如图2 1 所示。 8 第二章钾能细卷算法 ， ：i ：_ 、 ? i - j 。 j ， 图2 1 同溯试探法原理图 f i g 2 1s k e t c hr e t r o s p e c t i v et e s t i n gm e t h o d 上图表示三道题的试卷，满足第一道题的解有a l i 、a 1 2 ，满足第二道题的解有a 2 l 、a 2 2 、 a 2 3 ，满足第三道题的解有a 3 l 、a 3 2 、a 3 3 。回溯试探算法是采用自顶向下的方法先搜索数 据库，找到符合第一道题的解a l l 接着搜索第二道题的解a 2 l ，然后类似搜索至l j a 3 l ，若 ( a a 2 1 ，a 3 1 ) 满足总要求，则保存，否则不采用。第一组搜索完成后，将a 3 l 脱解， 继续搜索至a 3 2 ，再得一组解( a l l ，a 2 l ，a 3 2 ) ，若( a l l ，a 2 1 ，a 3 2 ) 满足总要求，则保存， 否则不采用。第二组搜索完成后，将a 3 2 脱解，继续搜索至a 3 3 ，再得一组解( a l l ，a 2 l ， a 3 3 ) ，若( a l l ，a 2 l ，a 3 3 ) 满足总要求，则保存，否则不采用。再回溯至a 2 1 ，继续搜索 至a 2 2 ，综上，这样的搜索结果是：( a l l ，a 2 1 ，a 3 1 ) 、( a l l ，a 2 1 ，a 3 2 ) 、( a l l ，a 2 1 ，a 3 3 ) 、( a l l ， a 2 2 ，a 3 1 ) 、( a l l ，a 2 2 ，a 3 2 ) 、( a t l ，a 2 2 ，a 3 3 ) 、( a l l ，a 2 3 ，a 3 1 ) 、( a l l ，a 2 3 ，a a 2 ) 、( a l i ，a 2 3 ， a 3 3 ) 、( a 1 2 ，a 2 1 ，a 3 1 ) 、( a 1 2 ，a 2 1 ，8 - 3 2 ) 、( a 1 2 ，a 2 1 ，a 3 3 ) 、( a 1 2 ，a 2 2 ，a 3 1 ) 、( a 1 2 ，a 2 2 ，a 3 2 ) 、 ( a i 2 ，a 2 2 ，a 3 3 ) 、( 8 1 2 ，a 2 3 ，a 3 j ) 、( a 1 2 ，a 2 3 ，a 3 2 ) 、( a 1 2 ，a 2 3 ，a 3 3 ) 。 回溯试探法的算法步骤如下： s t e p l ：根据给定的实体集序列，计算相应的各种参数值，得到试题集。 s t e p 2 ：如果得到的试题集不为空，随机从可满足的试题集中选择下一个试题。 s t e p 3 ：如果得到的试题集为空，则组卷失败，退出算法。 s t e p 4 ：检查当前试卷是否完成，若完成，则组卷成功，返回。 s t e p 5 ：若试卷未完成，回溯至失败的那个点，重新开始选择，直到组卷成功。 s t e p 6 ：若所有试题已经遍历一遍后，仍然没有得到满足条件的试卷，则组卷失败。 从理论上来说，回溯试探法能够遍历所有的试题组合，但是如果题库中试题数量比 较大时，对内存的占用量比较大，遍历的时间可能也会非常长，因此在实际的智能组卷 9 大连交通火学t 学硕十学位论文 中，回溯试探法的应用受到了很大的限制。针对上述方法的不足，很多研究人员对随机 组卷法和回溯试探法进行了改进，比如王萌、王晓荣等提出的一种集合随机抽选组卷算 法，即每次抽题均从满足抽取条件的试题集合中选取最优试题r 9 】；郝彦、陈丽燕等提出 的充分利用题库中试题的基本信息，通过对题量、试题历史信息以及知识点分布的调整 和控制来实现试题的智能筛选0 0 】；金汉均、郑世珏等提出的将众多试题数据进行分段处 理，在各段内随机抽取】。这些改进算法在一定程度上提高了组卷算法的效率，改善了 组卷的有效性，但它们都没从根本上改变传统组卷算法的缺陷，只是在应用于小规模试 题库时，算法的性能才有所改进，而对于大规模题库仍然缺乏智能性，难以满足实际组 卷的需要。 2 3 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是在2 0 世纪6 0 年代末7 0 年代初期由美 国密歇根( m i c h i g a n ) 大学的h o l l a n d 教授提出并发展起来的，它是一种借鉴生物界的 进化规律( 适者生存，优胜劣汰遗传机制) 演化而来的随机优化算法。遗传算法对目标 函数没有可微的要求( 即目标函数可以是离散的) ，以一个种群中所有个体为对象，利 用随机化技术指导，对一个被编码的参数空间进行高效搜索，尤其适用于处理传统搜索 方法难于解决的复杂问题和非线性问题。 2 3 1 遗传算法的发展与现状 二十世纪六十年代中期，作为遗传算法创始人之一的j o h nh o l l a n d 在a s f r a s e r 和 h j b r e m e r m a n n 等人工作的基础上，提出了位串编码技术，这种编码技术能够极大改进 原有的编码方案，既适用于交叉、变异等操作，又强调了交叉应作为主要的遗传操作， 为以后遗传算法的研究打下了良好的基础。随后，h o l l a n d 又将该方法应用于自然和人 工系统的自适应行为研究中，发现了基于适应度的人工遗传选择的基本作用，并对群体 操作进行研究，于1 9 6 5 年首次提出了人工遗传操作的重要性。1 9 7 5 年h o l l a n d 出版了 具有开创性的著作( ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) ，系统地阐述了遗传算 法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这 一理论首次确认了结构重组遗传算法对于获得隐含并行性的重要性。h o l l a n d 对遗传算 法的贡献，不仅仅在于他设计了遗传算法的模拟与操作原理，更重要的是，他运用统计 决策理论对遗传算法的搜索机理进行了理论分析，建立了著名的s c h e m a 定理和隐含并 行性原理，为遗传算法的发展奠定了基础。h o l l a n d 的学生d ej o n g 在论文a na n a l y s i s o f t h eb e h a v i o ro f ac l a s so f g e n e t i ca d a p t i v es y s t e m ) ) 中所做的研究工作可以看作是遗传 算法发展进程中的一个里程碑，他将遗传算法应用于最优化问题，在该论文中作了大量 l o 第一二章智能细卷算法 的计算实验，建立了d e j o n g 五函数测试平台，其中包括非凸函数、非连续函数、随机