基于遗传算法的自动组卷系统研究与实现

《基于遗传算法的自动组卷系统研究与实现》由会员分享，可在线阅读，更多相关《基于遗传算法的自动组卷系统研究与实现（104页珍藏版）》请在装配图网上搜索。

1、基于遗传算法的自动组卷系统研究与实现 分类号:TP39 10710-2009124046 硕 士 学 位 论 文 基于遗传算法的自动组卷系统 研究与实现 丁霞 导师姓名职称 康贤 副教授 申请学位级别 工学硕士 学科专业名称 计算机应用技术 论文提交日期 2012 年5 月7 日 论文答辩日期 2012 年6 月6 日 学位授予单位 长安大学 Study and Implement of Automatic Test Paper Generation System Based on Genetic Algorithm A Dissertation Submitted for the Degre

2、e of Master Candidate：Ding Xia Supervisor：Prof. Kang Xian II Changan University, Xian, China 摘 要 随着教育改革的深入，在教学活动中一直扮演重要角色的考试环节也发生了巨大的 变化，越来越多的考试都采用自动组卷系统出题。自动组卷系统能够有效改善传统的考 试方式，提高试卷命制工作的效率。自动组卷问题是一个在一定的约束条件下的多目标 参数优化问题，而自动组卷的效率和质量主要取决于组卷算法和试题库的设计。 为了提高试卷质量，增加考试的科学性和客观性，本文的主要研究内容就是改变传 统的命题方式，搭建一个全面、科

3、学、合理化的试题库，并在已生成的试题库中根据教 师和教学要求，利用改进的遗传算法抽取试题，自动生成试卷。 论文首先对课题的研究背景和组卷算法的研究现状做了广泛的调研，经过一系列的 理论研究和对不同的组卷算法分析比较，采用了改进的遗传算法作为组卷策略，以功能 强大的Visual C+6.0 作为开发工具，基于Access 2003 数据库，实现了自动组卷系统。 最后进行了功能测试和系统测试，测试结果表明基于遗传算法的自动组卷系统无论是在 组卷成功率还是在组卷所耗时间上都明显优于传统的组卷算法。系统界面友好，大大提 高了教师的出题组卷效率。 关键词：自动组卷、试题库、数学模型、遗传算法 i Abs

4、tract With the deepening of educational reform，the examination which plays an important role in the teaching activities has changed greatly, Now, more and more test papers are generated by the auto-generating test system. The auto-generating test system can effectively improve the traditional way of

5、 examination, it also can increase the efficiency of generating test papers. The test paper generating is an optimized problem to multi-objective parameter with certain restriction. Thus the efficiency and quality of this system mainly depends on the test composing algorithm and the test database de

6、sign. In order to improve the quality of the test paper, and enhance the scientific nature and objectivity of examination, the subject of this thesis will not only change the traditional way of proposition and build a comprehensive, scientific and rational examination questions database, but also ge

7、nerate test paper automatically according to teaching requirements. Using improved genetic algorithm to select questions, then generate a test paper. Firstly the background of the research and the composing algorithm was investigated widely. After a series of theoretical research, the comparison and

8、 analysis of different composing algorithm, finally the strategy of generating test paper based on the Genetic Algorithm was adopted. In this thesis, Visual C+6.0 and Access 2003 were used as development tools, which realized an auto-generating test paper system. At last, the results of function tes

9、t and system test showed that the auto-generating test paper system based on genetic algorithm are obviously better than the traditional algorithm both in the success rate and consume time of composing test paper. With friendly interfaces, the system greatly improved the efficiency of composing test

10、. Keywords: auto-generating examination papers, test bank, mathematical model, genetic algorithm ii 目 录 第一章 绪论. 1 1.1 课题研究背景及意义. 1 1.2 国内外研究现状.2 1.3 论文的主要研究内容.4 1.4 论文组织结构.4 第二章 组卷的评价体系与建模.6 2.1 组卷的基本原则.6 2.2 试题属性指标体系.7 2.3 试卷的质量衡量指标. 13 信度. 13 效度. 15 效度与信度的关系. 17 2.4 组卷问题的数学建模. 18 第三章 自动组卷算法研究.20 3

