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

东北失学硕士学位论文 摘要 基于改进遗传算法的智能组卷系统应用研究 摘要 随着计算机技术及人工智能的迅速发展，智能组卷系统的研究逐渐被越来越多的专 家学者所重视。由于影响组卷效率和质量的核心因素是组卷算法的设计，因此设计一种 行之有效的算法使生成的试卷能够最大程度满足用户需要是本文的研究目的。在对国内 外大量相关文献的分析研究基础上，本文提出了一种基于遗传算法基本原理的组卷方法 并针对传统遗传算法在全局寻优中容易出现的早熟及收敛速度馒的问题进行了改进。实 验结果表明：改进后的算法明显改善了全局寻优能力并具有较高的鲁棒性。 本文主要工作包括：依据教育测量理论分析了试卷的评价指标，建立了规范的组卷 指标体系。在对经典遗传算法的研究基础上设计了合理的算法编码方案、遗传算子及适 应度函数。其中，染色体编码方案采用实数分组编码；选择算子采用随机遍历抽样算法； 交叉、变异过程采用随演化进程不断调整的函数进行自适应遗传控制；为控制算法未成 熟收敛现象的产生，对原始适应度函数运用指数比例变换方法进行了适当调整。最后将 改进后的组卷算法应用到了实际题库系统中。 关键词：遗传算法；题库系统；智能组卷；测量理论 一i i 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho nt h ea p p l i c a t i o no fi n t e l l i g e n tt e s tp a p e rg e n e r a t i o n s y s t e mb a s e do i li m p r o v e dg e n e t i ca l g o r i t h m a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n da r t i f i c i a li n t e l l i g e n c e ，t h e r e s e a r c ho fi n t e l l i g e n tt e s tp a p e rg e n e r a t i o ns y s t e mh a sb e c o m em o r ea n dm o r es i g n i f i c a n tt o e x p e r t sa n ds c h o l a r s b e c a u s et h eg e n e r a t i o na l g o r i t h m i st h ek e yf a c t o ri nt e s tp a p e r g e n e r a t i o ne f f i c i e n c ya n dq u a l i t y , t h ep u r p o s eo ft h i sr e s e a r c hi s t od e s i g na ne f f e c t i v e a l g o r i t h mi no r d e rt om a k et h et e s tp a p e rg e n e r a t e db yt h es y s t e mf i tt h en e e d sf u r t h e s t a f t e r s t u d y i n ga n da n a l y z i n gm a n yd o m e s t i ca n do v e r s e a sa c a d e m i cp a p e r s ，an e wt e s tp a p e r g e n e r a t i o na l g o r i t h mb a s e do ng e n e t i ca l g o d t h mi sb r o u g h tf o r w a r da n dt h ei m p r o v e m e n t s a i m i n ga tt h ep r o b l e m so ft h ep r e m a t u r i t ya n dt h el o ws p e e do fc o n v e r g e n c ei nc l a s s i c a l g e n e t i ca l g o r i t h ma r em a d e t h et e s tr e s u l t ss h o wt h a tt h ea l g o r i t h mc a ni m p r o v et h eg l o b a l o p t i m i z a t i o na b i l i t ya n dt h ec o n v e r g e n c es p e e d 、“t l lah i g hm b u s t o e s s t h em a i nw o r ko ft h i sr e s e a r c hi n c l u d e s ：a n a l y z et h et e s t p a p e re v a l u a t i o nt a r g e t s a c c o r d i n gt ot h ee d u c a t i o nt e s tt h e o r ya n d e s t a b l i s hs t a n d a r d i z e dt e s tp a p e rg e n e r a t i o nt a r g e t s y s t e m , d e s i g nr e a s o n a b l ec o d i n gm e t h o d ，a r i t h m e t i co p e r a t o r sa n df i t n e s sf u n c t i o n t h er e a l n u m b e rg r o u p i n g c o d i n gm e t h o di sa d o p t e dt ob et h ec h r o m o s o m ec o d i n gm e t h o d t h e r a n d o ms a m p l ea l g o r i t h mi sa d o p t e dt ob et h es e l e c t i o no p e r a t o r t h ef u n c t i o nw h i c hc a n a d j u s tw i t l lt h ee v o l v e m e n tp r o c e s si sa d o p t e di nt h ec r o s s o v f ra n dm u t a t i o no p e r a t i o nt o m a k ea d a p t i v ei n h e r i t a n c ec o n t r 0 1 t h eo r i g i n a lf i t n e s sf u n c t i o ni sa d j u s t e du s i n ge x p o n e n t s c a l et r a n s f o r mm e t h o di no r d e rt oc o n t r o lt h ep r e m a t u r i t yp h e n o m e n o no ft h ea l g o r i t h m a t l a s t ，t h i si m p r o v e da l g o r i t h mi si m p l e m e n t e di n t op r a c t i c a li t e mb a n ks y s t e m 。 k e yw o r d s ：g e n e t i ca l g o r i t h m ；i t e mb a n ks y s t e m ；i n t e l l i g e n tt e s tp a p e rg e n e r a t i o n ；t e s tt h e o r y i i i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： 乒i 矽矽 签字日期：加7 ， 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不 学位论文作者签名：蕾c 澎乡导师签名： 签字日期：铆7 i7签字日期： 铆7 f 夕 东北大学硕士学位论文 第一章绪论 第一章绪论帚一早三石t 匕 1 1 研究背景及意义 在现代教育领域中，计算机技术正逐渐成为强有力的教学媒体和教育管理的有力工 具。计算机在现代教育领域的成功引入，使得教学手段、教学方法、教材观念与形式、课 堂教学结构以至教学思想与教学理论都发生了变革，从而逐渐形成了一门全新的、综合的、 把教育学理论知识与计算机科学技术相结合的崭新的研究领域一一计算机辅助教育 ( c b e ) 【1 1 。计算机辅助教育理论涉及教育学、心理学、哲学、传播学、学习理论、信息论、 控制论、系统论、计算机科学、数学等多个学科。 c b e ( c o m p u t e r - b a s e de d u c a t i o n ) 包括了两个重要的分支领域：计算机辅助教学( c a t ) 和计算机管理教学( c m i ) 。 c a i ( c o m p u t e r - a s s i s t e di n s t r u c t i o n ) 是指使用计算机辅助或代替教师执行部分教学任 务，向学生传授知识并提供技能训练，直接为学生服务。c m l ( c o m p u t e r - m a n a g e di n s t r u c t i o n ) 是利用计算机来实施教育管理功能，帮助教师及教育管理人员监测、评价和控制调节教学 和教育管理过程，提供教育决策，实施学校及整个教育系统现代化的一种新型管理手段。 它包括课堂信息处理、计算机辅助测验( c a t ) 、计算机辅助教务管理、计算机辅助教育行 政管理、图书资料管理和现代远程教育管理。 c a t ( c o m p u t e r - a s s i s t e dt e s t i n g ) 系统可以帮助教师或教学管理人员进行测验设计与 生成考卷，可以在一定条件下实施测验，也可以进行测验分析、管理成绩与提供报告。 它既能帮助完成测试过程涉及的全部工作，也可以只承担测验过程中某一阶段的工作， 如只进行测验编制的c a t 系统，只能完成评阅分析的c a t 系统等。c a t 系统能够完成 测验过程中的各项工作的关键是以大量的测验试题为基础。这些题目都是按各种测试题 目精心筛选的，并被赋予一定的属性( 如题型、难度、区分度等) ，同时以某种形式结 构组织起来存放于计算机中，构成计算机化试题数据库。利用这样的题库，c a t 系统才 能自动生成各种有效的考卷，用于各种目的的测试。因此，挑选大量题目，有效地组织 题目，建立起能够满足教学评价和学习诊断等需要的试题库是设计开发有效c a t 系统 的首要工作。 完整的c a t 系统应该包括四个功能模块：测验构成模块、测验实施模块、评阅与 分析模块和题库管理模块。如下图所示的是完整的c a t 系统的功能模块结构1 2 】。 东北大学硕士学位论文 第一章绪论 图1 1c a t 系统功能模块结构 f i g1 1 f u n c t i o nm o d u l ef r a m e w o r ko f c a ts y s t e m ( 1 ) 测验构成 测验构成模块的功能是按照测验目的和有关组卷的具体要求在题库中挑选题目，然 后组成一份或几份等价的试卷并根据需要进行试卷打印。 对于组卷的具体要求一般由教师根据测验的目的来拟订，通常涉及如下内容：题目 内容的范围、题目的类型和题目的数量。在系统功能较强时，还要给出题目的某些具体 属性，如难度属性、区分度属性等。这些内容将以参数的形式送入系统作为测验构成的 组卷依据。 ( 2 ) 测验实施 测验实施模块的功能是根据测验要求将试卷保存在计算机内，并向终端发送测验题 目，接受考生在终端上的回答，同时给以评分和打分。这实际上是一种联机测验形式， 这种测验方式有很多优点：首先，同一试卷可以不同的题序呈现给不同的学生，有利于 防止抄袭和学生间互相干扰，提高测试的可靠性：其次，在具有内部时钟的系统中，能 够确定学生对各题具体作答时间的长短，这样也可以确定对同一测验，不同的学生在相 同的时间里所作答题的数目，这有利于分析学生的学习情况；另外，在测验过程中，学 生能及时得到反馈，且能在测验结束时即得到测验结果，这既有利于学生的学习，又省 去了教师评阅试卷的工作；最后，这种测验不受考试场地和时间的限制，特别适合学生 自测验。 应当说明的是，测验实施模块作为一个独立的系统时，必须包括测验构成和题库， 只是题库中的题目可以少一些。这种独立系统适用于课程的单元测试。 ( 3 ) 评阅与分析 评阅与分析模块的功能包括两个方面：进行阅卷评分，统计成绩报告结果；进行学 生情况、试题和试卷情况分析，并保存被试信息及分析结果，为教学活动的评价、题库 管理和测验试卷生成的改进提供依据。 一2 一 东北大学硕士学位论文第一章绪论 在联机测验中，计算机自动对学生的回答进行评判，根据正确与否给予计分，同时 对每个学生测验的评阅结果作记录保存( 一般包括题号、正误情况、回答等待时间等) ， 以便进行测验分析。对非联机测验( 也称脱机测验) 情况，学生用笔在答题纸上作答( 即 在相应的选择位置上用铅笔做出选中标记) ，c a t 系统用光学标记阅读器阅读答题纸上 所作标记，转化为学生对试卷各题的回答信息，并与测验卷的标准答案对比，从而给各 学生打分。学生的测验情况被保留，以便用于各种分析。 分析包括对学生学习情况分析、试题分析和试卷分析。一个功能较强的c a t 系统 应该能够进行以下方面的分析。 学生情况分析：是指利用评阅所获得的信息进行分析，以评价学生的学习状态和能 力等。由阅卷得到的学生答对题数，并根据需要转换成成绩，如百分制计分、标准分或 班级加权分等，以进行基本统计分析；如班级平均分、最高( 低) 分以及均方和标准差 等。这些统计值从各个方面反映了班级总体的教学情况，可成为教学评价的参考依据。 试题分析：这项分析的目的是考察一次测验中所采用的各道试题对达到测验目的是 否有效。以评价教学和诊断学习为目的的测验，题目应能区分出学生学习的优与差，应 能评定教学过程的成功与失败。 试卷分析：当测验的目的是对学生进行等级划分、判断学生的水平与能力时，我们 总希望所进行的测验是公平、准确的。按照教育评价的要求，测验应该具有两个必须的 特点：可据性( 效度) 与可靠性( 信度) 。试卷分析就是对试卷的信度和效度的分析。 试卷分析的结果能够反映出测验是否真正检查出学生的知识水平与能力，是否真正检查 出教学过程的成功与否。也就是说据此可以判定测验的结果是否能作为评价的依据【3 】。 ( 4 ) 题库管理 题库管理模块的功能主要是输入试题并按所设计的结构保存题目及其所有相关信 息而建立起题库以及对题目库进行增加，删除、更新及其参数修改等处理。 题库是c a t 系统的基础。一个大的测验系统应能容纳足够数量的题目，这些题目 在题库中组织、分类及其特征信息的确立与描述将直接影响系统的工作效率与效果。 从以上对c a t 系统各模块功能的分析中可以看到，测验构成模块中的自动组卷功 能是一个评价考试测评系统质量好坏的最重要的因素，而如何保证生成的试卷能最大程 度地满足用户的不同需要，并具有随机性、科学性、合理性，是实现中的一个难点。尤 其在交互式环境下用户对于组卷速度要求较高，题目应具有多样性、不宜作弊等特点。 因此，一个良好的组卷系统对于教与学来说均起着非常重要的作用，应具有良好的全局 一3 一 东北大学硕士学位论文第一章绪论 寻优能力和快速收敛性能。 考试是一项“测量工程1 4 1 ”。从统计学的角度来看，考试是一种抽样测量，通常所说 的应考范围是考查的总体，而实际考查内容则是从总体中抽取的样本。要提高考试质量， 在实施考试之前，先要进行设计。实施一次考试命题，不论主观上的认识如何，都在进 行着不同形式、不同水平的设计，差别是有的设计是不自觉的模糊的，有的设计则是有 意识的、较周密的。命题是考试设计的核心。提高考试的科学化程度，最重要的是：加 强考试的设计工作，提高考试设计的科学程度；把数理统计的方法引入考试工作，对试卷 的编制和考试的质量进行定量分析。 测验是整个教学过程的重要环节，它既是对学生知识水平及能力的一种评价，也是 衡量教学效果的一种测量手段。目前许多考试的实施过程并不完全科学，考试手段落后， 命题内容、评分标准等由于受各种人为因素的干扰而使得考试信度和效度较低。利用计 算机建立试题库，实现计算机自动选题组卷，是c a t 工程的重要组成部分，是实现考 试规范化、科学化的重要措施，更是实现教考分离的一个重要手段。 1 2 计算机组卷技术研究现状 1 2 1 国内外发展概况 近年来关于题库的研究越来越深入。“通用题库系统”成为c b e 研究的重要内容之 一。在题库的建造、结构设计、存储的压缩以及题库建造工具等方面，从理论到实践都 取得了良好的研究结果。在国外已经建立起了一些针对标准化考试的试题库系统。例如： 美国的t o e f l ，g r e ，g m a t 等计算机试题库系统都能科学地测试出学生的实际水平并 有效防止试题外露。这表明利用计算机来成卷是可能的而且是有效的，但是，这些系统 涉及到的具体内容与细节，以及其设计思想与原理几乎都是保密的，要建立一套适合中 国国情的试题库就只能靠自己的努力。 在国内，已有一些适合我国特点的题库系统开发成功并获得了广泛的应用。例如， 杭州电子工业学院开发的大学英语题库系统现己拥有全国2 7 个省、市近3 0 0 家用户( 其 中高校用户已超过2 3 0 家) 。一些支持题库建立的通用性工具正在被开发，有的已获得 成功，如北京师范大学现代教育技术研究所开发的支持“支持学科题库建立的计算机系 统”( 早已通过部级技术鉴定) 。可以说题库系统的开发和应用已成为c a t 研究的主要 方面。但是，目前部分高校联合开发的一些基础学科的题库系统，就其使用范围而言， 这些系统大多是某一学科的“专用试题库”，而且有很强的封闭性，不能根据自己学科 - - 4 东北大学硕士学位论文 第一章绪论 的实际情况进行调整，缺乏可扩充性和灵活性。这样，同一所学校要实现所有学科的计 算机命题试卷，就必须为每一学科都开发或购置一套相应的题库系统，这就必将导致大 量的重复性劳动、浪费大量的资金。这种系统在一定程度上给人们的使用带来不便，也 阻碍了系统的推广，显然这样的题库系统是不完善的。 从组卷方面看，现有的题库系统大体分三种：一种是将题库看作试题集，命题时由 具有丰富经验的教师逐题抽取。二是将题库看作试卷集，将己出好的试卷存储起来，在 组卷时任意抽取一份。三是有自动形成试卷的功能，利用某种组卷策略，自动形成合理 的试卷。前两种虽能保证试卷质量，但第一种与人工命题无异，第二种只能出有限份试 卷，第三种则是随机出题，又有组卷策略可遵循，会形成千变万化的试卷，但所使用的 组卷技术和策略有优有劣。 在系统分析方面，现有的题库系统大多只统计学生的考试结果，而没有对试题和试 卷的评估，甚至有的系统连这一功能也并不具备。 因此，为更好地普及计算机命题组卷技术，有必要研制一个通用的采用先进组卷算 法的题库组卷系统。为此，本文着重对组卷算法进行研究，通过建立数学模型，结合遗 传算法理论，探讨一种更加合适的算法来解决题库系统中自动命题组卷的问题，同时在 此基础上生成一个面向多学科的试题管理与智能组卷系统。 1 2 2 通用题库组卷系统可行性分析 从目前己经运行的组卷系统来看，虽然各有差异，但其中的共性是主要的。虽然不 同学科的有些试题特征指标的命名不同，但其内涵是一样的；虽然不同学科的试题特征 指标的个数不同，但根据考试学理论的要求，有部分指标是必须的；从试卷的总体来看， 关于试卷的质量评价有极大的共性。根据考试学理论，一份试卷质量的好坏与下列几个 方面有关： ( 1 ) 组成试卷的各个试题是否科学、合理； ( 2 ) 试卷中试题的难度比例、考查的深度是否合理； o ) 试卷的覆盖面、考查点是否能很好地代表整个考试的内容； ( 4 ) 试卷所涉及到的知识是否很好地代表着需要考生掌握的知识，并反映了大纲的要求； ( 5 ) 试卷中的题目的形式是否新颖、丰富、比例是否恰当； 伯) 试卷能否达到考试功能，如选拔尖子或区分优劣等。 因此，建立通用的多学科组卷系统是可能的。系统的“通用性”的含义是：系统运 一，一 东北大学硕士学位论文第一章绪论 行的软、硬件环境设置是通用的；系统的文件内部格式是通用的；系统采用的算法是通 用的。通用题库系统可以派生出任意学科的题库系统，为多学科的试题管理和组卷服务， 不仅可以节省经费，避免重复开发，而且还可以使学校管理走上规范化【5 1 。 1 3 本文主要工作 本文通过对计算机组卷技术的发展及研究现状的分析总结，设计了基于现代教育测 量理论的通用题库系统的组卷数学模型；提出了一种基于遗传算法基本原理的改进的智 能组卷算法并对算法的性能进行了验证；最后将改进后的组卷算法应用到了实际的题库 系统当中。 在本文的编排上： 第一章介绍计算机组卷技术的发展及应用现状，分析了建立通用题库组卷系统的可 行性并简要介绍本文的研究工作； 第二章介绍现代考试系统的理论基础，包括经典测量理论及项目反应理论，并重点 阐述了经典测量理论( c t t ) 的主要内容； 第三章主要陈述题库系统组卷的基本原则，智能组卷系统的指标体系及其与题库分 布情况的相容性检测； 第四章首先介绍经典遗传算法原理，基本组成要素及基本步骤，其次详细论述了本 文所提出的改进后的遗传算法的各个环节及其理论依据并通过实验数据验证了算法的 性能； 第五章介绍了题库系统的整体设计与实现。 一6 一 东北大学硕士学位论文第二章现代考试理论研究 第二章现代考试理论研究 2 1 现代考试理论概述 题库系统的创建是一项十分复杂、技术性很强的工作。题库中试题有关指标取值的 准确性将直接关系到试卷的质量，因此题库设计者对试题指标值的计算与评估要依据合 理的理论基础。此外，题库系统中的成绩分析模块、试卷分析模块也需要相应的理论作 为指导。题库系统的设计是以现代考试理论为基础的。 现代考试的指导理论主要有两种：经典测量理论( c 1 和项目反应理论( i r t ) 嘲。这 两种理论的核心部分是数学模型，它们是基于不同的假设提出的。c t l ( c l a s s i c a lt e s t t h e o r y ) 采用的是线性的定性模型；i r t ( i t e m r e s p o n s e t h e o 劝采用的是非线性的概率模 型。其中，i r t 理论比较适合于在线自适应测试c c a t ) ，即根据测试对象答题情况给出 下一道题的测试。 本文中所研究的题库组卷系统是静态的，其主要功能为：在实施考试之前根据考试 具体要求，利用计算机根据某种选题策略自动生成试卷，之后可根据需要进行在线或非 在线考试，考试结束后可进行试卷分析，对相关试题指标进行调整，以不断完善系统。 经过对两种理论原理与应用的深入分析，本文采用c t t 理论的分析方法。 2 1 - 1 经典测量理论( c r r ) c t t 是在2 0 世纪初被提出来，又称真分数理论。它源于早期高尔顿关于个体差异 的测量和皮尔逊关于统计学的研究，后经斯皮尔曼、瑟斯顿，比纳和西蒙等人的工作而 初步系统化。经过几十年的发展，到2 0 世纪5 0 年代便形成了一套相当完整的理论体系。 c t t 在测验的编制、实施和评价等方面都提出了一系列具体的、实用的统计方法，直至 今天，这些方法仍然广泛地应用于测验工作的各个领域，在测验实际工作中保持着强有 力的影响。 任何一组信息都包含有真正的信息和无关的信息( 嗓音) 。教育测验的真正目的是为 了获得被试的真正信息，排除无关信息。教育测量上将前者称为真分数，后者称为误差。 由于误差的存在，直接测量的观测分数便会在一定范围内波动。 c t t 的特点之一是各种澳0 量参数须从考生样本中求得，其理论基础是真分数模型。 c t t 的真分数模型对此进行了简单而有效的描述，提出了一系列基本定义和推导。 东北大学硕士擘位论文第二章现代考试理论研究 x = ? 。+ e 其中，j 为观测分数，r 为真分数，e 为误差分数。 t = x 其中，j 为观测分数平均值，r 为真分数。 皿= 0 其中，庄为误差分数的期望值。 ( 2 1 ) ( 2 2 ) ( 2 3 ) 口；= 盯；+ 盯；( 2 4 ) 其中，盯；为测验观测分数方差，盯；为真分数方差，仃；为误差分数方差。 经典测量理论的特点是： ( 1 ) 经典测量理论是以弱假设为基础的，这些弱假设条件容易被绝大多数测验数据资料 所满足； ( 2 ) 经典测量理论经过了几十年的发展，形成了一套以真分数理论作为基础的，较为完 善的测量理论以及对项目和测验进行统计分析的方法，这些统计方法在计算上较为简 单，意义上也明了直观，易于教育工作者理解和掌握，更促进了它应用的普遍性； ( 3 ) 在我国的测验领域中大多是以经典测量理论作为指导的，在实践中不断形成和完善， 形成了一套适合我国国情的具体应用方法和应用原则。 2 1 2 项目反应理论( i r k 美国测量专家洛德于1 9 5 2 年在他的博士论文中首次提出了项且反应模型，即双参 数正态卵形模型，并提出了与此相关的参数估计方法，使得i r t 可被用来解决实际的二 值记分的测验问题。这是盯发展史上的里程碑，标志着这一理沦的正式诞生。i r t 又 称题目反应理论、潜在特质理论。 i r t 的发展首先建立在潜在特质理论的基础之上。其主要内容就是揭示被试在测验 项目上的反应行为( 作答) 与测验所测的被试潜在特质( 即制约人的行为的心理品质) 之间 的关系，这种关系的函数描述称为项日特征曲线o c t ) 。项目特征曲线的解析式，即这 种关系的函数表达式，则被称作为项目反应理论各种模型的项目特征函数( i c f ) ，若i c c 的形态确定后，再配上i c f ，则组成项目反应理论模型( 有时又简称项目反应模型) 。 i r t 的基本思想是：假设被试对于测验的反应是受某种心理特质的支配，那么我们 首先就要对这种特质进行界定，然后估计出该被试这种特质的分数，并根据该分数的高 低来预测和解释被试对于题目或测验的反应。因为这种特质无法直接测量，所以称作潜 一8 一 东北大学硕士学位论文 第二章现代考试理论研究 在特质。 其基本思路是确定被试的心理特质值和他们对于项目的反应之间的关系，这种关系 的数学形式就是“项目反应模型”。从某种意义上讲，i r t 的核心就是数学模型的建立 和对模型中各参数的估计。 随着计算机技术的发展，项目反应理论得以推广应用。它所采用非线性模型，建立 了被试对项目的反应( 观察变量) 与其潜在特质( 潜变量) 之间的非线性关系，这一点 更符合事实。但目前项目反应理论的应用仍以两级计分模型为主，且局限于单维反应模 型，更高级的项目反应理论模型尚处于理论上的探索阶段，并且对经典测量理论的一些 领域，如测验效度问题等，项目反应理论并没有提出独到的见解。 2 2c t t 理论研究内容 2 2 1 成绩分析 试题库系统应该具备成绩分析功能，该功能可以利用试卷的应试结果从平均孙、标 准差、方差、相关数等方面进行分析，以便实现班与班、个人与个人的比较，从而评价 试卷的构成是否合理。 。 成绩分析所涉及的理论如下所述f 刀： ( 1 ) 集中量数 代表一组数据( 成绩) 的集中趋势，均值( 平均分) 就是典型的集中量数，它可以用于 两组并行数据之间的比较。设有一组数据x i ，x ：，置，用x 表示其均值，则有： i = 去私 ， 厅百 ( 2 ) 差异量数 表示一组数据变异程度或离散程度的量，标准差，方差都是典型的差异量数，它可 以用于考察一组数据相对于平均数的分布状态，标准差越大，数据分布范围越广，越参 差不齐，反之，则分布范围越小，越整齐。设有一组数据五，x ：，置，用j 表 示其均值，仃2 表示方差，盯表示标准差，则有方差公式及标准差公式如下： o - 2 ：三窆伍，一i ) 2 ( 2 6 ) 一鲁 7 ”7 0 一 东北大学硕士学位论文第二章现代考试理论研究 盯2 氍丽 ( 2 7 ) ( 3 ) 相关量数 表示两组数据之间相关关系密切程度的量，相关系数是典型的相关量数。设有置， r ( 户l ，- ，2 ，n ) 两g t 数据，x ，y 是它们的均值，则有相关系数公式： 窆k i 地一歹) 廖面 ( 2 8 ) 若， 0 则为正相关，若r o 3 为区分度优秀的试卷，0 2 q - 0 3 的试卷为区分度良好的试卷，q 0 若t d 口= 0 ( 3 1 ) 难度级别为d j 的 ( 3 2 ) + 1 3 3 ) c 亿，d ) = 妻( 酗，d j ) - ( 3 4 ) = 1 为z 关于分布曲线l d 的在分布特征矩阵m 7 ( r ，d ) 下的相容度函数。由定义可知， c ( 正，d ) 反映了选择题型为互的试题时，相应于分布曲线l d 的难易程度，值越大越易 实现。 ( 2 ) 定义：函数 c ( r ，d ) = r a 矧i ；n 。 c ，d ) ) ( 3 5 ) 为r 关于分布曲线l d 的在分布特征矩阵m ( r ，d ) 下的相容度函数，也可称之为在题库 分布下，曲线工r 和l d 的相容度函数。若c 仃，d ) o ，且c ( d ，力o ，则称在题库分布 一1 9 东北大学硕士学位论文第三章智能组卷指标体系 下曲线l t 与曲线l d 相容。 类似地，对于任意的指标序列j ，j ：，蜀置，都可以定义相容函数c ( x ，一) ，( 其 中i j ：f ，j = 1 , 2 ，3 ，t ) 。 根据上述定义，下面给出组卷模式与题库分布相容的定义。 ( 3 ) 定义：对于给定的由选题指标曲线：从，l r ：，l 弘上置构成的组卷模式，若对于任 意的j ，j = 1 2 ，3 ，t ；i j ，都有曲线以，删，相容。即，c ( 置，) o 且c ( ，置) o ， 则称该组卷模式与题库分布相容。 注意：这仅仅是成卷模式可以实现的必要条件。 下面举例说明相容性检测的过程。设某课程的成卷模式的题型一分数分布曲线r ： 1 0 ，2 5 ，2 5 ，1 0 ，3 0 ) ，难度分布曲线l d ： 2 0 ，2 0 ，3 0 ，2 0 ，1 0 ，由特征库统计得，关于r 和 d 的分布特征矩阵为： m 7 p ，d ) =( 3 6 ) 计算结果为：c 亿，d ) = 5 0 ，c 佤，d ) - - 4 5 ，c 以，d ) = 3 5 ，c 佤，d ) = 7 0 ，c 亿，d ) 一1 0 ， 得到c 仃，d ) = 一1 0 0 。 因此，在该题库分布下，这两条曲线是不相容的。由这两条曲线构成的组卷模式与 题库分布是不相容的。对系统默认的几种组卷模式事先经过相容性检测，组卷时不用再 次检测。如果用户对组卷参数作了修改，则在组卷前应进行相容性检测，以便及早发现 不相容的组卷模式。 3 4 小结 本章主要介绍了智能组卷的指标体系构成。由于在组卷过程中可能出现用户组卷要 求与题库试题分布情况相矛盾而导致组卷失败的情况，因此对两者的相容性检测具有重 要意义，它是提高组卷成功率的重要条件。 一2 0 一 东北大学硕士学位论文 第四章智能组卷算法研究 第四章智能组卷算法研究 4 1 组卷算法的发展 智能组卷技术是根据用户设置的若干组卷条件，按照定的组卷策略由计算机自动 从题库中选择满足要求的最优解组成试卷。试卷主要质量控制指标有：试卷总分、各类 题型及试题数量、各知识点出题分数比例、各类难度等级出题分数比例以及不同教学要 求度出题分数比例等。其中，组卷系统所采用的算法是影响组卷效率和质量的关键因素 所在，它决定了组出的试卷是否满足用户的组卷要求以及满足的程度。 组卷问题是个多重约束条件下的组合优化问题。所谓组合优化，是指在离散的、 有限的数学结构上，寻找一个满足给定约束条件并使其目标函数值达到最大或最小解。 从某种角度看，组卷问题类似于背包问题。打一个比方，背包可看作是组卷问题中 的试卷，而各物件则对应题库中待选择的各道试题，把物件装入背包则相当于从题库中 选择添入试卷的试题，背包问题有它的重量约束条件，而组成一份试卷的约束条件则更 多，如各难度级别试题所占分数的百分比、需要考察的知识点、试题的题型等。可见， 组卷问题和背包问题有一定的相似之处，但它更加复杂一些，约束条件较多，且彼此制 约，另外还需要确定适当的目标函数。 长期以来国内外的许多科研机构都在对组卷系统进行研究。在题库试题能够保证高 质量的前提下，自动组卷的效率与质量完全取决于抽题算法的设计。如何设计一个算法 从题库中既快又好地抽出一组最符合考试要求的试题，涉及到全局寻优和收敛速度的问 题，很多学者对其进行了研究。到目前为止，先后出现了基于随机选取法的组卷系统， 基于回溯试探法的组卷系统和基于遗传算法的组卷系统等【1 3 - 瑚。 随机选取法根据状态空间的控制指标，由计算机随机地抽取一道试题，然后根据抽 题情况，调整控制指标，再去抽题，此过程不断重复，直到组卷完毕，或己无法从题库 中抽取满足控制指标的试题为止。该方法结构简单，对于单道题的抽取运行速度较快， 但是对于整个组卷过程来说组卷成功率较低，有时即使组卷成功，花费的时间也往往令 人难以忍受。 回溯试探法是将随机选取法产生的每一类型记录下来，当搜索失败时释放上次记录 的状态类型，然后再根据一定的规律( 正是这种规律破坏了选取试题的随机性) 变化一种 新的状态类型进行试探，通过不断地回溯试探直到试卷生成完毕或退回出发点为止，这 一2 1 东北大学硕士学位论丈 第四章智能组卷算法研究 种有条件的深度优先算法，对于状态类型和出题量都较少的系统而言，组卷成功率较好， 但是在实际应用中，发现这种算法对内存的占用量很大，程序结构相对比较复杂，而且 选取试题缺乏随机性，组卷时间也比较长。 遗传算法是一种模拟大自然生物进化过程的计算模型，它以其简单、鲁棒性强、全 局寻优以及不受搜索空间限制性条件约束等特点而日益受到人们的关注。遗传算法的群 体搜索策略为多目标优化提供了非常合适的解决方案。 朱玉祥、孙承佼等人采用了基于遗传算法的组卷策略实现了题库系统的智能组卷， 并通过科学的组卷实验对不同组法算法进行了性能比较分析1 6 1 。实验结果表明：与随机 选取法等传统组卷方法相比，基于遗传算法的组卷方法成功率更高，组卷时间更短，误 差更小，其中随机算法用时可达遗传算法用时的7 到1 7 倍。此外，魏平，毛秉毅等人也 采用了遗传算法作为题库系统的组卷策略并取得了良好的实际效果 1 7 , i s l 。众多的理论与 实践结果表明：遗传算法非常适合用于解决计算机智能组卷这样的多目标寻优的实际应 用问题 1 蛇”。 然而，传统的遗传算法本身仍然存在“早熟”及收敛速度慢等缺陷，这会导致在具 体应用中使算法陷入局部最优解并严重影响算法的性能。因此，必须对传统遗传算法进 行改进使其更加适合智能组卷的具体应用，使组成的试卷能够最大程度满足用户的组卷 要求。 4 2 经典遗传算法理论 4 2 1 遗传算法基本概念 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律 产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优 化算法。 遗传算法的概念最早是由b a g l e y j d 于1 9 6 7 年提出的，而开始遗传算法的理论和 方法的系统性研究的是1 9 7 5 年，这一开创性工作是由m i c h i g a n 大学的j h h o l l a n d 所 实行。当时，其主要目的是说明自然和人工系统的自适应过程嘲。 遗传算法简称g a ( g e n e t i c a l g o r i t h m ) ，在本质上是一种不依赖具体问题的直接搜索 方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应 控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，人们认为“遗传算 法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术 一2 2 东北大学硕士学位论文 第四章智能组卷算法研究 有重大影响的关键技长【2 3 p 。 遗传算法的基本思想是基于d a r w i n 进化论和m e n d e l 的遗传学说的。 d a r w i n 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环 境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。 在环境变化时，只有那些能适应环境的个体特征方能保留下来。 m e n d e l 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中， 并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每 个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的 后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，故而在这个算 法中要用到各种进化和遗传学的概念1 2 4 1 。这些概念如下： ( 1 ) 染色体( c h r o m o s o m e ) 染色体又可以叫做基因型个体( i n d i v i d u a l ) ，一定数量的个体组成了群体( p o p u l a t i o n ) ， 群体中个体的数量叫做群体大小( p o p u l a t i o ns i z e ) 。 ( 2 ) 基因( g e n e ) 基因是染色体中的元素，基因用于表示个体的特征。 例如有一个串s = 1 0 1 1 ，则其中的l ，0 ，l ，l 这4 个元素分别称为基因。 ( 3 ) 基因地点( l o c u s l 基因地点在算法中表示一个基因在染色体中的位置称为基因位置( g e n ep o s i t i o n ) ， 有时也简称基因位。基因位置由染色体从左向右计算。例如在串s = 1 1 0 1 中，0 的基因 位置是3 。 ( 4 ) 基因特征值( g e n ef e a t u r e ) 在用染色体表示整数时，基因的特征值与二进制数的权一致。例如在串s = 1 0 1 1 中，基因位置3 中的i ，它的基因特征值为2 ；基因位置1 中的1 ，它的基因特征值为8 。 ( 5 ) 适应度( f i t n e s s ) 各个个体对环境的适应程度叫做适应度( f i t n e s s ) 。为了体现染色体的适应能力，引 入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数被用来 计算个体在群体中被使用的概率。 ( 6 ) 结构空间s s 在染色体中，基因的任意组合所构成的染色体集合。基因操作是在结构空间中进行 - - 2 3 东北大学硕士学位论文 第四章智能组卷算法研究 的。染色体结构空间对应于遗传学中的基因型( g e n o t y p e ) 的集合。 ( 7 ) 参数空间s p 参数空间是染色体空间在物理系统中的映射，它对应于遗传学中的表现型 f p h e n o t y p e ) 的集合。 4 2 2 遗传算法数学理论 虽然遗传算法计算过程并不复杂，但是其运行机理却十分复杂。人们关心的问题是： 在g a 的迭代搜索过程中，什么类型的个体更容易生存下来，什么类型的个体容易被淘 汰。h o l l a n d 教授在研究中提出了模式( s c h e m a ) 的概念以及模式定理( s e h e m a t h e o r e m ) ， 试图对g a 的运行机理给予理论上的分析。 如果采用字符集k = o ，1 ) 对问题参数进行二进制编码，则位串空间表示为： s = o ，1 r ( 4 1 ) 扩展字符集k = 0 ，l ， ，其中“”称为通配符或无关符，则扩展位串空间表示 为： s 。= o ，1 ，r ( 4 2 ) 由此得到“模式”定义如下： 扩展位串空间s 。= o ，1 ，+ r 中的任何一个点，称为对应于位串空间s = o ，1 y 的一个模式( s c h e m a ) ： 日= 0 ia s ，v i ，h ， j 日。= a ，( 4 3 ) 其中口= 妇。，口：，4 。) ，h = 日。，h ：，日。 ，4 ， o ，1 】， h o ，l ， ，f = 1 ，2 ，；a 8 ，h s j 。 简言之，模式描述了在某些位置上具有相似结构特征的个体编码串的一个子集。例 如，模式1 1 料1 描述了长度为5 ，且在位置l 、2 、5 取值为“1 ”的所有字符串的集合，即 ( 1 1 0 0 1 ，1 1 0 1 l ，1 1 1 0 1 ，1 1 1 1 1 ) 。因此，模式的概念可以简明地描述具有相似结构特 点的个体编码字符串。 模式的阶( s c h e m ao r d e r ) 是指模式中所含有o 、1 确定基因位的个数，记作d ( 日) 。 模式的定义长度是指模式中从左到右第一个非 位和最后一位非宰位之间的距离，记 作j ) 。 模式的维数( s c h e m a d i m e n s i o n ) 是指模