（计算机应用技术专业论文）在线考试系统中组卷算法和题库的设计与实现.pdf

独创性声明 y 1 7 8 9 d 犁苕 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：亟西且日期：2 塑互：篁 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：烈石压导师签名： 日期：地星： 摘要 摘要 随着互联网在国际上迅猛的发展，基于互联网的各种应用也日益受到人们的 重视，特别是现代远程教育得到了巨大的发展。基于w e b 的考试系统正是在这种 形势下应运而生的。尽管传统的考试形式应用还非常普遍，但伴随着远程教学的 推广普及，作为远程教学系统子系统的在线考试系统呼之欲出 在考试系统中，自动组卷是关键的部分随着人工智能的快速发展，这个问题 已经被越来越多的科学家所关注计算机自动组卷的实质就是遵循一定的选题策 略，从试题库中选出一组试题，使得它们所有的属性都在一定的取值范围内满足 出卷人所期望的指标，其核心问题是多目标选题策略；题库设计也是考试系统中 一个非常重要的部分，题库设计的好坏将直接影响自动组卷的效果。 本文主要设计并实现了一个在线考试系统，功能包括在线考试、试题管理和 维护、自动组卷、阅卷评分、查看成绩和学生信息管理等功能，重点研究了自动 组卷算法和题库设计方案，结合在线考试系统的特点，给出了在线考试系统的组 卷算法和题库设计方案。 组卷算法是研究的重点所在，文中在分析国内外大量文献的基础上，借助了 遗传算法这一智能优化算法来解决组卷问题。文中对算法进行了详细的设计和分 析，并对编码结构、交叉算子和变异算子进行了富有特色的设计，使遗传算法满 足组卷这一特定问题的要求。 关键词考试系统；自动组卷；题库；遗传算法 北京工业大学工学硕士学位 i i a b s t r a c t a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to fi n t e m e ti nt h ei n t e m a t i o n a l ，m o r ea n dm o r e w e b - b a s e da p p l i c a t i o n sw e r ei n c r e a s i n g l ys u b j e c tt op e o p l e sa t t e n t i o ni nr e c e n ty e a r s ， a n dt h em o d e md i s t a n c ee d u c a t i o nh a sb e e nt r e m e n d o u sd e v e l o p m e n t t h ew e b b a s e d e x a m i n a t i o ns y s t e mi se m e r g e di ns u c has i t u a t i o n a l t h o u g ht h et r a d i t i o n a lf o r mo f e x a m i n a t i o ni sa l s ov e r yc o m m o n ，w i t ht h ee x p a n s i o na n du n i v e r s a l i t yo fd i s t a n c e l e a r n i n g ，t h eo n l i n ee x a m i n a t i o ns y s t e mc o m ei n t ob e i n ga sas u b s y s t e mo fd i s t a n c e l e a r n i n gs y s t e m a u t o m a t i cg e n e r a t i n gp a p e ri sac r u c i a lp a r ti nt h ee x a m i n a t i o ns y s t e m w i t ht h e r a p i dd e v e l o p m e n to fa r t i f i c i a li n t e l l i g e n c e ，t h i si s s u eh a sb e e nag r o w i n gn u m b e ro f s c i e n t i s t sc o n c e r n e d a u t o m a t i cg e n e r a t i n gp a p e ri st h er e a lf o l l o wa s t r a t e g yo ft o p i c s ， a n ds e l e c tag r o u po f q u e s t i o n sf r o mt h eq u e s t i o n s ，m a k e st h e ma l lt h ep r o p e r t i e sa r e w i t h i nac e r t a i nr a n g eb yv o l u m et om e e tt h ee x p e c t a t i o n si n d e x t h ec o r eo ft h e p r o b l e mi sm u l t i - t a r g e ts t r a t e g yo fc h o i c e t h ed e s i g no ft e s tq u e s t i o n sd a t a b a s ei s a l s oav e r yi m p o r t a n tp a r ti nt h ee x a m i n a t i o ns y s t e m ，a n dt h ed e s i g no ft e s tq u e s t i o n s d a t a b a s ei sg o o do rb a dw i l ld i r e c t l ya f f e c tt h ee f f e c t i v e n e s so fa u t o m a t i cg e n e r a t i n g p a p e r t h et e x td e s i g n sa n di m p l e m e n t sa no n - l i n ee x a m i n a t i o n s y s t e m ，a n di t s f u n c t i o n si n c l u d eo n - l i n ee x a m i n a t i o n s ，t e s tm a n a g e m e n ta n dm a i n t e n a n c e ，a u t o m a t i c g e n e r a t i n gp a p e r , g r a d i n ge x a m i n a t i o np a p e r sa n dg r a d i n gp o i n t ，s e e i n gr e s u l t sa n d i n f o r m a t i o nm a n a g e m e n tf e a t u r e ss u c ha ss t u d e n t se t c i tf o c u s e so nt h ea u t o m a t i c g e n e r a t i n gp a p e ra r i t h m e t i ca n dt h ep r o je c to fd e s i g n i n gt e s tq u e s t i o n sd a t a b a s e ，a n d g i v e st h eg e n e r a t i n gp a p e ra r i t h m e t i ca n dt h ep r o j e c to fd e s i g n i n gt e s t q u e s t i o n s d a t a b a s ei no n - l i n ee x a m i n a t i o ns y s t e mi n t e g r a t i n gt h ec h a r a c t e r i s t i c so ft h eo n l i n e e x a m i n a t i o ns y s t e m g e n e r a t i n gp a p e ra r i t h m e t i ci st h ef o c u so ft h er e s e a r c h ，a n do nt h eb a s i so fi na l a r g en u m b e ro f d o m e s t i ca n di n t e r n a t i o n a ll i t e r a t u r e ，t h i st e x tu s eag e n e t i ca r i t h m e t i c a sai n t e l l i g e n c ea n do p t i m i z a t i o ng e n e r a t i n gp a p e rt os o l v et h ep r o b l e mo f g e n e r a t i n g p a p e r a r i t h m e t i ci sc a r r i e do nt h ed e t a i l e dd e s i g na n da n a l y s i si nt h et e x t ，a n dc o d i n g s t r u c t u r e ，c r o s s 。o p e r a t o ra n dm u t a t i o no p e r a t o ra r ec a r r i e do n ad i s t i n c t i v ed e s i g n ，a n d m a k et h eg e n e t i ca r i t h m e t i ct om e e tg e n e r a t i n gp a p e ra st h er e q u i r e m e n t so ft h i s p a r t i c u l a ri s s u e - i i i 北京工业大学工学硕士学位 k e y w o r d se x a m i n a t i o ns y s t e m ；a u t o m a t i cg e n e r a t i n gp a p e r ；t e s tq u e s t i o nd a t a b a s e ； g e n e t i ca l g o r i t h m 目录 目录 摘要i a b s t r a c t 1 1 i 第1 章绪论。1 1 1 在线考试系统的现状1 1 1 1 在国外的发展状况l 1 1 2 在国内的发展状况l 1 1 3 当前在线考试系统的特征2 1 2 本课题的来源2 1 3 本文主要内容3 1 4 本章小节3 第2 章组卷算法与题库的研究5 2 1 组卷算法理论5 2 1 1 随机选取法和回溯试探法5 2 1 2 遗传算法5 2 2 在线考试系统的组卷算法8 2 2 1 组卷算法的确定8 2 2 2 组卷参数定义9 2 2 3 基于遗传算法的组卷算法设计1 1 2 3 题库基础理论1 4 2 3 1 题库的概念1 4 2 3 2 题库的特征1 4 2 3 3 题库的建设理论1 5 2 3 4 题库建设步骤1 5 2 4 在线考试系统的题库建设方案1 6 2 4 1 在线考试系统的题库建设步骤1 6 2 4 2 题库管理系统框架1 7 2 4 3 题库管理设计方案18 2 5 本章小结1 9 第3 章在线考试系统的需求分析和设计2 1 3 1 系统需求分析2 l 3 1 1 系统功能分析2 1 北京工业大学工学硕士学位 3 1 2 系统的数据流图2 l 3 2 系统概要设计2 2 3 2 1 系统功能模块的划分2 2 3 2 2 在线考试系统的主流程图2 3 3 2 3 数据库设计。2 4 3 3 系统详细设计2 9 3 4 本章小结3 3 第4 章考试系统中题库和组卷子系统的实现3 5 4 1 题库子系统的实现3 5 4 1 1 科目管理3 5 4 1 2 题库管理3 6 4 2 组卷子系统的实现3 7 4 2 1 组卷子系统的操作流程3 7 4 2 2 组卷子系统的操作界面3 8 4 2 3 基于遗传算法的组卷算法的实现3 8 4 3 组卷子系统的测试与评价4 0 4 4 本章小结4 l 结论。4 3 参考文献4 5 攻读硕士学位期间所发表的学术论文4 9 致谢51 第1 章绪论 第1 章绪论 1 1 在线考试系统的现状 1 1 1 在国外的发展状况 大约1 9 9 7 年初，国外开始出现支持网上教学的系统和平台，近年来层出不 穷。国外大多数系统侧重于网上的课程开发、课程管理、学生历史记录等方面， 对教学过程提供全面有效但是比较基础的支持，也有一些系统重视教学活动的设 计，如提供对不同教学模式的教学实施方便性的支持。美国的n t u 英国的p e n c o l e g e 都是十分典型的网络教育示例。但是，一些范围内的考试采取的技术还是 停留在局部范围内的基于c s 结构的应用程序，整体性的考试支撑工具还未形 成。由于技术和相关理论的不断成熟，近几年，基于w e b 的在线考试系统得到 了长足的发展，已经成为现代远程教育研究的一个热点；相反地，也正是因为技 术和相关理论的不够成熟，基于w e b 的在线考试系统还需要不断研究和完善， 因此它还没能够完全地在现代远程教育的教育评价和学习中开展和实施。 目前在英国，已经实现了英语资格考试的网上学习和水平认证的全过程，许 多国际著名的计算机公司所组织的各种认证考试大部分采用这种方式。 1 1 2 在国内的发展状况 国内网络教育和网络大学已经兴起，通过对国内网上学校了解发现，网上课 程考试支撑系统明显不足。我国的网络学院的开办，作为网络课程重要组成部分 的网络考试系统也有很多地方开发过，如北京师范大学的网络教学平台，其测试 考核自动化，但是功能单一，只能适用于计算机应用操作考试，网络版扩展性能 差，采用的是两层c s 结构，只能在局域网内使用；上海交大也开发了一个网 络考试平台，它的试题库做不得错，但是实时在线考试功能较差。不少高校及科 研单位也开发了各门各类的基于w e b 的在线考试系统。除了前文提及的教育部 现代远程教育试点网络学院正在研究和试用在线考试系统外，一些大规模高校的 部分计算机学科，特别是基础学科也在制作和试验使用在线考试系统来进行无纸 化考试，如华中理工大学，上海同济大学等。 大型的教育培训机构由于面向的培训对象分布范围广，他们是研制和使用在 线考试系统的积极力量。如全球最大的信息技术教育培训和提供i t 解决方案的 跨国公司之一m i t ( e i 度国家信息学院) ，它在中国的培训从2 0 0 4 年起全面实行 北京工业大学工学硕士学位论文 其学生都利用网上在线考试系统进行考试。 1 1 3 当前在线考试系统的特征 综观现有的网络课程，多数还是处于资源建设阶段，配套成熟的网络考试系 统不多。通过对一些远程教育学校、市场上的在线考试系统分析，其特点和存在 的问题如下。 基于w e b 的在线考试系统的特点： 1 、实现考试的远程化。可以不受时间和空间限制的开展考试，不必将考生 集中到一个具体的考场。 2 、测试方式多样化。可以针对客观题，如选择题，也可以针对主观题，如 填空题、简答题。 3 、实现了考试和评的自动化。除了部分主观题，在线考试系统都可以在考 试结束后自动地立即评阅考卷，从而快速得到考试结果，体现了考试的高效性与 准确性。 4 、充分发挥教师的主动性。教师( 或管理员) 可以较方便地对题库进行增添、 删除、修改等维护工作。 5 、可自动对学习者的考试结果进行记录和处理，为面向学习者的个别指导 提供依据。 目前市场上的考试系统的缺点： l 、缺乏开放性。由于考试系统是一个复杂的工程，其维护、管理、更新、 数据统计分析等都是由专业人员来进行，系统比较封闭。教师在其中只能使用部 分功能，这样无法在实际教学中真正发挥其作用。 2 、安全性。当前的考试系统大多没有足够的安全性和完整性考虑。在开放 的i n t e m e t 空间，这样的考试就不能保证考试的信度。 3 、智能化不高。早期的出题系统要么由人手工出题目，所有的考生采用同 一套试题；即使是电脑出题，但是由于是单机版的，使数据的收集和处理都变得 比较费时和困难，并且在考试出题的时候，大多采用的是随机出题法和回溯试探 法，出题的质量不高。 4 、智能试题库中试题属性值的确定问题不规范。 1 2 本课题的来源 我们学校以前所有课程的考试都是采用手工试卷考试形式，由任课教师根据 教学重点自己设计或从其他资料选些试题，组成试卷进行考试，考试后由任课教 第l 章绪论 师手工判卷。这样的试卷考试存在许多弊端： 1 、试卷侧重理论较多，实践操作较少。 2 、考试内容片面，一般均围绕教材甚至教材中老师划定的重点或范围而考， 且考试内容大多是知识导向性的，缺乏对学生综合能力和素质的评价。 3 、造成一些不公平的现象，平时不用功的学生只要考前突击也能通过考试， 考试的测评功能失效。 4 、考试过程复杂，考试、判卷、统分周期长等。 基于以上原因，学校想采用考试系统来完成组卷、考试和评分工作，这样就 避免了手工试卷考试的缺陷。虽然当前市场上有许多考试系统软件，但是这些软 件与学校对考试系统的需求都有很大差别。所以现在学校一方面在为每门课建立 试题库，另一方面也在积极开发自己的基于校园网络的在线考试系统，以便于满 足学校的考试需要，以及学生在宿舍做练习的需要。 1 3 本文主要内容 本文主要设计并实现了一个在线考试系统，考试系统功能包括在线考试、试 题管理和维护、智能组卷、阅卷评分、查看成绩和学生信息管理等功能。本文重 点研究了题库建设理论和组卷算法，并详细描述了本考试系统的题库建设方案和 基于遗传算法的组卷算法设计过程。本文将单设章节讨论题库建设方案和组卷算 法。 1 4 本章小节 本章主要分析了在线考试系统和组卷算法的当前现状，总结了考试系统的特 征，指出了当前考试系统的一些问题，最后对本课题的来源以及本文主要内容进 行了介绍。 北京工业大学工学硕士学位论文 第2 章组卷算法与题库的研究 第2 章组卷算法与题库的研究 2 1 组卷算法理论 2 1 。1 随机选取法和回溯试探法 以往的具有自动组卷功能的考试系统大多采用随机选取法和回溯试探法。 l 、随机选取法 随机选取法根据状态空间的控制指标，由计算机随机的抽取一道试题放入试 题库，此过程不断重复，直到组卷完毕，或已无法从题库中抽取满足控制指标的 试题为止。该方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组 卷过程来说组卷成功率低，即使组卷成功，花费时间也令人难以忍受。尤其是当 题库中各状态类型平均出题量较低时，组卷往往以失败而告终。简而言之，组卷 时显得较死板，无法满足题库多变要求，且不具有智能性【l 】o 2 、回溯试探法 回溯试探法是将随机选取法产生的每一状态类型记录下来，当搜索失败时释 放上次记录的状态类型，然后再依据一定的规律( 正是这种规律破坏了选取试题 的随机性) 变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成 完毕或退回出发点为止，这种有条件的深度优先算法，对于状态类型和出题量都 较少的题库系统而言，组卷成功率较好，但是在实际到一个应用时发现这种算法 对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷 时间长，后两点是用户无法接受的，因此它也不是一种很好的用来自动组卷的算 法。简而言之，对内存的占用量很大，程序结构相对比较复杂，组卷速度较慢， 选取试题缺乏随机性，且难以满足所有的约束条件【l 】。 2 1 2 遗传算法 1 、遗传算法概述 遗传算法是一种仿生优化算法。它的产生归功于美国m i c h i g a n 大学的 h o l l a n d 在2 0 世纪6 0 年代末、7 0 年代初的开创性工作，其本意是在人工适应系 统中设计的一种基于自然演化原理搜索机制。大约在同一时间，f o g e l 和 r e c h e n b e r g 及s c h w e f e l ，引入了另两种基于自然演化原理的算法，演化程序 ( e m v o l u t i o n a r yp r o g r a m m i n g ) 和演化策略( e v o l u t i o ns t r a t e g i e s ) 这三种算法构 成了目前的演化计算领域的三大分支，它们从不同层次、不同角度模拟自然原理， 北京工业大学工学硕士学位论文 以达到求解问题的目的【2 】。 遗传算法是一种概率搜索算法，它是利用某种编码技术作用于称为染色体的 二进制数串。其基本思想是模拟由这些串组成的群体的进化过程。遗传算法通过 有组织的然而又是随机的信息交换来新组合那些适应性好的串，在每一代中，利 用上一代串结构中适应性好的位和段来生成一个新的串的群体。作为额外增添， 也要在串的结构中尝试用新的位和段来替代原来的部分。 遗传算法是一类随机算法，但它不是简单的随机走动，它可以有效的利用已 有的信息来搜寻那些有希望改善解的质量的串。类似于自然进化，遗传算法通过 作用于染色体上的基因，寻找好的染色体来解决问题。与自然界相似，遗传算法 对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评 价，并基于适应值来选择染色体，使适应值好的染色体比适应值差的染色体有更 多的繁殖机会【3 j 。 作为一种优化搜索算法，遗传算法相对于其他算法所具有的优势在于： ( 1 ) 遗传算法的操作对象是一组可行解，而非单个可行解，搜索轨道有多 条，而非单条，因而具有良好的并行性。 ( 2 ) 遗传算法只需利用目标的取值信息，而无需梯度等价值信息，因而适 用于任何大规模、高度非线形的不连续多峰函数的优化以及无解析式的目标函数 的优化，具有良好的并行性。 ( 3 ) 遗传算法择优机制是一种“软”选择，加上其良好的并行性，使它具 有良好的全局优化性和稳健性。 ( 4 ) 遗传算法操作的可行解是经过编码化的，目标函数解释为编码化个体 的适应值，因而具有良好的可操作性与简单性。 ( 5 ) 遗传算法易于和别的技术( 如神经网络、模糊推理、混沌行为和人工 生命等) 相结合，形成性能更优的问题求解方法。 2 、遗传算法的基本实现技术【3 】 遗传算法主要包括几个基本要素，现结合这些要素来介绍一些基本的理论。 ( 1 ) 染色体编码 遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基 因按一定结构组成的染色体活个体。这一转换操作称为编码。由问题空间向g a 空间的映射称作编码，而由g a 空间向问题空间的映射称作译码。 染色体编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问 题的解空间映射到g a 算法的编码空间。如何将问题的解转换为编码表达的染色 体，即将问题的解空间映射成一组代码串是遗传算法的关键问题。编码方案的选 择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。 评估编码方案常采用以下三个规范： 6 第2 章组卷算法与题库的研究 完备性：问题空间中的所有点( 候选解) 都能作为g a 空间的点( 染色体) 出现； 健全性：g a 空间中染色体能对应所有问题空间中的候选解； 非冗余性：染色体和候选解一一对应。 ( 2 ) 初始化群体 在遗传算法处理流程中，继编码设计后的任务是初始群体的设定，并以此为 起点一代代进化直到按某种进化停止则终止进化过程，由此得到最后一代( 或群 体) 。初始群体设定可采取如下策略： 1 ) 根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布 范围，然后在此分布范围设定初始群体。 2 ) 先随机产生一定数目的个体，然后从中挑出最好的个体加到初始群体中。 这种过程不断迭代，直到初始群体中个数达到了预先确定的规模。 群体规模的确定受遗传操作中选择操作的影响很大。从考虑群体的多样性出 发，群体规模应较大，但群体规模太大也会带来若干弊病，所以在实际应用中群 体个数的取值范围一般为几十到几百。 ( 3 ) 目标函数和适应度函数 遗传算法在进化搜索中以目标函数即适应度函数为依据。遗传算法的目标函 数不受连续变化的约束且定义域可以为任意集合。对目标函数的唯一要求是针对 输入可计算出能加以比较的非负结果。这一特点使得遗传算法的应用范围很广。 在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。 ( 4 ) 遗传算子设计 遗传操作是模拟生物基因遗传的操作，包括选择、交叉和变异三个基本遗传 算子。 1 ) 选择算子( s e l e c t i o n r e p r o d u c t i o n ) - 从群体中选择优质个体，淘汰劣质个 体的操作称作选择或复制。其目的是把优质的个体( 或解) 直接遗传到下一代或 通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适 应度评估基础上的，目前常用的选择算子有适应度比例方法、最佳个体保存方法、 期望值方法、排序选择方法和排挤方法。判断个体优良与否的标准是各自的适应 度值的大小。 2 ) 交叉算子( c r o s s o v e r ) ：自然界生物进化过程中起核心作用的是生物遗传 基因的重组( 加上变异) 。同样，遗传算法中起核心作用的是遗传操作的交叉算 子。一方面，它使得在原始群体中的优良个体的特性能够在一定程度上保持；另 一方面，它使得算法能够探索新的基因空间，从而使新的群体中的个体具有多样 性。常用的交叉算子有：单点杂交算子、单点随机杂交算子、均匀随机杂交算子 魈 1 廿o 北京工业大学工学硕士学位论文 单点杂交算子：等概率的随机确定一个基因位置作为杂交点，再把一对母 体两个个体从杂交点分成前后两个部分，交换两个后半部分得到两个新的个体， 取第一个个体为杂交结果。 单点随机杂交算子：等概率的随机确定一个位置作为杂交点，再把一对母 体两个个体从杂交点分为前后两个部分，以概率p c 交换两个个体的后半部分， 得到两个新个体，取第一个个体为杂交结果 均匀随机杂交算子：独立地以概率p c 把母体的第一个个体的相应的分量交 换为第二个母体的相应分量，从而得到杂交结果。 3 ) 变异算子( m u t a t i o n ) ：变异算子的基本内容是对群体中的个体串的某些 基因座上的基因值做变动。就基于字符集 o ，1 ) 的二进制码串而言，变异操作就 是把某些基因座上的基因值取反，即1 - - 0 或0 1 。遗传算法中使用变异算子 一方面使得遗传算法具有局部的随机搜索能力，当遗传算法通过交叉算子已接近 最优解领域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛， 此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破 坏；另一方面可以使遗传算法维持群体的多样性，以防止出现未成熟收敛现象， 此时变异概率应取较大值，变异操作有可能限于局部解的弊病。主要的变异算子 有：基本变异算子、均匀变异、正态变异、自适应变异。 ( 5 ) 控制参数选择 在遗传算法的运行过程中存在对其性能产生重大影响的一组参数，包括染色 体位串长度l 、群体规模n 、交叉概率p c 、变异概率p m 等。在初始化阶段和群 体进化过程中，对这些参数进行合理的选择和控制，以使遗传算法以最佳的搜索 轨迹达到最优解。 2 2 在线考试系统的组卷算法 2 2 1 组卷算法的确定 在线考试系统将要实现多门课程的组卷和考试，而每一门课程中又包含多种 题型，每种题型中的每个试题又属于不同的章节，具有不同的难度，因此考试系 统是从不同科目、不同题型、不同难度、不同章节范围内的试题中选题组卷，组 卷时对试题的要求很多，其复杂程度可想而知；最重要的是在线考试系统是基于 w e b 的，组卷操作将通过网络来完成，所以对组卷算法的执行时间要求严格，不 能太长，否则组卷人将无法忍受。 而分析各种组卷算法的优缺点，不难发现，在限制条件状态空间的控制下， 随机选取法有时能够抽取出一组令用户满意的试题，只不过由于它随机选取试题 第2 章组卷算法与题库的研究 的范围太大，无法确定目前条件下哪些区域能够抽取合适的试题，反而可能在那 些已经证明是无法抽取合适试题的区域内反复选题，进行大量的无效操作进入死 循环，最终导致组卷失败。并且组卷比较死板，无法满足题库多变的要求，不具 有智能组卷的特点。回溯试探法组卷成功率高，但它是以牺牲大量的时间为代价 的，对于现今越来越流行的考生网上随机选题的考试过程来说，它已不符合要求。 只有遗传算法组卷效率较高，并且组卷具有智能性，所选取试题基本上能满足所 有的约束条件，组卷成功率很高。 因此在综合考虑在线考试系统自身的特点以及各种组卷算法的优缺点基础 上，决定采用遗传算法来完成在线考试系统的组卷。 2 2 2 组卷参数定义 我们知道，计算机抽题是根据试题的属性一道题一道题进行处理的，教师一 般都不可能对所有试题的属性进行设置，因此，我们要设置一些教师易于理解、 容易操作，同时又能很好体现教师考试意图的组卷参数。设置组卷参数的主要依 据是一套完整试卷的属性，比如试卷标题，考试时间，考察的知识点等，还有一 些特殊考虑，如试题的难度和认知分类等。下面介绍在线考试系统所设置的组卷 参数。 1 、总体参数 总体参数是指对试卷的整体属性的说明，具体有：试卷标题、考试时间、满 分值、平均难度、平均区分度、考察的章节知识点。 表2 - 1 总体参数表 t a b l e2 - 1t h eo v e r a l lp a r a m e t e r st a b l e 参数名称试卷标题考试时间满分值平均难度平均区分度考察的章节知识点 参数值 t e s t1 0 01 0 0难 中 ( 1 ) ( 2 ) ( 3 ) 2 、题型比例 题型比例指试卷的题型结构，也就是试卷中有那些大题型，某道大题型下有 多少道小试题，这些试题在试卷中占多少分，某题型要考察那些知识点，题型比 例参数可概括成为一个一维表，其中列为：题型，试题数，分数，题型考察的章 节知识点。 表2 - 2 题型比例表 t a b l e2 - 2t h et a b l eo fq u e s t i o nt y p ep r o p o r t i o n 题型试题数 分数 考察章节知识点 a1 02 0 ( 1 ) ( 6 ) ( 5 ) b5 2 0( 2 ) ( 4 ) nl5 ( 3 ) 北京工业大学工学硕士学位论文 3 、参数约束条件 在组卷输入上述参数时，并不是随意的，参数必须符合如下约束条件： ( 1 ) 题型分数值满足： 盖 题型j 的分数；总分数 l ( 2 ) 题型考试时间值满足： 罗题型i 的考试时问一总考试时问 7 ( 3 ) 题型比例表中所出现的知识点必须为总体参数中所设的知识点。 4 、平均难度与平均区分度计算模式 在使用平均难度与平均区分度参数时，并不是所有的试题的难度或区分度都 是平均值，而是有一个比例模式的，这种模式中包括所有的难度级别，区别只是 比例数不同。模式值可以有多个，在具体使用中，模式类型可以取随机值。平均 难度计算模式表和平均区分度计算模式表分别如下表2 - 3 和表2 - 4 所示。注意表 中数据为示例数据，具体应用时，可设置更多的模式类型，比例也可以有所变化。 表2 - 3 平均难度计算模式表 t a b l e2 3t h et a b l eo f t h ea v e r a g ed i f f i c u l t yc o m p u t e sm o d e 难 较难 中 较易易模式类型 难度比例 难 4 0 2 0 2 0 1 5 5 较难 1 5 4 0 2 5 1 5 5 a 中 1 0 9 62 0 4 0 2 0 l o 较易 5 1 0 2 5 4 0 2 0 易 5 5 2 5 2 5 4 0 难3 5 3 0 1 5 1 5 5 较难 2 0 3 0 2 5 1 5 5 b中5 2 5 4 0 9 62 5 5 较易5 5 3 0 4 0 2 0 9 6 易0 5 3 0 9 63 0 3 5 第2 章组卷算法与题库的研究 表2 - 4 平均区分度计算模式表 t a b l e2 - 4t h et a b l eo ft h ea v e r a g ed i s t i n c t i o nd e g r e ec o m p u t e sm o d e 优良中较差差模式类型 区分度比例 优4 0 2 0 2 0 1 5 5 良1 5 4 0 2 5 1 5 5 中1 0 2 0 4 0 2 0 1 0 较差 5 l o 2 5 4 0 2 0 差 5 5 2 5 2 5 4 0 优 3 5 3 0 1 5 1 5 5 良 2 0 3 0 2 5 1 5 5 b中5 2 5 4 0 9 62 5 5 较差 5 5 3 0 4 0 2 0 差 o 5 3 0 3 0 3 5 2 2 3 基于遗传算法的组卷算法设计 从上文可知，使用遗传算法组卷时要涉及到七大要素，并且上文己对这七大 要素的设计思想进行了介绍。下面详细介绍一下在线考试系统在使用遗传算法进 行组卷时所涉及的七大要素的设计方法。 1 、染色体编码 染色体的编码方案有二进制编码、十进制编码、实数编码等，我们采用的是 二进制编码。 二进制编码方案在设计时一般都借鉴背包问题的部分思想，假设题库中待选 试题数量为l ，那么组卷问题实际就是从l 道试题中选出满足约束条件的试题， 这样一张试卷就可以用一个长度为l 的字串表示，字串中每一位的取值为0 或1 ， 用l 表示该题被选中，0 表示该题未被选1 4 。 我们在将遗传算法应用到组卷过程中时发现一般试卷中有多种题型，每种题 型的题量是组卷前确定的，这样如果在进行染色体编码时按试题进行编码，一个 试题对应字串中的一位，操作时按位进行，有可能无法保证每种题型组卷前确定 的题量，为此我们把染色体分为几个子染色体，每个子染色体对应一种题型，我 们的考试系统中当前设置了单选题、多选题、判断题、填空题和问答题五种题型， 北京工业大学工学硕士学位论文 这样染色体被分为了五个子染色体，五个子染色体分别编码，这五个子染色体位 串中“1 的数量对应为组卷约束条件中设置的对应题型的试题数量。 2 、初始化群体 在初始化群体阶段就是初始化产生由一定数量个体组成的群体，群体中每个 个体的数值采用随机函数产生。 一般情况下种群中每个个体的位串位数都取试题库中的试题数，而试题库中 所包含的试题量一般都是很大的，而且大部分试题实际上是与组卷要求中试题的 参数不相符的，这样在初始化群体时为这些与试题组卷参数不相符的试题在位串 中保留位置，实际上是多此一举的，并且为这些试题保留位置，致使位串长度增 加了许多，在进行后面的选择、交叉、变异操作时会多占用大量的内存空间，同 时也会严重影响这些操作的执行效率。为此，我们在初始化群体时，先从试题库 中选出符合组卷约束条件中试题主要参数( 如题型、分值等) 的试题，使这些试 题中的每一个试题对应位串的一位，这样位串的长度就是符合组卷约束条件中试 题的主要参数( 如题型、分值等) 的试题量，由此位串长度将大大减少，后面各 种操作的执行效率将大大提升。 3 、确定目标函数和适应度函数 组卷问题实际是一个多重约束的求解问题，可以把这些组卷约束条件转化为 试卷目标例如所有试题的分数总和、反映不同章节要求的试题个数以及所占的 分数比例、试卷中各种题型所占的分数比例、所有试题的估时总和、试卷总区分 度等。这些约束都应等于用户指定的要求，或者误差最小在实际应用中，设定 来综合反映第i 个约束与用户要求的误差。并且由于这些约束的重要程度不同， 即有些条件要优先满足，有些则可以适当得放宽限制，所以将这些约束组合时， 应分配一定的权值，表明它们的重要程度，设w i 是组卷人员对第i 个约束条件 所赋予的权重。因此整卷的误差f 就是这些约束的加权和，同时为了不至于各个 误差相互抵消，这些约束与用户要求的误差都取绝对值，可以用下式( 2 1 ) 表 示： 力 ，n i ，2 乙i j i w ii ( 2 1 ) i = i 这里可以把整张试卷的误差f f g 为目标函数。由于在实际组卷过程中，有些 约束条件比较重要( 如章节、总分等) ，为了满足它们的需要，可以适当牺牲其他 约束。因此，组卷人可以根据每个约束条件的不同性质和组卷者的不同目标，对 w i 可自行赋值。这样组卷实际就是从题库中抽取试题，使得整张试卷的误差f 即目标函数最小因此，组卷问题可以看作是在约束条件下的最小化问题。由于 遗传算法使用过程中要使用适应度函数来描述每一个体的适宜程度的，所以对优 化问题来说，适应度函数就是目标函数【5 】。 第2 苹组卷算法与题厍的研冗 在线考试系统在设计适应度函数时是按照题型所对应的五个子染色体分别 计算每种题型的各试题的难度、区分度、分值、时间和总区分度等各参数指标的 和，然后各题型各种参数指标分别相加求和，然后将所有试题的各参数指标与指 定的整张试卷要求各参数指标相比较，计算误差，最后将误差与相应的权值求积， 再相加求和。 4 、选择算子 我们在设计选择算子时的思路是从当前群体中选出一半适应度较强的个体 通过配对交叉和变异产生新的个体遗传到下一代，而适应度强弱的判断是通过每 个个体的适应度值的大小比较，适应度值小的适应度更强。 5 、交叉算子 上文提到，编码时按照题型将染色体分为几个子染色体，每个子染色体中“l ” 的个数固定为组卷要求中每种题型的试题数量。但是即使亲代染色体中“1 ”的 数量固定，s g a 的单点交叉算子也不能保证交叉运算之后得到的子代染色体中 “1 的数量固定，也就是说即使初始种群中随机生成若干“1 ”数量固定的染色 体串，单点交叉操作也会破坏这种“1 数量确定的结构。我们必须设计新的交 叉算子。 为了保证交叉前后位串中“1 的数量固定，我们设计的交叉算子的交叉点 位置设置在各子染色体的边界，即各种题型边界。交叉操作时将每一个子染色体 作为整体来参与交叉，而不是从每种题型对应的子染色体内部来进行，并且是群 体中不同个体之间相同题型对应的子染色体的交叉，而不是将不同个体的不同题 型对应的子染色体交叉，这样不管如何交叉，染色体各部分位串信息都确定是初 始群体中某一染色体的某一部分，染色体中各子染色体中“1 的数量都固定为 组卷参数中对应题型要求的试题数量，保证了交叉前后亲代和子代染色体中“1 ” 的个数固定。 6 、变异算子 变异算子在实现时比较简单，只要随机取群体中某个体的某位，使其值取反