（计算机应用技术专业论文）基于自适应遗传算法的智能组卷系统的研究及应用.pdf

摘要 摘要 在网络迅猛发展的今天，远程网络教育已经成为现代教育中的一个重要分支，其有着 方法新颖，时间灵活，受益面广等特点。考试，作为教育中的一个重要的组成部分，是检 验学生对知识接受程度的一个重要手段，能够使学生了解自身的优劣，有的放矢的进行学 习：同时也是学校考核教师授课质量，授课深浅程度等的一种方式。远程网络教育中，自 然也不能缺少作为教育中不可分离的重要组成部分的考试。此时，智能组卷也作为其中一 个比较最关键的问题，得到了广泛的关注。 智能组卷问题( 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 ) 实际上是一 个多目标优化问题。传统的随机选取法和回溯试探法组卷在组卷时间和组卷的成功率上， 都存在着明显的缺陷，很难得到一个较为满意的解。如何在已有研究的基础上，针对智能 组卷问题的实际特点，提出一些行之有效的算法来解决智能组卷问题，已经成为大家关注 的一个热点。许多研究表明，遗传算法对于解决智能组卷问题，具有很大的潜力。 本文针对远程网络教学中的智能组卷问题，在对标准遗传算法研究的基础上，提出一 种基于整数分段编码的自适应遗传算法的组卷策略，着重改进了遗传算法中的选择操作。 在选择操作的环节中，采用竞赛选择机制，并对竞赛选择机制根据自适应的思想进行了改 进，将原有竞赛选择机制中固定的竞赛大小，改变为可以根据算法运行程度，可以自适应 改变竞赛大小的机制，进一步提高算法的运行效率。并且根据智能组卷的实际特点，对变 异操作进行了改进，使其具有一定的导向性。 本算法应用于实际的在线考试系统，与原有算法进行比较，证明了改进算法的有效性 和优越性。 关键词：遗传算法：智能组卷；整数编码：自适应选择 人近交通人。? l ：。z 硕十学位沦文 a b s t r a c t t h er a p i dd e v e l o p m e n to fn e t w o r k ，l o n g d i s t a n c en e t w o r ke d u c a t i o ni n m o d e r n e d u c a t i o nh a sb e c o m ea ni m p o r t a n te m b r a n c h m e n tw i t hl o t so fb e n e f i t ss u c ha sn e wm e t h o d ， t i m ef l e x i b i l i t y ，a n dw i d er a n g eo ff e a t u r e s e x a m i n a t i o ni sa ni m p o r t a n tc o m p o n e n to fe d u c a t i o n a n dak e yt ot e s ts t u d e n tt h a tc a na c c e p tt h ek n o w l e d g e t e s ta l s om a k es t u d e n t su n d e r s t a n dt h e i r o w n m e r i t s ，l e a r n i n gt a r g e t ；s i m u l t a n e i t ys c h o o lc a nr e v i e wt h eq u a l i t yo ft e a c h e r st e a c h i n g ，a n d t h ed e g r e eo ft h et e a c h i n gd i f f i c u l t y i nl o n g - d i s t a n c ee d u c a t i o n , e x a m i n a t i o ni sa l s oa ni m p o r t a n t c o m p o n e n to ft h ei n d i v i s i b l ep a r to ft h ee d u c a t i o n s ot 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 ya st h ek e yi s s u e sw a sw i d e s p r e a dc o n c e r n e d 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 yi 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 n p r o b l e m t h et r a d i t i o n a lm e t h o ds u c h a 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 gi nt h e g e n e r a t i n gp a p e rh a ss o m ep r o b l e m st h a tt h et i m ei st o ol o n ga n dt h es u c c e s sr a t ei st o ol o w ， t h e r ea r eo b v i o u ss h o r t c o m i n g s i ti sd i 伍c u l tt of i n da ne f f e c t i v ea l g o r i t h m h o wt of i n dau s e f u l m e t h o dt os o l v et h ep r o b l e mt h a tc a na 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 印e r i n t e l l i g e n t l yi nt h eb a s i so f t h es t u d 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 m a n ys t u d i e s h a v es h o w nt h a tg e n e t i ca l g o r i t h mf o rs o l v i n gt h eg 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 yh a sg r e a t p o t e n t i a l t h i sp a p e ra i ma tt 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 yi nt h el o n g d i s t a n c e e d u c a t i o n ，b r i n gf o r w a r dag e n e r a t i n gt e s tp a p e rs t r a t e g yb a s e do nt h es g a a n dt h en e w s t r a t e g yi saa d v a n c ea g a w i t ht h ei n t e g e rs u b s e c t i o nc o d i n g f o c u so ni m p r o v i n gt h eg a s s e l e c t i o no p e r a t i o n i nc h o o s i n ga r e a so fo p e r a t i o n ，as e l e c t i o nc o m p e t i t i o nm e c h a n i s m ，a n d c o m p e t i t i o nu n d e ra d a p t i v es e l e c t i o nm e c h a n i s mh a sb e e ni m p r o v e d a n dw i l lc o n t e s tt h eo r i g i n a l s e l e c t i o nm e c h a n i s mi nt h er a c ef i x e ds i z e ，a n dc h a n g et h eo p e r a t i o no ft h ea l g o r i t h mc a nb e a d a p t i v et oc h a n g et h es i z eo ft h ec o m p e t i t i o ns i z e ，a n df u r t h e re n h a n c ee f f i c i e n c y o ft h e a l g o r i t h m i c a c c o r d a n c ew i t ht 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 ri n t e l l i g e n t l yt o i m p r o v et h em u t a t i o no p e r a t i o n a n dm a k ei th a v eac e r t a i nd i r e c t i o n 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 ，a n dc o m p a r ew i t ht h e o r i g i n a la l g o r i t h m s v a l i d a t et h ea l g o r i t h mi se f f e c t i v ea n ds u p e r i o r k e y w o r d s ：g e n e t i ca l g o r i t h m ；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 n t e g e r c o d i n g ； a d a p t i v es e l e c t 绪论 绪论 一、智能组卷问题 l 、智能组卷问题的提出与研究意义 在教育领域中，整个教学可以分为几个环节。考试，就是其中相当重要的一个。它可 以对学生对所学知识掌握程度的进行一种量化的评价，同时也是对教师教学效果好坏，课 程编排优劣的一个监测手段。传统的考试方式是一种主观的经验型的命题方式，一般都是 由任课教师对所教授科目进行人工命题，比较容易受到人为主观因素的干扰，没有一个总 体的规范可以遵循，形式死板。现代教育理论和信息技术的发展促进了计算机考试系统的 发展。随着计算机和i n t e r n e t 的普及，远程网络教学逐渐成为研究的焦点，作为一种新 兴的教学方式，相对于传统的教育方式，具有自主性、交互性和个性化的特点。作为一种 新兴的教育模式，就应该有与之对应的考试模式的出现，传统的人工出卷阅卷的考试形式， 已经不能适应远程网络教育的需求。这时，网上考试就应运而生。网上考试由计算机自动 组卷，不仅节省时间，而且更加具有规范性，客观性，而且网上考试的考试时间更加灵活， 学生可以根据自己的时间，在任何时问段内参加考试，可以更加全面的考察教学的实际效 果，对学生以后的学习起到一个指导性的作用。可以极大地促进教学质量的提升。 2 、网上考试国内外研究现状 在网上考试出现的初期，大部分的考试系统只是固定的一些试卷。随着计算机技术的 发展，i r t 模型出现后，逐渐的被应用于在线考试中，发展出了自适应考试机制。试题的 形式也从固定在单一试卷中的试题发展到了可以根据学生要求的难度，章节等自由组合的 自适应考试机制。随着网上考试的发展，测试的形式发生了显著的变化，在传统考试中所 有的被测试者都使用同样的试卷进行测试，而现在在同一场考试用可以使用不同的试卷进 行单独的测试，而其考察效力相同。驯 在国外，已经有很多发展到实际应用的网上考试系统。例如美国的t o e f l 、g r e 、g m a t 等考试。这些考试从丌发使用到现在，已经经历了l 一几年甚至几十年的时间，经过实践证 明能够科学的检测学生的实际水半，达到人们所期争的h 的。但是这止鬯网上考试的设计思 想、具体的细节和智能组卷等核心内容，基本都足保密的。在国内，虽然较国外的研究起 步较晚，但是也取得了一些成就，一切高校也丌发出了自己的在线考试系统，但是这些系 统都或多或少的存在一些局限性，特别是在智能组卷方面的研究还有很多不完善的地方。 从目前的在线考试的组卷方式来看，大体可以分为三种：一是虽然号称网上考试，但 是实际的考试试题仍是由教师根据实际情况进行抽取，这种i f l 瓶装新酒的方式对于实际研 究是没有任何意义的。二是将若干套试卷存入系统中，每次随机的抽取一套试卷进行测试。 其实这种方式与第一种方式实质上是一样的。三是根据考试的要求，可以自动生成考试试 卷，利用某种组卷策略，自动生成符合要求的合理的考试试卷，也就是所谓的智能组卷。 人近交通人l ：硕f ：。f 节论文 3 、智能组卷问题的主要研究方法 经过这么多年的发展，对于智能组卷问题的研究已经有了相当的成果。其中智能组卷 中一般采用的组卷方法有三种： 1 ) 随机抽取法：顾名思义，就是随机的从题库中抽取试题，然后根据试题的难度， 所属章节等属性，来判断此试题是否适合出现在试卷中。如果不适合，则重新随机抽取直 到选出一道适合的试题，依此类推组成一份符合要求的试卷。随机抽取法组卷实现起来比 较简单，但是组卷成功率低，即使组卷成功，花费的时间也让人难以忍受，特别是当题库 中各状态类型平均出题量比较低时，组卷往往失败。 2 ) 回溯试探法：就是在随机抽取的基础上，将随机抽取法产生的每个状态记录下来， 当搜索失败，遇到不可解点时，就可以回溯到路径中最近的父节点，即上一个记录的状态， 然后再根据一定的规则从另一种新的状态类型进行搜索，这样通过不断的回溯试探直到生 成试卷。这样就避免了随机抽取法中一条路走到黑的做法。该算法对于状态类型和出题量 都比较少的题库系统而言，组卷成功率较高，但是这种算法的程序结构比较复杂，而且选 取的试题缺乏随机性，组卷时间也相对较长。 3 ) 遗传算法：遗传算法是一种模拟生物界自然选择和自然遗传的随机化搜索算法， 它利用一定的编码技术和繁殖机制来处理复杂的现象，适用于处理传统搜索方法难以解决 的组合优化问题。以遗传算法的基本思想为指导，设计智能组卷算法，能够较好的解决智 能组卷中的约束优化问题，组卷成功率较高，组卷时间也较短。m 1 二、遗传算法概述 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产 生适应环境变化的优良物种。而遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是就是模拟自然 界的物种进化和自然选择机制形成的一种易于操作的并行的全局优化搜索算法。 本世纪5 0 年代初，由于一些l 二物学家尝试刚计算机模拟生物系统，从而产生了g a 的 基本思想。2 0 世纪6 0 年代美国m i c h i g a n 大学的j h 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 等人：】：作的基础上，提出了位串编码技术。这种编码技术同时适用于交叉 和变异操作，并强调将交叉作为丰要的遗传操作。随后其将该算法应用于自然和人工系统 的自适应行为研究中。发现了基于适应度的人工遗传选择的基本作用，并对群体操作进行 研究，于1 9 6 5 年首次提出了人工遗传操作的重要性。1 9 7 0 年c a v i c c h i o 把遗传算法应用于 模式识别中。第一个把遗传算法用于函数优化的是h o l l s t i e n 。1 9 7 1 年他在论文计算机控 制系统中的人工遗传自适应方法中阐述了遗传算法用于数学反馈控制的方法。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 a la n da r t i f i c i a ls y s t e m ) ) ，书中系统地阐述了遗传算法的基本理论和方法，提出模式 定理，为遗传算法奠定了数学基础。同年，d e j o n g 在其论文a na n a l y s i so 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 ) ) 中作了大帚的计算实验，建立了d o o n g 血函数测试平 绪论 台，其中包括非凸函数、非连续函数、随机函数和高维函数，把模式理论和函数优化结合 起来，并且定义了遗传算法性能评价的标准，他在论文中所做的研究工作可以看作是遗传 算法发展进程中的一个里程碑，这是因为他把h o l l a n d 的模式理论与他的计算机实验结合 起来。进入8 0 年代，遗传算法迎来兴盛发展时期，无论是理论研究还是应用研究都成了 十分热门的课题。1 9 8 3 年，g o l d b e r g 第一次把遗传算法用于实际的工程系统煤气管道 的优化，很好地解决了这一非常复杂的问题。与此同时，w e t z e l 首次应用遗传算法解决旅 行商问题。从此，遗传算法进入了蓬勃发展的时期，有关遗传算法的会议i c g a ( i n t e r n a t i o n a l c o n f e r 2 e n c eo ng e n e t i ca l g o r i t h m ) ，f o g a ( f o u n d a t i o no fg e n e t i ca l g o r i t h m ) ，p p s n ( p a r a l l e l p r o b l e ms o l v i n gf o r mn a t u r e ) 等相继召开，1 9 8 9 年，g o l d b e r g 出版了搜索、优化和机器 学习中的遗传算法一书，这本可能是遗传算法领域被引用次数最多的书为这一领域奠定 了坚实的科学基础。2 0 余年来，遗传算法的应用无论是用来解决实际问题还是建模，其范 围不断扩展，这主要依赖于遗传算法本身的逐渐成熟，其应用范围也扩展到了控制、规划、 设计、组合优化、图像处理、信号处理、机器人、人工生命等多个领域。口捌 三、本文主要工作及意义 遗传算法是模拟大自然生物进化过程的计算模型，它以其简单，鲁棒性强，全局寻找， 收敛速度快以及不受搜索空间限制性条件约束等特点而同益受到人们的关注。这些都适宜 于处理试题库组卷的问题。该算法首先生成一定规模的初始群体，然后使其中的个体以一 定的概率进行交叉与变异，实现个体结构的重组，再按预定的评价函数选择复制优秀个体， 组成新的一代，如此循环迭代，以期最终找到满足寻优条件的全局最优解。传统的遗传算 法存在搜索后期效率低和易形成未成熟收敛的情况。为此，人们尝试了许多改进方法，包 括设计不同的选择、交叉及变异算子，改变算法结构，设计自适应交叉和变异概率，将遗 传算法与其它优化智能方法相结合等。针对试题组卷的具体情况，本文提出一种用改进的 自适应遗体算法来求解试题组卷问题的方法具有较高町信度、效度的试卷。取得了良好的 效果。 本论文研究课题来源为辽宁省软件专项基会项目“嵌入式网上智能教学平台”。 本课题的主要研究任务是： 1 ) 研究竞赛选择大小对选择操作的影响： 2 ) 提出一种改进的自适应遗传算法； 3 ) 针对智能组卷问题，改进了标准遗传算法中随机变异操作； 4 ) 研究基于这种改进的自适应遗传算法对于解决智能组卷问题的有效性； 5 ) 应用于实际项目中测试； 6 ) 论证算法在理论上和实际上的萨确性和优越性。 本章小结 人迕交通人l ：。硕卜f 节论文 在本章中，主要论述了智能组卷问题的基本理论及其研究的现状、方法和策略。详细 介绍了智能组卷问题的基本理论和研究方法。同时，本章中还简单介绍了遗传算法的发展 及研究现状。最后介绍了本文主要工作及意义。 第一一章纲卷问题的理论琏础 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 世纪2 0 年代起源于s p e a r m a n 的研究工作，经过八十多年的发 展历程，经典测量理论得到了长足的发展，很多现代测量理论得到了广泛的应用。例如动 态评测理论、题目反映理论、潜在等级分析理论等。这些理论的提出和应用，提高了我国 教育水平的提高。它是由基本假设、信度、效度、标准化等基本概念构成。基本假设是经 典测量理论基础。射长期以来，它被题库系统建设所采用，提供试卷分析和成绩分析的 依据。它是建立在三条假设的基础之上的。 1 ) 对某个学生进行测验所得分数x 可以看成是代表该生实际知识水平的真实分数 x ，和测验误差x 。的线性组合，即x = z + x 。 2 ) 误差分数的数学期望为零，因而真实分数可以用一个在大量测验中所得的分数的统 计平均值来表示。 3 ) 任意两次测验所得的误差相对独立。 经典测量理论也被成为真分数理论，真分数理论是每个个体都有某些无法直接观察的 心理变量，它们被称为“真分数”( t ) ，我们可以用实际得到的、具有一定测量误差( e ) 的“观察分数”( 或称“j 下确应答分数”) ( x ) 作为真分数的估计值。所以经典测量理 论是估计测验中实得分数与真分数之间的关系程度。所谓真分数，其数学上的定义为：测 量上被测试的真分数是观测分数的期望值，即t = s x 。上式中，x 为实际得分，f 代表期 望值，t 为被测试的真分数。但是仅仅根据这个公式足不能直接测量得到真分数的，所以， 可以将t 解释为被试在无数多次独立重复测量上获得的平均观测分数。其数学模型为：观 察分数真分数+ 误差，即x = t + e 。这是一个线性模型，表示在观察分数和真分数之i 日j 存在 着线性关系。 经典的测量理论建立了一系列的对试题进行分析的方法，由于其计算公式简明易懂， 而广泛的应用于教育测试。经过实际的应用发现，其具有如下几个优点： 1 ) 从实际应用上来说，假设条件容易满足，具有广泛性。 2 ) 经过几十年的发展，经典测量理论有着较为完善的理论基础和对测验进行统计分析的 方法，而这些方法又相对比较简单易懂，较为容易被使用者所掌握，更促进了他被普 人选交通人i ：。硕f - ”t il 论文 遍的应用。 3 ) 在实际应用经典测量理论的实践中，大家已经慢慢积累和完善了一些更为适合自身的 方法和应用原则。暖1 传统的考试就是以经典测量理论为指导，教师根据教学大纲要求，制定试卷的结构及 考试内容、试卷难度( 反映在考试平均分上) 等，并据此组织试题对学生进行考试。对于 学生来说，试卷中的题目，只有一部分才是符合自己真实能力的，其余试题要么难度太大、 要么太过于简单，因而考生的分数与试卷题目难度等有着密切关系，也就是说受测试样本 的影响比较大。 建立在经典测量理论上的测试是常模参照测试，测试对象是某一群体，利用常模参照 测验来衡量考生相对水平，某一学生学习成绩的好坏，是根据该生的成绩在规定群体中所 处的位置来判断的。常模参照测验中的试题必须能很好地区分学生不同学习水平，因此， 对于经典测量理论来说，测试样本的选择很重要，必须选择难度适中、区分度好的试题， 才能有效地区分考生的学习水平。 1 1 2 经典测量理论的不足 经典测量理论虽然有了较长的历史并取得了相当的成果，但是因为其自身的局限性还 存在着许多无法克服的问题： 1 ) 项目统计量( 项目难度和项目区分度) 依赖于测验所实施的考生样组。如果相同 的测试项目用来测试不同组的考生中时，所得到的结果是不一样的。比如测验项 目难度时，能力较高的组得到的项目难度就相对较低，而能力较低的组得到的项 目难度就较高。这样所得到的结果的置信度不高，用途相对要有限的多。 2 ) 考生的测试分数依赖于所测试项目的难度。考生所得到的分数除了跟自身的能力 有关之外，还依赖于被测试项目的难度，被测试项目难度越高，得分就越低，反 之办然。这样，就不能根据经典测量理论来比较不同能力组别的考乍的能力水平 的差异。 3 ) 信度作为经典测量理论的一个基本的概念，也导致了经典测量理论的第三个缺点。 信度的概念是根据平行测验定义的。而所谓的平行测验在实践中足很难实现的。 即使使用相同的项目对同一组考生进行测试，也不能达到完全平行的程度。所以 由此进行的各种测试的结果就不会非常精确。 4 ) 经典测量理论不能提供不同能力组别的考生对项目信息做出的反应。但是在现实 中需要对考生答对的项目的概率进行估计。 5 ) 经典测量理论对所有考生测量所产生的误差都假设是相等的，但是事实上这个是 难以满足的。旧卅 综卜所述，经典测肇理论的缺点涉及到该理论的各个摹本概念之问的相可依赖，相互 制约。测景专家认为，经典测量理论中最基本的四个概念是项目难度、项r j 区分度、信度 6 第一章组卷问题的理论荩础 和币确应答测试分数。项目难度和项目区分度、信度都依赖于考生组的能力水平分布，即 正确应答测试分数；而考生的正确应答测验分数又依赖于项目信度，这种基本概念之间的 相互依赖、互为前提，不可避免的为该理论带来许多难以克服的困难。这些不足都是经典 测量理论难以解决的问题，所以测量学家开始转向探索新的理论体系。 1 2 项目反映理论 1 2 1 项目反映理论的产生与发展 任何一种测试理论都着眼于考生预测之间的相互关系，都试图从可以观察到的考生的 测试分数去推测其潜在的心理特质。经典测量理论中运用的是线性模型，而近年来测量学 家的注意力已转向非线性模型，于是产生了项目反映理论。旧1 项目反映理论( i t e mr e s p o n s et h e o r y ，简称i r t ) 一种基于非线性概率模型的能力 测量理论，能够对被试者能力进行正确的评估。最初的项目反映理论的提出可以追溯到2 0 世纪三四十年代。1 9 3 6 年，理查森推导出了项目反映模型参数和经典测试理论中项目统计 量之间的关系，并首次提出了i r t 的参数估计方法。1 9 4 3 年，劳勒提出了一系列关于i r t 领域中基本的理论问题。1 9 4 4 年，格特曼提出了“无误差模型 ，这是一种确定性模型， 也称为理想量表项目。1 9 5 0 年，拉扎斯菲尔德经过大量研究，首次提出了“潜在特质”这 一术语，以及“潜在结构分析”方法，这是关于i r t 的先驱性工作之一，运用该方法可以 将个体进行合理的分组。但是其发展和兴起则出现在2 0 世纪五十年代，1 9 5 2 年，f m 罗 德在其博士论文关于测验分数的一个理论中，第一次对项目反应理论作了系统的阐述， 标志着项目反映理论的诞生。1 9 6 5 年洛德通过大规模的调查研究，证实了他所提出的项目 反应理论的假设与现实生活中的测验问题相符，由此而引发项目反应理论的研究和应用。 与此同时，月麦数学家g 。拉彻于1 9 6 0 年独立地提出了含有一个参数的“样本无关”的心 理测验模型，这就是以后项目反应理论中重要的单参数模型。此后，项目反映理论进入了 高速发展的时期。在七十到八十年代，众多的关于项目反映理论的研究相继发表。例如， 洛德项f j 反j 逦理论在实际测验问题中的应用( 1 9 8 0 年版) ，c l 赫林、f 德雷斯哥和 c k 帕森斯项日反应理在心理测量中的应用( 1 9 8 3 年版) ，r 汉如尔顿和h 斯 沃米纳摩项目反应理论：原理和应用( 1 9 8 5 年版) ：美国教育测杂志( j e m ) 于 1 9 7 7 年秋夏季号刊登了“潜在特质理论应用”专辑，共有六篇研究报告，美国应用心理 测量杂志于1 9 8 2 年秋季号发表了“项目反应理论和应用中的进展”专辑。这些研究成 功的实现了在项目反映理论中的参数估计，为项目反映理论在实践中的应用扫清了障碍。 目前，项日反应理论已经在欧美等发达国家中得到了发展和应用，应用领域涉及教育、军 事、工业等部门。近年来，项目反映理论也得到了国内学者的重视，在理论研究的同时， 也逐渐的丌始尝试实践应用。陆刀 1 2 2 项目反映理论的特点 7 人迕交通人，i ：学硕1 ：了：位论文 i r t 是教育和心理测量学中心的理论体系，在提出这一理论时，首先是考虑至l j 了广大 测验使用者在实践中提出的要求，可以概括为以下五条： 1 ) 项目统计量不依赖于特定的考生样组。 2 ) 考生的测试分数和测试难度无关。 3 ) 能够根据该测验理论选择和考生能力相匹配的测验项目。 4 ) 不要求测量误差及其方差对于所有的考生都相等。 5 ) 不要求通过严格的平行的测验来评价测量的精确度。 显然，经典测量理论是不能达到这些要求的，迄今为止能够满足这五条要求的也只有 项目反映理论。闺 1 2 3 项目反映理论的基本思想和优点 项目反映理论的基本思想是确定考生的心理特质值和他们对于项目的反应之间的关 系。这种关系的数学形式就是“项目反映模型 。但是这种模型并不是理想的表项，而是 概率型的模型，其原因是考生对于测验项目的反应除受到某种特定能力的支配，还受到许 多随机因素的影响，如焦虑、动机、考试技能的因素的影响。所以确切地讲，项目反映模 型表示的是考生能力和考生对测试项目j 下确概率之间的数学形式。从这个意义上说，项目 反映理论就是数学模型的建立和对模型中各个参数的估计。 项目反映理论非但认为考生的潜在特质和正确概率之间的关系可以用某个数学模型 表示，而且假设该模型可以用单调地增函数表示，该函数被称为项目特征函数，其图像就 是项目特征曲线。 由于项目反映理论中有多种模型可以选择，因此在对具体的测验数据进行分析时，首 先就应该检验它是否符合某个特定的数学模型，这就是模型与数据拟合度的检验问题，如 果所选取的模型能够和测验数扼拟合较好的话，那么项目反映理论的优点就可以充分的现 实出来，这些优点主要有： 1 ) 考生能力的估计值和所测试的项目无关。如果有一个很大的题库，他们都符合项 f 1 反映模型，其项目参数都是已知的，并且都是测量同一心理特质，那么对于考 生能力的估计值是和所测试的项目无关的。 2 ) 项目参数的估计值和考生样组无关。这意味着如果拿同一批项目对同一全域中的 不同考生样组进行测试，其项目分析的结果是一样的，这一性质称为项目参数不 变性，这种不变性为题库建设等许多方便提供了极大的便利。而这在经典测鼍理 论中实现是不可思议的事情。 3 ) 可以提供考生能力估计值的精确度指标，而且在测验实施前就町以知道各个测验 项目对于不同能力考生的估计精确度，这对于测验编制者是尤为重要的。 4 ) 在i r t 中，考生能力和项目难度是在同一量表上的，这就为测验的编制、测验分 数的报告和解释提供了便利。 r 第一章组卷n q 题的理论基础 这些特点能够满足广大测验使用者的要求，也正是由于这些优点，才是项目反映理论 成为当前教育和心理测量学中的前沿理论，并吸引了大量的测量专家和测试使用者。同时， 对于自适应考试，项目反应理论也更加适合。所以本文中的智能组卷问题，就是基于项目 反映理论进行设计和实现的。 1 2 4 项目反映理论的基本假设 任何一个数学模型都有一定的前提，任何一种测量理论都要有一定的假设，在项目反 映理论中也有如下几个最基本的假设： 1 ) 一维性假设：被测试的结果只取决于一种能力，而其他能力对测试结果的影响忽 略不计。绝大多数项目反映模型都是基于这个假设之上的，但是这个假设也使项 目反映理论受到一些批评，因为在实际中，这种假设是较难实现的。 2 ) 项目特征曲线假设：主要是指被试目标对测试所做出的反应遵循一定的函数关系。 而使用项目特征曲线可以将这种函数关系描述出来。 3 ) 局部独立性假设：考生对于试卷中的某个题目的反应是独立的，不会因为此题目 影响其他的题目，也不会因为其他题目而影响到此题目。同时，有关信息只在试 卷中出现一次，任何一道试题的内容都不会对其他题目有提示作用。 4 ) 非限时性假设：即要求测验是在不限时的条件下进行的。此假设可以保证测试结 果不受快速反应能力等其他条件的制约。 1 3 组卷问题的其它相关理论 测量是指人们对事物进行区分的过程。严格地讲，是指按照一定的法则，用数学的方 法对事物的属性进行描写的过程。任何一种测量都要定义单位、确定参照点和使用体现单 位、参照点的测量工具，这是测量的三要素。 要有单位、参照点和测量工具的测量三要素。 教育测量作为一种特殊的测量，毫不例外地 ，i ： 1 ) 单位：单位是计算数量的名称。没有单位，则数量的多少和大小就无法表示。任 何测昔都离不丌计量单位。教育测量也是如此。目自仃，教育测量最常用的单位是 百分单化和等级单位。百分单位就足规定。项测验的满分为1 0 0 乡j - ，把满分的1 1 0 0 作为一个计量单位。等级单位是根据一项测验结果的上限和下限，把结果分成若 干个等级，每一个等级作为一个计量单位。 2 ) 参照点：所谓参照点是指计量的起点，也称为零点。有了参照点，就可以比较两 个测量结果的异同。否则，测量的结果就无法进行比较。根据测量理论，参照点 可分成两类：类是绝对参照点：另一类是人为参照点。绝对参照点足符合实际意 义的参照点，除了绝对参照点之外，其余的参照点全部是人为参照点。教育测量 中的参照点，除了某些教育测量之外，其余测量的参照点，全部是人为参照点。 例如，在百分单位的测量中，习惯将6 0 分作为及格的参照点。 9 人迓交通人j ：。硕f ：学f 节论文 3 ) 测量工具：教育测量测量的是人的知识水平、智力水平、社会适应能力等，这些 特征不象物体的物理属性那样明确，因而无法对它进行直接测量，只能通过人的 外显行为反应的取样分析加以推断。在教育测量学中，考试是体现单位和参照点 的教育测量工具，我们可以通过学生对测验题日做出反应的数据进行统计分析， 即可对学生的知识能力水平等情况进行间接测量。 本章小结 本章介绍了经典测量理论和项目反映理论等组卷相关的理论知识的原理，特点，有缺 点等，同时，针对本文的需要，对项目反映理论做了较为详尽的描述。 1 0 第一：章遗传算法与白适戍| 遗传算法 第二章遗传算法与自适应遗传算法 2 1 遗传算法 生物进化理论表明，复杂结构的生命是在相对短的时间内进化而来的，这种机制目前 尚未完全弄清楚，但某些特征已为人们所掌握。大多数生物的进化是通过有性繁殖和自然 选择这两种基本过程进行的。有性繁殖完成了对后代基因的重组，重组的结果产生了群体 中对自然环境具有不同适应能力的个体，自然选择的机制决定了那些适应性较强的个体可 以存活下去，而较弱的将要被淘汰。自然选择的原则是适者生存。 进化计算方法就是基于上述思想发展起来的一类随机搜索技术，它们模拟了群体的进 化过程。其中每个个体表示给定问题搜索空间的一点，进化算法从任一初始的群体出发， 通过随机选择、变异和重组过程，使群体进化到搜索空间中越来越理想的区域。h 们选择过 程使群体中适应性强的个体比适应性弱的个体有更多的复制机会，交叉算子将父辈信息结 合在一起传给子代个体，变异使群体中产生新的变种。 进化计算方法有很多种，目前比较有代表性的典型算法有三种：遗传算法、进化策略 和进化规划。这三种方法是彼此独立发展起来的，有许多不同之处。但总的来说，它们都 有两大特点：群体搜索策略和群体中的个体之间的信息交换。这种显著特点，使算法不易 陷入局部极值；同时，算法由于不苛求于待求问题的具体表达形式及数学特性( 如：连续、 可微等) ，因而具有较强的鲁棒性和普适性，有广泛的应用价值。 2 1 1 遗传算法的发展与现状 遗传算法( g e n e t i ca l g o r it h m ，g a ) 作为进化计算中应用最广的一种算法，是一种宏 观意义下的模拟自然界生物进化过程与求解机制的一种仿生算法，是一种自组织、自适应 人工智能技术。其以达尔文的“优胜劣汰、适者生存”的进化规则为原理，通过模仿孟德 尔的遗传变异理论，形成了一种新的全局优化搜索算法，其具有简单通用、鲁棒性强、应 用范围广并且使用并行处理等显著的特点。心刀 早在2 0 世纪五十年代剑六十年代，就有少数几个计算机学者j l ：始研究所谓的“人工 进化系统”，其基本思想是应用进化的思想，解决工程问题。这个研究形成了遗传算法研 究的早期雏形，其中大多数系统都是根据达尔文的“适者生存”法则进行模仿自然进化法 则，有些系统还采用了种群的设计方案，并且采用二进制编码、自然选择、变异等进化操 作。六十年代初期，柏林工业大学的i r e c h e n b e r g 和h p s c h w e g e l 在进行风洞试验时， 山于传统的优化方法难以对设计中描述物体形状的参数进行优化，进而采用了生物进化的 思想进行优化，取得了较好的效果，并以此为基础，形成了进化算法中的一个分支一进化 策略( e s ) 。同时另外一些学者在设计有限自动机( f s m ) 时提出了进化规则( e p ) ，并 将此方法应用于模式识别、数据诊断等问题中，取得了较好的成果。但是由于缺乏一种 人迕交通人学l ：学硕f j 学f 节论文 通用的编码方案，所以早期的研究进展不大。 二十世纪六十年代中期，作为遗传算法创始人之一的j o h nh o l l a n d 在前人的基础上， 提出了位串编码技术，这种编码技术能够极大了改进了原有的编码方案，既适用于变异、 交叉等操作，又强调了交叉作为主要的遗传操作，为以后遗传算法的研究打下了良好的基 础。 随后，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 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 ll a n d 学生d ej o n g 将遗传 算法应用于最优化问题。而g r e f e n s t e t t e 开发了第一个遗传算法软件- - - g r e n e s i s ，为遗 传算法的普及和推广起了重要作用。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 对遗传算法的研究产生 了很大的影响，此书对遗传算法理论及其多领域的应用作了全面的分析和例证。1 9 9 2 年， m i c h a l e w i c z 发表了另外一本对遗传算法有着重要影响的著作“g e n e t i ca l g o r i t h m s + d a t a s t r u c t u r e s = e v o l u t i o np r o g r a m s ”，阐述了遗传算法在最优化问题上的应用。 2 0 多年来，随着遗传算法的r 渐成熟，其应用范围不断扩展。但是，近年来的许多遗 传算法的研究与h o ll a n d 最初提出的遗传算法的思路有了很大不同，不同的基因表达方式， 不同的交叉和变异算子。但是其基础，仍旧是基于自然界的生物进化。遗传算法的研究热 潮的兴起，已经在机器学习、过程控制、经济预测、工程优化等领域取得了成功，引起了 数学、物理学、化学、! 卜物学、计算机科学、社会科学、经济学以及工程应用的领域专家 的极大兴趣。2 0 世纪9 0 年代以后，人们较为重视遗传算法的一些基本问题，d ej o n g 称 为“重访基本的假设”，这方面的研究内容主要有： ( 1 ) 标识和形念发，匕学： ( 2 ) 意马克算子等的引入； ( 3 ) 非随机配对和物种形成； ( 4 ) 分散的高度并行的模型； ( 5 ) 自适戍系统： ( 6 ) 共同进化系统。 由于遗传算法在求解有效性、现有方针环境下易于实现、可扩充性和易于与其他方法 相结合的特点，随着理论研究的不断深入和应用领域的不断推广，遗传算法将会取得长足 的发展。 第二章遗传算法与白适应遗传算法 2 1 2 遗传算法的基本思想 既然遗传算法是基于达尔文的“优胜劣汰，适者生存的自然选择机制，那么我们就 有必要了解下这个自然选择机制的具体内容。总体上说，其主要内容有四点：过度繁殖， 生存斗争( 也叫生存竞争) ，遗传和变异，适者生存。 1 )过度繁殖：达尔文发现，地球上的各种生物普遍具有很强的繁殖能力，都有依照 几何比率增长的倾向。按照其增长速度来说，在一定时间内，就可以产生大量的 后代，占满整个地球。但是实际上几万年来，没有任何一个物种能达到理论上的 数量。各种生物的数量在一定的时期内都保持相对的稳定状态。 2 ) 生存斗争：生物都具有很强的繁殖能力，但实际上，每种生物的后代能够