11、.1 几种常用的组卷方法.20 3.2 遗传算法理论.22 遗传算法的特点.22 遗传算法的运算流程.23 3.3 自动组卷算法设计.28 第四章 自动组卷系统设计与实现.33 4.1 系统需求分析.33 4.2 系统总体设计.34 4.3 数据库设计.35 数据库概念结构设计.35 数据库逻辑结构设计.36 4.4 系统主要模块功能设计与实现.40 用户管理模块.40 科目管理模块.43 试题库管理模块.43 试卷生成模块.46 第五章 系统测试.48 iii 5.1 测试的基本概念. 48 测试的目的. 48 测试的方法. 48 5.2 系统测试方案. 49 功能测试. 49 系统测试.

12、51 5.3 测试总结. 52 总结和展望. 53 参考文献. 55 致 谢. 58 iv 长安大学硕士学位论文 第一章 绪论 1.1 课题研究背景及意义 在教学或培训考核过程中，考试占据着非常重要的地位，缺少考试的教学过程是不 完整的。古今中外所有的正规教育都把考试作为选拔人才、对学生的学习情况进行考核， 提高学习积极性，对教师的教学水平进行考核等的重要手段。另外，考试还可以为提高 教师的教学方法和学生学习的方法等提供重要的参考信息。由此可见，考试工作组织的 好坏直接影响到教学质量的评价。 组卷是考试过程中不可缺少的环节，试卷组织的好坏直接影响到考生真实水平的反 映。如果考试过程中不能采用一

13、份良好的试卷，就无法用考试的结果来正确衡量考生的 学习情况以及教师的教学成果，甚至得到相反的结果。因此，想要通过考试来考核学生 学习情况、衡量教学效果，考试过程中必须采用一份良好的试卷。传统的组卷方式，没 有一个标准化的试题库，一般需要教师收集大量试题资料作为题库，然后主观地再从中 选择合适的题目，随意性较大。采用这种组卷方式所生成的试卷，命题教师不同，所挑 选的题目就有不同的侧重点，这样不能够确保试卷的合理性、科学性，还有可能会使试 卷的难度超纲，不仅不能够达到考核的目的，而且也会因为大量的重复性工作耗费了出 题教师繁重的脑力劳动和体力劳动。总之，这样的组卷方法不仅会消耗大量的人力及物 力，

14、更浪费了出题教师大量的工作时间。自动组卷系统是根据考试大纲要求和教育测量 学理论来进行命题，建立标准化的试题库，这样组成的试卷可以解决试题的科学性问题， 提高试题质量。具体要求是：给出每道试题的难度值和区分度值，保证试题的科学性； 为每道试题提供参考答案、分值范围，确保其合理性；试题所涉及的范围全面，体现教 学大纲要求；试题数量要足够，减少抽取试题重复率。不管是什么类型、什么科目的考 试，如果可以按照教学大纲组建标准试题库，便可以进行自动组卷，而且组卷效率也高。 因此，针对采用计算机进行自动组卷问题的深入分析、研究已迫在眉睫。 近年来，计算机在教育上的应用已非常广泛，比较典型的的技术是计算机辅

15、助教学， 而利用计算机实现自动组卷是计算机辅助教学的重要方面。利用计算机自动组建试题 库，自动对题目进行参数分析，抽题组卷，完成对学生的各项学习情况的考核。根据考 核情况改革教学方法，还可以不断更新试题库内容，使试题库中的试题能更好的符合组 卷要求，提高组卷效率，节约命题教师时间。利用计算机自动选题组卷，不仅节约了组 1 第一章 绪论 卷工作者的工作时间，还能避免工作中出现的主观错误，增强考试的客观性、真实性以 全面的反应实际的效果，切实的提高教学质量与教学水平。另一方面，利用计算机组卷， 可以实现教学考试分离，敦促教师在教学过程中按照考试大纲组织教学，从教师的角度 1 提高教学水平。达到良好

