（计算机软件与理论专业论文）基于遗传算法自动组卷系统的研究与应用.pdf

太原理工大学硕士研究生学位论文 基于遗传算法自动组卷系统的研究与应用 摘要 遗传算法是一种通过模拟生物界自然选择和遗传变异的机制来求解复 杂问题的随机搜索和优化的方法；组卷问题是一个在一定约束条件下的多 目标参数优化问题。自动组卷的效率和质量很大程度上取决于试题库的设 计以及抽题算法的设计。传统的组卷算法存在“组卷速度慢、成功率低、 组卷质量不高”等缺点。针对上述缺点，本文在充分分析和研究考试系统 组卷算法的基础上，提出了遗传算法自动组卷策略，并将遗传算法自动组 卷应用于在线考试系统中，最大程度地满足了用户的需求，具有科学性、 合理性和较好的实用性。 本文提出的基于遗传算法的自动组卷系统是在一定的约束条件下，通 过分析试卷的各项评价指标、指标的作用及其相互关系，将其量化为描述 目标试卷特征的一组指标分数分布列，即建立了采用各个评价指标的分布 构建的成卷模式；在成卷模式的基础上建立最接近用户要求的多目标约束 优化模型，并对此模型进行求解，利用权重系数法将多目标优化转化为单 目标优化，建立了组卷数学模型。进而利用遗传算法对其进行求解，解集 即为目标试卷中具有相同试题指标取值的试题数量。 本文对传统遗传算法进行了适当的改进，利用c 拌编程将改进的遗传 算法应用于自动组卷系统中，使组卷的成功率和收敛速度都得到明显提高， 不仅适合于较大型题库系统，而且对于复杂的组卷条件也能满足，一次组 1 太原理工大学硕士研究生学位论文 卷还可以得到多份符合要求的试卷，并通过在线考试系统的实现，验证了 所提理论的正确性。， 在线考试系统是随着计算机网络技术在教育领域的广泛应用而提出 的，利用网络进行考试可以极大地提高考试的效率和质量。本文将遗传算 法自动组卷应用其中，并从用户的实际需求出发，对在线考试系统应具备 的主要功能进行了详细论述，分析了基于w e b 的在线考试系统模型，运用 面向对象的方法进行在线考试系统的设计和实现，具体运用u m l 模型图对 在线考试系统进行了分析和设计。构建了一个基于b s 结构的，以a s p n e t 技术和s q ls e r v e r2 0 0 0 后台数据库为基础的，具备“用户管理、试题库管 理、试卷管理、自动组卷、在线考试、试卷评阅、成绩统计”等多功能的 在线考试系统。具有重要的理论意义和现实意义。 关键词：自动组卷，遗传算法，数学模型，多目标优化，在线考试 太原理工大学硕士研究生学位论文 t h er e s e a r c ha n da p p l i c a t i o no f 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 s y s t e mb a s e do ng e n e t i ca l g o r i t h m a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i sr a n d o ms e a r c ha n do p t i m i z i n gm e t h o dw h a ti s u s e dt os o l v ec o m p l e xp r o b l e m sb ys i m u l a t e st h en a t u r a ls e l e c t i o ni nb i o s y s t e m a n dt h em e c h a n i s mo fa b e r r a n c ei nh e r e d i t y a n dt h ep r o b l e mo fc o m p o s i n g e x a m i n a t i o np a p e r si sm u l t i o b j e c t i v ep a r a m e t e ro p t i m i z i n gp r o b l e mw i t hs o m e c o n s t r a i n tc o n d i t i o n s 髓eq n a l i 够a n de f f i c i e n c yo fa u t o - g e n e r a t i n ge x a m i n a t i o n p a p e r s a r ea l ld e t e r m i n e db yt h et e s tq u e s t i o n s - d a t a b a s ed e s i g n sa n dg e t p r o b l e m s t e r m sa l g o r i t h m 1 1 l ec o n v e n t i o n a lc o m p o s i n ge x a m i n a t i o np a p e r s a l g o r i t h m sh a v es o m ed r a w b a c k ss u c ha ss l o ws p e e d , s m a l ls u c c e s sc h a n c ea n d p o o rq u a l i t y t i l i sp a p e r , w h i c ha i m s a tt h ed r a w b a c k so fa u t o - g e n e r a t i n g e x a m i n a t i o n p a p e r s i ne x a m i n a t i o n s y s t e m , c o m p l e t e l ya n a l y z e s a 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 s a n dp u t s f o r w a r dt h es t r a t e g yo f 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 sb a s e do ng a ， a p p l i e sg a i n t ot h ea 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 no n - l i n ee x a m i n m i o n s y s t e m n em e t h o dm e e t st h eu s e r s e x t r e m en e e db e c a u s eo fs c i e n t i f i c i t y , r a t i o n a l i t ya n dp r a c t i c a b i l i t y i i i 太原理工大学硕士研究生学位论文 t h i sp a p e rp u t sf o r w a r dt h ea 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 n g au n d e rs o m ec o n s t r a i n t c o n d i t i o n s ，a n a l y s e s e v a l u a t i n gi n d i c a t o r s ，t h e i r f u n c t i o n sa n dt h e i rr e l a t i o n s h i p ；e v a l u a t i n gi n d i c a t o r sa r eq u a n t i f i e dt oag r o u p o fd i s c r e t ei n d e x e s sd i s t r i b u t i v ec o l u m n s ，w h i c ha r eu s e dt od e s c r i b et h e c h a r a c t e r so fo b j e c t i v ee x a m i n a t i o np a p e r s ，n a m e l yae x a m i n a t i o n p a p e r g e n e r a t i o nm o d e li ss 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 b a s e do np r e s e n te x a m i n a t i o n p a p e rm o d e l ，am u l t i o b j e c t i v e o p t i m i z a t i o n m o d e l ，w h i c hs e e m sm u c hs a t i s f y i n gu s e r s d e m a n d s ，i se s t a b l i s h e d i nt h e p r o c e s so fs o l v i n gt h ep r o b l e m ，w e i g h tc o e f f i c i e n tm e t h o di si n t r o d u c e dt ot u r 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 np r o b l e mt os i n g l e o b j e c t i v eo p t i m i z a t i o n ，a m a t h e m a t i cm o d e lt og e n e r a t ee x a m i n a t i o np a p e r si se s t a b l i s h e d t h e nw ef i n d t h es o l u t i o nb yt h eu s eo fg e n e t i ca l g o r i t h m t h es e to fs o l u t i o ni sj u s tt h e q u a n t i t yo f t e s ti t e m st h a th a st h ei n d e xv a l u ei no b j e c t i v ee x a m i n a t i o np a p e r s i nt h i s t h e s i s ，t h et r a d k i o n a lg e n e t i ca l g o r i t h mh a sb e e ni m p r o v e d a p p r o p r i a t l y , a n dt h ea u t h o rm a k e sa ni m p r o v e dg e n e t i ca l g o r i t h mp r o g r a mo f 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 su s i n gc 散t h es u c c e s se f f i c i e n c ya n d c o n s t r i n g e n c ys p e e dh a v eb e e nb o o s t e dd i s t i n c t l y t h i sn o to n l ya d a p t st ob i g d a t a b a s es y s t e m ，b u ta l s os a t i s f i e sc o m p l e xr e s t r i c t e dc o n d i t i o n so fg e n e r a t i n g e x a m i n a t i o np a p e r s m a n ye x a m i n a t i o np a p e r sw i l lb e e ng a i n e dw h i c ha c c o r d w i t hg e n e r a t i n ge x a m i n a t i o np a p e r sr e q u e s tb yo n e o f fg e n e r a t i n g t h r o u g h i m p l e m e n t i n gt h eo n - l i n ee x a m i n a t i o ns y s t e m ，t h ec o r r e c t n e s so ft h et h e o r yh a s b e e n c a l i d a t e d i v 太原理工大学硕士研究生学位论文 w i t ht h ee x t e n s i v ea p p l i c a t i o no fn e t w o r kt e c h n i q u ei nt h ee d u c a t i n gr e a l m , t h eo n - l i n ee x a m i n a t i o ns y s t e mh a sb e e np u tf o r w a r d t ot e s tw i t ht h en e t w o r k c a r li m p r o v et h ee f f i c i e n c ya n dq u a l i t yo ft h ee x a m i n a t i o n t h i sp a p e ra p p l i e s t h e a u t o g e n e r a t i n g e x a m i n a t i o np a p e r s s y s t e mb a s e d o ng at oo n - l i n e , e x a m i n a t i o ns y s t e m a n de m b a r k sf r o mt h eu s e r s a c t u a ld e m a n d s ，g i v e sa 。 d e t a i l e de l a b o r a t i o no l lt h em a i nf u n c t i o no f t h eo n - l i n ee x a m i n a t i o ns y s t e ma n d a n a l y s e so n - l i n ee x a m i n a t i o ns y s t e mm o d e lb a s e do nt h ew e b t h i sp a p e r a n a l y s e sh o wt od e s i g na n di m p l e m e n tt h ee x a m i n a t i o ns y s t e mb yu s i n gt h e o b j e c t - o r i e n t e dm e t h o d ，s p e c i a l l yt h eu m l m o d e ld i a g r a ma n a l y z i n gd e s i g 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 m t h eo n - l i n ee x a m i n a t i o ns y s t e mb a s e so nb s s t r u c t u r e ，t h ea s p n e tt e c h n o l o g ya n ds q l - s e r v e r2 0 0 0d a t a b a s e ，a n dt h e a u t h o rd e v e l o p e sap r a c t i c a lo n - l i n ee x a m i n a t i o ns y s t e m a st om e e tt h e r e q u i r e m e n t s ，s u c ha st h em a n a g e m e n to f u s e r si n f o r m a t i o n , t h em a n a g e m e n t 。， o ft e s t q u e s t i o n sd a t a b a s e ，t h em a n a g e m e n to fe x a m i n a t i o np a p e r s ，t 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 s ，o n - l i n ee x a m i n a t i o n , m a r k i n ge x a m i n a t i o n p a p e r s a n a l y z i n gt e s ts c o r ee f c i tl m ai m p o r t a n tt h e o r ya n dr e a l i t ym e a n i n g s 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 , m a t h e m a t i c sm o d e l ，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 , o n - l i n ee x a m i n a t i o n v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下。 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体。均已在文中以明确方式标明。本声明的 法律责任由本人承担。 ， 论文作者签名：查耋丛日期：塑z ! ：! ! 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的。 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 签名： 查耋一丛 日期：竺! 兰! ! 导师签名：日期： 盟：圭：1 2 太原理工大学硕士研究生学位论文 1 1 研究的目的与意义 第一章绪论 在教育领域中，考试是整个教学过程中的重要环节，它是对学生所学知识和能力的 一种评价，也是衡量教师教学效果优劣的一种教育测量手段。传统考试在命题内容、评 分标准、阅卷等方面会受各种人为因素的干扰，考试可信度和效度较低。利用网络在线 组织考试可以极大地提高考试的效率；同时，它可以从对试题库进行动态管理到自动组 卷，再到考试过程监控、试卷评阅、成绩统计等全程实现智能化，更加客观、真实、全 面地反映教学的实际效果，有利于促进教学质量的提高。因此，开发在线考试系统具有 重要的现实意义。 实际上，考试是一项“测量工程”，从统计学的角度来看，考试是一种抽样测量， 通常告诉学生的应考内容是考查的总体，而试题实际考查到的内容则是从总体中抽取的 样本。因此，为了提高考试质量，必须在实施考试前进行详细的设计即把数理统计的 方法引入到考试工作中来，对试卷的质量进行定量分析。 对于组卷系统来讲，生成符合要求的试卷是一项最根本的功能要求，其抽题组卷算 法的设计对于整个组卷系统的性能和质量来讲是关键。自动组卷不但能最有效地把客户 的需求与计算机技术结合在一起，生成符合要求的试卷；且比较客观、规范，使用起来 也最为方便然而，自动组卷试题库的设计并不容易现有的试题库系统大体分三种； 一种是将试题库看做试题集，命题时由具有丰富经验的教师逐题抽取。二是将试题库看 做试卷集，将已经出好的试卷存储起来，在组卷时任意抽取一份。三是利用某种组卷策 略，自动组成合理的试卷。前两种虽能保证试卷质量，但第一种与人工命题无异，第二 种只能出有限份试卷，第三种则是随机出题，又有组卷策略可遵循，但所使用的组卷技 术和组卷策略有优有劣。自动组卷的效率和质量完全取决于组卷算法的设计。因此，对 组卷算法的研究是必要且具有重要实际意义的。 针对上述问题，本文提出将遗传算法的思想应用到在线考试系统的自动组卷中，通 过分析试题的指标属性，建立数学模型，并在一定的约束条件下，自动生成试卷，既提 高了组卷效率，又克服了传统组卷“速度慢、成功率低、组卷质量不高”等缺点，适用 l 太原理工大学硕士研究生学位论文 性很强，具有重要的理论意义和现实意义。 1 2 国内外研究动态 1 ，2 1 计算机网络教育研究 。 随着现代科学技术的发展，计算机已在教育领域形成了一个新的、综合的、教育学 知识与计算机科学知识相结合的研究领域一计算机辅助教育( c a d 。计算机辅助教育 的研究十分广泛，包括多方面、多层次的研究任务。考试是较重要的一方面，是教学过 程中的一个重要环节，开发试题库是实现考试的科学化、标准化和现代化的必要手段。 国外的计算机辅助教育发展较早，起始于1 9 6 5 年，但直到七十年代都没有正式的 实用系统。其发展经历了三个阶段：6 0 年代以程序教学为主要形式，将课程或实验编 成循序渐进的单个程序，在教学过程中起辅助讲解的作用；7 0 年代，从教育方法论的 角度，研究多媒体c a i ，即将文字、图像、声音，图形集成为一体，在计算机上创造良 好的学习环境，从而达到最优的学习效果；8 0 年代又开始智能体c a i 的研究，如美国 l v i i t 的a i h e n a 系统是一个多媒体、分布式网络的综合教学系统、s t a n f o r d 大学的v 系 统、加州b e r k e l e y 分校的s p r i t e 系统都已执行多年，并在不断完善和扩充之中。 而网络的出现与发展，使以因特n ( r n t e r n e t ) 为主要标志的网络技术成为了现代 技术文化的重要组成部分，联系上亿人的因特网将人类带入了一个全新的数字化时代， 拓展了人类的第二生存空间网络社会。在网络社会的大背景下，网络技术与教育更 是结下不解之缘：美国在1 9 9 8 年公布了i n t e r n e t 计划，宣布要使每一所学校、每一 间教室、每一户家庭和每一个美国公民都能享受i n t e r n e t 带来的全新的学习环境； 英国政府建议成立网上工业大学，并推出“全国学习网”，目标是到2 0 0 2 年使英国3 2 万所中小学全部进入因特网；我国教育部1 9 9 9 年推出面向2 1 世纪教育振兴行动计划 将校园网的构建提到日程上来；2 0 0 0 年4 月中国基础教育网正式开通；同年l o 月国家 教育部宣布全面实施“校校通”工程，目标是在未来的5 l o 年内使全国9 0 以上的中 小学能与网络联通，到2 0 0 5 年使所有大学和一千所中小学上网。 ， 1 2 2 在线考试系统研究 目前，考试系统的种类较多，按考试系统的组卷方式分，主要有：一是将试题库当 试题集，出卷时由具有丰富经验的教师逐题抽取：二是将试题库当试卷集，将已出好的 2 太原理工大学硕士研究生学位论文 试卷存储起来，出卷时抽取其中一份；三是具有自动成卷功能的试题库，利用命题人提 供的成卷规则编制成卷软件，自动生成合理的试卷。前两种为管理型，第三种为智能型： 从结构上划分，主要有：一类是采用客户机，服务器( c s ) 结构的考试系统，另一类是采 用浏览器服务器( b s ) 模式的分布式网络考试系统。它们均能实现计算机在线考试，考 试时考生登录系统参加考试，考试后系统自动计算考试成绩。 在线考试系统作为计算机网络教育的重要组成部分和发展分支，已经在国外一些发 达国家得到蓬勃发展。特别是i n t e r a c t 业务的普及，构筑高性能、低成本的计算机网络 化在线考试，从技术条件和经济条件上已经成熟。例如：在美国，包括m i c r o s o f t 公司 的m c s e ( 微软系统工程师认证考试) 、g m a t ( i 商管理硕士入学考试) 、托福考试、g r e 考试等，均采用了网上在线考试的形式，并已在全球范围内应用。 在国内，绝大多数的考试还停留在传统考试模式下。在此模式下，组织一次考试至 少要经过5 个步骤，即人工出卷、考生考试、人工阅卷、试卷分析和成绩评估。随着考 试类型的增加及考试要求的不断提高，教师的工作量将越来越大。到1 9 9 8 年后，随着 国内网络教育的兴起，各高校纷纷开发了自己的网络教学平台，作为网络课程重要组成 部分的网络考试系统也相继问世，如北京师范大学的网络教学平台、上海交大的网络考 试平台等。 近几年来，借鉴发达国家的成功经验，结合我国的实际情况，伴随着网络应用的不 断扩大，人们迫切要求利用网络技术进行在线考试，进而提高考试的质量，突出公正性 和客观性，减轻组织及保障工作的负担，提高工作效率，有力地推动了我国网络化在线 考试的发展水平，并积累了大量有价值的经验。 1 2 3 在线考试组卷系统研究 在线考试系统作为网络教育系统的一个子系统，是网络教育实现的关键，是保证网 络教学质量的重要手段，而组卷系统又是在线考试系统的一个重要组成部分。随着计算 机及数据库技术的发展，利用计算机存储大量的试题信息并结合数据库技术实现试题的 自动组卷功能已成为项非常实际可行并且应用性极其广泛的课题。国外和国内的许多 科研单位、学校机构等都在对组卷系统进行研究。目前，自动组卷系统根据其所使用的 组卷策略大致可以分为四类： ( 1 ) 基于随机抽取的自动组卷； ( 2 ) 基于深度与广度搜索算法的自动组卷； 3 奎垦墨三查堂堡主堑塞皇堂垡丝塞 ( 3 ) 基于回溯试探法的自动组卷； ( 4 ) 基于项目反应理论的自适应测试。 基于随机抽取的自动组卷策略【i 2 1 是利用随机函数在试题库中抽取符合要求的试题 组成试卷。这种方法实现起来比较简单，但抽取出来的试题难以符合指定要求，如整体 难度系数超出预定难度值等，从而导致组卷的效率较低；基于深度与广度搜索的自动组 卷策略【2 j j 是在基于随机函数抽取试题的基础上，在抽取过程中增加了验证过程，通过 验证所选择的试题是否满足系统给定的目标条件，来决定对该试题是否进行抽取，当发 现目前没有任何试题满足要求而组卷过程又没有完成时，则采用回溯方法来进行重新组 卷。显然，该方法当试题库的题量很大时将导致搜索空间过大，导致系统性能不理想； 基于回溯试探法【2 】的自动组卷将随机选取法产生的每状态类型纪录下来，当搜索失败 时释放上次纪录的状态类型，然后再依据一定的规律( 正是这种规律破坏了选取试题的 随机性) 变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退 回出发点为止，这种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统 而言，组卷成功率较好，但是在实际到一个应用时发现这种算法对内存的占用量很大， 程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长。因此，它也不是一种 很好的用来自动组卷的算法；基于项目反应理论的自适应测试策略o l 是通过建立一个 反映考生作答反应与题目质量及能力水平间关系的非线性模型，对考生的能力水平进行 估算，从而得出对该考生能力的测量，这种方法不依赖于特定的施测题目样本，但对于 模型的建立及其有效性方面缺乏验证，成功的实际应用尚不多见 遗传算法是一种随机寻优算法，由于其具有良好的全局寻优和收敛速度快的特点， 将遗传算法应用于自动组卷中，组卷质量和效率明显提高。文献【4 卅利用遗传算法对试 题组卷进行了研究，并通过采用染色体分段操作限制遗传算子的操作范围，以隐藏题型 题量的约束条件，简化了求解问题的复杂度，所产生的试卷具有较高的质量和水平。但 这种方法的缺陷是在变异过程中产生的无效解会影响染色体群的整体性能，从而影响了 算法的效率。因此，必须结合以上几种方法寻求一种新的改进的遗传算法，更好地满足 自动组卷的要求。 1 2 4 遗传算法应用研究 早在2 0 世纪6 0 年代，美国m i c h i g a n 大学的j o h nh o l l a n d 教授就开始研究自然和 人工系统的自适应行为，在这些研究中，他意识到用群体方法搜索以及选择、交换等操 4 太原理工大学硕士研究生学位论文 作策略的重要性。而b a g | e y 采用双倍体编码，发展了与目前类似的复制、交换、突变、 显性、倒位等基因操作，他还察觉到防止早熟收敛的机理，并发展了自组织遗传算法的 概念。 1 9 7 0 年c a v i c o t f i o 研究了基于遗传算法的子程序选择和模式识别问题，在模式识别 问题上，采用整数编码，检索的空间很大，提出了以预选择策略保证群体多样性，对遗 传算法参数进行中心控制的方法。同年，w e i n b e r g 提出了运用多层遗传算法来进行遗传 算法的参数自优化。1 9 6 8 至1 9 7 1 年，h o l l a n d 提出了重要的模式理论，并采用二进 制编码研究函数的优化问题。 ， 由于遗传算法能有效地求解属于n - p c 类型的组合优化问题及非线性多模型、多目 标的函数优化问题，从而得到了多学科的广泛重视。其主要应用领域有： ( 1 ) 组合优化：遗传算法作为随机化方法已在组合优化中得到广泛的应用，并在解 决某些典型的优化问题时显示出良好的效果。特别是对有约束、多目标的优化，已经发 展成进化计算中的一个分支 ( 2 ) 机器学习：遗传算法从开始就与机器学习有着密切的联系，h o l l a n d 首先提出 的遗传机器学习系统c s 1 ( m i c h i g a n 方法) 和d ej o n g 提出的l s - i 系统( p i t t s b u r g h ) t 法) ，为遗传算法和机器学习的结合翻开了新的一页。 ( 3 ) 人工生命：人工生命的重要研究内容之一是遗传、进化现象，基于遗传算法的 进化模型是研究人工生命的重要理论基础。同时，也为人工生命的研究和实现提供了有 效的工具。 。 此外，遗传算法在并行分布处理、复杂系统分析和建模、自适应控制，自动程序设 计、模式识别、图像处理、演化硬件等领域都有一定的应用。 ， 鉴于自动组卷在教学系统中的重要作用，d b f o g e o l 在神经网络的进化学习方法的 研究中首次提出把遗传算法用于试题组卷；g o r d b e r gm w 应用遗传算法的寻优特性为 组卷问题建立了寻优模型国内的遗传算法发展得较晚，其中在教学领域方面最主要的 应用是建立各种神经网络问题。由于遗传算法同时具有内在的并行性，一全局寻优和收敛 速度快的特点，这些特点都使得遗传算法适宜于处理试题库的自动组卷问题。 1 3 研究内容及方法 组卷问题实际上是一个典型的多重约束目标优化问题，类似的还有“排课问题”， 5 太原理工大学硕士研究生学位论文 “j o b s h o p ”问题，这其中涉及到计算理论、算法分析、优化控制等各个领域的知识。 文献1 1 提出了选题组卷策略，提出了“优先”、“随机”、“补偿”、“回溯”等四种方法， 较好地解决了约束求解的策略性问题；文献1 2 给出了回溯法的算法实现；文献1 3 讨论 了组卷问题中的题库结构。但是，由于问题的解空间往往出现组合爆炸，加上约束条件 的多样性，传统的搜索算法效率很低，并且容易陷入局部最优。 本论文用遗传算法进行处理，提出了有别于“传统遗传算法”的求解新思想，对初 始种群的生成、染色体编码及其遗传操作、控制参数等进行了研究并做了适当改进，最 终，将遗传算法成功地运用到了“自动组卷”系统中，完成了s q l - s e t v e r 2 0 0 0 数据库 c 撑n e t 环境下的“在线考试系统”。 本文研究的主要内容包括： ( 1 ) 研究并建立了自动组卷数学模型 组卷过程实质上是一个多重属性约束条件下复杂的多目标寻优过程。而自动组卷算 法实现的关键在于构建合理的自动组卷的数学模型。本文通过将用户对试题题型、试题 所属章节、试题难度、试题教学要求度等一系列属性的要求进行量化，建立了试卷模式， 得到了各个属性的分数分布列，进而建立了自动组卷数学模型。 ( 2 ) 对自动组卷数学模型进行求解 自动组卷数学模型是一个多目标优化的数学模型，常规的求解多重约束条件下的高 维方程组，在理论和实践上都有一定难度。本文分析了几种常用的求解多目标优化数学 模型的算法。由于遗传算法有较好的全局寻优能力，相对传统的方法而言，可以快速而 准确的得到较优解。通过利用权重系数法将多目标优化转化成单目标优化的模型，然后 运用改进遗传算法对其进行求解 ( 3 ) 运用改进遗传算法实现了自动组卷 根据组卷的实际问题对传统的遗传算法进行了在编码方式、遗传操作、控制参数等 方面的改进。然后，利用例n e t 编程实现了基于改进遗传算法的自动组卷 ( 4 ) 开发了基于遗传算法自动组卷的在线考试系统 开发的基于遗传算法自动组卷的在线考试系统包括：试题库管理子系统、试卷管理 子系统、自动组卷子系统、在线考试子系统、阅卷评分子系统、成绩统计分析予系统及 用户管理子系统等七个子系统。 6 太原理工大学硕士研究生学位论文 第二章自动组卷指标体系与数学模型的建立 2 。1 组卷系统概述 随着计算机及其数据库技术的发展，利用计算机存储大量的试题信息并结合数据库 技术实现试题的自动组卷已成为一项实际可行且应用广泛的课题。一个称得上完备的组 卷系统应该满足多种用严对试卷的不同需求，组卷合格率应为百分之百；但由于试题库 中试题的数量庞大，在计算机自动组卷过程中需要考虑的因素很多。因此，自动组卷系 统只能在不同程度上满足或接近用户需求。 组卷的初始阶段是用户输入对要生成的试卷的具体要求，然后计算机根据一定的算 法去抽取试题，把这些抽取出来的试题和评判条件相比较，如果评判不通过则重新选题， 通过则编排试题、打印试卷供考生考试。在组卷前，必须对试卷的特征进行具体的、系 统的分析，才能设计出合理的组卷系统。对组卷问题主要有以下几方面的特征： ( 1 ) 数据的不精确性、模糊性。组卷系统是要从试题库中找出一部分满足用户要求 的试题组成一份试卷，所以，系统中的数据首先就是试题内容以及相应的试题答案等。 如果试题是无规则的排列，则无法进行搜索或者搜索的难度很大所以，必须有一些描 述这些试题的指标数据。这些指标数据有一些是明确的，比如：分数、题型等；但有些 数据是比较模糊的，比如：难度等级；还有些数据是需要测试才能得到的，比如：解答 该题所需时间等。因此，系统中的数据不是单一的精确数据，有的具有模糊性。 ( 2 ) 解的多样性。组卷是一个状态空间问题的求解过程，初始节点为用户输入的试 卷要求，叶节点为一些满足要求的试题由于题库中的试题很多，能满足用户要求的试 题也很多，即问题的解空间很大，因而，就能在相同的条件下组出不同的、内容丰富的 试卷。 ( 3 ) 知识的特征不同。对于组卷系统，知识大都来源于成卷专家的经验不同的专 家有不同的成卷经验，一个专家所认同的经验，可能另一个专家不能接受；有些专家经 验也许对某一部分内容是有效的，但对于其它部分却无效；随着时间的推移、环境条件 的变化，原来有效的经验还会变得无效。而软件开发的过程本身就是在不断的总结专家 经验。所以，在组卷系统维护中就必须不断的更新知识、增减知识、完善知识，使得系 7 太原理工大学硕士研究生学位论文 统能尽可能地组出高质量的试卷。 2 2 自动组卷指标体系的建立 试题本身均含有一些固有的特性参数，这些固有的特性参数都需要用相应的指标来 描述，通过建立试题的指标体系，来支持组卷模块功能。 指标体系是指试题参数，是对试题的内在属性、外在特征及其在考试系统中的功能 进行定性的或定量的描述；它是建立试题库管理系统，实现计算机自动组卷的关键。试 题的指标体系越丰富，组卷的质量越高。本论文定义的试题指标体系为：c ； 题型，所 属章节，知识点，难度系数，教学要求度，分值，使用率，。 ( 1 ) 题型：试题的类型有多种划分形式，本论文是指从试题的形式上进行区分，具 体的试题类型分为“单选题、判断题、填空题、应用题、程序题”五种。 ( 2 ) 所属章节：试题库中的试题均与课程的章节相对应。 ( 3 ) 知识点：又称考核点，它涉及试题的具体考核内容。 ( 4 ) 难度系数：在组卷的过程中，针对不同的考试目的、不同阶段的考试，试题的 命题难度也不同。在定义试题的难度系数时，采用以下方法： 设试卷中第_ ，道试题的难度系裂1 q 为p ，； 对于主观性试题，相应的难度系数为： l 占 一 p j ：1 - = 面- l l x # ：1 一一x j 式( 2 1 ) i| 对于客观性试题，相应的难度系数为： p ，小斋 式( 2 2 ) 其中，为第i 个学生在第j 道试题上的得分，工，为第j 道试题的平均分，一为第 j 道试题的满分值，n j 为答对第，道试题的人数，n 为考生总人数 p 的取值范围在 0 ，o 4 】为难； o 4 ，o 7 】为中等；【o 7 ，1 】为易 ( 5 ) 教学要求度：指试题对考生知识和能力的要求程度，分为“识记、领会、简单 应用、综合应用”四个层次。 8 太原理工大学硕士研究生学位论文 ( 6 ) 分值：分值是每道试题的满分值。对各种不同类型的题目可以根据考试时间及 试题难度等设置不同的分值。， ( 7 ) 使用率：题目的己出题次数和上次使用时间两个参数可以用来控制题目的使用 率。为了试卷的保密性、公平性和安全性，在抽取试题进行组卷时，需要控制题目的使 用率。 2 3 组卷系统成卷模式 对于任何组卷系统来说，其功能的实现都必须经过“获取用户需求、根据用户需求 建立相应的试卷模式、根据试卷模式建立组卷算法的数学模型和对数学模型进行求解从 而实现抽题组卷”这四个步骤。组卷数学模型建立的好坏直接关系到求解的难易程度以 及整个组卷算法实现的快慢，而成卷模式是对用户要求的一种定量的反映，是建立组卷 数学模型的基础。 在计算机自动组卷时，可以通过改变试卷的难度分配来达到控制试卷的平均难度的 目的，文献1 5 给出了一种用正态分布方式计算难度分布曲线的模型。利用该模型进行 测试，将试题的难度分为五档( 易、较易、中等、较难、难) ，对应的难度系数分别为1 ， 2 ，3 ，4 ，5 ；试卷满分值设为1 0 0 分，试卷期望的平均得分为7 5 分时，利用此正态分 布模型计算得到的难度分数曲线为 3 0 ，6 3 ，7 ，0 ，0 ) ，试题过分地集中在第一、二档 难度，而第四、五档难度的试题没有，组卷很不合理。 在此，采用离散型随机变量的二项分布函数口似p ) 建立一个由试卷的期望平均分计 算难度分布曲线的模型。离散型随机变量的二项分布函数占( 一，力： ，( 砷= 矿g “ 式( 2 - 3 ) 其中：k = 0 ，1 2 j ，刀为整数，p o , q o , p + q = 1 令g = 期望的平均值，脚眩， p = l q ，n = v + l ( 其中1 ，为难度级别数) 。代入式( 2 - 3 ) ，求得p ( 七l 七= o ，1 2 j 一般地，q o 6 ，0 l 尸o 一1 ) 通常很小，可以将它们加到p o 一2 ) 上，将计算后得到的 p ( _ ) 作为难度级别为k + 1 的分数比例，再将它们乘以满分值，便得到难度分布曲线 例如：设试题的难度分为五档( 易、较易、中等、较难、难) ，对应的难度系数分别 9 太原理工大学硕士研究生学位论文 为l ，2 ，3 ，4 ，5 ；试卷满分值设为1 0 0 分，试卷期望的平均得分为7 5 分，则g = 0 7 5 ，p = 0 2 5 ， 由式( 2 - 3 ) 得： p ( 0 ) = a p o q 6 = l x o 2 5 0 x o 7 5 6 = o 1 7 8 0 p ( 1 ) = c ；v q = 6 x o 2 5 1x o 7 5 5 = o 3 5 6 0 p ( 2 ) = c ：p 2 q 4 = 1 5 x o 2 5 2x o 7 5 4 = o 2 9 6 6 p ( 3 ) = a p 3 9 3 = 2 0 x o 2 5 3xo 7 5 3 = o 1 3 1 8 即) = p “q = l s x o 2 5 4 x o 7 5 2 = o 0 3 3 0 p ( 5 ) = c ：p 5 q 1 = 6 x o 2 5 5 x o 7 5 1 = o 0 0 4 4 p ( 6 ) = p 6 9 0 = l x o 2 5 6 x o 7 5 0 = 0 0 0 0 2 由于p ( 5 l 尸( 6 ) 相对很小。可以根据情况略去或加到p ( 4 ) 中，( o ) ，p 尸( 2 l p ( 3 ) ，p ( 4 ) 即是难度级别分别为1 ，2 ，3 ，4 ，5 的试题在试卷中所占的分数比例将它们乘以满分 值1 0 0 ，即可得到难度分数曲线 1 8 ，3 6 ，3 0 ，1 3 ，3 ) 。 用此模型进行了很多次测试，结果表明，它是有效的。 根据试卷的平均难度计算出各个不同难度级别的试题的分数后，再综合考虑不同教 学要求度的试题分数和不同章节范围的试题分数，就可以建立当前试卷模式。当前试卷 模式的具体描述如下： ( 1 ) 满分值m f z ：答题完全正确所获得的试卷总分，通常设为1 0 0 分。 ( 2 ) 试卷的答题时间：可用于控制试卷的试题数量和试题的难度，通常设为1 2 0 分 钟。