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

摘要 随着计算机辅助教育研究的不断深入，计算机考试系统作为计算机辅助 教学的重要组成部分越来越受到人们的关注。自动组卷是按照一定的要求， 由计算机自动从试题库中选择试题，组成符合特定总分、总时间要求和难度、 区分度、知识点、题型、认知层次等各种参数分布要求的试卷。它是计算机 教学管理的重要组成部分。本文针对现有组卷算法组卷成功率低，耗时长， 生成的试卷难以满足实际考试需求等不足，在充分分析和研究考试系统组卷 算法的基础上，提出了遗传算法自动组卷策略，并将遗传算法自动组卷应用 于在线考试系统中。 首先，分析了试卷的评价指标、各项指标的作用及几个重要指标间的关 系，建立了采用各个评价指标的分布构建的成卷模式，根据成卷模式建立了 组卷数学模型。 其次，在传统遗传算法的基础上，对算法中操作概率的自适应调整方法 及遗传操作过程中个体的替换策略进行了改进，应用了基于精英交叉的精英 保留遗传算法，并通过对比实验对改进算法的全局搜索性能、效率和有效性 进行了验证。实验表明，改进算法具有较好的克服早熟的能力，在全局搜索 性能及收敛速度上较传统遗传算法有显著提高。 然后，针对自动组卷系统的自身特征，本文采用分组自然数编码，减少 了染色体长度空间，编码直接采用试题编号，省去了编码和解码的繁琐。并 提出了相应的交叉、变异算子。通过仿真实验表明，基于改进算法的智能组 卷算法组卷速度快，组卷质量较好，能够满足实际组卷需求。 最后，本文对基于遗传算法的自动组卷系统进行了分析和设计，并利用 编程实现了基于遗传算法自动组卷系统。 关键词自动组卷，遗传算法，智能组卷，多目标优化，组卷策略 a bs t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rb a s e de d u c a t i o n ，c o m p u t e re x a m i n a t io n s y s t e ma sa l li m p o r t a n tc o m p o n e n to fc o m p u t e rm a n a g e di n s t r u c t i o ng e t sm o r ea n d m o r ea t t e n t i o n t e s tp a p e ra u t o g e n e r a t i o ni st og e n e r a t eat e s tp a p e rw i t hs p e c i f i ct o t a l p o i n t ，t o t a lt i m e ，p o i n t s d i s t r i b u t i o n so fd i f f i c u l t y , d i s t i n c t i o n ，k n o w l e d g e ，t y p e ， c o g n i t i o na n ds oo na c c o r d i n gt oac e r t a i nr e q u i r e m e n t sb ya u t o m a t i c a l l ys e l e c t i n g q u e s t i o n sf r o mb a n ko ft e s tq u e s t i o n s t e s tp a p e ra u t o - g e n e r a t i o ni so n eo ft h em o s t i m p o r t a n tc o m p o n e n t so fc o m p u t e rm a n a g e di n s t r u c t i o n ( c m i ) e x i s t i n gt e s tp a p e r g e n e r a t i o na l g o r i t h m sh a v es o m ed e f e c t s ，s u c ha sl o w s u c c e s sr a t i o ，c o s t i n gl o n gt i m e a n dp o o rq u a l i t yo ft e s tp a p e r a i m e da tt h e s ed e f e c t s ，c o m p l e t e l ya n a l y z e sa n d i n v e s t i g a t e st h ea l g o r i t h mo fa u t o - g e n e r a t i n ge x a m i n a t i o np a p e r sa n dp u t s f o r w a r dt h e s t r a t e g yo fa u t o g e n e r a t i n ge x a m i n a t i o np a p e r sb a s e do ng a ，a p p l i e sg ai n t ot h e a u t o - g e n e r a t i n ge x a m i n a t i o np a p e r si ne x a m i n a t i o ns y s t e m f i r s t l y , b a s e do nt h ef u n d a m e n t a lp r i n c i p l e so f t e s tp a p e rg e n e r a t i o n ，a n a l y s e so f e v a l u a t i n gi n d i c a t o r sa n dt h e i rf u n c t i o n s ，r e l a t i o n s h i pw e r ed o n ei nd e t a i l ，at e s tp a p e r g e n e r a t i o nm o d ew a s s e tu pw i t ht h ed i s t r i b u t i o n so ft h ee v a l u a t i n gi n d i c a t o r s ，a m a t h e m a t i cm o d a lt og e n e r a t et e s t p a p e rw a se s t a b l i s h e dg r o u n d e du p o nt h e p r e f e r e n c eo ft e s tp a p e rq u a l i t yd e f i n e db yt h eg e n e r a t i o nm o d e s e c o n d l y , c o m b i n i n g e l i t i s tg a ( e g a ) w i t ht h ek i n gc r o s s o v e rs t r a t e g y , k i n g - c r o s s o v e rb a s e de l i t i s tg e n e t i ca l g o r i t h m ( k e g a ) i sa p p l i e d i nt h ei m p r o v e d a l g o r i t h m ，t h e r ea r et w oc h a n g e da s p e c t s o n ei st h ew a y t oa d j u s tt h ep r o b a b i l i t yo f g e n e t i co p e r a t o r sa n dt h eo t h e ri s t h er e p l a c e m e n ts t r a t e g y t h ev a l i d i t yo ft h e i m p r o v e da l g o r i t h mi sp r o v e db ys i m u l a t i o nt e s t s t h et e s t sr e s u l t ss h o wt h a tt h e i m p r o v e da l g o r i t h mc a ni m p r o v eg l o b a lo p t i m i z a t i o na b i l i t y a n dt h ec o n v e r g e n c e s p e e d t h i r d l y , a i m i n g a tt h ec h a r a c t e r i s t i co fa u t o m a t i c g e n e r a t i n g t e s t p a p e r s y s t e m ，t h i st h e s i sm a k e su s eo ft h en a t i o n a lc o d ew h i c hi s u s e di nt h eg e n e t i c a l g o r i t h mi no r d e rt od e c r e a s es p a c eo fc h r o m o s o m e s d u et ot h ec o d i n gs t r a t e g y , c r o s s o v e ra n dm u t a t i o no p e r a t o ra r ed e s i g n e d t h es i m u l a t i o nt e s ti n d i c a t e st h a tt h e i n t e l l e g e n tt e s tp a p e ra u t o g e n e t a t i o na l g o r i t h mb 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 c a ns a t i s f yt h en e e d sf o ra c t u a le x a m i n a t i o n s ，t h es p e e di sf a s t e ra n dt h eq u a l i t yo ft e s t p a p e ri sb e t t e r f i n a l l y , t h ee n g i n e e r i n gi m p l e m e n tp r o b l e m so ft h ea u t o m a t i cg e n e r a t i n gt e s t p a p e rs y s t e mb a s e do ng e n e t i ca l g o r i t h m sa r ed i s c u s s e di nd e t a i l ，a n dt h es y s t e mh a s b e e na c h i e v e d k e yw o r d s ：a u t o - g e n e r a t i n ge x a m i n a t i o np a p e r s ，g e n e t i ca l g o r i t h m ， i n t e l l i g e n tt e s tp a p e rc o m p o s i t i o n ，m 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 a p e r - d e v e l o p i n g s t r a t e g i e s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成 果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得丞洼王些太堂或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 学位论文作者签名：本期嚼签字日期：肋阵2 月知日 学位论文版权使用授权书 本学位论文作者完全了解云洼王些太堂有关保留、使用学位论文的规定。特授权 云洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影 印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机 构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：茎捌祷 导师签名： 乃 矿- - k 三k 签字日期：2 叫年2 月2 0e l 签字日期：2 0 0 q 年2 月移e l 学位论文的主要创新点 一、针对遗传算法局部搜索能力较弱的缺点，借鉴了一种能改善 遗传算法的局部搜索性能的精英交叉策略，首次将一种基于精英 交叉的精英保留遗传算法应用于智能组卷系统。 第一章绪论 1 1 研究的背景和意义 第一章绪论 网络教学为学生的学习创建了广阔自由的环境，提供了丰富的资源，拓 延了教学时空的维度，现在国内许多院校都已经或即将开展基于网络的辅助 教学，选择或开发一个性能优异、功能完善、能够充分满足校园网络教学需 要的网络教学平台成为关键。网络教学平台开发是一项复杂、庞大的工程， 它集成大量支撑工具，一方面它要考虑与数字校园的集成，另一方面它还要 考虑平台上各应用子系统的集成。 计算机在教育方面的应用始于2 0 世纪5 0 年代的计算机辅助教学系统， 其中包括考试系统、排课系统、教学管理系统等。最初的计算机辅助教学系 统有电子翻页器( p a g e t u r n e r s ) 以及句型和练习监控程序( d r i l l - a n d - p r a c t i c e m o n i t o r s ) 。计算机辅助教学系统是利用计算机为媒介，通过运行事先存入的 计算机程序来实现教学、辅导答疑、实验仿真以及测验考试等教学活动。它 是一个涉及计算机科学、教育学、心理学、认知科学和行为科学的复杂系统， 其研究的目的是由计算机系统在一定程度上代替教师，实现最佳教学。 自2 0 世纪7 0 年代以来，计算机在辅助教学上的应用取得了新的进展。 国外早期比较有名的是s c h o l a r 系统( c a r b o n e l l & c o l l i n s ，1 9 7 0 ) ，它应用人 工智能的知识表达方式，其知识库采用语义网络形式，并由事实、概念和过 程组成，教学方式采用苏格拉底对话式，根据学生的回答，通过推理机制产 生更多提问并评价学生的解答，系统能诊断学生的一些错误概念并引导学生 自己思考后纠正错误。2 0 世纪8 0 年代后，随着人工智能的发展以及在计算 机辅助教学系统的知识表示、推理方法和自然语言处理等方面的应用，使得 计算机辅助教学系统的设计越来越智能化。 在学校教学工作中，考试是其中重要组成部分。通过考试，教师可以了 解学生的学习情况，并借此了解教学效果，改进教学方法，提高教学质量， 学生则可以通过考试了解自己对内容的掌握情况，有目的地进行学习。但是， 传统考试在编制试题、组织考试、统计分数的过程中，要花费大量的时间、 人力和物力。其中不可避免地存在大量的重复劳动，工作效率比较低，而且 很难避免人为因素对考试造成的影响。 随着计算机的普及，现在的各种考试都逐渐采用计算机出题，并且随着 天津工业大学硕士学位论文 网络时代的到来，考试的技术手段和载体发生了划时代的变化，计算机技术、 网络技术和考试理论的日渐成熟，使考试从传统的纸笔考试到计算机辅助考 试再发展到基于w e b 的在线考试成为现实，用计算机进行网上考试已经成 了一种不可逆转的趋势。它改变了以往靠人工进行考试的各种不足，同时 也对考试系统提出了一些新的问题，如何从试题库中快速地、能满足用户各 项要求地抽出试题组成一份试卷就是其中一个亟待解决的问题。传统的教师 出卷方式主要是由出题者根据自己的知识收集试题、选取试题、编制试题。 虽然试题的效度和信用度较高，但也存在一些缺点。主要表现是：试题制作 质量由于人为因素不能稳定；选题范围狭窄；耗费教师大量时间、精力；不 利于实现教考分离；出卷成果难以与其他出题者共享；无法实现完全的计算 机评卷、分析乜1 。利用计算机建立题库并对其进行管理，是实现教考规范化、 标准化的一个重要措施，更是教考分离的一个重要手段。一方面计算机参与 管理题库节省了教师的宝贵时间，另一方面使考试更加标准化，更加客观真 实全面地反映教学成果，从而促进教学质量的提高。因此，利用计算机在题 库中按照用户要求进行随机抽取相应试题组成一张试卷成为组卷系统研制的 必然。 智能组卷系统，不仅能节省教师的宝贵时间，提高工作效率，还能消除 人为因素的干扰，使考试更加标准化，更能客观、真实、全面地反映教学的 实际效果。有利于促使任课教师必须按照教学大纲的要求认真备课，认真组 织教学内容，改进教学方法，因此对教学质量和整体教学水平的提高有着重 要意义。还可利用智能组卷系统对试卷和考试分数进行分析和评价，使考试 这一教学环节更加科学化。 对于组卷系统来讲，生成符合要求的试卷是一项最根本的功能要求，其 抽题组卷算法的设计对于整个组卷系统的性能和质量来讲是关键。自动组卷 不但能最有效地把客户的需求与计算机技术结合在一起，生成符合要求的试 卷且比较客观、规范，使用起来也最为方便。然而，自动组卷试题库的设计 并不容易。现有的试题库系统大体分三种：一是将试题库看做试题集，命题 时由具有丰富经验的教师逐题抽取。二是将试题库看做试卷集，将已经出好 的试卷存储起来，在组卷时任意抽取一份。三是利用某种组卷策略，自动组 成合理的试卷。前两种虽能保证试卷质量，但第一种与人工命题无异，第二 种只能出有限份试卷，第三种则是随机出题，又有组卷策略可遵循，但所使 用的组卷技术和组卷策略有优有劣。自动组卷的效率和质量完全取决于组卷 算法的设计。因此，对组卷算法的研究是必要且具有重要实际意义的。 本课题是为了解决现有计算机考试系统组卷模块难以满足实际考试需求 第一章绪论 这一问题提出的。有效的解决计算机考试系统中的组卷问题，对于合理、高 效地利用现代化手段进行教育、教学，实现考试现代化、规范化，减轻教师 工作量，提高教学效率和质量具有重要的实际应用价值。 1 2 国内外研究现状 传统的考试系统大多是应用于单机环境，即使是在网络教室中进行考试， 也是采取将系统装载到本地机器运行，而并非真j f 意义上的网络考试。随着 信息技术的发展，目前有两类应用比较普遍的考试系统，一类是针对某一专 业或课程的考试系统，一类是基于网络教学平台的考试系统。 2 0 世纪5 0 年代美国首先将计算机用于教育测验开始，多年来计算机辅 助测验系统发展迅速。8 0 年代，人们将计算机辅助测验( c o m p u t e ra s s i s t e d t e s t ，o 叮) 系统应用于大规模等级考试，形成了计算机等级考试系统，最 出名的网络远程教育案例，当属美国政府举办的t o f e l 考试，目前在全球 范围内，均可以通过国际互联网进行t o f e l 培i j l i 与考试，大大减少了美国 政府对于此项考试的开支，并能更快速、准确地为期望进入美国学习的学生 服务。针对某一专业或课程的考试系统，国内外已有一些基于网络的信息技 术在线考试与测评系统。比如，我国的计算机等级考试、国际上c i s c o 的 c c n a 、c c n p ；微软的m c s e 、m d b a 、s u n 的j a v a 、s o l a r i su n i x 、 h p 的各类信息技术认证考试等1 。 在国内，绝大多数的考试还停留在传统考试模式下。在此模式下，组织 一次考试至少要经过5 个步骤，即人工出卷、考生考试、人工阅卷、试卷分 析和成绩评估。随着考试类型的增加及考试要求的不断提高，教师的工作量 将越来越大。到1 9 9 8 年后，随着国内网络教育的兴起，各高校纷纷开发了自 己的网络教学平台，作为网络课程重要组成部分的网络考试系统也相继问世， 如北京师范大学的网络教学平台、上海交大的网络考试平台等。 组卷模块是计算机考试系统中重要的组成部分，组卷模块中的自动组卷 功能是考试系统自动化的核心目标之一，能否生成高效、科学、合理的试卷 对于考试系统至关重要。因此，为了提高计算机考试系统组卷模块的实用性 及有效性，组卷算法研究成为计算机考试系统研究的一个重要方面。 由于自动组卷是从题库中选取试题并自动生成能满足教学和教师要求的 各类试题，因此它是一个带约束的多目标优化问题，由于c s p 问题通常是一 个n p 一完全类问题，采用经典的数学方法很难解决这个难题，自动组卷的 效率和质量完全取决于抽题算法的设计。如何设计一个算法从试题库既快又 好地抽出一组最符合考生要求的试题，涉及到一个全局寻优和收敛速度快慢 天津【：业大学硕十学位论文 的问题。目前的自动组卷系统根据其所使用的组卷策略大致可以分成四类： ( 1 ) 基于随机抽取的自动组卷 ( 2 ) 基于深度与广度搜索算法的自动组卷 ( 3 ) 基于项目反应理论的自适应测试 h ) 基于数据挖掘和知识发现的的自动组卷 基于随机抽耿的自动组卷策略n 2 1 就是利用计算机提供的随机函数在对 应的试题库中随机搜索满足条件的试题，不断重复搜索过程，直到试题生成 操作完成或不能搜索到满足约束条件的试题为止。尽管随机组卷算法结构简 单、单次组卷过程的运行速度比较快，但是对于整个组卷过程来说组卷的重 复率高，组卷成功率非常低，即使组卷成功，耗费时间也较长。在实际应用 过程中，由于采用随机抽取试题的过程中，可能发现抽取出来的试题不符合 某种要求，如整体难度系数超出预定的难度值，或者考试过程中预计学生所 花费的考试时间超过给定的考试时间等原因，从而导致本次组卷过程失败。 基于深度与广度搜索算法的自动组策略乜3 1 是在组卷过程中采用随机的 方法抽取试题，但在抽取过程中通过验证所选择的试题是否满足系统给定的 目标条件来决定该试题是否抽取，当发现目前没有任何试题满足要求而组卷 过程又没有完成时，则采用回溯试探方法，通过废弃前一段时问所做的组卷 操作来重新进行组卷。由于这种方法在组卷的过程中通过废弃部分工作而不 是废弃本次组卷过程中的全部操作，从而有效地降低了无效组卷的次数，使 得自动组卷算法性能得到提高。显然这种有条件的深度优先法，对于状态类 型和出题量都较小的题库系统而言，组卷成功率较好，但是在实际到一个应 用时发现这种算法对内存的占用量大，程序结构相对比较复杂，而且选取试 题缺乏随机性，组卷时间长。 基于项目反应理论的自适应测试策略h 町是通过建立一个反映考生作答 反应与题目质量及能力水平间关系的非线性模型，对考生的能力水平进行估 算，从而得出对该考生能力的测量，这种方法不依赖于特定的施测题目样本， 但对于模型的建立及其有效性方面缺乏验证，成功的实际应用尚不多见。 数据挖掘和知识发现作为一门新的研究领域，涉及到机器学习、模式识 别、统计学、数据库和人工智能等科学。特别是它可被看作是数据库理论和 机器学习的交叉学科m 1 。目前国内数据挖掘的研究重点是找出频繁项目集 ( f r e q u e n ti t e m s e t s ) 。典型的关联规则挖掘算法有r a g r a w a l 等人提出的 a p r i o r i 算法d h p 算法等。它们都属于数据库遍历类算法。这些算法的提出， 不同程度地改进了关联规则发现过程。但至今，提高算法的效率，仍然是关 联规则发现问题中需要解决的问题。虽然数据挖掘在组卷寻优中具有一定的 第一章绪论 先进性，但对它的研究目前却停留在理论上，缺乏成熟的技术和理论。 1 3 遗传算法在组卷中的应用 分析上述算法的优缺点，不难发现，在限定条件和状态空间的限制下， 随机选取法有时能够取出一组令用户满意的试题。只不过由于它随机选取试 题的范围太大，无法确定目前条件下那些区域能抽出合适的试题，反而可能 在那些已经证明是无法抽取合适的试题区域内反复选题，进行大量的无效操 作进入死循环，最终导致组卷失败。回溯法组卷成功率高，但它以牺牲大量 的时间为代价，且随机性差。采用数据挖掘得智能搜索算法具有全局寻优和 收敛速度快的特点，但是其研究广泛，有些技术和理论还不成熟，必须从中 挑选出适合自动组卷的算法。经过研究发现，遗传算法作为智能搜索算法的 一种，具有全局寻优和智能搜索技术，以及收敛速度快的特性，能够很好的 满足自动组卷的需要，有效的解决随机函数选取法和深度广度回溯试探法组 卷的不足。 在众多的优化搜索方法中，遗传算法是后起之秀。它是2 0 世纪6 0 年代 末期到7 0 年代初期由美国m i c h i g a n 大学的j h h o l l a n d 教授及其学生和同事 发展起来的。六十年代初，h o l l a n d 教授开始认识到生物的自然遗传现象与人 工自适应行为的相似性，提出了在研究和设计人工自适应系统时可以借鉴生 物自然遗传的基本原理，模仿生物自然遗传的基本方法。1 9 6 7 年，他的学生 j d b a g e l e y 在其博士论文中首次提出“遗传算法( g e n e t i ca l g o r i t h m ) ”的概 念。在b a g e l e y 的论文中，采用了双倍体编码，发展了与目前g a 类似的复 制、交叉、变异、显性、倒位等遗传操作，并对早熟机理进行了研究嘲。2 0 世纪8 0 年代以来，遗传算法进入了蓬勃发展时期，无论是理论研究还是应用 研究都十分活跃。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 n s 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 ) ) ，总结了g a 研究的主要成果，对 g a 及其应用作了全面而系统的论述，奠定了现代g a 的基础。1 9 9 1 年， l d a v i s 编辑出版了( h a n d b o o ko f g e n e t i ca l g o r i t h m s ) ) ，其中包括了g a 在工 程技术和社会生活中的大量应用实例，对遗传算法的有效应用具有重要的指 导作用n 0 1 。 作为一种优化与搜索算法，遗传算法相比于其它算法应用于组卷系统所 具有的优势在于h ： ( 1 ) 遗传算法的操作对象是一组可行解，而非单个可行解，搜索轨道有 多条，而非单条，因而具有良好的并行性。 ( 2 ) 遗传算法只需利用目标的取值信息，而无需梯度等高价值信息，因 天津工业大学硕士学位论文 而适用于任何大规模、高度非线性的不连续多峰函数的优化以及无解析式的 目标函数的优化，具有很强的通用性。 ( 3 ) 遗传算法择优机制是一种“软”选择，加上其良好的并行性，使它 具有良好的全局优化性和稳健性。 ( 4 ) 遗传算法操作的可行解是经过编码化的，目标函数解释为编码化个 体的适应值，因而具有良好的可操作性与简单性。 ( 5 ) 遗传算法易于和别的技术如神经网络、模糊推理、混沌行为和人工 生命等相结合，形成性能更优的问题求解方法。 作为一种优化方法，遗传算法也存在着自身的不足。由于计算机条件的 限制，遗传算法的种群规模是有限的，并且在算法运行过程中通常保持群体 规模不变，而遗传操作中的选择操作往往使优良个体呈指数级增长，因此， 在进化初期，种群中往往会出现大量相同的优良个体，种群多样性丧失，导 致算法只能收敛于局部最优解，引起“早熟 现象的发生。另外，遗传算法 中参数的确定没有通用的方法，通常只能通过大量的实验来确定，而不恰当 的参数又往往导致算法的搜索性能不高n 引。 针对遗传算法存在的不足，众多学者致力于推动遗传算法的发展，改善 遗传算法的性能，提出了各种改进的遗传算法，比如结合了精英选择、异物 种重组、大变异的改进遗传算法；采用变长染色体的m e s s yg a u 引；交叉、 变异概率可变的自适应遗传算法n 劓；基于小生境技术的遗传算法；根据问题 自身特点引入非标准遗传操作算子n 副；与传统启发式算法相结合的混和遗传 算法口6 1 以及并行遗传算法口力等。这些改进算法不但在一定程度上弥补了遗传 算法的缺陷，使遗传算法的性能和效率得到了提升，而且为遗传算法的研究 发展提供了新的思路。 正是因为遗传算法与传统优化算法相比具有简单通用、鲁棒性强、适于 并行处理、全局寻优等特点，较之传统组卷方法，遗传算法更适用于组卷问 题。很多学者把其应用到组卷系统的研究中，d b f o g e o l 在神经网络的进化 学习方法的研究中首次提出把遗传算法用于试题组卷，g o r d b e r gm w 应用遗 传算法的寻优特性为组卷问题建立了寻优模型等。国内的遗传算法的发展较 晚，其中王友仁、施玉霞等在系统分析组卷理论的基础上提出了一种基于自 适应多点变异混合算法的智能组卷方法n 引；焦翠珍、戴文华等改变了传统的 遗传算法编码方式，根据组卷问题的特点提出了十进制编码，试验表明该方 法取得了比传统二进制编码更好的效果口引。 将遗传算法应用于组卷问题仍处于研究阶段，针对遗传算法自身存在着 不足以及组卷问题的特点，需要探索出更加符合组卷问题特点并能够克服遗 第一章绪论 传算法缺陷的改进算法。 1 4 本文的主要工作 本论文对现有的计算机自动组卷技术进行了深入、系统的研究，综合现 有算法的特点，提出自己的看法。并在此基础上利用c 拌开发实现一个简单的 比较实用的自动组卷系统。主要内容如下： ( 1 ) 通过查阅大量中外文献，了解国内各种题库特点，分析功能需求。 确定本系统的设计方案。 ( 2 ) 采用预先对试题库进行基于知识点范围约束条件的初始化，将试题 库按题型分割为几个分库表，组卷时减小了算法的搜索范围，使试题知识点 定位更加准确，提高了成卷速度。 ( 3 ) 试卷染色体采用分组自然数编码，减少了染色体空间，提高了求解 效率。 ( 4 ) 基于遗传算法，针对考试系统的自动出题问题，选取一个合适的控 制矩阵，应用其全局寻优和智能搜索的特性，在试题的各种属性满足控制矩 阵的控制指标的基础上，从而从题库中既快又好的抽出一组最佳解或是抽出 一组非常接近最佳解的实体。 ( 5 ) 将自适应理论运用于交叉概率及变异概率，更好的保留优秀个体并 防止“早熟 。 ( 6 ) 开发了基于遗传算法自动组卷的在线考试系统。 1 5 本文的组织结构 本文共分五章，具体结构如下： 第一章是绪论，包括论文的研究背景、研究的目的意义、国内外研究现 状、本文的主要工作、本文的组织结构等内容，同时对比了几种常用的试题 生成算法。 第二章介绍了自动组卷系统组卷的基本原则，分析了试题的属性指标、 试卷的评价指标、各项指标的作用及几个重要指标间的关系，组卷的数学模 型和目标函数。 第三章介绍多目标优化问题，遗传算法的基本概念和基础知识、多目标 遗传算法的求解策略。 第四章介绍了遗传算法早熟的成因分析及常见预防措施，基于精英交叉 的精英保留遗传算法，采用自适应调整对遗传算法进行了改进。 第五章详细介绍利用改进算法求解组卷问题的具体步骤，其中包括编码 天津工业大学硕士学位论文 方式、交叉、变异算子的设计，考试系统的具体实现过程，并使用模拟题库 进行仿真实验。 第六章总结全文，对智能组卷研究进行展望。 第二章组卷问题的基本理论及数学模型 第二章组卷问题的基本理论及数学模型 在线考试系统的设计是以现代考试理论为基础的瞳们。当前，现代考试的 指导理论主要有两种：经典测量理论( c t t ：c l a s s i c a lt e s tt h e o r y ) 和项目 反应理论( i r t ：i t e mr e s p o n s et h e o r y ) 。两种理论的核心部分都是数学模型， 它们是基于不同的假设提出的。经典测量理论是以信度、效度、区分度等统 计特征量为中心的测试理论；项目反应理是以受测者回答问题的情况，经题 目特征函数的运算，推测受测者的能力。两种理论仍有许多相互联系的地方， 经典理论中的项目统计量与项目反应理论中的项目参数有着很高的相关性。 经典测试理论对建立试卷、考分转换与等值等均有一套比较完整的方法，这 对于测验的编制和实施适应性测验都是非常重要的，因此本系统采用的理论 基础是经典测量理论。 本章将根据组卷的基本原则、试卷的评价指标及各指标间的关系等基本 组卷知识建立试卷模式，并在此基础上构建组卷问题模型。 2 1 组卷的基本原则 一份合格的试卷不是试题的随意堆砌。只有按照一定的原则，精心选择 内容、难度、区分度等属性指标相匹配的试题，才能保证试卷的信度和效度， 满足实际考试的需求。对于一般的在线测试来说，一方面主要是用于学生自 测，检验自己对学科知识的掌握程度；另一方面用于教师对学生进行考试， 考察教学效果，进而改进教学方式。这两个方面的用处均在于考察学生知道 什么，能做什么，因此属于目标参照性测验。对于大规模的人才选拔，考虑 到公平性和保密性，一般不会采用在线测试系统，而对于小规模的人才考核， 一般也不会采用这种复杂的考察方式，而是采用最新的项目反应理论进行测 试，不需要这种复杂的在线测试系统。因此本文研究的在线测试系统主要侧 重于目标参照性测验。 对于目标参照性测验，组卷的基本原则主要体现在晗们： ( 1 ) 组卷的主要依据是考试大纲，试卷有适当多的试题数和较大的内容覆 盖面，必须全面反映大纲的广度和深度。 考题要体现教学大纲的基本要求，既要反映出考生对基本知识、基本理 论和基本技能的掌握程度，又要考核考生灵活运用所学理论去分析和解决问 题的能力。要使组卷全面反映大纲的广度和深度，试题数量要足够，覆盖面 天津工业大学硕士学位论文 要大，以保证试卷的信度。一般情况下，认知层次较高、教学时间较长的章 节或知识点允许出现多个题目，但应尽量有难度及题型的差别。 ( 2 ) 组卷要利于考核考生能力和促进考生智力发展。 考试不仅考核考生知识掌握情况，而且通过考试，可以促进考生智能的 发展和提高。要使试题类型多样化，从不同侧面考核考生的知识与智能。在 组卷时，要考虑试题多种类型和功能，选择最佳组合结构。 ( 3 ) 组卷要讲究层次，要有难度台阶，才能在分数上拉开距离。 试卷的难度尽量适中，以保证试卷有较高的区分度。根据考试的目的， 可适当对试卷难度进行调整，比如以检验知识掌握程度为目标的一般性考试， 可设定试卷难度在0 5 左右；选拔性考试可适当地加大难度，尽量避免试卷 难度过高或过低。试卷中不同难度试题的比例也应合理安排，试题难度应呈 梯度分布。 ( 4 ) 命题要注重发挥考题对考生学习方法的引导作用。 众所周知，考生一般都重视考试，自觉或不自觉地受到考试“指挥棒 的影响。当然，不能把考生引向为分而学习，为了应付考试而学习。但是， 要充分估计到考试对学生的引导作用。如果考题偏重记忆，考生就要去死记 硬背，如果考题着重灵活应用，学生就要开动脑筋，思考钻研问题。因此， 可以通过命题来引导学生掌握正确的学习方法。 ( 5 ) 考试不能出偏题、怪题，但要有一定的深度，要能测量出考生的不同 知识水平。 ( 6 ) 试卷有一定的总分及时间限制。一般试卷满分值为1 0 0 分，考试时间 可为9 0 分钟、1 2 0 分钟、1 5 0 分钟等。 ( 7 ) 命题的表达语或指导语要清楚无误，以提高考试的效度。 组卷工作是一项复杂的智力劳动，组卷者首先要研究考试大纲和命题计 划，明确考试的目的、对象、性质，试题的形式、数目，试题数量和分数在 各部分中的分配比例，考查的重点和其它要求。其次，根据命题计划编制试 题，给出答案。并对编出的试题进行审查、修改和筛选，同时注明各试题的 预计难度、区分度、所属章节和认知层次，分数及评分标准。 2 2 试题的几个重要属性指标 考试作为测量工作的重要形式，运用教育测量的方法对其进行分析离不 开教育统计的理论和方法。教育统计是运用数理统计学的原理和方法研究教 育现象，具体的说，就是研究如何收集、整理、分析推断教育现象中的数据， 对教育科学进行定量分析，用以发现和表明教育现象的某些特征和规律瞳“纠。 1 0 第二章组卷问题的基本理论及数学模型 洳量中的“：j 度”即难度、区分度、信度、效度指标皆是统计中百分数、平 均数、标准差、相关系数的结果，测量结果的分析和评价离不开统计学的估 计和检验方法心副。 考试的科学性包括考试形式与考试内容的科学性两个方面。判断考试科 学与否，必须用评价指标进行度量。考试的评价指标是考试质量分析的依据， 也是组卷的依据。就考试的发展现状来看，评价考试的科学性主要有难度和 区分度。 组卷就是从大量试题中选取一定数量的试题，组成一份合乎考试要求的 试卷。不同的试题组合而成的多份试卷在质量上也不尽相同，试卷中试题的 质量及其他属性指标对试卷的检验能力起到了决定性的作用。组卷时，常常 需要进行试题分析。试题分析包括定性分析与定量分析。定性分析是指对试 题的科学性的分析，如试题是否符合编制原则，试题测量的是否是预定的教 学内容以及试题测量的是否是预定的教学目标等。定量分析是指对试题的难 度与区分度的分析。难度与区分度是衡量试题质量的基本指标，本节对试题 的难度与区分度等衡量指标进行简单介绍。 试题的难度、区分度都是试题的重要质量指标，但它们不是试题自身的 性质，而是试题针对参加统计的这组学生反映出的特性，因此，它们的数值 总是和某批学生有关，难度和区分度的确定也比较困难。然而，对于学校的 教学考试，虽每年的学生不同，但情况类似，所以可用学生成绩计算结果， 并逐年修正，作为试题对该校学生的属性值。所以实际建立题库的时候，常 常让有经验的老师给试题的难度和区分度确定一个初始值，然后根据每年考 试的结果，依据一定的算法进行修正。 2 2 1 试题的难度 难度通常就是指完成题目或项目任务时所遇到的困难程度。它可分为绝 对难度和相对难度两种，绝对难度又称认知难度，是指项目本身固有的难度 相对难度又称统计难度，是学生实测后，经计算得到的难度指标n 1 。被试学 生作答一个题目所遇到的困难程度的量数，就叫题目的难度系数，也常称为 难度值，用符号口表示，公式表示为： 吼- - i 一墨 ( 2 1 ) 门 其中，仍为试题i 的难度系数，足为该题平均得分值，n 为该题满分值。 从公式可知，足越大，仍越小，当r = n 时，q a = 0 ；足越小，纽值越大， 当足= 0 时，仍= 1 。仍的取值范围0 s 吼l 。 天津工业大学硕士学位论文 也就是说，试题得分越多，试题的难度值越小，试题越容易；试题等分 越少，试题的难度值越大，试题越难。当所有被试者都答对了时，试题的难 度值为0 ，试题最容易；当所有试题都不会答时，试题的难度值为1 ，试题最 难；当难度值为o 5 时，试题为中等难度。一般情况下，我们把试题难度划 分为五个等级，难度区间与难度等级的对应关系如表2 1 所示。 表2 1 试题难度等级 难度等级易较易中等较难 难 难度区间 【0 , 0 2 】( 0 2 ，0 4 】( 0 4 ，0 6 】( 0 6 ，0 8 】 ( o 8 ，1 】 2 2 2 试题的区分度 区分度是衡量试卷质量的又一重要指标，是区分不同层次的学生水平能 力的指标，它是由被试者在该题上的得分与被试者的实际能力水平之间的关 系来确定的，可衡量题目对不同水平被试者的心理特质的区分程度乜5 1 。用字 母表示。区分度一般可采用高低分组法计算，计算公式如下： d ：益一一x l kk ( 2 2 ) d 为试题区分度的估计值，k 和k 分别为高分组和低分组在该试题上 的平均得分，k 为试题的满分分值。 根据公式，试题区分度的取值范围在1 和l 之间，区分度过低表明该试 题的质量不佳，这种试题对测验总分起着不良的干扰作用。具体的区分度评 价标准如表2 2 所示。 表2 - 2 试题区分度评价表 区分度指数( q ) 评价 0 4 0 以上高 0 3 0 - - , 0 3 9 较高，如能改进更好 0 2 m 一0 2 9尚可，使用时需做改进 0 1 9 以下劣，必须淘汰或加以修改 如果试题的区分度高，那么水平高的被试者在题目上的得分就会高，而 水平低的被试者就会得分低，这样就可以把不同水平的被试者区分开来。区 分度属性在题库中的作用也是挑选题目。由难度和区分度的计算方法可知， 第二章组卷问题的基本理论及数学模型 试题的难度和区分度依赖于考生的答题情况，同一道试题对不同能力水平的 学生群体施测可能会得到不同的难度和区分度。只有考试实施后，才能准确 地计算出对该批考生来说这两项指标的取值。但由于学生的能力水平基本呈 正态分布，尽管情况略有不同，但大体相似。因此，编制试卷时，试题的难 度及区分度可由经验丰富的教师确定一个初始值，再根据学生的实际考试情 况进行适当的修正，作为下次组卷时试题质量的依据。 难度和区分度是对试题质量的定量分析。除了这两项指标外，每道试题 还有诸如认知程度、题型、知识点等属性。其中，认知程度用于反映学生对 知识独立获取和驾驭的程度，从低级到高级可分为识记、理解、应用、分析、 综合、评价六个层次。这些指标是对试题的定性描述，对于科学评价试题、 合理组卷起着重要作用。 2 2 3 难度与区分度的关系 难度和区分度都是评价试题质量的数量化指标。试题的难度影响试题的 区分度，当难度过高或过低时，区分度将会很低；当难度在0 5 0 左右时，试 题的区分度将会很高，有时可接近或达到最大值。例如，当难度值为1 o o 时， 几乎所有被试者都答不对，即都得零分，此时便无法区别优秀生和差生，试 题的区分能力为0 ；当难度值为0 时， 满分，此时也无法区别被试者的优劣， 几乎所有的被试者都能答对，即都得 试题的区分能力也为o ：而当难度值 在0 5 0 左右时，被试者的分数分布最为广泛，即试题对被试者的区别能力最 强2 耵。 2 3 衡量试卷质量的指标 试题指标是建立试题库的基础，试题库的建立就是为了克服人为的主观 性和片面性，提高组卷的客观性和科学性，以及组卷的质量和效率。试卷指 标也是组卷过程中的一个关键因素，用户在提出组卷需求时，不能对单个试 题指标提出要求，但是可以对整份试卷提出相关要求，因此也需要了解试卷 指标。 2 3 1 试卷的信度 信度( r e l i a b i l i t y ) 指的是测量结果的稳定性程度，简单地说就是测量结