16、的教学效果 。所以利用计算机组织试卷已经成为组织考试工 作的发展趋势。它不仅避免了人工组卷的各种不足，还具有良好的定制性，可以根据要 求从试题库的大量试题中快速准确的抽出一套符合各项参数要求的试题。能够生成符合 要求的试卷是整个组卷系统中最为基本的要求，而这其中组卷算法的设计起着关键性的 作用。通过自动组卷系统，可以把客户的实际需求和计算机结合在一起，让计算机自动 抽取符合客户需求的试卷。但是，自动组卷系统的试题库设计比较复杂，现有的试题库 设计有三种：一是将整个试题库中所有的试题由教学经验丰富的教师进行审查、对比后 手动抽取，组成一份相对合理的试卷。二是将整个试题库作为一个大的试题集，然后根

17、 据不同的组卷条件组织多份试卷并存储起来，在真正需要抽题组卷时，从已存储的试卷 中任意的抽取一份作为考试试卷。三是利用某种组卷方法，根据组卷约束条件，利用计 算机自动抽题组成一份符合要求的试卷。第一种方法能够保证试卷质量，但是类似于传 统的人工组卷，所以具有很大的局限性。第二种方法也可以保证试卷质量，但是所出的 试卷份数有限，同样也有很大的局限性。第三种方法则是根据一定的组卷策略利用计算 机随机出题，但是其组卷的效率和质量与所采用的组卷算法息息相关。所以，研究组卷 算法意义重大。 经过分析研究，本文结合遗传算法的基本理论，就将遗传算法应用于自动组卷系统 中，通过对组卷问题的数学建模，利用遗传算

18、法的高效求解过程，自动生成符合条件的 试卷。不但提高了效率，同时克服了传统组卷工作的诸多缺点。因此具有重要的理论意 义和现实意义。 1.2 国内外研究现状 考试的核心工作之一就是组卷。将计算机技术与数据库技术应用于考试组卷系统已 成为一项具有很高价值的课题。上个世纪50 年代，计算机技术首次应用到教学领域， 这其中包括程序教学，利用计算机进行教学内容的呈现等。60 年代，又出现了计算机辅 助教学技术 CAI ，该技术是在计算机上运行程序，实现辅助课堂教学、学生问题答疑、 模拟考试等操作。到了20 世纪70 年代，又出现了一种和计算机科学、教育学、心理学、 认知科学和行为科学等多种学科的新兴技术

19、，被称为智能教学系统。它是在一定程度上 2 长安大学硕士学位论文 代替人类教师实现最佳教学，让计算机系统负担起人类教育的责任。后来，人们对智能 教学系统展开了全面、深入的研究，取得了较好的进展。例如国外早期比较有名的地理 2 教学系统、电子学线路故障排除教学系统、逻辑和集合论教学系统等 。20 世纪80 年 代后，又出现了计算机等级考试系统，如美国的计算机适应性考试 GRE 、托福考试 TOEFL 、经企管理研究生入学考试 GMAT 等。80 年代中后期，荷兰林顿等将随机现 行规划方法引入到测验编制领域。而后又有许多其他的以现行规划法为基本算法的组卷 3 形式出现。当前我国许多科研机构以都展开

20、了对这方面的研究工作 。 在国内，计算机辅助教学系统虽然起步较晚，但经过最近几年的发展，仍然取得了 较大的进步，许多科研机构将计算机自动推理运算的理论应用于教学，并开发了一些计 算机考试系统，包括高等数学试题库及计算机辅助命题和评估软件系统 MATBAS 4 、 基于 PASCAL 的题库系统，尽管这些系统都应用了先进的计算机技术，但是他们并没 有实现自动组卷，考试试题的产生仍然需要人工命题。因此，后来又出现了大量的计算 机考试系统，他们的发展推动了自动组卷问题的研究。随着现代教育技术的进步，教育 领域中的考试环节已向无纸化、电子化、分值科学化的方向发展，很多类型的考试也已 逐渐在网络教学平台

