（计算机应用技术专业论文）考试系统及其组卷算法的研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 近年来，由于高等院校的扩招，使得高等院校的在校学生人数大大增加，由 此使命题、阅卷、考试管理等考试工作变得更加繁重。这给教师和教学管理部门 都造成了巨大的负担，因而迫切需要一种新的考试方式来解决上述问题。随着计 算机技术和网络技术在教育中的应用，传统的考试方式也面临着重大的变革，利 用网络考试系统进行考试则是一种先进的考试方式，它有很多传统的考试方式所 不具有的优越性。 论文对考试系统进行了需求分析，设计了考试系统的结构，并对系统进行了 详细设计。系统共包含六个子系统，分别是题库维护和管理子系统、组卷子系统、 在线测试子系统、阅卷评分子系统、试卷及成绩分析子系统和成绩查询子系统， 其中论文的研究重点是组卷子系统。系统安全控制采用了管理员、教师及学生三 级授权。管理员负责系统的维护，可以增加、删除能对题库进行操作的教师；教 师负责题库的管理以及试卷的生成、考试的综合评估等工作；学生可以利用考试 系统进行答卷，并可通过系统查询成绩。 论文研究了传统的组卷过程，分析了试卷的评价指标、各项指标的作用及几 个重要指标间的关系，建立了采用各个评价指标的分布构建的成卷模式，并根据 成卷模式定义了评价试卷质量的偏好关系，建立了组卷数学模型。 基于该数学模型，论文对经典遗传算法从多方面进行改进。运用自适应理论 改进交叉概率及变异概率，算法本身总能找到适合于自己的交叉概率和变异概率。 引入i 蠹传灾变”算法使变异概率在监测到染色体有“早熟倾向时，会自动突变其 值，发生灾变，增加变异的机会，使种群跳出“早熟”。选择算子采用模拟小生境的 方法，其基本做法是：当新产生的子代个体的适应度超过其父代个体的适应度时， 所产生的子代个体才能代替其父代个体而遗传到下一代种群中，否则父代个体仍 保留在下一代种群中。由于子代个体和父代个体之间编码结构具有相似性，所以 替换掉的只是一些编码结构相似的个体，故它能够有效地维持种群的多样性，从 而避免产生局部最优解，改善未成熟收敛。 关键词：考试系统，教育测量，试卷模式，数学模型，遗传算法 重庆大学硕士学位论文英文摘要 a b s t r a c t i nr e c e n ty e a r s ，t h e r ea l em o r ed i f f i c u l t i e sf o rt e s tp a p e rc o n s t r u c t i o na n dt e s t m a n a g e m e n tb c c a n s eo fm o r ea n dm o r es t u d e n t si nu n i v e r s i t i e so fc h i n a a sa 懈u l t - w en e e dan o v e lt e c h n o l o g yt oi m p r o v et h ep r o b l e mo ft e s tm a n a g e m e n t w i t ht h e d e v e l o p m e n to f c o m p u t e ra n dn e t w o r kt e c h n o l o g y , i t sp o s s i b l ef o ru st op u to n l i n et e s t m a n a g e m e n tm e t h o di n t o 璐e ，w h i c hh a sm o r ea d v a n t a g 鹤t h a nt r a d i t i o n a l t e s t m a n a g e m e n tm e t h o d t h et h e s i sp r e n t st h ew h o l ep r o c c s $ o fd e s i g nf o rt e s tm a n a g e m e n ts y s t e mf r o m r e q u i r e m e n tt od e t a i l e dd 嚣i g n t h e r ea g os i xs u b s y s t e m si nt h ea b o v es y s t e m , w h i c ha g e t e s ts u b j e c tl i b r a r ym a i n t e n a n c ea n da d m i n i s t r a t i o ns u b s y s t e m , t e s tp a p e rc o n s t r u c t i o n s u b s y s t e m , o n l i n et e s ts u b s y s t e m , t e s tp a p e rc h e c k i n gs u b s y s t e m , t e s tp a p e ra n ds c o m a n a l y s i ss u b s y s t e ma n ds c o r es e a r c hs u b s y s t e m t h et h e s i sf o c u s e d0 1 1t e s tp a p e r c o n s t r u c t i o ns u b s y s t e m t h e r ea r ct h r e el e v e lr o l e sf o rs y s t e ms c c u t i t yc o n t r o l m a n a g e m e n tw h a ta r ca d m i n i s t r a t o r , t e a c h e ra n ds t u d e n t e v e r yr o l eh a sd i f f e r e n t f u n c t i o n s a saa d m i n i s t r a t o r , h ec a nm a i n t a i ns y s t e m , i n s e r ta n dd e l e t ed a t af o rt e s t s u b j e c tl i b r a r y a sat e a c h e r , h e 锄m a i n t a i nt e s ts u b j e c tl i b r a , m a n a g et e s tp a p e r c o n s t r u c t i o na n dt e s tp a p e ra n a l y s i s a sas t u d e n t , h e 锄a n s w e rt h eo l l l i n et e s tp a p e r a n ds e a r c hs c o r ew i t ht h eo i l l i n et e s ts y s t e m m y r e s e a r c hf o c u s e do nd e s i g no fm a t h e m a t i c a lm o d e lf o rt e s tp a p e rc o n s t r u c t i o n b a s e do nf a c t o r sa n da r g u m e n t so ft e s tp a p e ra n dt h e i rr e l a t i o n sc o m p a r e dw i t h t r a d i t i o n a lt e s tp a p e rc o n s l n m t i o np r o c e s s i nt h en o v e lm a t h e m a t i c a lm o d e l ，t h e r ea r e 8 0 m en o v e lt e s tp a p e rc o n s t r u c t i o np a t t e r nf o rt e s tp a p e rd i s t r i b u t ec o n s l z u c t i o n t r a d i t i o n a lg e n e t i ca l g o r i t h mf o rt e s tp a p e rc o n s t r u c t i o ni si m p r o v e db a s e do nt h e a b o v em a t h e m a t i c a lm o d e l t h ec r o s s o v e rp r o b a b i l i t ya n dm u t a t i o np r o b a b i l i t ya r c i m p r o v e do ns o l f - p r o p c rt h e o r y , s ot h a tt h ep r o p e rn u m b e r so f c r o s s o v e rp r o b a b i l i t ya n d m u t a t i o np r o b a b i l i t yc 趾b ef o u n d t h eg e n e t i c - m u t a t i o na l g o r i t h mi si n t r o d u c e di n o r d e rt oe n h a n c em u t a t i o nc h a n c e sa n dr u no u tp r e m a t u r e s i m u l a t e dn i c h ei s i n t r o d u c e di nt h es e l e c t i o no p e r a t o rw h i c hm e a n st h ef i l i a lg e n c r a t i o n sf i t n e s si sb e t t e r t h a nt h o s eo ft h e i rf a t h e rg e n e r a t i o nb u tt h e f a t h e rg e n e r a t i o ni sr e m a i n e d i t 锄 m a i n t a i nm u l t i - s e e d se f f e c t i v e l ya n da v o i dr u n n i n gi n t ot h et r a po f t h ep a r tb e s tv a l u e k e y w o r 山：t e s ts y s t e m ，e d u c a t i o nm o a s u r et h e o r y ， m o d d ，g 锄e d ca l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重迭太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 柱) j f 签字日期： - 州7 年，月f 日 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庆太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名： 签字日期：剐年 导师签名：i 壶 签字日期：由即浑多月，日 盖q ， 日捉吖 ，p 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 论文研究背景 计算机在教育方面的应用始于2 0 世纪5 0 年代的计算机辅助教学系统，其中 包括考试系统、排课系统、教学管理系统等【l 】。计算机辅助教学系统是利用计算机 为媒介，通过运行事先存入的计算机程序来实现教学、辅导答疑、实验仿真以及 测验考试等教学活动，是一个涉及计算机科学、教育学、心理学、认知科学和行 为科学的复杂系统。它一般需要通过计算机硬件系统、系统软件和课程软件来实 现。计算机辅助教学主要是把计算机技术应用到教学领域，以提高教学水平和教 学质量【2 捌。它研究的目的是建造教学系统，最初的系统有电子翻页器( p a g e - t i 删e 玛) 以及句型和练习监控程序( d r i l l - a n d - p r a c t i c em o n i t o r s ) t 4 】。 1 9 7 0 年，c a r b o n e h 融合人工智能技术，定义了一种新型的计算机辅助教学系 统并称之为基于智能的计算机辅助教学系纠卯。国外早期比较有名的由c a r b o n e l l 和c o l l i n s 研究的地理教学系统s c h o l a r 系统，它应用人工智能的知识表达方 式，其知识库采用语义网络形式，并由事实、概念和过程组成，教学方式采用苏 格拉底对话式，根据学生的回答，通过推理机制产生更多提问并评价学生的解答， 系统能诊断学生的一些错误概念并引导学生自己思考后纠正错误 6 1 。2 0 世纪7 0 年 代后，随着人工智能的发展以及在计算机辅助教学系统的知识表示、推理方法和 自然语言处理等方面的应用i _ ”，使得计算机辅助教学系统的设计越来越智能化。 2 0 世纪8 0 年代后，认知心理学、教学设计理论给计算机辅助教学系统的研究 带来了深远的影响，使计算机辅助教学系统迸一步得到发展。人们在研究计算机 辅助教学系统时更多考虑学生的学习过程，学生获得知识的过程。c l a n c e y 等开发 的计算机辅助教学系统g u i d o n 与专家系统m y c i n 相结合，代表了计算机辅助 教学系统研究中的一个重大发展。它采用产生式规则的知识表示方法。建立了学 生模型，教学过程是一个交互式的学习环境【s 】。 一般说来，计算机辅助教学系统主要由三部分组成【9 】。 知识库模块由某领域的专家按选定的知识将领域知识、教学规则转换成计 算机系统可以理解的表达形式，建立包括领域知识和教学规则在内的知识库。领 域知识就是有关教学内容的专业知识与技能，它既包括说明事物概念的陈述性知 识，又包括利用这个概念解决问题的过程性知识。智能计算机辅助教学系统特别 强调后者的训练。此外，领域知识还包括知识形成或技能运用过程的元知识。教 学规则汇集了适用在特定环境和条件下有效的教学方法。由以上领域知识和教学 规则构成的知识库，包括了教学所需要的全部事实。智能计算机辅助教学系统中， 重庆大学硕士学位论文1 绪论 除了像一般的专家系统的知识库所要求的内容外( 比如知识的表达方式要易于理 解、规划、存取和扩充等) ，还要特别注意以下四个方面：要有明确的教学目标和教 学范围；要形成比较连贯的关系或基础体系；要形成一个适用的思维或推理模型； 要考虑学生接受能力的限制。 学生模型模块。所谓学生模型，是指生成一种可靠的表达方式来展示学生 的实际水平状况。其过程就是根据学生的表现来估测他的学习要求，他对知识与 技能的掌握情况以及他的能力，这种对学生表现的估测结果就是学生模型。学生 模型是通过智能化交互接口跟踪学习过程，对每个课程建立独立的单元，建立各 单元水平的判定规则。当学生完成一课的学习时，给出水平判定值：进行错误诊 断时，能够用不同的方法。在跟踪学习时给出错误的原因，如概念性错误用扰动 发，方法性错误用过程协议分析法和解题过程网络分类分析法等。查出原因后再 给出改正的提示，同时记录下来作为学习辅导的依据；学习跟踪时学习过程的纪 录，记下学生的学习历史和进步情况；模型更新是随学生学习深入而改变的，它 可以用覆盖法或差错法来说明学生具有的知识与计算机系统中存储的知识的差 距，进一步更新学生模型、继续进行教授内容和方法的决策。 教师模型模块。教师模型模块也叫做辅导模块，就是模拟人类教师，使智 能计算机辅助教学系统能像人类教师一样，按照自己教材内容的理解，根据学生 的状况( 包括知识水平和学习背景，如爱好、总体水平、性格、智力等) ，选择对该 生最为有效的教学方法，监督和评价学生的学习行为，选择提出问题并根据学生 的要求适时地为其提供帮助和选择补充知识。智能计算机辅助教学系统的教师模 块能够控制学生的学习，掌握学生的学习水平并做出适时反馈，决定下一步的教 学内容和应该采取的教学方法、策略。因此，教师模块必须有完整的关于自然语 言对话、教学方法、教学策略和教学题材的知识，能够决策采用什么样的方式、 顺序以及教学模式等。 计算机测试作为计算机辅助教学的不可分割的一个重要环节，在计算机辅助 教学系统中占有极其重要的地位。而自动组卷是考试系统自动化或半自动化操作 的核心目标之一，而如何保证生成的试卷能最大程度的满足用户的不同需要，并 具有随机性、科学性、合理性，这是实现中的一个难点，也是本论文要解决的主 要问题之一。 1 2 国内外研究现状 1 2 1 考试系统研究现状 目前，计算机和网络的应用在各行各业已经很广泛，尤其是在高校。校园网 的建设己逐步完善，大多数学生也己经具备了利用网络进行交流和学习的能力。 2 重庆大学硕士学位论文 1 绪论 但是在教学这个环节中，我们仍然过分依赖于传统的教学模式，对于网络的开发 和应用程度远远不够。即使是网络教学系统，也是大多为静态、无反馈的系统， 很少提供在线考试的功鲥”。 考试系统是在教育测量理论指导下对传统纸笔考试过程的数字化改造。一个 完善的计算机考试系统，应该包括题库管理、组卷、统判卷和成绩统计分析等各 项面向教师、面向试题题库的功能，还包括试题呈现、考场管理、自动判卷等面 向考生的在线考试功能l l ”。 目前市场上考试系统的种类较多，比较多的是按以下三种情况来进行分类的。 按照用途来分，主要有三种：专用考试系统、固定科目的考试系统、通用考 试系统，但主要以前两种为主，其功能单一，通用性较差，使用的范围极其狭掣1 2 】。 这就要求我们在开发网络考试系统应尽可能考虑它的通用性，以使其有更为广阔 的应用空间。 按照考试系统的组卷方式来分，主要有三种：一是将试题库当试题集，出卷 时由具有丰富经验的教师逐题抽取；二是将试题库当试卷集，将已出好的试卷存储 起来，出卷时抽取其中的一份；- - 是具有自动威卷功能的试题库，利用任课教师提 供的成卷规则编制成卷软件，以自动生成合理的试卷【1 3 1 。 从结构上来划分，主要有两大类。一类是采用客户机服务器( c s ) 结构的 考试系统，另一类是采用1 3 8 模式的分布式网络考试系统【1 4 】。它们都能够实现无 纸化的计算机考试，考试时学生登录系统参加考试，考试后系统自动生成考试成 绩。但由于设计时的局限，现行的这两类考试系统都有着许多有待改进的地方。 其中，客户机服务器( c s ) 模式主要适用于工作组规模的运行，但要在更大范 围去使用则难以实现，并且由于相当部分功能集成客户机上，使客户机的功能日 趋复杂，被人们戏称“胖客户机”。其开发、发布、移植的工作量非常大，也非常繁 琐，维护和管理的开销也不少，更不利于考试系统的安全。还有的c s 模式的考 试系统甚至将功能全部集成在服务器端，使考试系统的界面、数据访问、数据存 储、数据管理等都由服务器端程序完成，从而使服务器成为网络数据访问的瓶颈。 当考试期间大量学生访问服务器时，导致服务器响应缓慢，甚至出现服务器塞机 现象。同时c s 结构还存在灵活性差、升级困难和系统安全性差等缺陷，已较难 适应当前信息技术与网络技术发展的需要【l ”。 现在比较行的是b s 模式的分布式网络考试系统，它们虽然克服了c s 模式 的许多不足，但其也存在不少可以改进的地方：一是考试科目单一，通常是为某一 门课程而设计，系统通用性差；- - 是以试卷为存取单位，有的实质上只是一个试卷 库，不能随机生成试卷，难以满足出题者多方面的要求；- - - 是试题单一，仅限于文 本类型和客观题，很难满足准确、全面考查学生所学知识的需要旧；四是有的软 3 重庆大学硕士学位论文1 绪论 件用户界面不美观，使用不够方便1 1 6 l ；五是忽视了考试后的管理【1 ”，如考生成绩 的查询、试题难度的分析等。 1 2 2 自动组卷系统研究现状 在试题库系统的研究上，国外对标准化考试系统建立的试题库软件系统，有 美国的t o e f l ，g r e ，g m a t 考试计算机系统【1 s 1 9 】、新加坡的化学标准化考试计算 机系统。但是这些试题库在组卷功能上存在着针对性、随机性太强的缺点，原因 有两点，一是不能处理用户的不同层次的、模糊或不完整的组卷要求信息；二是 如果考试偶然和考生的学习相悖，则无法测试真实水平，不能很好的适应个性教 育。 1 9 8 6 年以来，国内也建立了许多各种学科的试题库系统，如计算机辅助英语 设计系统、高等数学试题系统m a t b a s m2 、大学工科物理试题库( p b i c s ) 、南 京大学计算机科学与技术系研制的p a s c a l 题库系统例，高教司的重点项目“基于 知识的成卷系统通用外壳软件啦3 j 等系统。但这些系统大多数还停留在题库管理 上，对试题和试卷的度量指标、组卷理论及教育测量的研究还不够，在模拟专家 组卷方面的能力较差，大多几乎没有自动组卷功能，并且其规模和软件质量参差 不齐，存在着专用、封闭、功能单一、单用户使用等不足。 目前出现了一些专用的自动组卷系统，它们按照试题的数据结构和生成算法 大致可分为三类i 驯： 基于随机函数或随机变量算法的自动组卷系统： 基于深度及广度搜索算法的自动组卷系统； 基于智能搜索算法的自动组卷系统。 许多文献对组卷算法进行了研究。文献1 2 5 直接利用随机函数从题库中抽取试 题：文献 2 6 1 提出一种新的“分段随机抽选法”，并用该算法与传统的组卷算法在生 成试卷的效率上进行了比较，同时针对由本算法所引起的修改操作困难提出了解 决方法；文献【2 7 】介绍了两个基于分割策略的随机变量算法，一是用来完成如何根 据试卷的难度系数确定不同难度系数试题抽取的数量，二是用来完成如何从试题 库中抽取满足试卷要求的一定数量的试题；文献【2 8 】提出了随机优化组卷的算法， 并实现了试卷的自动排版；文献 2 9 h 3 2 】介绍了基于深度和广度算法的数据库搜索 策略；文献 3 3 】提出了智能组卷所涉及到的启发知识和组卷要求的约束满足问题， 并在此基础上给出了智能组卷问题求解的主要数据结构，以及在深度广度上实现 的智能搜索；文献 3 4 】基于遗传算法对组卷数据库结构进行研究，提出了一种新的 试题库结构；文献【3 5 】在试题库中引入专家系统，提出了基于成组技术的试题标识、 基于框架模式的试题库组卷专家系统；文献 3 6 】采用试卷参数双向细目表”和试 卷统计参数预览表”为线索来规划试卷，相应的数据库结构为题号、范围、内容、 4 重庆大学硕士学位论文1 绪论 难度、区分度、分值、时间、被选次数、选中标志、知识点等；文献 3 7 】利用优选 权、多并行、误差补偿、随机、回溯五种算法的综合应用，选择的数据库结构为 题号、题型、内容、难度、分数、时间、教学要求度、区分度、信度；文献 3 8 1 根据随机化启发式搜索算法提出了试题基本信息、正文信息、图形信息、答案、 评分等结构；文献【3 9 】使用多级查询算法，确定的试题库结构为题数、题型、难度、 知识重点、认识层次；文献 4 0 1 以一个学习环境为基础，讨论了一个通用的试题库 模型及其实现技术，并给出了几种组卷算法进行对比。k o t l m a n 用并行理论的方法 建立了一个组卷模型，华南理工大学基于深度搜索理论设计了一个物理试题库智 能组卷系统，西安交大也正在开发组合式考试系统。但是这些研究普遍只是停留 在理论探讨的基础上，没有进行实际的应用。 1 3 论文研究目的与意义 在计算机技术和网络技术日益发展成熟，并逐步渗入到社会生活各个领域的 今天，各行各业都发生了深刻的变革，计算机技术和网络技术己经被广泛地用于 各行各业，学校也不例外，传统的考试方式也面临着重大的变革，而利用网络考 试系统进行考试则是一种先进的考试方式，它有很多传统的考试方式所不具有的 优越性。传统的考试方式下，多数学校的考试的工作流程是教师出题、印制试卷、 学生考试、教师阅卷、统计成绩与评估、试卷分析等，其中制卷、阅卷、统计成 绩的工作量非常大，而且也特别容易出错。尤其是随着高校学生的扩招，考生数 量大幅度增加，阅卷和成绩统计的工作将变得更加的烦琐。利用网络考试系统进 行考试则不再需要印刷试卷，可以节省大量的人力、物力和财力；课程考试题目 在考前输入计算机，建成试题库，利用网络考试系统对试题库进行科学的管理， 为教师题目的保存、分类和检索提供了便利，也为编制试卷提供了高效率和低成 本的手段；考试试卷由试题库中的信息按照教师制定的组卷策略自动生成，提高 了出卷的效率，并避免了考试前试题信息的泄露：考试系统可以对历次考试的结 果进行统计分析，教师可以依据分析结果，根据实际情况，调整、更新试题，增 强试题库的生命力，使试题库能够更加准确的反映要考核的内容，增强出题的科 学性和合理性；采用标准化的客观型试题进行考试，网络考试系统可以直接对试 卷进行评分，就不需要人工阅卷，从而不但可以大量减轻任课教师烦琐的阅卷工 作，还提高了阅卷的效率和准确度，避免了人工判卷时经常出现的错判、漏判和 分数计算错误等情况，使考试过程更加规范化；考试后每个题目的分数存储在数 据库中，利用数据库能方便地对数据进行统计、汇总、排序等操作，就不再需要 教师做毫无意义的统分工作了，教师也能从中了解考试的情况；考试试卷及考试 成绩保存在数据库中，为考生查询成绩提供了方便，也增加了考试的公开性与透 5 重庆大学硕士学位论文 i 绪论 明度。因此可见，设计并开发一个功能完善的考试系统是非常有意义的。 对组卷系统来说，能生成符合要求的试卷是一项最根本的功能要求，其抽题 组卷算法的设计对于整个组卷系统的质量和性能是关键。自动组卷不但能最有效 地把具有丰富经验的教师群体的知识和组卷经验与计算机技术结合在一起，生成 符合要求的试卷且比较客观和规范性好；同时，使用起来又最为方便，对操作人 员几乎没有什么专业上的要求【4 1 】。然而，自动组卷系统的设计并不容易，主要原 因有以下三点： 对试卷的要求不同于一般的练习。它同时也必须满足教学和考试目标的要 求 4 2 4 3 1 。因此在内容、深度、难度、题型、时间、分数等方面都必须有严格的要 求。 不同校系的考生对象和不同的考试目标，对试卷要求很不相同 4 4 1 。考试内 容既可以包括课程又可局限于某一篇章或某几个题类；各院校的教学内容和教学 水平又不完全一致，对试卷各部分的分数比例、深度和难度都会有不同的要求。 因此要求组卷系统在各种场合下都适用，具有很大的适应性。 考试是一项严肃的教学活动，任何一份试卷都必须是合格的。组出的试卷 哪怕是有_ 个很小的概率出现差错，也是不允许的。 以上三点可称之为试卷的指标综合要求性、试卷的规格多样性、试卷的严肃 性，要满足这三点，要求组卷系统必须具有一个好的组卷算法，然而在抽题过程 中要做到随机、无法预知、不重复、优化数据存取和快速组卷等并不容易，因此， 自动组卷的效率和质量完全取决于组卷算法的设计，这成为当前组卷系统研制的 重点嗍。 虽然组卷系统是个被探讨了很长时间的问题，但至今并没有一个很好的自动 出题算法方案。由于自动组卷是从题库中选题自动生成满足教学和教师要求的各 类试题( 包括考试内容、章、节、题目类型、难度、教学要求度、时间等一系列的 要求) ，因此它是一个典型的约束满足问题( c s p ) 的求解过程嗍。采用经典的数学方 法很难解决这个难题，自动组卷的效率和质量完全取决于试题库设计以及抽题算 法的设计【4 7 】。如何设计一个算法从试题库即快又好的抽出一组最符合考试要求的 试题，是本文研究的目的之一。 目前常用的算法有： 1 ) 随机选取法 随机选取法根据用户提交的组卷要求，由于计算机利用随机函数自动抽取若 干分量构成状态类型，再从试题库中选取一道试题加入试卷中，此过程不断重复， 直到生成试卷或者题库中取出不合适的题目为止。随机选取法的特点是实现简单， 对于题库不太大的试题来说，速度快、成功率高。建设某课程的试题库，可以考 6 重庆大学硕士学位论文 1 绪论 虑使用该算法。 该算法在用户要求小于试题题量时，总能成功，且速度快，但当试题库中某 一状态储题量较小，不能满足用户要求时，组卷往往以失败告终。 2 ) 回溯试探法 回溯试探法是对随机选取法的改进，它将随机选取法产生的第一状态类型记 录下来，当搜索失败时释放上次记录的状态类型，然后再根据一定的规律变换出 一种新的状态类型进行试探，通过不断回溯试探直至试卷生成或退回出发点为止。 回溯试探法在理论上可以遍历每一种可能的状态组成，但是，当试卷总题量 较大时，状态类型的变换便成为一个巨大的数字，因此，该方法只适用于状态类 型和试卷总题量都较少的题库系统，而且该方法对内存的占用较大，程序结构比 较复杂，所以选试题比较缺乏随机性。 3 ) 随机化启发式搜索法 随机化启发式搜索法是比较有效的方法之一，它建立在适当的概率模型和人 工智能的搜索理论基础上，是对随机选取法和回溯试探法的改进。 在搜索的前几步中采取随机选取法，当搜索进入死结点时，采用下面的方法 作启发后再试：首先将造成死结点的状态类型记录下来，然后回溯走过的路径， 将与该状态有关( 指某分量相同) 的元素全部释放，将剩下的无关元素重新构成 一个路径然后根据启发函数的最小值确定下一个结点。启发函数定义为新元素状 态类型与记录死结点元素状态分量相同的个数。 若用户的要求合理，则该算法组卷成功率高，且用户等待时间短，具有较好 的通用性，但该算法增加了程序设计的复杂度，适用于试题量较大的题库系统。 4 ) 遗传算法 遗传算法g a ( g e n e t i ca l g o r i t h m ) 是一种模拟自然界生物进化过程的计算模型， 遗传算法能解决随机算法的盲目随机性，并能从群体中选择更满足条件的个体， 具有很强的智能性，同时它能根据不同的环境产生不同的后代，具有动态性，自 适应性，从而能满足题库不断变化的要求，由于试题库容量大，覆盖面广，因此 选题计算量大，利用遗传算法的内在并行性，可以有效的解决计算量大的问题。 但遗传算法主要通过交叉算子繁衍后代，当交叉算子所作用的两个个体相同 时，不能产生有意义的新的个体，因此要求初始种群体具有广泛多样性。当群体 进化到其中的各个个体均相同时，交叉算予无效，此时仅靠变异算子产生新的个 体，遗传迭代难以进行下去，即发生所谓“早熟收敛”现象。 本论文在对组卷系统进行研究的同时，根据教育测量理论，制定符合教育测 量理论的试题属性，以及有利于算法的题库结构，并结合了遗传算法理论，对算 法进行改进，采用改进的自适应遗传算子，优化了交叉和变异操作，解决了遗传 7 重庆大学硕士学位论文 1 绪论 算法在组卷系统中易出现的低效及“早熟”等问题。 1 4 论文主要工作及结构安排 论文的主要工作包括：分析现有考试系统的结构，结合实际应用需要，设计 出考试系统的结构，并进行系统详细设计；研究组卷系统的数学模型，分析现有 组卷算法的不足，在此基础上提出一种改进的组卷算法；详细分析组卷的各项约 束指标，根据教育测量理论建立组卷数学模型，并将改进的组卷算法应用到组卷 系统中。 论文的结构安排如下： 第一章绪论。介绍论文的研究背景、研究目的和意义、国内外研究现状、论 文的主要工作以及论文的组织结构。 第二章考试系统结构。对考试系统进行了需求分析和详细设计，并简单介绍 了考试系统的关键问题。 第三章组卷评价与建模。分析了组卷的评价指标和各指标问的关系，并采用 试题各项评价的分布构建了成卷模式，在此基础上根据成卷模式的偏好关系建立 了组卷模型，得到了组卷模型的目标函数。 第四章组卷算法研究。对遗传算法进行了研究，在此基础上提出了一种用于 组卷的改进遗传算法。 第五章总结与展望。对全文工作进行了总结，并提出了下一步工作的设想。 1 5 本章小结 本章主要论述了论文的研究背景，国内外研究现状，论文研究的目的与意义， 最后对论文的工作和结构安排作了简单介绍。 8 重庆大学硕士学位论文2 考试系统结构 2 考试系统结构 本系统是为了满足教育在线实时考试的需求而设计开发的，是一个开放式、 实用性、可实现大容量用户并发的在线考试系统，采用流行的b s 三层体系结构， 运行于所有操作系统之上，可在i n t r a n e v d i n t e m o t 上进行实时的考试。 2 1 需求分析 2 1 1 系统功能要求 系统需要一个高效共享的标准化题库，来保存试题信息。用户应该能对题 库进行有效的管理，对题库进行维护和管理，如添加新的试题，对选定的试题进 行修改或删除等。试题类型可为单选题、填空题和解答题等。 用户可用智能组卷系统进行自动组卷，设置一定的参数，如各章节的考察 比例、难度分值比以及各类题型的题数和分值等，组卷系统根据用户设置的条件 来组成一份满意的试卷。用户也可使用手工组卷系统，手动地挑选试题组卷。为 了研究组卷算法，提供一定的算法分析功能。系统可同时保存多份试卷，教师可 浏览试卷，查看试卷内容。考试前，从众多试卷中选出一份供本次考试使用。 对于在线考试，考生只需通过标准w e b 浏览器便可参加，考试前应登录， 在限定的考试时间答题；时间到时，强行交卷。对于考试过程中出现非法操作或 断电死机等意外故障而导致考试中途停止的情况，系统应提供一次登录功能，可 恢复考生的答题状态。 提交试卷后，系统可对客观题部分( 如单选题) 进行自动评分。对于主观题部分， 系统提供评分功能来使教师能按试卷试题阅卷，并给定主观题的分数。当某考生 所答的主客观试题均已评分后，系统可对各类题型的分数进行汇总，得出考生总 分数并存入成绩库中。 系统可以对考试成绩和试卷进行科学有效的分析，为教学提供有效的反馈 信息。成绩发布后，考生可查阅自己的考试成绩。 2 1 2 系统设计要求 由于考试机构进行在线考试时的需求的多样性以及使用系统用户的能力和水 平的千差万别。因此，在进行在线系统设计时，充分考虑了系统的可扩展性、易 于维护和管理、易于使用、高性能和高可靠性，智能化和计算能力强，可分布式 处理和设计，以及系统的安全性。 用户易用性及易于管理 由于在线考试系统的特点决定了接触和使用本系统用户规模的庞大和水平的 9 重庆大学硕士学位论文2 考试系统结构 多样性以及使用平台的不确定性。因此，我们希望给网络用户提供一个方便的与 平台无关的访问使用接口。w e b 无疑是最好的选择。本系统基于b s 结构三层体 系，即方便了用户的使用，又便于系统管理员以w e b 方式对系统及系统数据库进 行管理维护。 智能化和强大的计算处理能力，支持分布式处理计算 本系统中引入的遗传算法，既解决了传统考试系统中出卷的随机性，其内在 的并行性，又可满足用户进行并行分布式处理设计的需要。 系统的可维护性和规模的可扩展性 由于考试机构形式及内容的不断变化，要求本系统的开放性和可扩展性很强。 2 1 3 系统安全要求 系统安全是保证一个主机系统的安全，主要包括主机系统的密码安全、重要 服务器( 如w w w 服务器) 、数据库服务器等大型应用系统的安全。 软硬件安全要求 该系统的安全涉及到服务器硬件安全和软件安全。服务器硬件安全主要是防止服 务器上存放试题资料的硬盘的物理损坏而造成资料的丢失。软件安全主要是针对 网络上的数据传输安全。 机密性安全 由于是基于w e b 的在线考试系统，安全性便显得至关重要，特别是涉及许多 重要的信息，如试卷信息，成绩信息等，因此保证信息不被泄露给非授权的人或 实体。 2 2 详细设计 2 2 1 数据库设计 考试系统有大量的数据需要存储，如题库试题，定义好的试卷，考生状态及 考生成绩等。本系统数据库名为t e s t ，内建8 个数据表，具体设计如下： 选择题表：用于存储选择题，该表包含： 试题编号( q d ) ( 题目在数据库中的唯一标识) ； 试题内容( q c o n t e n t ) ： 第一个选项内容( q a n s w e r a ) , 第二个选项内容( q a n s w e r b ) ； 第三个选项内容( q a n s w e r c ) ； 第四个选项内容( q a n s w e r d ) ； 试题答案( q a n s w e r ) ： 试题类型( q t y p e ) ； 1 0 重庆大学硕士学位论文 2 考试系统结构 试题所属知识点( q k n o w l e d g e ) ； 试题难度( q d i f f i c u l t y ) , 试题分值( q m a r k ) ； 试题使用频次( q u s e r _ f i m e s ) ： 试题正确率( c o r r o a _ t 豳s ) ( 用于计算难度) ； 修改日期( d a t e ) ( 该日期为修改当天的系统日期) 。 填空题表：用于存储填空题。该表包含： 试题编号( q i d ) ( 题目在数据库中的唯一标识) ； 试题内容( q c o n t e n t ) ； 试题答案( q a n s w e x ) ： 试题类型( q t y p e ) ： 试题所属知识点( q k n o w l e d g e ) ： 试题难度( q d i f f i c u l t y ) ； 试题分值( q m a r k ) t 试题使用频次( q u s e r _ f i m e s ) ： 试题正确率( c o r r e c tt i m e s x m ：酣算难度) ； 修改日期( d a t e ) ( 该日期为修改当天的系统日期) 一 主观题表：用于存储主观题。该表包含： 试题编号( q i d x 题目在数据库中的唯一标识) ； 试题内容( q c o n t 髓t ) ： 试题答案( q a n s w c r ) ( 可为空，此处为参考答案) ； 试题类型( q t y p e ) , 试题所属知识点( q k n o w l e c l g e ) t 试题难度( q d i f f i c u l t y ) ； 试题分值( q m a r k ) ； 试题使用频次( q u s e r _ t i i n e s ) ： 试题正确率( a 耵鳅缸e s ) ( 用于计算难度) ； 修改日期( d a t e x 该日期为修改当天的系统日期) 。 p a p c r d o c 表：用于存放各测试卷的名称、试卷号、分数、考试时间、生成试 卷标志位和是否被核分标志位。该表包含： 试卷编号( p ) ( 试卷在数据库中的唯一标识) ； 试卷名称( p n a m e ) ： 考试时间( p t t m e ) ； 试卷总分数口s c o f e ) 重庆大学硕士学位论文 2 考试系统结构 生成试卷标志位( g e n e r a t e ) ( 在试卷浏览中被调用，用于判断该试卷是否生成试 卷1 ： 核分标志位( f i n i s h x 判断是否要将该试卷做为考试卷，在评分子系统中被调 用，判断该试卷是否被核分) 。 p a p e r 表：用于存放各测试卷的试题。该表包含： 试卷号( p ) ) ( 试卷在数据库中的唯一标识) ； 试卷名称( p n a m e ) , 试题类型( q t y p e ) ； 试题号( q ) ) ； 试卷中试题号( p q i d ) ( 系统自动生成) 。 a b s w c r 表：用于存放考试过程考生每道题的答案。该表包含： 学号( s d ) ( 该考生在数据库中的唯一标识) ； 学生姓名( s n a m e ) ； 试卷号( p d ) ( 试卷在数据库的唯一标识) ； 试卷名称( f n a m e ) , 试卷中试题编号( p q i d ) ( 试题在试卷中的编号，系统自动生成) ； 试题编号( q 叻( 试题在数据库中的唯一标识) ； 试题类型( q t y p e ) ； 考生答案( s a n s w e r x 用于记录考生每道题的答案) ； 试题得分( s c o r e ) ( 用于选择题和填空题，记录该题的得分) ； 评分标志位( f l a g ) ( i 己录该题是否被评分，默认值为0 ，选择和填写空题自动判 断，f l a g 置1 ) 。 s t a t u s 表：用于存放考生的考试状态，记录考试剩余时间，当前题号，并设 有开始位和结束位。该表包含： 学号( s d x 该考生在数据库中的唯一标识) ； 试卷号( p d ) ( 试卷在数据库中的唯一标识) ； 剩余小时( l t h n eh o u r ) ( 录考试剩余小时数) ； 剩余分钟( l t i m e m i n u t ex 记录考试剩余分钟数) ； 剩余秒( l t i m e c o n 似记录考试剩余秒数) ； 当前题号( c u n 舶t _ i d ) ( 记录答题时的当前题号，不是p q i d ，是试题过程中显示 的答题号) ； 开始位e g i l l - n a 曲( 记录考生是否开始考试，当开始考试时将该位置d ； 结束位( f i n i s h _ f l a g ) ( 记录考生是否结束考试，当考试正常结束时将该位置1 ) 。 s c o r e 表：用于存放考生的考试成绩。该表包含： 重庆大学硕士学位论文2 考试系统结构 学号( s i d x 考生在数据库中听唯一标识) ； 姓名( s n a m e ) ： 试卷号( p ”( 试卷在数据库中的唯一标识) ； 试卷名称( p n a m e ) ； 分数( s c o r e ) ( 该考生此试卷的得分1 ； 核分标志位0 ：l a g ) ( 拍j 断该张试卷是否被核分，默认值为o ) 。 2 2 2 功能模块设计 本系统有六个子系统，包含的主要模块有：登录模块、题库管理模块、智能 组