基于遗传算法的智能组卷

摘要 智能组卷是考试系统自动化操作的核心目标之一，它是按照教师和教学的要求，由计算机自动从试题库中选择试题，组成符合要求的试卷，它是计算机辅助教学的重要组成部分。如何保证生成的试卷能最大限度地满足用户的不同要求，并具有随机性、科学性、合理性，是实现中的一个难点。 组卷的方法有多种多样，本文研究了基于遗传算法的组卷策略。遗传算法是一种有效的非凸函数寻优算法，模拟自然进化的过程。它经过种群产生、计算适应度函数、遗传操作等几个步骤，最终生成较优的、符合要求的试卷。本文将试题建模为拥有难度和曝光度参数的实体，用access数据库保存，最后在Visual C++平台上实现了一个智能组卷系统。实验显示，系统能有效根据输入参数进行组卷。 关键词：组卷，遗传算法，Visual C++ 研究背景与意义 随着计算机辅助教学的不断普及。自动组卷系统开发已成为一个热点问题。在组卷过程中，由于指标问的相互影响以及试题库题量的限制要生成一份符合各项指标要求(如：大纲要求、覆盖面要求、难易分布、题型分布、区分度要求等)的试卷是一个不断试探往复的多目标搜索过程。 ?? 自动组卷就是根据用户输入的组卷要求，由计算机自动从已建的试题库中按照一定的组卷算法抽取试题，组成一份符合要求的试卷。在各种计算机辅助考试系统的软件开发中，自动组卷系统一直是一个重要的研究方向，而一个自动组卷系统的效率和组卷质量主要取决于组卷算法。传统的组卷算法具有很大的随意性和不确定性，时间复杂度很大，是要完整地组成一张试卷，无法从整体上把握题库不断变化的要求，不具有智能性。而且常常由于约束条件的局部不满足而导致组卷失败。 在我国目前教育领域中, 考试是整个教学过程中的重要环节, 它是对学生所学知识和能力的一种评价, 也是衡量教师教学效果优劣的一种教育测量手段 。然而传统的经验考试是由任课教师出试卷, 命题重点、难点带有较大的主观性, 不够客观和准确, 而且批改该卷和统计成绩辛苦、不够准确。随着计算机的发展和普及使用计算机来组卷、批改试卷和统计反馈是计算机辅助教学CAI (Computer Aided Instruction) 工程的重要组成部分。消除了人工的弊端，使考试标准化，实现考、教分离对提高教学质量和整体教学水平有着非常重要的意义 。 ??? 尽管考试系统已经迅速发展甚至普及, 但是大多系统存在无法展示试题或者答案中的图形和无法控制试题重复率、难度、分布等问题。要解决这些问题只有从试题库的组建以及组卷算法上进行改进。 1.2? 国内外研究现状 ?计算机辅助组卷系统是指计算机根据出卷人指定的组卷参数，如(题目类型数、难度系数、区分度、知识点范围、完成试题时间等)从题库中抽取满足以上组卷约束条件的试题组成试卷。目前在这方面常用的组卷方式有回溯(生成测试策略)和整卷抽取策略两种。但从实际使用情况看，两种方法都有一些缺点：第一种方法对内存的占用量很大，程序结构相对比较复杂，组卷速度较慢，选取试题缺乏随机性，且难以满足所有的约束条件；第二种方法组卷时显得较死板，无法满足题库多变要求，且不具有智能性，而遗传算法在此类问题上的求解有独到的优势。 目前国内组卷方法主要采用随机选取法，回溯试探法，遗传算法。 遗传算法是一种模拟自然选择和自然遗传机制的随机优化算法，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，因而对目标函数无可微的要求(目标函数可以是离散的)。它能根据不同环境产生不同的后代，具有动态性，自适应性，从而满足题库不断变化的需求。遗传算法同时具有内在的并行性，能有效地解决计算量大的问题，它具有全局寻优和收敛速度快的特点，这些都适宜于处理试题库自动组卷的问题。 本文就是对遗传算法的改进，实现一种收敛速度快，效果好的遗传组卷算法。 1.3? ?本文主要工作 本文首先介绍了计算机辅助组卷的意义和研究现状，并介绍了组卷的几种方法。然后介绍了遗传算法的原理，简述了遗传算法进行寻优的优点。最后对组卷问题进行建模，并用Visual C++平台编程，用access作为数据库，实现了一个简单的组卷系统。所做的工作可以总结如下： 第一章 引言。简述了组卷问题的研究背景以及意义，并介绍了全文的研究重点，概述了各章的主要工作。 第二章 基本遗传算法的原理。介绍基本遗传算法的原理，并用典型测试函数测试其性能。 第三章 VC平台与access数据库。介绍Visual C++平台和MFC编程，介绍access数据库及ODBC。 第四章 组卷系统实现。介绍如果建立组卷模型，并在VC下编程实现。给出演示的效果图。 第五章 总结与展望。总结全书的工作，并指出其中的不足和未来改进的方向。