21、上实现测评与阅卷，而其中的组卷问题则是保证能够实现这一发展 的重要指标，也是网络教学平台中的关键环节。近年来，国内自从把计算机技术、人工 智能技术和数据库技术等应用到自动组卷系统后，对于自动组卷的研究就有了突破性的 进展，自动组卷技术的研究已经涉及到了对算法的分析，数学模型的建立，以及人工智 5 能处理等领域 。 对于自动组卷的研究由来已久，目前对这类问题结局的方法较多，而侧重点却各有 不同。国外算法主要以线性规划法进行基于项目反映理论，而国内则有随机组卷算法、 回溯试探组卷算法和基于遗传算法的组卷算法。自动这些组卷算法有各自的特色之处， 在一定的程度上都能够满足使用要求，但在当今的信息时代，

22、各学科教育不断提高，有 6 些组卷算法较为简单，只有很少的一点自动组卷功能，难以满足用户的实际需求 。例 如设置组卷条件组卷时，随机选取方式在有限的概率内会抽取出一套符合要求的试题， 但是如果试题库过大，系统有可能会在不可能抽出符合试卷的区域内反复运行，最终进 入无限循环，程序崩溃，无法成功选题；而利用回溯试探算法的成功率虽然比较高，但 是会消耗大量的运算时间。也不能达到较好的效果。 3 第一章 绪论 由上所述，为了更好的使用计算机组卷，必须研制一套合理有效地组卷系统，本系 统在对诸多算法分析后，最终采用遗传算法理论作为组卷的核心算法，提高了组卷效率 和组卷成功率。 1.3 论文的主要研究内容

23、 1 试题属性指标的分析 本文重点分析了试题的属性指标体系，并且对试题的难度、区分度、信度、效度等 指标加以详细论述。 2 试题库的建立 分析完试题的属性指标后，就需要确定试题库的设计方法，重点定义了系统需要的 数据表和各个表之间的关系，以方便操作维护试题库。 3 系统框架及各个模块的设计 给出系统需求分析，设计系统框架，开发相应模块。根据需求分析得出本系统主要 是由用户信息管理模块、科目管理模块、试题库管理模块和组卷模块四个模块组成的。 4 各个模块程序的编写 对系统进行总体设计完之后，就需要编写各个模块的代码，在代码实现过程中，主 要考虑程序语句、结构、效率、可移植性、健壮性等方面。 5

24、组卷算法的实现 组卷模块是本系统的核心，本论文讨论了采用遗传算法求解一定约束条件下的多目 标参数优化问题，将试卷的难度、区分度、章节、题型和分值等约束条件转化为目标函 数，然后采用自然数编码方案，把遗传算法应用到自动组卷模块中，最后使用 Visual C+6.0 结合Access 2003 技术编程实现了自动组卷系统。 1.4 论文组织结构 第一章，绪论。分析大量的国内外参考文献，阐述了本课题研究的背景及意义，分 析国内外研究现状，给出论文的主要研究内容和组织结构安排。 第二章，组卷的评价体系与建模。详细介绍了系统的组卷原则，分析了试题属性、 质量衡量指标、影响因素以及如何提高。 4 长安大学

25、硕士学位论文 第三章，自动组卷算法研究。提出了几种常用的自动组卷算法，并加以分析比较各 自的优缺点。重点分析了遗传算法，介绍了遗传算法的几个特点和主要的运算流程，结 合遗传算法设计出了本系统所采用的算法，为后面系统的实现做铺垫。 第四章，自动组卷系统设计与实现。按照学校各个部门和各类人员对试卷生成系统 的要求，提出本系统的需求分析、系统总体设计，并对系统中所使用的几个重要的数据 库表结构给以说明，详细介绍了系统各个主要模块功能。 第五章系统测试。介绍了测试的基本概念，如测试目的、方法等，给出了系统的主 要功能测试和系统测试。 文章的最后总结了整个系统，分析了当前系统存在的问题与不足，探讨了未来

26、系统 的完善方向，并对论文下一步的工作进行了展望。 5 第二章 组卷的评价体系与建模 第二章 组卷的评价体系与建模 作为考试的重要环节，组卷的质量决定了考试的成功与否，试题质量的好坏直接关 系到整个考试的结果，进而影响到考生真实水平的反应。而试题的质量又由组卷时能否 科学、合理等因素决定。一般来说，影响组卷效率的两大指标分别是其代表性和针对性。 试题的代表性是指取样试题对考试大纲与要求的反应度，针对性是指所抽取的试题应当 合理，考试目的、时间不同，试卷的试题内容也有不同的侧重点。本章中，根据组卷的 基本原则，试卷评价指标以及相互关系等创建组卷问题的数学模型，为实现本系统奠定 良好的基础。 2.

