智能在线考试系统中遗传算法组卷的设计和实现.pdf

l 生 甸 似 智能在线考试系统中遗传算法组卷的设计和实现 S ma rt o n l i n e e x a m i n a ti o n s y s te m g e n e ti c a l g o ri th m d e s i g n a n d i mp l e me n ta t i o n o f te s t p a p e r 吴英 大犬 WU Y i n g 上海政法学院 上海 201701 摘要 计算机考试系统研究主要是用来实现学生上机考试 传统的组卷方法采取完全随机的方式来 抽题对试卷在能力和层次上的差异性 覆盖面宽窄等现象难以有效解决 本文阐述了遗传算 法组卷在计算机考试系统中的设计和实现 从试题的数量及试题库结构两个方面分析 解决 上述问题 关键词 遗传算法 组卷技术 考试系统 中图分类号 T P 391 文献标识码 B 文章编号 1 009 01 34 2ol 1 1 下 021 5 03 D o i 1 0 3969 J i ssn 1 009 01 34 2011 1 下 73 0 引言 在计算机课程的教学中 把传统笔试 与计算 机技术结合到一起 的考试方式越来越被师生所接 受 智能在 线考试系统 研究主要是用来实现学生 上机考试 软件 系统通过网络服务器的设置 学 生所用 的计算机作为客户端来登录服务器获得试 题 答题完毕后 网上提交试卷 软 件系统对学生 的答卷按班级学号等进行分类 整理 然后进行 智能化的判卷 给分 对部分题 目类型能够实现 其中 试题库系统的开发一直是教学改革中的重要 方面 对改进教学方法和提高教学质量 以及实现 考试的公平性起到 了很大的作用 其 中全 自动成 卷模块是试题库系统的一个亮点 1 在线智能考试系统的设计 1 1 系统的组成模块 学生考试部分 注册 登录 验证信息 试题 下载 系统管理部分 课程管理 试题管理 学生管 理 成绩管理及查询 补考管理 数据库部分 学生基本信息 学生选课信息 课程信息 教师信息 试卷信息 各题型信息 1 2 系统各模块设计 1 用户登录和注册 根据用户所属的不 同角 色显示不同的操作页面 如考生登录时 显示生 成试卷等待页面 教 师登录时 显示题库管理页 面 系统管理 员登录时 显示系统维护页面 2 角色 管理 添加 角色 修改用户 删除用 户 角色权限管理 3 用户管理 添加用户 修 改用户 删除用 户 分配用户的角色 4 题库管理 1 试题类别管理 主要实现试 题类别的添加 删除 修 改和排序功能 2 考试 试题管理 主要实现试题 的添加 删除 修 改和 排序功能 3 试题答案管理 主要实现试题答案 的添加 删除和修改功能 5 在线答题 1 动态随机生成试卷 使用遗 传组卷算法动态地从题库 中取得试卷的题 目 每 次生成的试卷是不同的 2 显示整套试卷 6 成绩管理 2在线智能考试系统的关键技术 2 1 A S P N E T技术 A SP N E T 是 当今 最 先进 的开发 平 台 运行 在服务器端 它不仅是 A cti ve Server Page A SP 的下一个版本 还提供 了一个统一的 W eb 开发模 型 其 中包括开发人 员生成企业级 W eb 应用程序 所需的各种服务 利用它可建立功能更加强大的 W eb 应 用 作 为 M i crosoft N E T 平 台 的一 部 分 A SP N E T 提供 了划时代的新程序设计框架 是创 建 W eb 应用 的首选平 台 A SP N ET 开发速度快 并且为开发 部署和运行 W eb 应用提供 了最快捷 并且 可缩放性程度最高的方式 它可选择任何一 种可用的 NET 编译性程序设计语言 不需要重新 收稿日期 2010 12 I 作者简介 吴英 1972 女 上海人 讲师 硕士 研究方向为计算机基础教学 软件工程 第33卷第1期2011 1 下 215 学兔兔 w w w x u e t u t u c o m l 匐 化 编译 极 大地简化了部署的过程 只需要将程序 复制到 W eb 服务器即可 此外 它还提供 了一些 对数据库 访问的数据控件 比如 D ataL i st D at aG ri d 控 件 使得对数 据库操作更加灵活 方便 鉴于 A SP N E T 的以上优势和 目前远程考试存在的 问题 采用 A SP N E T 技术结合 B S 模式 设计远 程考试系统 2 2 使用A DO NET访问数据库的方法 系统使用 SQ L Server 2000 作为应用程序的数 据库 考虑实际需要 主要包括七个表 基本 结 构如下 1 角色表 角色 ID 角色名称 2 用户表 用户 ID 用户名 密码 E m ai l 角色 ID 3 考生表 考生 I 用户 考试时间 成绩 4 问题种类表 问题类型 ID 类型名称 问 题顺序号 5 图片表 图片 ID 图片标题 图 片存 储 地址 6 问题表 问题表 ID 问题标题 问题内容 添加 试 题 的 时 问 问 题 类型 ID 问题 的 图 片 ID 难度系数 成绩 7 问题答案表 问题 ID 答案标题 答案内 容 图片 ID 问题 ID 系统采用类 D B C onnecti on 来封装访 问数据库 的某些基 础属性和 函数 如数据库连 接字符 串 添加数据库的参数等 2 3 基于遗传算法的自动组卷技术 以往智能在线考试 系统大多采用随机选取法 和回溯试探法 随机选取法方法结构简单 对于 单道题 的抽取运行速度较快 但是对于整个组卷 过程来说组卷成功率低 有时能够抽取 出一组令 用户满意的试题 只不过 由于它随机选取试题的 范 围太大 无法确定 目前条件下哪些区域能够抽 取合适的试题 反 而可能在那些已经证明是无法 抽取合适试题的区域 内反复选题 进行大量的无 效操作进入死循环 最终导致组卷失败 即使组 卷成功 花费时间也令人难以忍受 回溯试探法 是种 有条件的深度优先算法 对于状态类型和 出 题量都较 少的题库系统而 言 组卷成功 率较好 但在 实际应用时对内存的 占用量很大 程序结构 相对 比较 复 杂 而 且 选取 试 题 缺 乏 随机 性 组 卷 时间长 对于现今越来越流行的考生网上随机即 12161 第33卷第1期2011 1C F 时调题的考试过程来说 它巳不符合要求 我们从试题的数 量及试题库结构两个方面分 析 将遗传算法应用到该系统中 努力实现试卷 的生成和考查的知识点尽可能地接近 并 由教师 控制试卷的难度系数等 遗传算法是模拟生物界 适者生存 自然选择 等生物进化机制发 展起来的 一 种高度并行 随机和 自适应 的搜索算法 是解 决复杂问题的一个有效途径 2 4 遗传算法的一般结构 在设计遗传算法时通常按以下步骤进行闭 1 编 码方案 遗传算法求解问题 一般不是直接在问题 的解空间上 而是利用解的某种编码表示 2 确定 适应 函数 适应值是对解 的质量的一种 度量 解 的适应值是演化过程中进行选择 的依据 3 选择 策略的确定 优胜劣汰的选择机制使得适应值好 的解有较高的存活概率 4 控制参数的选取 控 制参数主要包括种群规模 算法执行的最大代数 执 行不 同的遗传操作的概率及一些辅助性的控制 参数 5 算子的设计 主要有杂交 变异和再生 6 确定算法的终止准则 2 5 基于遗传算法的组卷问题的设计 1 染色体编码 编码就是用一种数字排列方案来表示问题的解 的方法 利用编码将问题的解空间映射到 G A 算法 的编码空间 如何将问题的解转换为编码表达的染 色体是遗传算法的关键问题 即先要将问题的解空 间映射成一组代码串 编码方案的选择依赖于问题 的性质 并影响到算法内操作的设计 是影响算法 性能的重要因素 常见的编码方案有二进制编码 十进制编码 实数编码等 采用二进制编码 用 1 表示该题被选中 0 表示该题未被选中 这种编码 简单明了 但进行交换等遗传操作时 各题型的题 目数难以精确控制 而且 当题库 中题量很大时 编码很长 我们采用实数编码 将一份试卷映射为 一 个染色体 组成试卷的各个试题映射为基因 基 因的值直接用试题的题号表示 这样染色体的编码 可表示为 G 1 G 2 G 3 G n 其中G i i 1 2 11 n 为试卷的总题目数 为试题编号 比如要组成 一 份选择题 5 道 填空题 5 道 简答题 2 道的一份 试卷 则染色体编码可以是 23 45 90 67 22 11 69 l 12 9 37 选择题 填 空题 78 54 J 简答题 学兔兔 w w w x u e t u t u c o m 务I 匐 化 编码时将 同一题型 的题 目放在一起 同时为 保证一份试卷 中考查点不重复 每条染色体 中各 基因的考查点编码必须各不相 同 由于不 同的题 型是从不同的题型表 中取 出 有可能在 同一个基 因串中会出现相 同的试题编号 它们 属于不 同题 型 考察的知识点也未必相同 故这种情况很正 常的 不影响我们进行组卷 在实 际组卷过程 中 假设在试卷中每种题型 的数 目是 固定的 且相同题 型的分数和答题时间 是相 同的 这样我们将整个编码 串按照题 目类型 划分为不 同的功 能块 每个功能块可以认 为是独 立的编码 也就是说每个功能块对应一种特定 的 题型 显然按这种规则产生 的群体已经满足 了试 卷对题型 分数和答题时间的要求 2 群体的初始化 根据用户选定 的考试内容及各种题型的题 目 数 按 同一试卷中考查点不重复的原则 从相应 题型表中随机抽取试题 生成初始群体 群体的 大小按经验或实验给出由于遗传算法和其它启发式 算法一样 不对全部解空间进行穷举搜索 因此初 始的候选解群体的选择会对得到最终解的速度和质 量有影响 初始的候选解群体在解空间内分布得越 均匀 它们拥有的遗传基因就越有代表性 3 适应度函数 在遗传算法中 以适应度大小来 区分群体 中 个 体 的优 劣 设 di i 1 2 m rlq 为 试 卷的总题 目数 表示基 因串中所选试题的考查点 用集合表示用户要求试卷中应包含考查点的集合 生成的试卷满足用户关于各考查点要求的程度可 以用 f1 的大小来评价 fl m di 1 1 l 其 中di 茎 曼 c2 可见 f1 的取值范围为 0 fl 1 fl的值 越小 生成的试卷越接近于用户关 于各考查点的 要求 4 遗传算子 遗传算法的交叉概率 Pc 和变异概率 Pm 是影 响遗传算法行为和性能 的关键所在 直接影响算 法的收敛性 Pc 和 Pm 越大 算法 产生新个体 的 能力就越强 个体之 间的适应度波动 比较大 产 生新的超平面的能力比较强 Pc 和 Pm 越小 算法 使个体 趋于收敛的能力越 强 个体 的平均适应度 比较平稳 有可能产生早熟现象 所以我们采用 自适应的思想 在算法 的运行过程 中对 Pc 和 Pm 进行调整 让 它们随着个体适应度值的增加而变 小 随着个体适应度值的减小而增加 由于种群中 每一个功能块对应着一个题型 所以 为了保证每 个题型的数 目不变 交叉点的选择不能破坏功能块 的完整性 假设交叉点位于第 i 个功能块内 则前 i 个功能块不变 从第 i 1 个功能块开始逐位交换 交叉如果在功能块内也发生的话 可能会出现同 一 模块中有重复试题的情况 普通的变异操作可 能会使用户指定范围外的题 目出现在染色体 中 也 会使各题型的题 目数难以保证 采用有条件的变异 算子 即每个个体的每一个基因座上的基因都按设 定的变异概率 Pm 在一定范 围内 与该基因题型 相同且考查点与本个体其他题的考查点不重复 变 异 通过变异算子可以达到局部搜索的 目的 5 最优保存策略 进行 了选择 交叉 变异操作 后 比较新一 代 的最好个体 与上一代的最好个体的适应度 如 下降 则 以上一代最好个体替换 新一代的最差个 体 此策略可以保证迄今为止的最优个体不会被 交叉 变异等遗传运算所破坏 它是遗传算法收 敛性的一个重要保证条件 3结束语 我院上机考试系统在实施过程 中存在 的问题 也是显而易见的 例如 试卷的生成和考查 的知 识点如何尽可能地接近 交叉概率和变异概率波 动度有限 导致某些个体产生早熟现象 未能满 足计划中的考查点的要求等 如何改变 由管理员 控制试卷 的难度 系数 而 由系统提高 自适 应性 最终到达根据学生在考试过程 出现的