（管理科学与工程专业论文）基于遗传算法的试题库设计与组卷方法研究.pdf

山东师范大学硕士学位论文 摘要 随着计算机技术及人工智能的发展，组卷系统的研究逐渐被越来越多的专家 学者所注意。 本文首先探讨试题库系统建设的理论基础，对试卷的测量标准、试卷和试题 的参数进行了分析；接着论述了试题库组卷系统的设计思想、总体功能及其实现 方法，并在组卷设计思想的基础上对数据库结构的建立进行了改造与设计，从而 为提高组卷的成功率和工作效率打下良好的基础。最后，在分析国内外大量文献 的基础上，着重对自动组卷算法进行了研究，以难度、题型、教学区分度及整卷 时间为主要控制参数建立了自动组卷问题的数学模型，提出了一种基于遗传算法 解决组卷问题的改进方法，该算法以其具有的自适应全局寻优和智能搜索技术、 且收敛速度快的特点解决了传统组卷中编码太长、适应度函数值计算困难等问 题，很好的满足了自动组卷的要求，进而建立和描述了组卷问题的染色体结构和 适应度函数，设计了问题的遗传操作，并编制了相应的组卷遗传算法应用软件， 为进一步完善网络试题库的建设奠定了坚实的基础。 关键词：试题库数学模型遗传算法智能组卷经典测量理论 中图分类号： 山东师范大学硕士学位论文 a bs t r a c t w j t l lt h ed e v e l o p m e n to ft h ec 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 nt h ea u t o g e n e r a t i n gt e s tp a p e rs y s t e mh a sa r o u s e dt h ec o n c e r no fm o r e a n d m o r ee x p e r t s i nt h el i t e r a t u r e ，f i r s t l y , t h et h e o r e t i c a lf o u n d a t i o no ft h ei t e mb a n k c o n s t r u c t i o nw e r ep r o b e d ，t h ee v a l u a t i o ns t a n d a r do fa ne x a m i n a t i o np a p e ra n dt h e p a r a m e t e r so ft h et e s t p a p e r s a n dt h ee x a m i n a t i o nq u e s t i o n sw e r e a n a l y z e d s e c o n d l y , t h eb u i l d i n go ft h ed a t a b a s es t r u c t u r ew e r er e c o n s t r u c t e da n dd e s i g n e do n t h eb a s i so ft h ed e s i g ni d e ao ft h ea u t o g e n e r a t i n gt e s tp a p e r , i ts e tt h eb e t t e rs t a g ef o r i m p r o v i n gt h ea c c o m p l i s h m e n tr a t eo ft ha u o t g e n e r a t i n gt e s tp a p e r t h ea l g o r i t h m s w e r er e s e a c h e do nt h eb a s i so fa n a l y s ef r o man u m b e ro fd o m e s t i ca n do v e r s e a s l i t e r a t u r e t h em a t h e m e t i c sm o d e lw a sb u i l d e dw i t ht h ed e g r e eo fd i f f i c u l t y , t y p e so f q u e s t i o n s ，t e a c h i n gd i s t i n g u i s h ，t o t a lt i m ea st h em a j o rc o n t r o l l i n gp a r a m e t e r s t h e i m p r o v e m e n tm e t h o db a s e do nt h eg e n e t i ca l g o r i t h m sw e r eo f f e r e d c h a r a c t e r i z e d b yi t sa u t o m a t i cr e s e a r c h i n ga b i l i t y , a r t i f i c i a li n t e l l i g e n c es e a r c h i n gm c h n o l o g ) ra n di t s h i g hs p e e do fc o n v e r g e n c e ，t h i sa l g o r i t h mc a nb eu s e dt or e s o l v et h ep r o b l e m si n t r a d i t i o n a la u t o g e n e r a t i n gt e s t p a p e rs u c ha st h eo v e r - l o n gc o d i n g ，t h ed i f f i c u l t yo f c a l c u l a t i n g t h e a d a p t a b i l i t yf u n c t i o n ，w h i c hh e n c e ，m e e t s t h ed e m a n d so f a u t o g e n e r a t i n gt e s tp a p e r i ta l s ob r o u g h tf o r t han e w s t r h l l c t l l r eo fc h r o m o s o m ea n d t h ef i t n e s s f u n c t i o n ，d e s i g n e dt h eg e n e t i co p e r a t i o n t h et h e s i sd e v e l o p e do n a u t o g e n e t a t i n gt e s tp a p e r i ts e tt h es t a b l es t a g ef o rt h ef a r t h e ra n dp e r f e c tc o n s t r u c t i o n o ft h ea u t o g e n e r a t i n gt e s tp a p e r k e yw o r d s ：i t e mb a n k ；m a t h e m a t i c sm o d e l ；g e n e t i ca l g o r i t h m s ；a u t o g e n e r a t i n g t e s tp a p e r ；c l a s s i c a lt e s tt h e o r y c l a s s i f i c a t i o n ： 2 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如没 有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 学位论文作者签名： 渺1 新擀参撕苌 学位论文版权使用授权书 本学位论文作者完全了解遨有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权邋可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解 密后适用本授权书) 学位论文作者签名： 导师签字芬k 备苌 签字日期：2 0 0 子年丫月t 3 日签字日期：2 0 0 辟y 月1 1 日 山东师范大学硕士学位论文 1 1 问题的研究背景 第1 章绪论 在社会的发展与技术的进步中，学校的教学过程及方法也日益丰富和提高， 我国提出的教育改革，不仅仅是教育思想的更新和进步，也是教育技术和手段的 改进和提高。而在各种教育机构的教学过程中，考试都是一个非常重要的环节， 考试工作组织的好坏直接关系着教学质量的评价。传统的考试，长期以来都是以 纸和笔为媒介工具，在命制试题、组织考试、统计分数的过程中，工作效率低、 纸张浪费大，花费大量的时间、人力和物力。其中不可避免的存在大量的重复劳 动，而且很难避免人为因素对考试造成的影响。因此，考试方式的改革己迫在眉 睫。当今各项技术突飞猛进，尤以计算机技术的发展最为突出，在这种双重因素 的作用下，以计算机技术为主的无纸化考试应运而生。 所谓无纸化考试也就是利用计算机及相关技术，通过建立庞大的试题库、利 用智能方式组卷、机上无纸考试、自动阅卷等工作，取代传统的基于纸和笔的考 试方式。其出题方便快捷、阅卷准确快速、成绩分析科学直观等主要优势是传统 的考试方式不可比拟的【。 试题库与计算机技术相结合就是电子试题库l2 1 ，这种试题库便于海量试题的 存储、使用和修改，更便于试题和试卷的难度划分、知识点的运用和试后分析等。 试题库的出现和发展显示出强大的生命力，在教学活动中发挥了重要作用，不仅 弥补了传统教学的部分缺陷，而且将计算机在教学管理中的应用推向了一个新的 阶段，引起了计算机界和教育界广泛的兴趣和重视。国外许多国家，试题库系统 己开始应用于各个教学阶段，特别是大、中学的考试和作业以及正迅猛发展的远 程教育等方面的应用，收到了显著的效果。 试题库不仅是一项网络数据库技术，而且是一种实实在在的产品，一项很有 前途的有利于促进教育发展的服务，也是竞争非常激烈的一个领域【引。现在的试 题库都是以专业应用为主，其技术一般都是保密的，所以在试题库领域存在各自 为战的局面。目前试题库系统存在的种种缺陷己经不能适应需求。 目前，国内外基于网络远程教学的迅速发展，迫切需要一个支持远程教学的 山东师范大学硕士学位论文 专用平台，网络试题库系统是实现这种教学平台的基础和工具。网络试题库系统 为试题的保存、分类和检索提供了科学、有效的方式，为编制科学、公正的试卷 提供了高效率和低成本的手段。 1 2 相关研究及现有题库状况 随着信息技术的高速发展以及网络技术的日趋成熟，以互联网为主要手段的 现代远程教育已成为当今教育发展的趋势。目前，美国已有6 0 的高校开展了现 代远程教育，其开设的学位、学历课程基本覆盖了美国高等学校的所有学科和专 业，通过网络学习的人数正以每年3 倍的速度增长。德国有近1 0 0 所学校开设了 网络课程教育鸭英国提出将普及网络化教育作为保证英国人才培养紧跟世界潮 流的战略性举措。 在国内，教育部提出实施“现代远程教育工程，形成开放式教育网络，构 建终身学习体系。在面向2 1 世纪中国网络教育发展战略的构想中，国家大 力强调了网络教学资源的建设，把发展网络教育作为国家信息化的一项基本国 策，加大对网络教育的投入，同时借鉴网络教育发达国家( 地区) 的成功经验，为 网络教育营造宽松环境。在现代远程教育实施的过程中，教育部强调要不断加强 现代教育技术的研究与应用，加快教学资源的建设，积极探索现代远程教育的人 才培养模式和教学管理制度1 5 】。 目前，在英国，已经实现了英语资格考试的网上学习和水平认证的全过程。 国内也有认证考试是完全通过基于w e b 的在线考试系统来完成的。如n i i t ( 印 度国家信息学院) ，是全球最大的信息技术教育培训和提供i t 解决方案的跨国公 司之一，已在中国开展的相关培训，自2 0 0 4 起全面实行其学生用网上在线考试 系统进行考试。国内一些高校及科研单位也开发了各门各类的基于试题库的在线 考试系统投入实际应用【4 】1 6 】。 国内外的许多科研单位、学校机构都对组卷系统进行了研究。虽然组卷系统 是个被探讨了很长时的问题，但至今也没有一个很好的解决其自动出题的算法方 案。组卷问题是一个带约束的多目标优化问题【3 】，采用经典的数学方法很难解决 这个难题，自动组卷的效率和质量很大程度上取决于选题算法的设计。如何设计 一个算法从试题库即快又好的抽出一组最符合考生要求的试题，涉及到一个全局 2 山东师范大学硕士学位论文 寻优和收敛速度快慢的问题。以往的有自动组卷功能的考试系统大多采用随机选 取法和回溯试探法，虽然都能最终组出试卷，但都存在不足和缺点 随机选取法根据状态空间的控制指标，随机的抽取一道试题放入试题库f 7 1 ， 此过程不断重复，直到组卷完毕，或已无法从题库中抽取满足条件的试题为止。 该方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说 组卷成功率低，即使组卷成功，花费时间也很长，组卷往往以失败告终。 回溯试探法是将随机选取法产生的每一状态都记录下来，当搜索失败时释放 上次记录的状态类型，然后再依据一定的规律( 正式这种规律破坏了选取试题的 随机性) 变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完 毕或退回出发点为止【7 】【8 1 ，这种有条件的深度优先法，对于状态类型和出题量都 较小的题库系统而言，组卷成功率较好，但是在实际到一个应用时发现这种算法 对内存的占用量大，程序结构相对比较复杂，而且选取试题缺乏随机性、组卷时 间长。而选取试题缺乏随机性、组卷时间长这两点是用户无法接受的，因此它不 是一种很好的用来自动组卷的算法。 分析上述两种算法的优缺点，不难发现，在限制条件和状态空间的限制下， 随机选取法有时能够取出一组令用户满意的试题，只不过由于它随机选取试题的 范围太大，无法确定目前条件下那些区域能抽出合适的试题，反而可能在那些已 经证明是无法抽取合适的试题区域内反复选题，进行大量的无效操作进入死循 环，最终导致组卷失败8 ：i 【9 】。回溯法组卷成功率高，但它以牺牲大量的时间为 代价，对于现在越来越流行的考生网上随机即时调题的考试过程来说，它己不符 合要求。 由上分析我们知道必须结合以上几种方法寻求一种新的改进算法。这种算法 要具有全局寻优和收敛速度快的特点。遗传算法( g e n e t i ca l g o r i t h m s ) 其具有自 适应全局寻优和智能搜索技术，并且收敛性好的特性能很好满足自动组卷的需要 2 1 7 1 l l o l 。 1 3 研究的可行性 首先，作为一种科研与管理的工具，计算机技术的应用已经进入社会经济与 山东师范大学硕士学位论文 生活的各个领域了，特别实在相关的教育部门，已经具备了很好的硬件基础，使 我们能够突破传统的考试模式，实现无纸化考试的研究。同时，适应计算机网络 教学的要求，也进一步要求要建立起配套的软件环境来更好地进行教育教学的改 革。 而相关的软件环境也使进行试题库设计与自动组卷的要求成为现实：管理数 据技术的发展日新月异，数据管理的效率越来越高，比如，应用很广的o r a c l e ，s q l 等系列产品，能够很好地满足对大型数据库的管理工作，能够应付各种各样的应 用环境与不同级别用户的使用。而且，对试题库组卷算法的研究也早日呈现 出蓬勃发展之态势，相关的研究在人工智能、知识库、模糊搜索技术等不同领域 都有很好的成果。 综合各方面的有利条件，结合实际工作的要求，提出试题库设计与相关算法 的研究是充分的，经过努力是应该能够实现的。 1 4 本文的主要工作 本文研究的主要内容如下 自动组卷数学模型的研究 自动组卷算法实现的关键在于构建合理的自动组卷模型。组卷过程实质上是 一个多重属性约束条件下复杂的多目标寻优过程引 1 3 l 。将用户对试题数量、试题 难度等属性的要求进行量化，建立试卷模式，得到各个属性的分数分布列，这些 分布列联立起来就构成了自动组卷的数学模型。 自动组卷数学模型的求解 自动组卷模型是一个多目标优化的数学模型，模型结构复杂，能否正确、快 速求解成为关键内容，常规的求解多重约束条件下的高维方程组，在理论和实践 上都有一定的难度【1 引。本文首先利用权重系数法将多目标优化转化成单目标 优化的模型，然后运用自适应遗传算法对其进行求解。由于遗传算法具有较好的 全局寻优能力，相对传统的方法而言，可以快速而准确的得到较优解。本文的主 要工作就是在充分掌握遗传算法的基本原理的基础上，就遗传算法的改进进行了 研究 4 山东师范大学硕士学位论文 选用实现的相关技术 在充分考虑试题库应用环境的基础上，结合当前的计算机相关技术的发展， 学习并使用了当前比较简便和安全的c 群语言及数据库系统中的代表性工具s q l 来开发实现相关算法与应用。 山东师范大学硕士学位论文 2 1 理论分析 第二章自动组卷系统的理论基础 自动组卷在本质上就是利用一定的组卷算法，自动地从题库中抽取合适的试 题，使它们组成的试卷既能满足教学要求又能达到考试单位的目的要求。 如何自动地抽取试题呢? 这就是组卷算法要解决的问题，也是组卷系统的核 心问题。要想让组卷系统能按用户要求自动地抽题，首先必须要让系统了解用户 要求。用户对试卷的要求往往是模糊的，组卷算法首要解决的问题就是将这种模 糊的要求量化，转化成计算机可以理解的要求，也就是将用户的要求转化成对试 卷指标的具体要求 j s j ，如考试目的、考试时间、难度要求、教学度要求、知识 考察范围等等。知道了用户对系统的这些指标的要求后，我们就只需要找到满足 这些指标、要求的试题即可。 如何找到这些试题呢? 一般有两种思路。一种是先从试题库中抽取试题，抽 出试题后再验证它们是否和这些指标要求相符合，若符合了，抽出的这些题就可 以组成满足用户要求的试卷；若不符合了，则继续抽取试题继续验证，直到符合 为止。另外一种就是先分析这些指标要求，我们就会发现用户对这些指标的要求 是和用户对每一道试题的要求联系在一起的，因此我们可以根据这种联系建立试 卷模式，试卷模式就是用户要求的一种定量反映。我们可以根据试卷模式分析出 哪些试题的组合可以满足这个模式的要求，然后再在试题库中找到这样的试题即 可。后一种算法的思路显然可以避免盲目抽题，而且由于不需要多次遍历试题库， 也因此减少了抽题的时间。 但是根据试卷模式如何分析出满足试卷模式的试题组合呢? 这是后一种思路 的难点，也是后一种组卷算法的核心和关键【2 1 1 6 1 。以前有许多组卷系统都采取前 一种算法思路，这种算法有许多明显的缺点。而我们在上述试卷模式的基础上建 立了一个最接近用户要求的多目标优化的数学模型，然后对试卷模型进行求解， 求出的解即是满足当前试卷模式下的各道试题的具体指标要求值，然后在题库中 找到和这些指标值相符合的试题即可。 6 山东师范大学硕士学位论文 简单的说，组卷算法的原理就是：首先将用户要求量化成试卷模式，然后基 于试卷模式建立组卷的数学模型，并对模型进行求解，最后根据求出的解在试题 库中找到和求出的解一致的试题即完成了组卷【3 】【17 1 。 2 2 经典测量理论的内容 一、教育测量与教育统计理论 教育测量与教育统计理论是试题库设计所依据的测试理论【3 】1 1 8 1 。 试题库系统是目前迅速发展的计算机辅助教学的有利的工具，是计算机科 学、教育测量理论科学相结合的产物。试题库是按照一定的教育测量理论，在计 算机系统中实现的某个学科题目的集合，是严格遵循教育测量理论，在精确的数 学模型基础上建立起来教育测量工具 所谓测试是指通过一定的仪器和试题对受测者的行为样本进行测试的系统 程序5 1 【1 9 】。考试作为一种教育测量与评价的术语，是用于较正式场合下的测试， 完全适用测试理论。目前广泛应用的测试理论主要有两种i 经典测试理论 ( c l a s s i c a lt e s tt h e o r y ) 和厢目反映理论( 1 t e mr e s p o n s et h e o r y ) 2 0 1 ，与之相对 应的，就是现今所广泛采用的标准化测试和自适应测试。 学科体系与教育目标分类理论将决定整个题库及生成试卷的内容效度，是甄 选试题的根本依据，试题库的整个框架结构就要按照这个要求来设计与建造的。 教育目标的分类一般是采用布卢姆的六类方法【2 0 】。 美国教育家布卢姆将认知活动的教育目标划分为六类。识记：指认知和回 忆事实、规则或概念的能力。理解二指理解事实和概念的能力。它包括解释事 实和原理、法则、图表、图象，对要点作出分类、摘要、归纳，将材料由一种形 式转换成另一种形式。应用：指利用事实和概念解决新问题的能力。它包括将 概念、原理、法则、定律等应用到实际中，解答试题，绘制图表和图象，方法和 程序的正确使用与演示等。分析：指辨别整体中的各个局部并认识其相互联系 的能力。它包括对各组成部份的辨认，对各部份之间相互关系的分析，对把各部 份组合起来的原理法则的识别等。综合：指把有关局部综合成新的整体能力。 7 山东师范大学硕士学位论文 包括综合运用知识以解答问题，制定计划或提出方案等。评价判断，比较不同 方法、结果等的能力。 二、经典测量理论的内容9 】【1 4 】 1 、成绩分析 平均分数 平均分数是用得最多的一种集中量数。所谓集中量数是指反映分数集中位置 这个特征的数值，它代表一批分数，反映一批分数的典型情况，因此常用它进行 不同分组之间的比较。集中量数的形式有多种，如算术平均数、中位数等。算术 平均数则是最常用的一种，通常用x 来表示。 x = + x 2 + + x ，2 其中x 1 ，x 2 ，x 。表示n 个学生在某一次考试中的成绩，i 表示的是这次考试 的算术平均值。简记为： 方差、标准差 x= f ，厶 石 f - l 对于一批分数，除了要了解它的集中量数外，还要了解它的差异量数，即表 示分数的离散程度，方差和标准差是用得最多的。 若有n 个学生的成绩为x 1 ，x 2 ，x n ，；是他们的平均分，s 2 表示方差， 则 s 2 = ! n ( 五一面2 刀鲁一 7 将方差开方就得到标准差： 山东师范大学硕士学位论文 s = = s 越大就表示分数的离散程度越大。 2 、项目分析 除了对考试成绩的分析外，还要对试卷中的各个试题进行分析。在教育测验 中，通常对考试的分析与评价分两方而进行。一是对各个试题进行的分析，称为 “项目分析”，二是对整个试卷或考试进行的分析或评价，称为“整体分析”。 学业成绩测验可以用来衡量学生的相对水平，也可用于衡量学生的实际水 平。在教育测量中，把用于测量学生相对水平的测验叫做常模参照测验；把用于 衡量学生实际水平的测验叫做目标参照测验【1 4 】。 由于存在着常模参照测验和目标参照测验，对项目分析和整体分析也有不同 的要求。常模参照测验的项目分析包括难度分析和区分度分析。 难度分析 一道试题的难度是表示考生解答该题的难易程度的指标。试题的难度值是用 考生对该题的失分率来表示的，失分率越高，难度也就越大。确定试题难度的方 法有多种，其中一种常用的方法是利用下式计算： p 一 ；一 i 1 一旦 其中：e 表示第i 题的难度，s ，e 分别为考生的第i 题的平均分和第i 题 的满分分数。 如果有n 个学生，则可利用下式，由考生在第i 题上的得分直接求得第i 题 的难度。 有了试卷每个题的难度与分值，就可以由下式求出整个试卷的难度 9 山东师范大学硕士学位论文 4 n d = 掣- 一( z = 0 , 1 ，聊) 掰 、77 ， 只 i = 1 其中n d 为试卷的整体难度，1 1 是试卷所含的题目数，p i ，d j 分别是第i 道题 组卷时用户可以指定所抽取试卷的平均难度( 为某一确定值) 。 试题的区分度就是鉴别度，就是试题在用于考试时，使水平高的考生得高分、 水平低的学生得低分的倾向力犯o 】【2 2 】。区分度好的试题能够把不同水平的被试者 q 2 ( h l ) 伊 式中h 为高分组学生在该题的平均分，l 为低分组学生在该题的平均分，f q = 瞽i - - 1 刁产 夕 其中q 为全卷的区分度，q 为第i 道题的区分度，f 为第i 道题的满分值， 组成的试卷应该能够区分出不同水平的学生的能力，全卷的区分度不应该太 1 0 山东师范大学硕士学位论文 低，不然不同考生的分数都趋近于一致，达不到考试的目的。每道试题的区分度 事先由有经验的教师确定，并根据考生的考试成绩不断调整。 一般评测标准：0 9 以上为优秀题目：0 3 0 9 为良好题目；0 2 0 2 9 为勉强 合格；0 1 9 以下为差的题卧2 】。 山东师范大学硕士学位论文 第三章系统分析和试题库设计 3 1 自动组卷的系统分析 一、系统需要解决的主要问题 传统的计算机自动组卷方法是在题库中随机搜索满足条件的试题，直到试题 总分数满足要求，该方法具有很大的随机性和不确定性，无法从整体上把握教育 的要求，不具有智能性。为了保证智能组卷的可用性，必须分析研究在用户给定 基木约束条件( 如总难度系数、考试范围等) 下，如何设计科学的模型和算法，保 证组卷的合理性及科学性，同时，要保证系统高效可用。本系统采用了遗传算法 解决智能组卷问题。 二、系统功能要求 系统需要一个高效共享的标准化题库，来保存试题信息。用户应该能对题 库进行有效的管理，对题库进行维护和管理，如添加新的试题，对选定的试题进 行修改或删除等。试题类型可为单选题、填空题和概念题等。 用户可用智能组卷系统进行自动组卷，设置一定的参数，如各章节的考察 比例、难度分值比以及各类题型的题数和分值等，组卷系统根据用户设置的条件 来组成一份满意的试卷。输出供考试使用。 对于在线考试，考生登录后可以在限定的考试时间答题，时间到时强行交 卷。为保证学生的答案能及时保存，应该设置自动保存的功能等。 对于已经提交或结束的考试试卷，进行尽可能准确的评阅，各项( 各题型) 评阅成绩也要有所保留，以供在考试后对试卷进行分析统计之用，避免日后做重 复性的输入工作。 在整个过程中，对数据及程序的控制要做到安全、高效。数据的存储、查 询要方便快捷，程序流程清晰简洁，并且由于考试形式及内容的不断变化，系统 要有很强的开放性和可扩展性，在开发过程中，使用o o p ( o b j e c t i v eo r i e n t e d p r o g r a m ) 的方法来开发。 3 2 自动组卷的问题分析 自动组卷是考试系统自动化或半自动化操作的核心目标之一，而如何保证生 山东师范大学硕士学位论文 成的试卷能最大程度的满足用户的不同需要，并具有随机性、科学性、合理性， 这是实现中的一个难点。尤其在交互式环境下用户对于组卷速度要求较高，题目 应具有多样性，因此一个良好的组卷系统对于考生考试来说起着非常重要的作 用。 组卷系统首先要了解考试的要求，然后应用组卷经验知识，确定考试的要求 特性，设计出相应的试卷模式，再按试卷模式选取试题组成试卷。对于组卷系统 来说，它要符合一定的约束和规范，对生成的试卷进行测试主要是使生成的试卷 满足有效考试的条件、考试的信度和效度、组卷系统的评价标准等。 组卷的目的是生成一份用于考试的试卷。组卷的初始阶段是用户输入对要生 成的试卷的具体要求，然后计算机就根据一定的算法去抽取试题，把这些抽取出 来的试题和评判条件相比较，如果评判不通过则重新选题，通过，则编排试题、 打印试卷供考生考试。在进行出题之前，我们必须对问题的特征进行具体的分析， 才能设计出合理的组卷系统。 对组卷问题来说，可规约为以下内容，也即组卷的特点。 数据的不精确性、模糊性 组卷系统是要从一些已有的试题中找出一部分满足用户要求的试题合成一 份试卷，首先要对系统中的数据格式与内容有所明确，比如，试题正文以及相应 的试题答案等。另外，明确试题的排列方式，如果试题是无规则的排列的话，则 无法进行搜索或者搜索的难度很大，所以必须有一些描述这些试题的指标数据。 而这些指标数据有二些是明确的，比如分数、题型等，但有些数据也是一个比较 模糊的概念，比如，难度等级，特别地，还有些数据需要测试得到，比如解答该 题所需要的时间等。因此，系统中的数据不是单一的精确数据，有的具有模糊性。 2 3 1 解的多样性 组卷是一个状态空间的问题的求解过程，初始数据为用户输入的试卷要求， 问题的结果为一份满足要求的试题。由于题库中的试题很多，一般情况下能满足 用户要求的试题有许多，即问题的解空间是相当大的，这样就会在相同的条件下 组出内容不同的多份试卷。 知识的特征 山东师范大学硕士学位论文 对于组卷系统来说，因为知识大都来源于成卷专家的经验，因此不可避免的 会出现以下的问题：不同的专家有不同的成卷经验，一个专家所认同的经验，可 能另一个专家不接受或者否定；有些专家经验也许对某一部分内容是有效的，但 对于其它部分却无效；随着时间的推移、环境条件的变化，原来有效的经验变得 无效。同时，软件的研究过程本身就是在不断的总结专家经验，吸取专家错误的 基础上进行的，所以以往的组卷系统都存在着不能及时更新等不完善性，因此， 在试题库系统的维护过程中就必须不断的更新知识、增减知识、完善知识，使得 系统能尽量产生符合要求的高质量的试卷。 3 3 试题库的结构设计 一、数据库设计 题库建设是一项相当艰巨的系统工程。要建设一个题库，一般要包括以下几 个步骤： 题库的结构设计】 2 4 】。包括题目的各属性值及度量标准的设置等。 试题的收集与编制。前面的分析中己经指出，为了使题库更加科学化、标 准化，题库必须具有大量的、高质量的试题，而题目的来源主要有两个方面：一 是收集正在大量使用的优秀试题，二是组织专家专门命题。 确定各个试题的属性值。这一步是题库开发中极为重要的一步，因为以后 试卷的生成主要依靠题目的这些属性值来确定选择哪些题目加入到试卷中。生成 的试卷的质量在很大程度上取决于题库中各个试题指标的可靠性。 题目存储工作。一般题库的规模都比较大，少则几千道题，多则上万道题， 这就要求我们使用紧凑、安全、高效的题目存储方式，并且要设计一个方便灵活 的题目输入界面，以方便把试题存储到数据库中。 题库中的题目维护。题库应具有动态性，应随情况的变化而变化。这是因 为各门学科都在发展变化，学科内容也应不断更新，需要不断的删除、修改、增 添试题。另一方面，考生水平也在不断地变化，这样考试参数及考核能力层次也 会有所变化。因此要使题库能更好的服务，就应该提供试题的增加、修改、删除 等功能。 二、试题库属性结构 1 4 山东师范大学硕士学位论文 题型一般有选择题、判断题、填空题、操作题、概念题，论述题。在题库管 理中，将每种题型定义为一个单独的表，每种题型一张表，这样有利于提高算法 的实现效率。 尽管采用的是各种题型在试题库中分别保存的方式，其实各表的结构是完全 是相同的，下表各表的的属性表： 表格1试题库中各种题型统一的属性结构 属性类型备注 i d 自动编号主码 s u b j e c t 文本题干 s c o r e 文本本题分值 d i f f i c u l t 文本难度 d i s t i n c t i o n文本区分度 k n o w le d g e文本知识点 p u t d a t e 日期出题日期 a n s w e r 文本答案 t i m e 文本答题时间 l a s t i m e 文本上次使用时间 w r i t e r 文本出题人 其中： i d 属性为主码属性，由系统自动生成，最大值表示本题型的题目数，且随 题目的录入自动增加，兼有题号的功能。 s c o r e 为建议分值，本试题在一份标准试卷上所占的分数值。这里所说的标 准试卷应符合下述三条要求：考试时间为1 2 0 分钟；试卷的满分值为1 0 0 分；用于学期结束评定学生成绩的考试( 总结性考试) 。 d i f f i c u l t 为难度系数属性，难度系数反映试题的难易程序的指标。在试题库 建设的初期，由用户根据经验设置，以后可以根据实际测试情况逐步修正。本试 题库试题的难度系数分为4 个级别。在具体的实现界面中，用户只需要在“简单”、 山东师范大学硕士学位论文 “一般，“较难 ，“难 中选择，系统会自动取其所对应的具体数据。 d i s t i n c t i o n 为区分度：根据测量学理论，对于一道试题，如果q = 0 3 认 为区分度比较好，q 值太小时，表明该题太易或太难，此时这道题已无法区分考 生的水平1 2 j 。对于选拔性考试，其目的是考察学生对一些基本知识的掌握情况， 区分度这个指标就非常重要。严格来说，区分度应该通过测试后才得到，但对每 题进行实测存在技术困难，而且实测的信度难以保证，因此，类似难度指标，我 们采用预先给定经验值，在实际的环境中可进一步精确。 t i m e 为学生解答该题所需的时间( 分钟) 的预估值，包括了下面三个时间之 和：读题、审题所需的时间，进行解答书写的时间，可能的检查时间。 l a s t i m e 为最近使用时间：指最近一次使用该题的日期，可以控制一道试题 出现的时间间隔，避免出现雷同的试卷。 w r i t e r 项：出题人项，可在试题库建设中作为教师工作量统计等工作的参 考。 1 6 山东师范大学硕士学位论文 第四章自动组卷系统的算法设计原理 4 1 遗传算法理论与相关学科技术 遗传算法的基本思想是基于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 6 1 【1 9 l ，所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因 杂交可产生更适应于环境的后代，经过存优去劣的自然淘汰，适应性高的基因结 构得以保存下来。 而遗传算法( g a ) 是由美国j h h o l l a n d 教授于1 9 7 5 年首先提出来的，采用简 单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操 作和优胜劣汰的自然选择来指导学习和确定搜索的方向f 1 8 】 4 1 1 。其主要特点是群 体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，因而对目标 函数没有可微的要求( 目标函数可以是离散的) 。它能根据不同环境产生不同的后 代，具有动态性，自适应性【3 1 1 4 4 l ，从而满足题库不断变化的需求。遗传算法同时 具有内在的并行性，能有效的解决计算量大的问题，它具有全局寻优和收敛速度 快的特点，这些都适宜于处理试题库自动组卷的问题。 一、遗传算法的基本概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，故而在 这个算法中要用到各种进化和遗传学的概念。这些概念如下1 3 】| 8 】f 4 5 ：| ： 争( s t r i n g ) 串是个体( i n d i v i d u a l ) 的形式，在算法中为二进制串，并且对应于遗传学中的 染色体f c h r o m o s o m e ) 。 群体( p o p u l a t i o n ) 个体的集合称为群体，串是群体的元素。 群体大小( p o p u l a t i o n s i z e ) 1 7 山东师范大学硕士学位论文 在群体中个体的数量称为群体的大小。 基因( g e n e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串s = 1 0 1 1 ，则 其中的l ，0 ，1 ，1 这4 个元素分别称为基因。它们的值称为等位基因( a l l e t e s ) 基因位置( g e n e p o s i t i o n ) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的 左向右计算，例如在串s = 1 1 0 1 中，0 的基因位置是3 。基因位置对应于遗传学中 的地点( l o c u s ) 。 基因特征值( g e n e f e a t u r e ) 在用串表示整数时，基因的特征值与二进制数的权一致。例如在串s = 1 0 1 1 中，基因位置3 中的1 ，它的基因特征值为2 ；基因位置1 中的l ，它的基因特 征值为8 。 串结构空间( s s ) 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。 串结构空间对应于遗传学中的基因型( g e n o t y p e ) 的集合。 参数空间( s p ) 这是串空间在物理系统中的映射，它对应于遗传学中的表现型( p h e n o t y p e ) 的集。 非线性 它对应遗传学中的异位显性( e p i s t a s i s ) 。 适应度( f i t n e s s ) 表示某一个体对于环境的适应程度。 二、遗传算法的特点 遗传算法的特点有： 遗传算法从问题解的集合开始嫂索，而不是从单个解开始。 这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭 代求最优解的；容易误入局部最优解。遗传算法从串的集合开始搜索，覆盖面大， 利于全局选优【7 l 1 19 1 4 9 1 。 山东师范大学硕士学位论文 遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序【4 6 1 。 由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直 接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问 题。 遗传算法有极强的容错能力。 遗传算法的初始串集本身就带有大量与最优解甚远的信息，通过选择、交叉、 变异操作能迅速排除与最优解相差极大的串，这是一个强烈的滤波过程；并且是 一个并行滤波机制【2 。故而，遗传算法有很高的容错能力【4 7 1 。 遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。 遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉 体现了最优解的产生，变异体现了全局最优解的覆盖蚴【2 3 】 4 5 1 。 遗传算法具有隐含的并行性【l o 】 4 8 1 遗传算法的特点使其内在地具有并行处理的性质。 4 2 遗传算法的基本构成要素与算法描述 一、根据遗传算法的理论，试题数据库结构要符合以下要求： 试题数据库要易于遗传算法操作，题库中的题目按题型分类。 题库的题量必须足够大，比例合理。如果题量太小，就难以生成让用户满 意的试卷，试题的类型比例要合理科学，知识点要分布均匀。 题库中的每一试题由两部分组成，即题目属性指标和题目本身。题目属性 指标有多项，反映有关题目的多种信息，这些信息要能够全面客观反映试题的本 质，并将某一题目与库中的其它题目区别开。 二、遗传算法的基本原理 长度为l 的m 个二进制串组成了遗传算法的初解群，也称为初始群体。在 每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的 操作有三种【2 】【4 2 1 ： 选择( s e l e c t i o n ) 这是从群体中选择出较适应环境的个体。这些被选中的个体用于繁殖下一 代。故有时也称这一操作为再生( r e p r o d u c t i o n ) 。由于在选择用于繁殖下一代的 1 9 山东师范大学硕士学位论文 个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀 再生( d i 航r e n t i a l r e p r o d u c t i o n ) i ：4 3 】。 交叉( c r o s s o v e r ) 这是在被选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基 因进行交换，从而产生新的个体。 变异( m u t a t i o n ) 这是在被选中的个体中，对个体中的某些基因执行异向转化。在串中，如果 某位基因为1 ，产生变异时就是把它变成0 ；如果为1 ，则变成0 。 遗传算法的原理可以简要概述如下： 遗传算法是一种群体型操作，该操作以群体中的所有个体为对象，选择、交 又和变异构成的遗传操作，使遗传算法有了其它传统方法所没有的特征。遗传操 作的设计与参数编码、初始群体的生成、适应度函数的设计、控制参数设定一起 构成了遗传算法的核心内容，一般将它们称之为遗传算法的五大要素1 6 1 。 三、遗传算法的基本步骤如下： 根据具体的环境构造一定编码方案f ； 按编码方案的结构随机产生一个初始种群； 用相应的解码方法，将编码后的个体转换成问题空间的决策变量，并求得 个体的适应值； 按照个体适应值的大小，从种群中选出适应值较大的个体构成交配池； 由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代 的种群； 反复执行步骤固，直至满足收敛判断为止。 其流程图表示如下： 山东师范大学硕士学位论文 图1 ：遗传算法的基本步骤的流程图 4 3 改进的遗传算法 一、遗传算法需要决定的运行参数 使用遗传算法需要决定的运行参数有：编码串长度、种群大小、交叉和变异 概率【2 = i 】。 编码串长度：由优化问题所要求的求解精度决定。 种群大小：表示种群中所含个体的数量，种群较小时，可提高遗传算法的 运算速度，但却降低了群体的多样性，可能找不出最优解；种群较大时，又会增 加计算速度，使遗传算法的运行效率降低。一般取种群数目为2 0 1 0 0 。 交叉概率：交叉概率控制着交叉操作的频率，由于交叉操作是遗传算法中 产生新个体的主要方法，所以交叉概率通常应取较大值；但若过大的话，又可能 破坏群体的优良模式，一般取0 4 - 0 9 9 。 变异概率：变异概率也是影响新个体产生的一个因素，变异概率小，产生 新个体少，变异概率太