27、1 组卷的基本原则 试卷的编制并不是将任意选取的几道试题堆砌到一起，而是按照一定的原则从试题 库中抽取符合约束条件的题目，把这些符合要求的题目组合成一套试卷，这样才能确保 考试时的试卷质量，才能使考试顺利进行，达到考核的目的。一般来讲，常规的考试主 要有两方面的作用：第一，用于学生对自身能力的测试，考核自己对知识的掌握程度； 7 第二，教师考核自己的教学水平，检测学生学习情况，改进教学方式，掌握侧重点 。 这两个方面均为考察学生所学到多少知识及掌握的程度如何，都为目标参照性的测试。 本课题所研究与实现的自动组卷系统主要用于学校考试，都为考察学生的学习情况和教 8 师的教学效果，属于目标参照性测

28、验。其组卷原则 要在以下几个方面体现： 1 组卷要以考试大纲为依据，试卷的内容必须全面反映考试大纲的广度和深度。 组卷时，被抽取的试题要全面符合考试大纲的基本要求，整个试卷的题目从总体上 要考核学生对基础知识的熟记、对基本理论的掌握、对基本技能的应用，更要考核考生 能灵活运用所学的基本知识和理论分析和解决实际问题的能力。一份完整的试卷要有足 够多的试题，试题覆盖面才广泛，才能全面反映大纲的广度和深度。 2 重点抽取能体现考生能力及提高考生智力的试题。 检测考生对基本理论的掌握程度不是考试的唯一目的，更要通过考试来提高学生的 学习积极性和思考能力，从而促进考生智力的发展。组卷时要考虑多种类型的试

29、题和多 个知识点，选择最佳的组合结构，才能从不同侧面考核考生对知识的掌握情况和智力能 力，达到更好的效果。 3 组卷的层次要清晰，难度要有级别，保证考生在分数上拉开距离。 6 长安大学硕士学位论文 难度过大或过小的试题都不会有好的区分度。如果试题太简单，考生的分数都很高， 考生会感觉不用付出努力就可以轻而易举的得高分，不仅不能提高学生在学习上的积极 性，也得不到考生的实际水平；相反，如果试题难度太大，不在考生的实际能力范围内， 通过考试后所得到的分数都很低，考试分数和学生的努力程度不能成正比，这不仅难以 区分考生的能力，更容易丧失考生的信心，同样也无法得到考生的真实水平。因此，试 卷的难度过大

30、或过小都不符合要求，应从大多数中等水平考生的能力出发，设置实际难 度值，让优秀考生得高分，成绩差点的考生得低分，中等水平考生的分数介于两者之间， 即在分数上拉开距离，达到区分考生的目的。 4 用户决定试卷中的试题内容，可以根据章节、题型等选取试题。 在考核考生对基本知识掌握程度时，应当考虑各个章节所用的教学时间和试卷中各 个章节所占分数的关系，一般情况下是成正比的，但特殊情况下用户也可以根据不同考 试目的需要改变分数比例。 5 试卷的编排要合理。 每份试卷的题型、分数、难度、区分度等也随考试目的、考试性质等的不同而不同， 所以要根据具体情况合理编排试卷。 6 为提高考试信度，命题的表达语句或指

31、导语句要清楚并且无误。 命题的表达语句和指导语要清楚，保证考生不会因外部不可预料的因素而影响发 9 挥，才能通过考试得到真实的结果 。 组卷工作是一项比较复杂的脑力劳动，不仅要求命题教师对考试科目的大纲有深刻 的了解，还要求对考试对象、考试性质、考试试卷形式、题量、考查重点、以及难易程 度等有着深刻的把握。组卷时，需要命题教师根据命题计划编制试题并给出答案，同时 需要标明每道试题的难度、区分度、所属章节、认知层次等所有属性指标。为保证试卷 的正确性，防止因个人疏忽而出现主观性错误，组卷完成后还需要对已编制的试题进行 审查、修改和筛选。因此，组卷是一项很繁重的脑力劳动。 2.2 试题属性指标体系

