（计算数学专业论文）应用多方向进化遗传算法的自动组卷算法模型设计.pdf

中文摘要 摘要：随着计算机技术的不断发展，利用计算机辅助教学得到越来越广泛的 应用。而试题库系统就是计算机辅助教学的其中一个应用。无论在国内或者在国 外，试题库系统理论的研究和实践都在不断发展。在国内，目前也有许多试题库 系统在应用，对改进教学方法和提高教学质量起到了很大的作用。高等数学等课 程是高效理工科及管理类专业学生的重要基础课，学习这些课程的学生人数众多， 课程学时量大，再加上高校目前对高等数学课程采用分级教学模式，对该课程的 考核方式、命题质量、考试次数等均提出了更多的要求。因此如何科学、准确、 客观的组卷成为当前的热门课题。而遗传算法在函数优化、组合优化、人工智能、 人工生命、运筹学、自动程序设计、机电和控制工程等各种领域中己经取得了大 量的应用成果，表现了求解复杂问题尤其是n p 难解问题和设计自适应性系统的极 大潜力。文中介绍了国内外题库系统的发展现状，比较了使用题库系统自动组卷 与传统的手工组卷的差别，同时也举出了现阶段己成形的题库系统存在的一些问 题。进而，本文应用遗传算法的算法框架结合正态分布提出了一套新的智能组卷 算法的模型。该模型对遗传算法的初始种群及选择进化策略结合组卷应用做了修 改及改进。文中详细地介绍了这智能组卷系统的选题算法模弄设计。 关键词：遗传算法；正态分布；初始种群；多方向进化；试题库；自动组卷 分类号：t p 3 0 1 6 a b s t r a c t a b s t r a c i ： w i t ht h ec o n t i n u o u sd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , t h ea p p l i c a t i o no fc a t ( c o m p u t e ra s s i s tt e a c h i n g ) h a sb e c o m em o r ea n dm o r ew i d e s p r e a d t h et e s tq u e s t i o n s b a s es y s t e mi so n eo ft h e m w h e t h e ra th o m eo ra b r o a d ，t h et h e o r i e so ft h et e s t q u e s t i o n sb a s es y s t e mi sd e v e l o p i n gc o n t i n u o u s l y , w h i c hh a v eg r e a te f f e c t o nt h e i m p r o v e m e n to ft e a c h i n gm e t h o d sa n dq u a l i t y i nr e c e n ty e a r s ，t h ee n l a r g i n gr e c r u i t m e n t o fc o l l e g e sa n dt m i v e r s i t i e s ，t h ei n c r e a s eo fs t u d e n t s ，t h eo p e nw i n d o wt ot h ep u b l i co f l l i 曲m a t h e m a t i c sc l a s s e s a n dt h eu s eo fg r a d et e a c h i n gm o d e lb yc o l l e g e sa n d u n i v e r s i t i e s - a l lm a k em u c hm o r er e q u e s tt ot h ee x a m i n em e t h o d sa n dt h es e l e c t e d t o p i c sq u a l i t ya n dt h ee x a m i n et i m e s g e n e t i ca l g o r i t h mh a sm a d ean u m b e ro f a c h i e v e m e n t si na l lf i e l d s ，w h i c ho f f e r su n t a p p e dp o t e n t i a lf o rs o l v i n gt h o s ec o m p l e x p r o b l e m ss u c ha sn pa n d f i t n e s ss y s t e m t h i st h e s i si n t r o d u c e st h ed e v e l o p m e n ts t a t u s o ft h et e s tq u e s t i o n sb a s es y s t e m ，c o m p a r e st h eo r g a n i z a t i o no ft e s tp a p e ra u t o m a t i c a l l y b yu s eo ft h et e s tq u e s t i o n sb a s es y s t e mw i t ht h et r a d i t i o n a lo n eb yh a n da n da l s ol i s t s t h ee x i s t e n tq u e s t i o n sa b o u tt h ef o r m i n gb yt e s tq u e s t i o n sb a s es y s t e m f u r t h e r m o r e ， t h i st h e s i sp u tf o r w a r dan e wi n t e l l e c t u a la l g o r i t h mm o d e lw h i c hc o m b i n e st h eg e n e t i c a l g o r i t h mf r a m e w i t ht h en o r m a ld i s t r i b u t i o n t h i sm o d e lh a sm a d es o m ea l t e r a t i o n sa n d o p t i m i z i n gt o t h ep r i m a r yp o p u l a t i o na n ds e l e c ta n de v o l u t i o ns t r a t e g yo fg e n e t i c a l g o r i t h mb a s e do nt h et e s tp a p e rs y s t e m t h i sp a p e rm a k e sad e t a i li n t r o d u c t i o nt ot h e t e s tp a p e rg e n e r a t i n ga l g o r i t h mo f t h ei n t e l l e c t u a ls y s t e mo f i t e md a t a b a s e k e y w o r d s ：g e n e t i ca l g o r i t h m ：n o r m a ld i s t r i b u t i o n ；p r i m a r yp o p u l a t i o n ； m u l t i d i r e c t i o n a le v o l u t i o n ；a u t o g e n e r a t i n gt e s tp a p e r ； c l a s s n 0 ：t p 3 0 1 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：硒 签字f j 期：枷碧年善月争日 导师躲考l 签字开期：夕舻乡月够日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：j 氍翱 签字日期：p 站年石月4 日 致谢 两年的研究生学习和生活中，我要特别感谢导师黄晓鸣副教授。他无论是在 科研上，还是在平时的生活中，都给了我无微不至的关怀与鼓励。当我在课程学 习中遇到难点时，他总能以循循善诱的授课方式使我豁然开朗；当我在科研上遇 到困惑时，他给了我很多新的思路和方法，使我受益匪浅。他严谨的治学风格， 乐观积极、甘于奉献的生活态度，将永远是我学习的榜样! 本论文是在黄晓鸣老师的精心指导和关怀下完成的。无论是在研究生课程学 习过程中，还是在论文选题、研究、定稿的过程中，黄老师自始至终给了我大力 的支持和无私的关怀，在此向黄老师表示深深的感谢。 感谢我同门的师哥师姐师弟师妹。“三人行，必有我师 ，共同的学习生活使 我收获颇丰。非常感谢在我攻读硕士学位期问给予我帮助的院领导和老师。我还 要感谢同窗的各位同学。我从他们身上学到了很多有益的知识和学习方法。两年 的同窗之谊，离别之际，更显珍贵。我为自己两年来生活在那种坦诚相待、互帮 互助的氛围中感到莫大的荣幸! 最后，感谢各位专家、学者在百忙中审阅我的论文，并给出批评意见。在完 成本论文、即将踏入工作岗位之时，我深深地感到：自己每一步的前进，都离不 开老师、亲朋和同学的支持与教诲，在此表达我对他们最衷心的感谢! 宋莉 2 0 0 8 年5 月 丁，j 于北京交通大学理学院 1 综述 本文讨论了试题库及智能组卷系统的选题模型算法设计。 随着计算机技术的不断发展，利用计算机辅助教学得到越来越广泛的应用。 而试题库系统就是计算机辅助教学的其中一个应用。无论在国内或者在国外，试 题库系统的理论不断的在发展。现在已经有许多试题库系统投入了应用，对改进 教学方法和提高教学质量起到了很大的作用。题库系统是保证考试或测验题目具 有较高质量、保持水平稳定、更好地达到预测目的的重要手段。 本文提出了一种新的自动组卷系统的模型，应用了正态分布及当前在自动组 卷算法中效果较好的遗传算法，提出了一种新的结合了正态分布的应用于多目标 优化的选题算法。 第二章：选题背景、意义及系统需求分析。 在这一章中，首先介绍了国内外在试题库建设方面的发展，接下来介绍了实 现自动组卷系统的必要性，最后，分析了本模型的选题背景和意义，介绍了本算 法模型的主要目标。 第三章：多方向进化算法的提出。 这一章含有四节。第一节主要介绍了本文用到的题目及试卷相关参数设定。 第二节简要介绍了正态分布及遗传算法的知识及现状。第三节及第四节为本文的 重点。第三节提出了应用于多目标优化组卷问题的多方向进化遗传算法及正态分 布在本算法模型中的应用。第四节介绍了本文所提出的遗传算法各要素的具体设 置。 第四章：算法的流程及实现。 本章主要介绍算法的流程和实现，详细介绍了算法各步骤及重要数据结构的 定义和主要代码实现。 第五章：算法的收敛性及效率的理论分析。 由于遗传算法的特殊性，对其收敛性及效率的定量分析是十分困难的，因此 本章对算法的收敛性及效率做了简单的理论分析。 第六章：总结与未完成的工作。 这一章是对整体工作的一个总结，在这个算法模型设计中还存在很多未解决 的问题和未完成的工作，在今后的工作中将进一步完善。 2 2 选题背景、意义及系统需求分析 2 1 国内外在试题库建设方面的发展 在国外，大型题库的建设是在二次世界大战后开始进行研究的。在标准化测试 发展的初期，即上世纪二、三十年代以前，并没有提出题库的问题。四十年代中期 以后，由于战后科学技术和经济的迅猛发展，竞争变得日益激烈，对各类专业人员 和劳动者的知识和能力水平提出了更高要求，考试获得了前所未有的大规模的发 展。 考试次数的增多，命题工作量的增大，对考试的要求日益严格，考试的命题工 作亟待革新，客观、准确、高效率地评估人的专业知识和能力水平，成为教育部门 的一项重要工作。同时，6 0 年代以后计算机技术的迅速发展，也为高质量、大容量、 高智能化题库的产生提供了必要条件。题库是适应考试事业大规模发展，考试进一 步科学化、标准化需要而发展起来的。目前，不少发达国家的专业考试机构都己建 立起了大规模考试的题库。 八十年代中期，随着标准化考试在我国的实施与推广，题库建设也被提上了改 革的日程，不少中学、大学、考试机构都在酝酿或开始建设题库系统。 在传统的考试中，准备一次考试是一件很繁琐的事，从搜集资料开始，选取考 题、对考题赋分、考卷排版、考卷印刷、考试、评卷、到最后记录分数，工作量十 分繁重，工作周期从数周到数月不等。而随着计算机技术的不断发展及其功能的不 断强大，计算机被应用于越来越多的领域。对传统的考试过程进行改革，引进计算 机技术减轻工作量提高效率成为了一个热门课题。试题库系统应运而生，建立与使 用试题库的目的就是为了克服在命题中人为的主观性和片面性，提高考试命题的客 观性和科学性，以及命题的质量和效率。 运用了试题库系统后，可以实现教学与考试的分离，使得任课老师必须按照教 学大纲的要求认真备课，认真组织教学内容，改进教学方法，对提高教学质量和整 体教学水平都有十分重要的意义。 目前，国内外已经有不少试题库系统投入使用，并且有不错的效果。在国外， 不少发达国家的专业考试结构都已建立了大规模考试的题库，已经投入使用的试题 库系统有著名的美国t o e f l ，g r e ，g m a t 等标准化英语考试；新加坡的化学标准化考 试等。另外，除了上述这些著名的试题库系统外，近年来，在国外( 主要是在美国) 出现了一些支持网络考试的产品。 在国内，随着大学教学改革的深入，尤其是“教考分离的逐步实施，对考试 的要求变得越来越严格。“教考分离 指的是对一门课程，组织教学的老师只负责 课堂讲授、课后辅导、批改作业等工作。出考卷和学生成绩评定由其他教师或计算 机完成。我国于八十年代初，随着标准化考试在我国的实施与推广，题库建设也被 提上了改革日程，不少中学、大学、考试机构都在酝酿或开始建设题库，甚至有些 计算机公司也积极地参与进来，并取得了可喜的进步，但是这时的题库存在很大的 不足，大部分题库是整卷库、卡片库或是简单地将题目存储在计算机中的“题库 ， 不能满足社会发展的需要。 计算机的迅速发展给题库建设带来了新的动力，九十年代大容量、多媒体高速 个人电脑的发展给题库的存储管理带来了极大的便利。 试题库系统的理论与技术研究在最近十多年中取得了很大的进步。我国许多高 等院校都投入了大量的人力和物力研制各门课程的试题库系统，在试题库的框架结 构、模型建立和选题算法上获得了进展，并取得了一定的成果。 随着人工智能研究的不断发展，目前比较流行的组卷算法大多采用智能搜索算 法，基本的算法是：根据用户输入的试卷总体要求，分别匹配试卷的知识分布、题型 分布、认知分类分布、难度分布、区分度分布、时间分布、分数分布，形成组卷参 数表，然后根据该参数表从试题库中选题。这类方法在形成最终的组卷参数表时， 没有考虑知识分布、题型分布、难度分布等各种参数之间的相互制约关系，因此在 组卷时题库中经常会出现找不到满足所有属性的试题，只好用具有近似属性的试题 替代，最终会降低组卷的指标。 组卷系统是个被探讨了很长时间的问题，但至今并没有一个很好的自动出题算 法方案。组卷问题是一个带约束的多目标优化问题，采用经典的数学方法很难解决 这个难题，自动组卷的效率和质量完全取决于试题库设计以及抽题算法的设计。如 何设计一个算法从试题库即快又好的抽出一组最符合考试要求的试题，是本文研究 的目的。 4 2 2 实现自动智能组卷的必要性 建设试题库并使用试题库进行考试是国家教委高教司加强宏观管理指导教学 工作在现阶段所采取的手段之一。它既能为高校教学改革服务，又有利于国家教委 宏观监控教学质量。 考试是教育测量的一种普遍采用的重要手段，是高等院校教学管理工作中的一 个重要环节，同时也是一项复杂的系统工程。随着高教改革的不断深入，教学及教 学管理手段的进步和更新，必须彻底改革传统的命题方式。逐步建立起系统、科学、 严密、客观的试题库，并且科学规范地使用试题库考试，已成为教学及教学管理工 作者亟待解决的一个重要课题。 立足于传统教学方式的考试制度，教与学之间的关系是失衡的，教学双方都有 较强的功利主义取向，学生考试主要由教师根据个人教学经验命题，或由教研室临 时组织教师命题。长此以往对学校、对学生乃至对社会都会产生不利影响。这种传 统的经验命题方式存在不少显而易见的弊端。 首先，由于教师个人对教学目标和教学基本要求的理解不尽相同，个人的教学 经验存在差异，对教学内容的研究和讲授也有所偏重，设计的试卷在考核重点、难 度、题型等方面带有很大的主观性和随意性。由于没有统一的科学命题要求和试题 的各项技术指标，因而，同一学科的考试，在班级之间、学校之间和学校不同年度 之间都缺乏准确的可比性，更不利于检查、评估教学质量。 其次，不同性质的考试，对试卷的要求不同。如招生考试是选拔考试，学业考 试则属水平考试，前者对试题的区分度要求较高，后者则更加重视试题的难度、知 识覆盖面及题量大小。但由于大多数教师不熟悉教育测量理论，往往不注意根据考 试性质和要求来恰当选择试题的难度和区分度，以致出现临考试采取修改试卷、延 长考试时间、放宽评分标准等办法，以调整考试成绩的情况。这样的考试不能很好 地达到预期目的。 其三，传统的经验命题大多采用主观题型，题型单调，题量较少，注重知识点 而覆盖面较窄，试卷的信度和效度难以保证。这样的考试反馈的有效的教学信息量 少，无法真正考评教学质量，不利于进一步改进教学。 其四，考试具有双向性，既一方面是考查学生对某一专业课程知识的掌握及运 用情况，另一方面也是对教师教学内容的深广度、科学性及教学效果优劣的衡量。 传统的命题方式使考试侧重考查学生而忽略了对教师教学情况的考评，至少无法对 教师教学质量进行明确有效的评估。 要克服以上弊端，使得教师的教与学生的考两相分离，其中心环节就是建立试 题库，实现题库式考试。利用计算机建立一套完整的试题库，可以根据需要随时自 由选取考题，形成考卷，组织考试。建立使用试题库系统，是实现考试科学化、标 准化的一条有效的途径。 试卷建设可以将命题组卷、题库管理等一系列工作统一化、规范化、系统化， 从而使考试能客观、准确地反映教学双方的质量水平，有效可靠地分析和评估教学 质量。具体表现在以下几个方面： ( 1 ) 能够提高命题工作的效率。题库是由许多适应于不同目的、知识、技能 需要的试题所组成，如果题库中包括了学科中所有内容的高质量试题，则命题者的 工作就会变得简捷而卓有成效，同时命题所花费的时间也会减少。 ( 2 ) 使命题更具有客观性。题库是由许多具有丰富教学经验的教师，经过多 年探索，共同命题，并经过专家论证认可而形成的，而且题库不断得到调整和充实， 具有题量大、覆盖面广、考卷组成随机等特点。通过题库组织的考试可以避免传统 考试中出题主观性强、题目有限、考题与课堂所讲题目类型相近等缺点，使考试更 具客观性。 ( 3 ) 使命题更具方便性。传统的考题需同时提供正式试卷和补考卷及其标准 答案，而且要避免与以往的考题有过多的重复，给任课教师增加了很大的工作量。 有了利用计算机集中管理的题库和自动组卷系统，要完成一套试卷则是轻而易举的 事。 ( 3 ) 能保证和稳定试卷的质量水平。由于试题库是由学科专家总体设计，从 长期大量使用过的成熟的试题中征集，又经过专家加工审议编制而成，因此，无论 是科学性或在考核功能上都是优良的，有着较为科学合理的覆盖率、难度、效度、 区分度。教学内容的各个部分，教学目标的各个层次，各种类型试题的题量比例， 都能够满足命题规范要求。 ( 4 ) 提高了平行试卷的一致性。题库中，由于试题的各方面参数经过统一标 准的严格核正，用这些试题构成的平行试卷具有等价性，其相关程度较高，可以使 不同试卷的内容、难度稳定。 6 ( 5 ) 能有效地充分地反馈教学信息。用试题库命题，不仅可供选择的题量充 分，知识覆盖面宽，而且由于试题库中每道试题在设计时都已确定了它所体现的一 定的教学目标和考核要求，从而，通过试卷的统计分析，可以得到更多有用的教学 反馈信息，便于及时改进教学工作，提高教学质量。 ( 6 ) 有利于开展教学评估、检查教学质量。由于试题库的试题特别是同一类 型的试题在难度、信度、效度、区分度上基本上是等值的，因而可以互相校准，使 整个测量系统具有较好的一致性和稳定性，也便于进行横向和纵向比较，便于检查 教学质量，开展教学评估。 ( 7 ) 由于题库中的题目是大量命题工作者的智慧，题目都附有参数，不必再 测试，因而可以重复使用，节省了大量人力、物力和时间，因此我们可以说题库更 经济。 ( 8 ) 由于试题是题库的最小单位，针对不同内容、难度要求，题库很容易生 成不同试卷，因此具有灵活性。从而克服了在没有题库前，试卷修订困难，内容、 难度不定适合特定要求等问题。 从上述分析可知，与传统命题相比较，题库式命题有其显著的优势。因此使用 试题库系统组卷，可为教学效果的测量提供更为科学、合理的标准，有利于提高教 与学的质量和教育“产品 的综合素质。可以更好地体现教学目标及教学基本要求， 更有效地推动教学改革，提高教学质量。 总之，从国内外建设题库的经验来看，题库可以从两个方面显示出其优越性， 即：第一是题库管理学上的优越性，也就是能做到高效、灵活、经济和高度的保密 性；第二是由于对考试范围、能力层次、难度等有严格的要求，从而使我们根据题 库生成的试卷质量更高，统计特性、可比性能更加稳定一致。 2 3 系统需求分析 2 3 1 课题提出背景 高等数学等课程是高效理工科及管理类专业学生的重要基础课，学习这些课程 的学生人数众多，课程学时量大，再加上高校目前对高等数学课程采用分级教学模 7 式，对该课程的考核方式、命题质量、考试次数等均提出了更多的要求。特别是在 考试命题过程中，为了能够客观准确地考核学生对该课程的学习情况，每次命题时 总要花费很多人力、时间来筛选试题，但却由于种种原因，命题中难免出现诸如章 节、难度、题量、题型、分值分配把握不当的情况，从而在定程度上影响了考试 效果，也为任课教师最终对学生该门课程学习情况的评价带来不便。 传统考试的组织管理方式不仅工作任务繁重，而且试卷的标准化程度、难易程 度、题量大小等各方面难以控制。如何提高教学质量，规范化考试过程，尽量减少 人为因素对考试的影响，使考试更具有客观性、科学性，是教育界多年来追求的目 标。利用计算机自动生成试卷，并逐步积累形成有效的试题库，能够使对试题和试 卷的管理变得高效而便捷，对于提高工作效率，使试卷管理逐步走向正规化、自动 化将起到十分重要的作用。 随着计算机技术的飞速发展，现代教育思想和教学手段的不断变革，计算机辅 助的题库系统越来越收到重视。题库系统是保证考试或测验题目具有较高质量、保 持水平稳定、更好地达到预测目的的重要手段。现在已经有许多试题库系统投入了 应用，对改进教学方法和提高教学质量起了很大的作用。 目前国内已有几种类似软件系统在使用( 例如，教育部的试题库软件、早期西 安交大的题库软件，等) ，但根据部分教师使用这些软件的体会，国内类似软件还 可以在以下几个方面加以改进： ( 1 ) 命题时选题的科学性、客观性； ( 2 ) 入库试题的分类、分级评价标准； ( 3 ) 试题类型不丰富； ( 4 ) 题库的题量不大； ( 5 ) 软件使用的方便性、灵活性不足。 本课题“高等数学题库及智能组卷系统的选题模型及算法设计就是在这种背 景下产生的。 2 3 2 课题选题意义 与传统的专家经验命题、手工组卷的考试方式相比，课题的理论意义和应用价 值在于： 8 ( 1 ) 在教学管理上能做到高效、经济、灵活而又高度保密地编制出所需试卷， 有利于教考分离，对教学内容和质量进行全面、公正、客观的测评。 ( 2 ) 在教育测量上能成批编制出高质量、能预控、等值可比、性能稳定一致 的试卷，有利于按事先指定要求控制考核的内容范围、目标层次及难度系数，能有 效地避免传统的人工组卷命题和评分标准的主观随意性。 ( 3 ) 有利于提高试卷的质量。考试是检查学生学习水平的一种手段。人工编 制试卷的质量易受编制人员的责任心、知识域度、对教材的理解深度、对教学大纲 的把握程度等主观因素的影响，采用计算机题库组卷方式则能排除人工编制过程中 影响试卷质量的多种主客观因素。 ( 4 ) 有利于教学质量管理水平的提高。采用计算机题库组卷方式，可节约大 量的时间、人力、物力和财力，并基本上做到客观公正，反馈的教学信息也有较高 的可信度。 ( 5 ) 有利于减轻教师劳动强度。高质量的题库可为教师腾出大量时间，对教 材教法从事更多更深入的分析研究，充实更多的新知识，更加有利于提高教学质量。 ( 6 ) 如何更加科学、客观的组卷是本系统模型的重点。设计一个算法，能够 满足用户对系统不同程度自动化的要求，同时能够科学、客观的选题，组成一套试 卷返回给用户，是本论文的重要组成部分。 9 3 多方向进化算法的提出 3 1 主要参数设定 在本算法中，应用到的各题目及试卷的相关参数定义如下： 3 1 1 题目属性参数 题库中每道题目有以下几个参数： 1 )序号( i d ) 例如1 2 0 1 ，表示该题目第1 2 0 1 号题目。这一属性将 在题目被存入数据库时自动生成。 2 ) 题目编号( q n o ) 每题唯一。题目编号是标识每道题目的唯一参 数。一但生成，将不能被更改。 3 ) 题目属性( q a ) 一一耿值为1 、2 、3 、4 。分别表示：1 、选择题，2 、填 空题，3 、解答题，4 、证明题。 4 ) 难度系数( q d c ) - - 一由难到易分别为0 1 、0 2 0 9 共l o 个等级。每 题的难度系数与考生答题的平均正确率相关。例如，题目难度为0 8 ， 则将有8 0 的考生能够答对此题目。此系数将根据有关专家和教师的 评估及实际统计结果来确定，以保证其科学和准确性。 5 ) 题目区分度( q q ) 一一衡量考生对各类知识掌握能力的指标。也称为题 目的鉴别力，如果试题的区分度高，那么被测对象水平高的在该试题 上的得分就会高，而水平低的就会得分低，这样就可以把不同水平的 被测对象区分开来。区分度越高，它分辨学生的知识水平和素质高低 的能力就越强。题目区分度是很重要的参数，区分度过大或过小都不 利于反映测试对象的真实差异。一般来说q o 0 2 为劣等题，0 2 q q o 3 为一般题，0 3 q o 0 4 为优良题。 6 ) 选中概率( q p r o ) 一一该属性标识题目在组卷中被选中的概率，最大 为1 ，最小为0 。当一道题目在一套试卷中被选中后，这道题目的q p r o 值将被设置为0 ，表示在下一次组卷时该题目不会被选中。每完成一 l o 7 ) 8 ) 9 ) 次组卷将对题库中的试题的q p r o 值进行重置。 考点编号( q z ) 设计题库时一般易将书中所列的章节当作题目的划 分依据，选题时也依章节来选题，这样的设计方法乎略了这样一种情 况，在高等数学教科书中往往有些章节只是做为基础知识来要求考生 掌握，而不会在这样的章节中出题。针对这种情况，我们设计以考点 为划分题目的依据。例如0 1 0 0 9 ，0 1 表示该题为第一章题目，0 0 9 表 示题目属于第九个考点。 生成同期( q d 卜题目被填加入题库的时间。 被应用次数( q t 卜题目被抽出的次数。每被抽取一次，该参数加一。 3 1 2 试卷属性参数 在本选题算法中，套试卷的生成需要用户设定如下几个参数： 1 ) 试卷应用人群。分为四大类，分别为文、理、工、商。应用于不同人 群对题目的难度及覆盖范围会有各自不同的要求，相同的题目对于不 同的应用人群来说会有不同的难度，不同的专业也对高等数学教学的 深度和广度有着不同的要求，因此我们需要将试卷分为这四大类。对 应系数为x l 、工：、x 3 、毛。这四个系数为相对于标准情况的系数。将 用于试卷期望平均得分与总体难度期望的转换的计算中。这四个系数 的确定同样也需要专家的评估和实际应用的统计来确定。 2 ) 试卷期望平均得分x 。即一套试卷应用后期望的平均得分。这一参数 与组卷试题的总体难度有关。设定，以一定层次的考生答题情况为标 准，在标准情况下，试卷的平均得分如果为7 5 分，则试卷总体难度 期望为0 7 5 。设标准情况下x 对应的总体难度期望为1 。，其它非标 准情况时，期望平均得分x 将对应总体难度期望： 以= 毛胁( i = 1 2 3 4 ) ( 3 1 ) 3 ) 难度方差盯2 。对试卷题目难度分布的约束条件。决定难度分布的图像 的平缓程度。 4 ) 每种题目的总分和题目总数的要求。用户在设置试卷时可以对每种题 目的题目数量和总分进行要求。 5 )每种题目中包含的章和章中的考点。用户在设置试卷时可以根据出题 的特殊要求和目的对考题所覆盖的章和考点进行约束。 在系统的数据库中，将存有给定的出题模板。根据用户所选的试卷分类，将 挑选数据库中相应的模板对每一步骤给出系统默认值。这样，用户可以具体设置 每一种题型的具体章节考点和考题数目、分数而得到一套试卷，也可以只设定应 用人群即得到一套试卷，从而满足了用户出题不同程度的自主性。 3 2 背景知识介绍 3 2 1 正态函数 引散文家詹克明的一段散文：草坪中央，一棵高大的银杏树落叶知秋，褪绿 披黄，金灿灿的扇叶自由飘落，或远或近，或旱或迟，但最后结果? 落叶数量与其 对树心的距离必成“工f 态分布。 正态分布是连续性随机变量中常见的一种概率分布形态，因此，也有人称其为 常态分布。正态分布是统计学研究中最基本、也是最重要的一种分布。它的密度 函数写成以下形式： -(x-,u)21 m ) = 而g 2 扩( 3 2 ) o z 死 图像如下图所示： 1 2 嘶o 0 0 8 ，q 0 0 0 6 o 0 0 0 4 ， o 0 0 0 2 1 0 0 0- 5 0 0 5 0 0l 0 0 0 图3 1 正态分布函数图像 从形态上看，正态分布是一条单峰、对称呈钟形的曲线，其对称轴为过x = n 的纵线。曲线在x = n 点取值得最大值。从x = g 点开始，曲线向正负两个方向递减 延伸，不断向x 轴逼近，但永不与x 轴相交，因此说曲线在正负两个方向上都以x 轴为渐近线。一个随机变量服从正态分布的最大特点是其取值的平均数附近的概 率很大，而取值离平均数越远，其概率越小。 概率论的中心极限定理表明：一个现实的量如果是由大量独立的且均匀小的 变量相加而成，则它的分布就近似于正态分布。现实生活中的许多量都有上述性 质，例如，成年人的身高应该近似地服从正态分布，同样道理，测量误差、某地 年平均气温等也都应该服从j 下态分布。同样，一套试卷的题目的难度也应该近似 地服从正态分布。这就是本算法模型中应用正态分布的原因。 3 2 2 遗传算法 现存的自动组卷系统按照试题的数据结构和生成算法大致可分为三类： ( 1 ) 基于随机函数或随机变量算法的自动组卷系统； ( 2 ) 基于深度及广度搜索算法的自动组卷系统； ( 3 ) 基于智能搜索算法的自动组卷系统。 1 、随机函数选取法 随机函数选取法根据状态空间的控制指标，随机地抽取一道试题放入试题库， 此过程不断重复，直到组卷完毕或无法从题库中抽取满足条件的试题为止。该方 法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷 成功率低，即使组卷成功，费时间也另人难以容忍。 2 、深度广度回溯试探法 深度广度回溯试探法是将随机选取法产生的每一状态都记录下来，当搜索失 败时释放上次记录的状态类型，然后再依据一定的规律变换一种新的状态类型进 行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止。由于回溯是 依据的规律是不变的，破坏了选取试题的随机性。这种有条件的深度优先法，对 于状态类型和出题量都较小的题库系统而言，组卷成功率较好，但是在实际到一 个应用时发现这种算法存在这些问题：( 1 ) 对内存的占用量大；( 2 ) 程序结构相对比 较复杂；( 3 ) 由于变换新状态搜索所遵循的变换规律固定性，破坏了选取试题的随 机性，不能更好的全局搜索；( 4 ) 组卷时问较长。 3 智能搜索算法 智能搜索算法涉及到机器学习、模式识别、统计学、数据库、和人工智能等 学科。数据挖掘和知识发现作为一种独立于应用的智能搜索技术，受到了广泛的 关注，已被应用于商业管理、科学研究、智能决策、故障诊断等方面，在自动组 卷系统中也有应用。但至今，提高算法的效率仍然是采用关联规则发现任务中需 要解决的问题。虽然数据挖掘在组卷寻优中具有一定的先进性，但对它的研究目 前却停留在理论上，缺乏成熟的技术和理论。 分析上述算法的优缺点，不难发现，在限定条件和状态空间的限制下，随机 选取法有时能够取出一组令用户满意的试题。只不过由于它随机选取试题的范围 太大，无法确定目前条件下那些区域能抽出合适的试题，反而可能在那些已经证 明是无法抽取合适的试题区域内反复选题，进行大量的无效操作进入死循环，最 终导致组卷失败。回溯法组卷成功率高，但它以牺牲大量的时间为代价，且随机 性差。智能搜索算法具有全局寻优和收敛速度快的特点，但是其研究广泛，有些 技术和理论还不成熟，必须从中挑选出适合自动组卷的算法。经过研究发现，遗 传算法( g e n e t i ca l g o r i t h m ) 作为智能搜索算法的一种，具有全局寻优和智能搜索技 术，以及收敛速度快的特性，能够很好的满足自动组卷的需要，有效的解决随机 函数选取法和深度广度回溯试探法组卷的不足。 遗传算法( g e n e t i c a l g o r i t h m s ，简称g a ) 是进化算法中发展最快和最为有效 1 4 的一种算法。1 9 6 2 年，美国m i c h i g a n 大学的h o l l a n d 教授及其同事首先提出了g a 的基本思想，并于6 0 年代木期形成了遗传算法的数学框架一一模式理论。他们研 究的目的一方面是抽象出自然系统中自适应机制并加以严格解释和分析；另一方 面是设计具有这种机制的人工系统和相应软件。8 0 年代后，g a 引起了国际学术 界的普遍重视。目前，它己成为人工智能中一个重要领域，是一种十分重要的优 化算法。 遗传算法目前己在各个领域得到了广泛的应用，大量的应用结果证明了遗传 算法具有很强的优化能力。一个标准的遗传算法的处理过程如下图所示： 图3 - 2 遗传算法基本流程 可见，它是通过模拟自然界的生物进化过程，将所求问题的解用编码串( 也 称为“染色体”) 来加以表示，并形成一组代表该优化问题的一些可能解的集合， 我们称为种群；然后利用相应的遗传仿生算子( 选择、交叉、变异) 作用于种群 中的各个染色体，存优去劣，反复迭代，最终得到包含问题的最优解染色体的优 良种群，达到优化目的。 遗传算法处理过程中包含了四个基本要素，即：编码，适应值计算，基因操 作算子和g a 控制参数。这些要素相互配合，支配着遗传算法的收敛速度和求出 的解的优良度。 3 3 多方向进化遗传算法的提出及应用 3 3 1 多方向进化遗传算法 遗传算法是一种模拟自然界生物进化过程的计算模型，它能从群体中选择更 满足条件的个体，具有很强的智能性，同时它能根据不同的环境产生不同的后代， 具有动态性、自适应性。据以上的特点，本文提出一种多方向进化的遗传算法。 应用于多目标约束的试题库组卷策略中时，可模拟同一物种在不同的环境中的进 化过程，并选取其中能更好的适应多种环境的后代保持下去，满足不同目标约束 的条件。 在多目标约束问题中，假定有n 个目标，它们的约束条件分别为： 互= 石( 工) e = 厶( x ) f 。= f n ( 蚺 同时，这些条件分别具有权重，形成一个权重向量： 缈= 池缈2 缈4 ) 对于一个初始种群来说，可以将这些约束条件看作是不同环境对物种不同的 要求，物种需要向更加适应这些环境的方向进化。初始种群经过遗传算子的作用 产生后代，针对不同环境的约束条件的评价函数对后代进行评分后，选出评分较 高的后代，代表这些后代更适应相应的生存环境。在评分较高的m 个后代中，若 存在相同的r n 个个体，表示这些个体同时能比父辈更适合这n 个不同环境的要求。 以这m 个个体作为父代，进行下一代的遗传过程。直到不再产生更优的个体或者 有多于1 1 个约束条件的评分超出预定要求，进化过程停止。这时各项评分与权重 向量综合，综合评分最高的个体即可作为满足目标约束的最优解。 相对于将多约束条件加权组合评分的方法，在这种遗传算法的作用下，可以 使一些在权重不高的约束条件上得分较高而在其它约束条件上得分相对不高的个 体得以保留，进入下一步的进化过程中，使它们突出的基因可以保留到下一子代 中。 1 6 3 3 2 应用于试题库自动组卷策略 要使计算机能自动生成试卷，首先涉及试卷质量评价与组卷目标问题。根据 教育测量与统计学理论，传统试卷质量评价指标主要以试卷的难度、区分度、信 度和效度等作为衡量的标准。组卷目标应体现试卷质量评价指标与教学要求，一 般要求所设计的计算机组卷目标为：试卷总分、章节分值、题型分值、试卷难度、 考试时间、知识点满足、能力层次满足、试卷区分度、试卷形式。 在本自动组卷算法中，主要考查的指标有：试卷难度、试卷区分度、选题重 复性、知识点满足四个指标。 针对高等数学考试的普遍要求，试卷设计为四大部分题目，分别为选择题、 填空题、解答及证明题。在本选题算法中，将整体试卷的抽题分解为四个部分题 目的分别抽取。将每一部分的题目看作是一个小的试卷，应用选题算法选题后进 行组合，形成整体的试卷。 髫试琶竺构矿 月一“ j ；渤 3 3 3 编码策略 图3 3 试卷结构 以往应用遗传算法的选题策略中，通常对题目进行d n a 编码，但在多目标约束 的组卷要求中，针对多个目标，对每个题目进行编码显得力不从心，使得题目的 d n a 编码趋于复杂。因此在本算法中，将每一个候选试题块看作一个个体，每个基 因位对应一道题目，每道题目有相应的难度，区分度，选中概率及所属知识点的 参数，这样对于每一个候选试题块，将会生成个二维矩阵的d n a 编码： 1 7 上。 删= i d ti a 2 d ld 2 耐， d ， 吼 z 5 p ， 通过这样的遗传算法的编码策略，将原始的题目空间t 映射到组卷的解空间s 其中，i d 是每一道题目唯一的编号，用于标记题目；d 为题目难度；q 为题目 区分度；z 为题目所属知识点；p 为题目被选中的概率。 也可以表示为： d n a = dqz 书 ( 一) 基于正态分布的基因编码分段 在本选题算法中，应用正态分布来计算题目难度区间内的选题个数，跟据这 一结果对个体基因进行分段，在进行进化时，以基因段为交叉等运算的基本单位。 当用户设定好试卷类型及期望平均得分x 后，根据公式( 1 ) 可计算得到要组试 卷的总体难度期望“。加上用户设定的难度方差盯2 ，便可得到一个题目难度分布 的正态函数，图形如下： o 2 o 4 0 6 o 81 图3 - 4 正态函数图像( ，= o 5o r 2 = o 0 1 ) 跟据图中所示，将每一个难度对应的函数值求出，设它们分别是石、五、六 石a 再设： c t = 轰( i ，k - 1 2 9 ) ( 3 3 ) 则c ，表示相应难度题目在总题目中所占比例。 根据用户设定的四种题型的各自的题目个数；，可计算出每种题型，每一难 度内要选出的题目个数n ： = q n j = 1 2 。9 ；j = 1 2 3 ，4 ) ( 3 4 ) 这样计算得到的题目个数可能不是整数，可应用四舍五入的办法将它们变成 整数，再应用与数据库读取操作相结合的程序及随机生成算法选出相应个数的题 目。 ( 二) 改进的分段模型 在应用上面的算法模型进行分段时，可能出现下列的问题： ( 1 ) 一套试卷的每一题型的数量不会太多，尤其是解答和证明，有可能只有 两道或三道题目要选。应用上述的算法计算时可能由于；太小，而使得九个难度 的题目计算出来的个数在应用四舍五入的原则时都转换成了0 ，从而不能顺利地进 行选题。 ( 2 ) 在计算每个难度的抽题个数时，所得到的结果一定不可能都是整数，应 用四舍五入的原则进行转换时，可能出现最后题目个数的总合少于或多于用户要 求的个数的情况。 ( 3 ) 分段过于细致，不利于下面遗传算子的作用。 鉴于以上的两点，可对上面的算法进行了改进。 当用户设定好试卷期类型及望平均得分x 后，根据( 1 ) 可计算得到要组试卷的 总体难度期, u i 。加上用户设定的难度方差o r 2 ，便可得到个题目难度分布的正 态函数，如图3 4 。 针对问题1 ，我们对产生的正态函数的图像做下图的修改： 1 9 一 图3 5 修改的正态函数图像 将题目按难度分为四段，第一段为l 1 ( 旷o 3 5 ，第二段为l 2 ( 0 3 5 o 5 5 1 ，第 三段为l 3 ( o 。5 5 川7 5 1 ，第四段为l 4 ( 0 7 5 一1 ) 。 我们计算四个难度区间中各难度区间内所需抽取的题目的个数，在每个区间 内抽取题目个数确定后，按均匀分布随机抽取符合条件的题目。 各区间需抽取题目个数的确定方法如下： 所得正念函数在区间( 沪1 ) 内积分设为s ： i s = j