（计算机应用技术专业论文）试卷辅助生成系统的设计与实现.pdf

华中科技大学硕士学位论文 摘要 考试是教学过程中一个极其重要的环节，而出卷是考试的重点，出卷如果仍然采 用传统的手工方式就很难跟上时代的步伐，利用试卷辅助生成系统辅助试卷生成己成 为计算机辅助教学中的一个重要研究课题，自动组卷是试卷辅助生成系统中的重要组 成部分，自动组卷算法的好坏直接影响系统的性能以及试卷的质量。如何设计一种算 法使组卷具有较高的效率和成功率是系统实现的一个难点。 传统的遗传算法采用二进制编码，在进行交叉和变异操作时，各题型的题量很难 控制，而且当试题库题量很大时编码很长。传统的遗传算法以进化代数等于最大进化 代数作为终止条件，但是在实际组卷过程中并不知道种群进化到第几代就能得到试卷 的最优组合。通过详细分析试卷的各项约束条件，建立了一个以知识点、难度系数、 区分度等为核心属性的自动组卷数学模型，并利用改进的遗传算法实现了自动组卷。 改进后的遗传算法采用分段实数编码，把同一题型的试题放在同一段，组成试卷的各 道试题的题号直接映射为基因，用实数编码不存在编码变换，因此可以提高运算效率， 而且交叉和变异操作都在各段内部进行，因此可以保证组卷过程中各题型题量的正确 匹配。在改进的遗传算法中，当适应度最高的个体的适应度值大于期望适应度值时组 卷结束。 根据试卷辅助生成系统的功能需求，对系统进行了五个功能模块的设计。这五个 功能模块分别是用户登录模块、题库录入模块、题库维护模块、试卷生成模块和系统 设置模块。试卷生成模块是系统的核心，在试卷生成模块中组卷方式有两种：人工组 卷和自动组卷。生成的试卷以及试卷答案可以直接送入目前广泛使用的字处理软件 w j r d 中，在w o r d 中可以对试卷以及试卷答案进行编辑修改并打印出来。 关键词：人工组卷，自动组卷，数学模型，遗传算法，试题库 华中科技大学硕士学位论文 a b s 仃a c t e x a m i n a t i o ni sav e r yi m p o r t a ms t e pi nt e a c h i n gp r o c e s s m o r e o v e r ，m em a i 【i r 培- u po f t e s tp a p e ri sm ec r u xo f t i l ee x 锄i n a t i o n i f t e s tp a p e h n a k i n gs t i l ia d o p t st r a d i t i o n a lm a i l u a l m e t h o d ，i ti sv e r yh a r df o ru st ok e 印u pw i t ht i m e s u s i n gt e s tp a p e r - a i d e dg e n e r a t i o n s y s t e mf o rt e s tp a p e r m a k i n gh a sb e c o m ea ni m p o n a mr c s e a r c hp 删e c ti nc o m p u t c ra i d e d i n s t r u c t i o n ，s i n c et h ea u t o m a t i cm a l ( i n g u po f t e s tp a p e ri sa ni m p o 咖tc o m p o n e n ti nt e s t 脚e r - a i d e dg e n e r a t i o ns y s t e m ，t h ea l g o r i t h j 【1 1o fa u t o i n a t i cm a k i l l g u po ft e s tp a p e r 谢l l h a v ead i r c c te 低c to nt | i ep e r f b r i l l a i l c eo fs y s t e ma 1 1 dt h eq u a l i t yo ft e s tp 印e r ni sh a r dt o d e t e 肌i n eh o wt od e v i s ea i l a l g o r i t l l l _ 1 1t om a k et e s tp a p e r - m a k i n gm o r ee f f i c i e n ta n d s u c c e s s f u l a s 订a d i t i 9 n a lg e n e t i ca 1 9 0 r i t l l ma d o p t sb i n a r yc o d e ，w h i l ec r o s s i n ga n dm u t a t i n g ，i ti s d i 历c u l tf o ru st oc o m r o lt 1 1 eq u a l l t i t yo fe v e r yq u e s t i o nt y p e ，a i l dw h e nt l l eq u a n t i t yo f e x a m i n a t i o nd a t a b a s ei sv e r yl a r g e ，t h ec o d eb e c o m e sv e r yl o n g t h d i t i o n a lg e n e t i c a l g o r i t h i nt a k e s “e v o i u t i o ng e n e r a t i o ne q u a l st om el a r g e s te v o l u t i o ng e n e m t i o n a si t s e n d i n gc o n d i t i o ng e n e r a t i o n b u t ，i nt h ep r o c e s so fp r a c t i c a lt e s tp 印e r - m a k i n g ，w es t i i ld o n o t 王( 1 1 0 wh o wm a n yg e n e m t i o n sp 叩u l a t i o ne v 0 1 v e sa i l dw h e nw ec a l lg e tt h em o s t s a t i s f a c t o r yt e s tp 印e r a f t e rac a r e 血1a n a 王y s i so f e a c hb i n d i n gc o n d i t i o ni nm et e s tp a p e r ， w eh a v es e tu pam a m e m a t i c a lm o d e lf o ra u t o m a t i ct e s tp a p e r i m a l ( i n gb a s e do nh o w l e d g e p o i m ，d j 币c u i t yf a c t o r d i s t i n g u i s h m gd e g r e e ，e t c ，a n dh a v er e a l i z e d a u t o m a t i ct e s t p a p e r - m a k i n gw i t hi n l p r o v e dg e n e t i ca l g o r i t l l r l l i m p r o v e dg e n e t i ca l g o r i t l l i l la d o p t s s e g m e n tr e a ln u m b e rc o d e ，p u t t i n gt h eq u e s t i o no ft l l es a m et y p eo nm es 锄es e c t i o n ，锄d m e nt h eq u e s t i o nn u m b e rm a p sg e n ed i r e c t l yr e a ln 啪b e rc o d ed o e sn o tc o n v e r t ，t h u s ，i t m a ye i l l l a n c eo p e r a t i o ne m c i e n t l yi na d d i t i o n ，c r o s s o v e ra 1 1 dm u t a t i o no p e r a t i o nc o n d u c ti n t h ei m e r i o ro fe a c 抽s e c t i o n ，i tm a yg u a r a n t e et h eq u a n t i t yo f e a c ht y p ec o r r e c tm a t c h i n gi n t h ep c e s so ft e s tp a p e h n a k i n g i ni m p r o v e dg e n e t i ca i g o r i t ，w h e nt h e 矗t n e s sv a l u eo f h i g h e s ti n d i v i d u a li sl a 略e rt h a t le x p e c t a t i o nf i t n e s sv a l u e ，t e s tp a p e r m a l ( i n gi sf m i s h e d a c c o r d i n gt ot h ef l l i l c t i o n a ld c m a n do ft e s tp a p e r _ a i d e dg e 删i o ns y s t c m ，、eh a v e d e s i g n e df i v e 血n c t i o n a lm o d u l e s ：u s e rr e g i s t e r ，e x a m i n a t i o nd 砒a b 船ei n p u t ，e x 啪i n a t i o n d a t a b a s em a i n t e n a n c e ，t e s tp a p e r g e n e m t i o na n ds y s t e ms e t u p t e s tp 印e rg e n e r a t i o n m o d u l ei s 恤ec o r co ft h es y s t e m ，i ti n c l u d e st w ow a y so ft e s tp a p e r m 珧j i 培：m a n u a la n d a u t o m a t i c ，t e s tp a p e ra sw e l la si t sa n s w e r sc a nb es e n td i r e c t l yi n t om i c r o s o f to m c ew b r d ， i nw h i c ht e s tp a p e ra s 、e l la si t sa n s w e r sa r ee d i t e d ，r e v i s e da 1 1 dp r i n t e do u t k e yw o r d s ：m a l l u a lt e s tp a p e r m a l 【i n g ，a u t o m a t i ct e s tp 印e r - m a k i n g ， m a m e m a t i c a lm o d e l ，g e n e t i ca l g o r i m m ，e x a m i n a t i o nd a t a b a s e i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：详刻 日期：硼年r 月岁日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密口。 ( 请在以上方框内打“”) 学位论文作者签名：评狍 日期；沙年，月歹日 指导教师签名：等电1 日期：陟6 年r 月7 日 华中科技大学硕士学位论文 1 绪论 1 1 课题背景 计算机技术的高速发展，对教育的管理模式、教学模式带来了巨大的影响，教育 要适应未来社会的需要，就要有新的教育思想，新的教育理论。计算机辅助教学【1 ，2 l 的产生与发展对促进教育、教学技术的变革与发展具有巨大的推动作用。考试是教学 管理中一个重要的环节，而出卷是考试的重点，出卷如果仍然采用传统的手工方式就 很难跟上时代的步伐，利用计算机辅助试卷生成已成为当今非常热门的话题。 考试不仅要对学生的学习情况进行评价，而且还要对任课老师的教学质量进行评 价，为了使评价公f 、准确，需要合理的组卷1 3 。传统的手工出卷是教师根据教学大 纲、教材要求或所讲授的内容来手工命题组卷，采用这种方式出卷需要根据许多教师 多年的教学经验，经过反复推敲，才能完成一份比较满意的试卷。而且组织试卷这一 过程是一项非常繁重的脑力劳动，从收集资料到试题的选取、试题分值的设爱等工作 非常烦琐。 采取传统的手工出卷，存在一些弊端。由少数任课老师凭借经验出卷，考试前有 些学生总爱向任课老师打听考试的重点，有些任课老师也习惯在考前给学生划重点， 而且手工出卷在试卷的标准化程度、题量大小、覆盖面等方面都难以控制，不可避免 由不同老师出卷而产生试题的难度、重点、内容的差异，这样的试卷很难做到考试的 公平性、合理性，不利于对教学质量的统一评估。有些学校的评价为了避开任课老师 经常请一些没有任课的老师来命题，这样经常会出现试卷过难或过易的情况，使评价 失去原有的意义。 总之，传统的手工出卷存在许多不足，主要原因在于缺少科学的命题程序，缺少 控制命题质量的有效措施。随着计算机技术的飞速发展，传统的手工出卷已经不能适 应现代化教学的需要【4 】，因此，必须进行改革。如果利用计算机辅助试卷生成，建立 有效的试题库，待需要考试之前，输入试卷的各项约束条件，由计算机快速地生成试 卷，这样不仅可以减少甚至可以杜绝由于各种主观因素产生的误差，而且方便科学， 华中科技大学硕士学位论文 试卷具有很高的保密性。 随着计算机在组卷、阅卷、计分等方面的广泛应用，在很多学科里，都开始采用 计算机辅助生成标准化试卷进行标准化考试5 1 。目前，各级各类学校都在推行标准化 考试，在教学和考试改革中逐步实现规范化、标准化的教学管理。实践证明，使用计 算机辅助试卷生成系统具有许多优越性，归纳起来主要有以下几点6 ，7 1 。 ( 1 ) 提高了考试工作的科学性和严肃性，使考试工作更加规范化，促进了教学管理 水平的不断提高。 ( 2 ) 使用试卷辅助生成系统大大地缩短了命题时间，可以减轻教师的负担。试卷辅 助生成系统可以根据用户要求，随时输出一套套试卷，从而减轻了教师的负担。 ( 3 ) 使用试卷辅助生成系统可以提高试卷的质量。试题库中的每一道题，我们都可 以事先进行主观预测或样本测试，很多指标( 如难度、区分度等) 都有确定的参数， 从而可以做到心中有数，且题量多，覆盖面宽，有一定的准确性和科学性，生成的试 卷能够测出学生较真实的成绩。 ( 4 ) 使用试卷生成系统有助于调动教师的积极性，提高教学质量和教学管理水平。 因为用试卷辅助生成系统来生成试卷，试题库中每道试题被命中的几率是相等的，因 此可以做到公正无私，而且改变了以前谁授课谁命题以及划范围、定重点的做法，促 进教师严格按教学大纲进行教学，努力上好每一堂课，强化教师之间的竞争意识。 1 2 国内外概况 自动组卷是试卷辅助生成系统中的重要组成部分，自动组卷算法的好坏直接影响 到试卷辅助生成系统的性能以及试卷的质量。如何从试题库中选出试题组成符合用户 要求的试卷，并使组卷具有较高的效率和成功率是系统实现的一个难点。现有的试卷 辅助生成系统在实现自动组卷时一般采取三种算法：随机选取法、回溯试探法和遗传 算法。 1 2 1 随机选取法 随机选取法【8 1 有两种情况，一是从试题库中随机抽取试题，然后判断是否符合试 卷的约束条件。二是从符合试卷某项约束条件的试题库子集中随机抽取试题，然后判 2 华中科技大学硕士学位论文 断是否符合试卷的其它约束条件。实际上随机选取法就是在试题库中随机搜索满足条 件的试题，不断重复搜索过程，直到试卷生成操作完成或不能搜索到满足约束条件的 试题为止。随机选取法对于单道题的抽取运行速度较快，但是对于整个组卷过程来说 组卷成功率低，即使组卷成功，花费的时间也令人难以忍受。尤其是当题库中各状态 类型平均出题量较低时，组卷往往以失败而告终。文献 9 给出了具有均匀概率分布 的、知识点不重复的随机自动组卷算法。在试卷生成过程中，首先确定每种题型的题 量和每个知识点的题量，然后根据要求随机抽耿试题组成试卷。文献 1 0 根据用户提 出的需求，从试题库中根据所需题型、试题的难度系数、每种题型所占的分值以及每 种题型所需的试题数随机抽取试题组成试卷。实验证明，采用随机算法自动组卷，组 卷算法简单，但是该方法具有很大的随机性和不确定性，求解效率不高。随机选取法 自动组卷流程图如图i 1 所示。 1 2 ，2 回溯试探法 图1 1 随机选取法自动组卷流程图 回溯试探法【川有“通用的解题法”之称，用它可以求出问题的所有解或任意解。 回溯试探法是将随机选取法产生的每一状态类型记录下来，当搜索失败时释放上次记 华中科技大学硕士学位论文 录的状态类型，然后再依据一定的规律( 正是这种规律破坏了选取试题的随机性) 变 换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点 为止，这种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统而言， 组卷成功率较好，但是在具体应用这种算法时发现这种算法对内存的占用量很大，程 序结构相对比较复杂，而已选取试题缺乏随机性，组卷时间长，后两点是用户无法接 受的，因此它也不是一种很好地用来自动组卷的算法。回溯试探法在包含问题的所有 解的一棵状态树中，按照深度优先的策略，从根出发进行搜索。该深度算法理论上可 以遍历每一种可能的组合，但实际上当题库中的试题量较大时，状态类型的组合树便 产生了组合爆炸，所以该方法只适用于题少的试卷辅助生成系统。文献 1 2 采用了回 溯试探法实现自动组卷，为了使选择的章节不重复从而达到知识覆盖率的要求，这种 算法对每章节设置了一个选择标志，当某一章节被选中，标志置位，当在某章节的试 题中进行了一定次数的选择后，选取的试题不能满足命题计划的指标就回溯，再通过 随机产生章节序号在新的章节中抽取试题，同时上一章的选择标志复位。实验证明， 采用回溯试探法组卷成功率高，但它是以牺牲大量的时间为代价的，因此它也不实用。 1 2 3 遗传算法 遗传算法【1 3 _ 1 6 1 ( g e n e t i ca l g o r i t h m ，简称g a ) 是由进化论和遗传学机理相结合而 产生的直接搜索优化算法【1 7 】，因此，在这种算法中会用到各种进化和遗传学的概念， 下面先介绍几个概念。 ( 1 ) 串( s t r i n g ) ：即遗传学中的染色体，它是个体的形式。 ( 2 ) 群体( p o p u l a t i o n ) ：个体的集合称为群体，串是群体的元素。 ( 3 ) 基因( g e n e ) ：基因是串中的元素，基因用于表示个体的特征。 ( 4 ) 群体大小( p o p u l a t i o ns i z e ) ：在群体中个体的数量称为群体大小。 ( 5 ) 基因位置( ( k n e p o s i t i o n ) ：一个基因在串中的位置，有时也简称基因位。基因 位置在串中从左向右计算。 ( 6 ) 适应度( f i t n e s s ) ：表示某一个个体对于环境的适应程度。 遗传算法是一种“生成+ 检测”的迭代搜索算法，遗传算法是以适应度函数( 或 目标函数) 为依据，通过对群体中的个体进行遗传操作实现群体内个体结构重组的迭 4 华中科技大学硕士学位论文 代处理过程。在这一过程中，群体中的个体一代一代地得以优化，并逐渐地逼近最优 解，最终获得最优解。传统遗传算法的主要步骤包括初始染色体群体生成、适应度评 估和检测、选择操作、交叉操作和变异操作。传统遗传算法的主要工作过程1 8 。2 0 】如下。 ( 1 ) 随机产生初始染色体群体。染色体采用二进制编码，用l 表示某题选中，用o 表示某题没有选中。每条染色体有n 个基因，n 为试题库的题量，n 个基因对应n 道 试题，每个基因是一道入选的试题，一条染色体就是随机组成的一套试卷，因此初始 染色体群体就是问题假设解的集合。设置进化代数计数器t 初值为o ，最大进化代数 为t 0 ，随机产生的m 条染色体作为初始染色体群体q ( o ) 。 ( 2 ) 个体评价，利用适应度函数计算个体的适应度值。适应度是对染色体进行评价 的一种指标，是遗传算法进行优化所用的主要信息，它与个体的目标值存在一种对应 关系。染色体的适应度越高，问题的解就越优，即表示这个试题的组合的各项约束条 件越接近用户指定的理想值。 ( 3 ) 将群体q ( t ) 进行选择、交换、变异操作。每条染色体进行交叉和变异操作后， 很可能变为非法，即染色体中l 的个数很可能大于或小于试卷中要求的题量，因此必 须对染色体进行修f ，具体做法是进行相应的运算，使得染色体中1 的个数等于试卷 中要求的题量。修正后得到下一代群体q ( t + 1 ) ，下一代群体中包含选择的染色体以及 交叉和变异操作后产生的新染色体。同时t = t + 1 。 1 ) 选择。根据适应度对染色体进行排序，选择操作通常采用比例选择，即选择概 率与个体的适应度值成正比，这就意味着适应度值高的个体选择概率大，从而提高群 体的平均适应度值。 2 ) 交叉。两个个体按一定的概率，随机的选择一个交换点进行交换，所产生的新 个体添加到新群体中。交叉操作通过交换父代个体的部分信息构成后代个体，使得后 代继承父代的有效模式，从而有助于产生优良个体。 3 ) 变异。个体按一定的概率，随机地改变某一个个体的基因位后添加到新群体中。 变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避 免早熟收敛。 ( 4 ) 重复执行步骤2 和3 ，一旦达到终止条件，即进化代数t 等于最大进化代数 华中科技大学硕士学位论文 t o 时，则以进化过程中得到的具有最高适应度值的个体作为最佳解，终止运算。 传统遗传算法流程图如图1 2 所示。 随机产生初始染色体群体q ( o ) ，卢0 n y 计算当前染色体群体中个体的适应度值 根据个体的适应度值及 选择策略进行选择操作 进行交义、变异操作 产生染色体群体q ( t + 1 ) ，t = f + l 剀 图1 2 传统遗传算法流程图 遗传算法是一种新发展起来的并行优化算法。它不依赖于问题的具体领域，对问 题的种类有很强的鲁棒性，所以广泛应用于很多学科。遗传算法之所以能如此广泛地 使用和发展，这和它自身的显著优点是分不开的。遗传算法具有以下几个优点。 ( 1 ) 遗传算法属于群体搜索算法，它从多个初始点开始搜索，不易陷入局部最优。 ( 2 ) 遗传算法采用数学编码表示个体，运用选择、交叉、变异等算子进行操作，不 需要导数信息，也不需要目标函数连续。 ( 3 ) 概念简单，容易掌握，算法运用自然选择，适者生存的规律引导种群搜索最优， 具有一定的自适应性，优化人员不需要对目标函数的特性有太多的了解。 ( 4 ) 遗传算法具有自组织性、自适应性和智能性。应用遗传算法来求解问题时，在 华中科技大学硕士学位论文 确定了编码方案、适应度函数及遗传算子后，算法将利用进化过程中所获得的信息自 行组织搜索。遗传算法的这一特性，使它同时具有能根据环境的变化而自动发现环境 的特性和规律的能力。从而使遗传算法可以用来解决一些复杂的非结构化的问题。 ( 5 ) 遗传算法是一种随机优化算法，它采用概率的变迁规则来指导它的搜索方向。 在优化过程中，使搜索的每一步向最终结果靠近的机制或智能性称为搜索的探索性或 启发性。 ( 6 ) 遗传算法对给定的问题，可以产生很多的潜在解，最终的选择可以由使用者来 确定。 遗传算法虽然是一种优化搜索算法口”，但它自身也存在些局限性。如对不同的 问题要选择合适的编码方案，不同的编码方案会影响算法的执行效率，如果编码选择 不合适就会造成遗传算法的搜索效率低下。传统的遗传算法采用二进制编码，用i 表 示某题选中，用0 表示某题没有选中，在进行交叉和变异操作时，各题型的题量很难 控制，而且当试题库题量很大时编码很长。用什么条件作为遗传算法的终止条件也是 遗传算法的一个重要问题，对不同的问题要选择不同的终止条件。传统的遗传算法以 进化代数等于最大进化代数作为终止条件，但在实际组卷过程中并不知道种群进化到 第几代就能得到试卷的最优组合，因此有时候可能得不到最优解。 分析以上三种组卷算法不难发现，在限制条件状态空间的控制下，随机选取法有 时能够抽取出一组令用户满意的试题。只不过由于它随机选取试题的范围太大，无法 确定目前条件下哪些区域能够抽取合适的试题，反而可能在那些已经证明是无法抽取 合适试题的区域内反复选题，进行大量的无效操作，进入死循环，最终导致组卷失败。 回溯试探法组卷成功率高，但它是以牺牲大量的时间为代价的，它也不实用。因此， 必须结合以上两种算法寻找一种新的改进算法，这种算法就是遗传算法，遗传算法很 适合解决自动组卷问题。但因为传统的遗传算法本身存在一定的局限性，因此用遗传 算法实现自动组卷时，要对传统遗传算法在编码方法、终止条件和遗传算子上进行一 些改进。 1 _ 3 课题主要研究工作 建立试卷辅助生成系统的主要目的是在计算机上建立一个试题库，然后根据试卷 华中科技大学硕士学位论文 的约束条件从试题库中人工选取试题或自动选取试题构成一份满足用户要求的试卷。 主要研究工作包括以下三个方面。 ( 1 ) 详细地分析了试卷生成过程中试卷的各项约束条件，建立了一个以知识点、难 度系数、区分度等为核心属性的自动组卷数学模型，并在传统遗传算法的基础上对编 码方法、终止条件、遗传算子进行了一些改进，提出了一种利用改进型遗传算法实现 自动组卷的方法。 ( 2 ) 分析了试卷辅助生成系统的功能需求，根据系统的功能需求，对系统进行了五 个功能模块的设计。试题库是建立试卷辅助生成系统的基础，试题库的质量直接影响 试卷的质量，因此对试题库的结构进行了详细地设计。 ( 3 ) 介绍了系统实现过程中用到的两种技术，a d o 技术和w o r d 组件技术。以计算 机文化基础理论考试试卷生成为例，对系统各功能模块的实现做了详细地介绍，给出 了各功能模块的处理流程。 华中科技大学硕士学位论文 2 基于遗传算法的试卷自动生成 自动组卷就是根据用户的要求，采用一定的算法自动地从试题库中抽取一定数量 的试题组成试卷“。要想使试卷辅助生成系统能按用户要求自动地抽取试题组成试 卷，首先必须了解用户要求，但用户对试卷的要求往往是模糊的，因此自动组卷首先 要解决的问题就是将这些模糊的要求进行量化，转化成计算机可以理解的要求，也就 是将用户的要求转化成对试卷的具体要求，如考试时间、试卷难度要求、知识考查范 围等等。知道了用户对试卷的要求后，就只需要找到满足这些要求的试题组合即可。 2 1 试卷约束条件分析 一般来说，用户在生成试卷时会对试卷提出多方面的要求，如试卷中包含的题型、 每种题型的题量、试卷难度、试卷区分度、试卷的总答题时间等等，用户的每一个要 求对应一个试卷约束条件，生成试卷时就是按照这些约束条件，由计算机自动从试题 库中选取试题，组成份符合用户要求的试卷。要组成一份符合要求的、高质量的试 卷。对于一个组卷系统来说，它应该考虑以下几个方面1 2 引。 ( 1 ) 总分的设置。根据用户的需求，设置试卷总分。 ( 2 ) 试卷中包含的题型和每种题型题量的控制。试卷中包含的题型以及各种题型的 题量由用户决定，并且各小题的分值之和必须达到总分要求。 ( 3 ) 考试内容可以由用户决定，各个知识点在试卷中所占的比例也可以由用户根据 需要来决定。试卷的覆盖面要广，对课程的主要内容一定要覆盖到，这样的试卷才会 具有代表性，此外，试卷要有重点与非重点之分。 ( 4 ) 试卷难易程度的控制。由于知识点侧重的不同，题目有难易之分。对于不同类 型的学生，其试卷难易程度也应有所不同。试卷中试题的难度比例要符合考试大纲的 要求，试卷的难度要适中，并且能根据不同的时间、不同的考试对象动态地改变。 ( 5 ) 组成的试卷应该能够区分不同水平学生的能力，即全卷的区分度不应该太低， 不然不同的学生的分数都接近于一致，达不到考试的目的。 ( 6 ) 试卷的总答题时间可由用户来决定。 9 华中科技大学硕士学位论文 2 2 试题核心属性的确定 在自动组卷系统中，一些文献设置了试题的各类属性，如章节、题类、细目、层 次、要求、题型、难度系数、难度级别、各章节分值等属性24 | ，其实过多的试卷约束 条件会增加实际组卷的难度、降低效率，使遗传算法陷入局部徘徊不前的状态。通过 对试卷约束条件的分析可以发现，组卷的各项约束条件的重要性是不一样的，而且许 多约束条件之间存在内在的联系，因此有必要精简约束条件，试题的属性也有必要精 简。以教育学理论为指导，选择以下属性作为试题的核心属性。 ( 1 ) 题号。试题的编号，在不同的试题表中用来唯一标识试题。 ( 2 ) 题型。试题的类型。如选择题、填空题、判断改错题、简答题等。 ( 3 ) 知识点。某道题属于某门课程的哪个知识点，知识点的设置不以章节为依据， 从而可以避免教材版本的不同对组卷造成影响。知识点的划分采用树型分层的方法， 每个叶子结点( 知识点) 深度不一定相同。 ( 4 ) 难度系数。难度系数障5 1 是表示某一试题的难易程度，通常用未通过率来表示， 即一次考试中未答对某道试题的考生数在其总体中所占的比例。难度系数是评价试题 质量的一个数量指标。难度系数除了与知识点的含量有关外，还与学生对该试题的适 应程度有关。它并不是试题本身所固有的属性，而是一个动态指标。难度系数可以由 统计资料来求得，在求试题的难度系数时，我们可以根据试题的类型具体分析。 1 ) 对于客观题，其计算公式为： h = m n 其中h 表示试题的难度系数，m 表示答错某题的人数，n 表示参加测试的总人数。 2 ) 对于主观题，其计算公式为： h = p k 其中h 表示试题的难度系数，p 表示测试者某题的平均失分，k 表示某题满分。 显然，h 值越大，试题的难度就越高。一般来说，难度系数值为o 5 时，是中等 难度，如果小于o 3 试题太简单，如果大于o 7 试题太难，对考生都会做或都不会做( 难 度系数为0 或为1 ) 的试题，属于无意义的试题，必须淘汰。 ( 5 ) 区分度。区分度口6 】是指某道题对不同水平考生加以区分的能力。区分度高的 华中科技大学硕士学位论文 试题，对学生水平有较好的鉴别力，在区分度高的试题上，学得好的学生得高分，学得 不好的学生得低分，也就是通常说的分数能够拉开距离。区分度低的试题，学得好的 与学得不好的学生得分差不多。试题的区分度越高，试题的质量越好。区分度的计算 公式为： b ：旦兰 世 其中，b 表示试题的区分度，h 表示样本中高分组在某题上所得的平均分l 表示 样本中低分组在某题上所得的平均分，k 表示某题满分。高分组和低分组一般各占样 本的2 5 3 0 ，最好取2 7 。一般来说，试题的区分度在0 4 以上就被认为是很好的。 在0 3 o 3 9 之间，认为良好：在o 2 o 2 9 之间，认为可以；在0 1 9 以下，认为差， 必须淘汰或加以修改。对在校学生的达标考试，试卷的区分度不宜太高，因为它不是 选拔性质的考试。但也不能过低，否则对学生的鉴别效果差，不能很好的达到考试的 目的。一般区分度控制在o 2 0 3 之间为宜。 ( 6 ) 分值。某小题的分数。 ( 7 ) 答题时间。完成某题估计所需的时间。 2 3自动组卷数学模型 通过对试卷约束条件和试题核心属性的分析，建立了一个以题号、题型、知识点、 难度系数、区分度、分值、答题时间为核心属性的自动组卷数学模型口7 1 。组卷中决定 一道试题，其实就是决定一个包含题号、题型、知识点、难度系数、区分度、分值、 答题时间的七维向量( a l ，a 2 ，a 3 ，a 4 ，a 5 ，a 6 ，a 7 ) 。假设一套试卷中包含n 道试题。一套 试卷就决定了一个n 7 的矩阵s ： s 这就是问题求解中的目标矩阵，其中a i l 、a n a i 3 、a i 4 、a i 5 、a i 6 、a i 7 分别表 1 叫i f i i 刖舭 m 6 6 晒 扪 舢 叫鲫 郴 叭c 罾 c；手 3 0 剐妄 舢 2 z 已 引凇 舢 h “ 引出 m ，。，。l 华中科技大学硕士学位论文 示试卷中第i 道题的题号、题型、知识点、难度系数、区分度、分值、答题时间。目 标矩阵s 的分布分别要满足用户指定的试卷的总体要求，也就是说目标矩阵应该满足 以下试卷约束条件。 ( 1 ) 试卷中包含的题型以及每种题型的题量要与用户的设置相符。 k 种题型的题量= 6 ，= l 睇i ： a i 2 表示试卷中第i 题的题型，用题型号表示。如果第i 题的题型是k 种题型，则 k 种题型的数量加1 ，否则数量保持不变。 ( 2 ) 试卷中包含知识点即考核知识点以及各考核知识点所占分数的比例要与用 户设置相符。 k 种考核知识点所占分数= ( c ，口。) i ： a i 3 表示试卷中第i 题所属的知识点，用知识点号表示。如果第i 题属于k 种知识 点，则第i 题的分值a i 6 累加到k 种知识点所占的分数中，否则分数保持不变。 ( 3 ) 试卷的难度系数要满足用户的要求，试卷的难度系数【2 8 】一般用试卷中每道试 题的难度系数的加权平均来计算。即： 试卷的难度系数2 ( 日。) 总分 ( 4 ) 试卷的区分度要满足用户的要求，试卷的区分度【2 8 】一般用试卷中每道试题的 区分度的加权平均来计算。 试卷的区分度= ( 口，q 。) 总分 ，= l ( 5 ) 试卷的总分要与设置相符。 试卷的总分= 日。 华中科技大学硕士学位论文 ( 6 ) 试卷的总答题时间要与用户设置相符。 * 试卷的总答题时间= y 口， 百 从上述矩阵可以看出组卷问题是一个多重约束目标的问题求解，且目标状态不是 唯一的。在众多的约束条件内，对各项约束条件是否必须满足用户要求是不一样的， 因此，我们可以将约束条件分成两大类【2 4 】。 强约束条件：试卷的总分，考核知识点( 不考核的知识点不能出现在试卷中) ， 各题型每小题分值，试卷中包含的题型以及各题型的题量。 弱约束条件：试卷中各考核知识点所占的分数，试卷的难度系数和区分度，试卷 的总答题时间。 强约束条件必须完全达到出卷的约束条件，弱约束条件可以存在一定的误差，也 就是况可以完全达到出卷的约束条件，也可以是接近出卷的约束条件。误差的大小由 用户的要求和设置决定，即由用户的期望值和各约束条件的重要性决定。 下面根据试卷的约束条件建立目标函数。 试卷的总分、考核知识点、各题型每小题分值、试卷中包含的题型、各题型的题 量都应该是精确达到的，任何近似的解都是不行的。对于如何实现试卷中的总分要求， 可以在用户设置试卷约束条件时实现，设置时使各题型的分值之和达到总分要求。对 于如何实现试卷中只出现要考核的知识点中试题，可以在用户设置试卷约束条件之 后，生成临时数据表，试卷中包含几种题型就生成几张临时数据表，临时数据表中只 包含要考核的知识点中的试题。对于如何实现试卷中只出现与各题型每小题分值设置 相符的试题，也是在生成临时数据表时进行筛选，因此临时数据表中只包含要考核的 知识点中与对应题型每小题分值设置相符的试题。对于如何使生成的试卷中包含的题 型、各种题型的题量满足用户的要求，因为试题库中的题量大，这一要求很容易实现， 可以在生成初始染色体群体时实现这一要求。 设c i ( i ：l ，2 m ，m 为考核知识点的数量j 为用户要求的各考核知识点应占的分 数，x j ( i = 1 ，2 ，m ，m 为考核知识点的数量j 为实际生成试卷中各考核知识点所占的 分数。生成的试卷满足用户关于各考核知识点应占分数要求的程度可由下式值的大小 华中科技大学硕士学位论文 来评价： f 1 2 d 总分其中d i = | x 。- c i i ，= 1 由上式可以看出，f l 的值越小，则生成的试卷越接近于用户关于各考核知识点应 占分数的要求。 组卷中实际生成试卷的难度系数设为n d x s l ，用户指定的试卷的难度系数设为 n d x s o ，这一要求的满足程度可用下式值的大小来衡量： f 2 = ln d x s l 一n d x s o 由上式可以看出，f 2 的值越小，生成的试卷越接近于用户关于试卷难度的要求。 组卷中实际生成试卷的区分度设为q f d l ，用户指定的试卷的区分度设为q f d o ，这 一要求的满足程度可用下式值的大小来衡量： f 3 = jq f d l 一q f d o 由上式可以看出，f 3 的值越小，生成的试卷越接近于用户关于试卷区分度的要求。 组卷中实际生成试卷的总答题时间设为s j l ，用户指定的总答题时间设为s j 0 ，这 一要求的满足程度可用下式值的大小来衡量： f 4 = | s j 卜s j oi 总答题时间 由上式可以看出，f 4 的值越小，生成的试卷越接近于用户关于总答题时间的要求。 为了不至于各个误差相互抵消，实际值与用户要求值的误差都应取绝对值。其中， f l ，f 4 为各项指标的绝对误差与用户要求值的比，f 2 ，f 3 为实际值与用户要求值的误 差的绝对值。在实际应用中，各约束条件的重要性是不同的，因此，目标函数就取上 面四项误差的加权和。目标函数f 可以表示为： 4 f = ；w f ：1 w 表示第i 个约束条件的权值，w i 通常由专家经验或试验给出，o w i l ， 4 = 1 。由上式可知，目标函数f 的值越小，即误差越小，问题的解越优，即生成 j - 1 的试卷越接近用户的需求。 华中科技大学硕士学位论文 2 1 4 基于遗传算法的试卷自动生成 2 4 1 遗传算法的改进 不同的编码方案、选择算子、交叉算子、变异算子和终止条件相结合，构成了不 同的遗传算法。 ( 1 ) 染色体编码 遗传算法不直接处理问题空间的参数，而是处理以基因链码形式表示的个体，因 此使用遗传算法来求解问题的时候，就必须把问题解的参数形式转换成遗传空间的由 基因按一定结构组成的染色体即个体，这一转换就是编码。从生物学的角度来看，编 码就相当于选择遗传物质，它是研究遗传的基础。选择哪种编码方案一般会对算法的 性能、效率产生很大的影响。根据实际问题设计编码方法，提高效率是遗传算法研究 的热门话题。二进制编码是最常用的编码方法，二进制编码用1 表示某题被选中，0 表示某题没有被选中，这种编码非常简单，但是进行交换、变异等操作时，各题型的 题量难以精确控制，而且，当试题库题量很大时，编码很长。文献 2 9 采用的编码就 是二进制编码。通过对编码的大量分析，提出了一种分段实数编码机制，首先将染色 体分成若干段，每一段对应一种题型，组成试卷的各道试题题号直接映射为基因，编 码时将同一题型的试题放在同一段，同一段内题号各不相同，不同的段题号可以相同。 以题号编码的方法所表达的意义清楚、明确、不需解码，从而可以提高算法性能，提 高运算效率。而且交叉和变异操作都在各段内部进行，因此可以保证组卷过程中各题 型题量的正确匹配。 ( 2 ) 适应度函数设计 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群 中每个个体的适应度值来进行搜索。因此，适应度函数的选择至关重要，它直接影响 到遗传算法的收敛速度以及能否找到最优解。适应度函数是度量个体适应度的函数， 在遗传算法中以适应度的大小来区分群体中个体的优劣，一般情况下，适应度越大， 说明个体越好。一般而言，适应度函数是由目标函数变换而成的。上面提出的自动组 卷模型是最小化问题，采用如下方法可将目标函数f 转换成适应度函数f 。 华中科技大学硕士学位论文 nf 1 一， 1 1 i o 厂l 、 。 由上式可知，f 的取值范围为o 1 ，适应度函数f 的值越大，说明个体越好，个 体越接近问题的最优解。 ( 3 ) 初始化染色体群体 随机生成初始染色体群体，在初始染色体群体中，染色体的长度为n ( n 为试卷 中试题的数量) ，群体的大小为m ( 初始染色体群体中包含的试卷的数量) ，m 太小 时，难以求出最优解，太大时则增长收敛时间。群体的大小般根据需要，按经验或 试验给出，一般m = 3 0 1 6 0 。 ( 4 ) 遗传算子 遗传算法包括三个基本遗传算子：选择、交叉、变异，这三个遗传算子具有如下 几个特点。 1 ) 三种遗传操作都是随机化操作，这种随机化操作与传统的随机搜索方法是有 区别的，遗传操作进行的是高效的、有向的搜索，而不是一般搜索方法所进行的无向 操作。 2 ) 遗传操作的效果和三个遗传算子所取的操作概率，编码方法，群体大小，初 始染色体群体以及适应度函数的设定密切相关。 3 ) 三种遗传算子的操作方法或操作策略随具体求解问题的不同而不同。 下面分别介绍改进后的三种遗传算子。 1 ) 选择算予 选择【3 0 1 操作的目的是为了强调群体中适应性强的个体，并希望其后代也能具有较 强的适应性。但是，选择强度太大将会使局部最优个体在群体中占优势，从而使群体 的多样性减少，