32、 将试题库存储在试题库中，其本身含有固定的属性，而各项属性指标的确定都直接 关系到所组织试卷的准确性和组卷的效率。组卷时，用户根据自己的需要设置约束条件， 系统把试题库中试题的各项属性指标和用户提出的约束条件进行比较，确定是否选取该 10 试题。所以试题的属性指标是计算机进行抽题组卷的基础 。 7 第二章 组卷的评价体系与建模 结合实际教学和技术情况，本文主要定义了题号、题型、难度、区分度、能力层次、 11 分值、答题时间、曝光度、最后一次抽题时间等属性指标 ，下面对试题指标体系的构 成进行详细的阐述。 1 题号 题号是试题在题库中的编号，每道试题都有唯一的编号，本系统在利用遗传算法选 取试题

33、时，题号作为染色体基因出现，是抽取试题的一个重要依据。题号是试题库字段 的主键。 2 题型 题型是抽取试题的一个重要依据。考试科目不同，其题型也有差异。为简单起见， 本系统主要设有单项选择题、多项选择题、程序填空题、程序设计题等四种题型。用户 根据自己的需求选择题型。如果所需要的题型不在系统列出的题型中，可以选择一种相 似的题型代替，等到组卷成功之后，再手动修改题型。 3 难度 难度是衡量试题质量的一个重要指标，在实际抽题组卷时，会根据不同的考试目的、 时间等要求选取不同难度的试题，达到更好的考察效果。本课题在设计系统时结合现实 情况，将难度系数主要分为五个级别，具体如表2.1 所示。 表2.

34、1 试题的难度系数表 难度级别 容易 较易 中等 较难 难 难度系数 0，0.2 0.2，0.4 0.4，0.6 0.6，0.8 0.8，1.0 12 试题的难度值 是指参加考试的学生群体在某道题上的失分率，用符号 D 表示。 其计算公式为： ? X D 1? 2-1 W ? X 其中， 为整个考生群体在该试题的得分的平均值，W 为该题的实际分值。 ? ? ? ? X X X 从式 2-1 知， 越大，D 值越小，当 W ，D 0 ； 越小，D 值越大，当 0 X ? ? 0,1 时，D l ，D 的取值范围为 。 也就是说，学生群体在某试题上的平均得分越高，该试题的难度值就越小；相反， 平均

35、得分越低，难度值就越大。当所有考生都通过某试题的考核时，难度值为0，试题 8 长安大学硕士学位论文 最容易；反之，当所有考生都没有通过某试题的考核时，难度值为1，试题最难；当有 一半考生答对某试题时，此试题的难度值就为0.5 。 公式 2-1 定义的难度，是指某道试题的难度。而试卷的难度是指试卷中所有试题难 度的平均值。在实际的考试时，应根据具体要求来确定这个总难度值。 如果想要通过考试来检查考生对知识的掌握程度，则对试题的难度没有特殊性要 求，必须掌握的知识，难度值为0 或接近于l 的试题，都可以采用。而如果想要通过考 试来选拔人才，区分考试的能力，则最好选取难度为0.5 左右的试题。如高考

36、、研究生 入学考试等，都有一定的难度级别。通常易、中、难试题的比例为 3:5:2 ，即使整个试 卷的平均难度保持在0.5 左右。 为计算方便，本系统中用整数表示难度级别，对应关系如表2.2 所示。 表2.2 难度级别对应整数值表 难度级别 易 较易 中等 较难 难 整数值 1 2 3 4 5 4 区分度 区分度是指试题区分不同水平考生的程度，即题目的鉴别力。试题的区分度和试题 的难度息息相关。难度过大，能答对题的人数就少，大多数考生的得分都很低；难度过 小，很少有考生会答错，考生的分数都集中在高分段，这两种情况都会导致考试分数比 较集中，因而过难或过易的题目都不能很好的把不同水平的考生区分开来。只有当题目 的难度为中等时，区分度最高，题目被采用的价值就越大。也就是说，可以利用区分度 就把不同水平的考生区分开来。同难度指标一样，不同类型的考试，区分度的要求也不 一样。对