当前位置:首页 >> 数学 >>

基于遗传算法的试题库组卷研究


基于遗传算法的试题库组卷研究

摘要:组卷问题是一个多重优化约束目标求解问题, 使用传统方法解决此种问题较困难,考试题库以及组卷算法 的设计决定了组卷的效率和质量。文中提出一种基于遗传算 法的组卷方法, 给出了初始种群方法, 分段编码及交叉算子、 变异算子,优化了搜索过程,实验证明求解组卷问题采用该 方法行之有效,有利于实现考试的规范化、科学化、教考分 离。

关键词:组卷 遗传算法 试题库 计算机辅助测验 中图分类号: TP39 文献标识码: A 文章编号: 1007-9416 (2014)12-0128-02 Abstract:Test paper construction is a multi-object optimization restrict problem, it is quite difficultly to solve using traditional mathematics method.The efficiency and the quality completely are decided to tries the question bank design as well as pulls out the topic algorithm the design.This paper puts forward an intelligent algorithm,which optimizes the search course and adopts the segment code.The experiment proves that the algorithm has practicability.It is a key way to separate the examination from teaching and make the exam more standard.

Key Words: test paper construction, Genetic algorithm, item bank, computer assisted testing 计算机辅助测验[1] (computer assisted testing, 简称 CAT) 是现代管理教学中的重要组成部分之一,它综合利用信息和 网络技术协助对考生的研习效果进行测验和学习能力评估, 并对测验的结果做出相应解析。通常情况下,完善的 CAT 系统是以试题库为基础,包括试题库模块、试卷组合模块、 联机测试、考卷批阅、测试分析、成绩管理与总结等。组卷 是 CAT 非常重要的一部分, 考卷可以全面地反应考生的真实 水平,它的质量直接决定了本次考试的有效性。因此,组卷 模块是影响 CAT 系统性能指标的重要参考依据。 文中基于遗传算法的基本原理和思想方法,设计了一个 组卷算法,能够在较短的时间内生成较高质量的试卷。 1 遗传算法的基本原理 遗传算法[2,3]的本质可以理解为一种求解问题的高效 并行全局搜索方法,它模仿整个群体的学习过程,每个个体 都表示既定问题中搜索空间的一个待解点。 首先,需要对问题数据进行抽象,实现从问题到位串的 编码映射,初始种群也会从解中随机产生出来。将初始化群 体置于遗传算法的执行过程中,依据适者生存的原则,由个 体适应度函数值的大小决定出适应环境的个体进行复制,再 通过随机选择、交叉和变异等遗传操作过程产生出更适应的

下一代种群,使群体逐代地进化到搜索空间中越来越适应环 境的区域,直到解趋于收敛,得到最优解为止。 2 组卷问题的基本原则 组卷过程中应遵循一些准则,以使产生的试卷能够满足 高可信度的测验要求: (1)按设定指标适当配比题目分数以保证组成试卷的 效度。 (2)试卷内试题知识点涵盖面较全,数目适当,为确 保试卷的可信度,应尽量避免临近知识点试题多次抽取在同 一份试卷中。 (3)适当设定试卷的难度,同时使试卷具有较好的区 分度,适当地调整试卷的难易程度。 (4)设定卷面的满分值和考试用时,一般的,卷面满 分为 100 分,考试用时 2 小时。 (5)适当降低考题抽中率。 3 数学描述 根据文中问题的基本原则和特点,通过分析试卷指标, 采用矩阵理论方法,建立问题空间的数学模型。如果各考卷 包含 m 道考题,且各题包含 5 个属性,如表 1 所示,可以映 射为建构一个 m×5 阶的目标矩阵 X,如下所示。其中,m 表示每份试卷题目数,行代表某一道考题,列表示考题的某 种属性。

4 组卷算法 4.1 编码方案 文中应用分段自然数编码方法,在此方法中,首先将编 码按题型分为三组,每组编码代表一个题型,每个题型的编 码方法同样应用自然数编码,也就是在试题库中各题型的题 目单独建立试题表,题目均使用自然数编号。按照组卷的需 求,在试题库中每个题型都要筛选题目(编号)组成染色体, 染色体采用变长编码策略,一个考题就代表染色体中的某一 位基因,考卷所含考题的数目就是染色体包含基因的数目, 不同题型间的编码都是相对独立的。 试卷包含选择、判断、简答等 3 种题型,每个题型的数 目分别为 m1、m2、m3,总共 100 道考题,如下所示。 4.2 初始种群 针对组卷问题,初始种群是指从试题库中按照设定的参 数随机抽取的考题组成的考卷。设定的初始种群的大小对组 卷算法的收敛速度和性能有很大影响,故初始种群的设置一 定要合理。文中使用初始试卷的套数作为初始种群,且参与 算法的试卷数目设置要合理,因数目过多将减缓算法的收敛 速度,过少则对生成最优试卷造成消极影响。设初始群体大 小为 100,从题库中分别随机抽取考题,构成 100 套初始试 卷,并计算它们的适应度值。 4.3 适应度函数

本文适应度函数设计如下: , 。

其中,

U(0≤U≤1)代表每个约束条件分属权重,|sMi|代表考 卷中难度为 i 的考题分值总和同第 i 种设定难度的分值 Mi 的偏差值的绝对值;|sNj|表示考卷中第 j 个知识点的考题的 分值总和同第 j 种设定知识点的数值 Ni 的偏差的绝对值; |sQh|表示考卷中第 h 种考题要求度的分数总和与第 h 种设定 要求度的数值 Qh 的偏差的绝对值。 4.4 选择算子 选择操作的作用是确定下一步要进行交叉和变异操作 的个体,通常情况下,由适应度函数值的高低来决定要使用 哪些优良个体。文中使用轮盘赌选择方法[4],算子描述: (1)分别计算当前考卷群体中各个考卷的适应度函数 值,分别得到累计值 Ki,以及最末一个累计值 Kn; (2)在区间[0,Kn]产生一个随机数 X; (3)分别将 Ki 与 X 做对比,当产生第一个 Ki≥X 的考 卷 i 时,即作为复制对象; (4)重复操作上述两步,直到满足所需个体数目为止。 4.5 交叉算子 文中应用分段单点交叉策略:不同题型在各自的编码段 内随机设定交叉点,实现交叉时,对其附近的某些基因进行 交换。依据基本遗传算法的应用经验,交叉概率 Qc 常在

0.5-0.8 间选取,按此 Qc 值,在群体中抽出 M(M=Qc×群 体规模 N)个适应度值较高的个体组成一个群体。随机选出 试卷 S1 和 P1 配对,并在各段中均随机生成一个交叉点,各 段逐一交换对应基因位上的基因,产生一对新的个体 S2 和 P2。新考卷个体 S2 和 P2 在段内可能出现相同考题,但并不 调整每个题型数目,此时需将重复的试题编号替换成此段中 未出现过的编号。操作方法是:产生一个范围为 1-K 的随机 数 i,判断其是否与考卷中同类型题号相同,如果相同则继 续随机抽取, 不相同则替换掉重复出现的题号。 如图 1 所示。 4.6 变异算子 针对编码特点,文中将变异算子 Hm 的操作转换为对新 试题的搜索和替换,以确保变异后的编号未超出指定范围。 具体的变异操作如下: (l)设 nMax 作为考卷考题数目,变异操作前将当前查 找新考题的次数 N=0。 (2)在区间[0,1]内随机生成实数 J,若 J 不小于 Hm, 该位基因不变;否则,产生一个随机数用来标记变异基因的 位置,由此位置判断归属题型。开始在题库中搜索新试题, 如搜索成功, 则将新题号替换掉该基因的值, 如失败则继续。 (3)搜索次数 N 增 1,如 N>nMax,则停止搜索,该基 因位保持不变。 (4)判断新搜索试题所在章节是否在本次考试范围内,

如不是,重复第三步;判断新题号与已有题号是否一致,如 是,重复第三步。 (5)将原染色体基因替换为新试题编号。 变异操作如图 2 所示。 如上所示,随机生成一个实数 J,因大于 Hm,随机数指 出变异的基因位在箭头所指处,此位置位于判断题型内,在 判断题范围内随机生成一个整数 88 当做新考题编号,在父 个体判断题段编码串中没有 88,将原基因位上的编号 35 用 88 代替,变异操作完成。 5 结果分析 为证实文中方法的有效性和可操作性, 在.NET 环境下采 用 C#语言实现了该程序,完成组卷试验。本次实验有选择、 判断、简答等题型,共 1000 道试题,各题 2 分,分属 7 章。 题库中难度分布如下,容易试题 100 道,难度系数 0.85-1.0, 较易试题 240 道,难度系数 0.76-0.85,中等试题 330 道,难 度系数 0.66-0.75,较难试题 250 道,难度系数 0.56-0.65,难 试题 110 道,难度系数 0.0-0.55。程序运行前需设置参数包 括群体规模、变异概率、难度系数、最大迭代次数、交叉概 率。试卷满分为 100,期望平均得分为 85。 实验证实,当设置的参数适当,群体规模 M 取 100,变 异概率 Hm 在 0.01-0.02 之间,交叉概率 Pc 在 0.5-0.6 之间, 平均迭代次数 70 次,此时组卷效果较好。

6 结语 本文采用分段编码方法在组卷问题中实现了遗传算法, 能够更好的反映实际组卷情况,相应的采用段交叉算子和段 内变异算子,恰当的适应度函数比较好的解决了组卷问题, 不仅提高了搜索效率,也可以使种群较快地收敛于全局最优 解。应用分段编码方式不需在进化过程中控制题型和题目数 量,问题求解难度得到了显著降低。实践说明,采用遗传算 法解决组卷问题可以得到良好的组卷效果。 参考文献 [1]马宗梅.遗传算法在考试系统组卷中的应用与研究[D]. 郑州:郑州大学,2009. [2]孙凤喜.基于遗传算法的智能组卷系统的设计与实现 [D].石家庄:河北科技大学,2013. [3]李会民, 张仁津, 马桂英.基于遗传算法的交规考试自 动组卷方法研究[J].计算机工程与设计,2009:4333-4335. [4]韩蕾.基于遗传算法的自动组卷系统的研究与实现[D]. 青岛:中国海洋大学,2010.


相关文章:
基于遗传算法的试题库组卷研究.doc
基于遗传算法的试题库组卷研究 - 基于遗传算法的试题库组卷研究 摘要:组卷问题是
基于遗传算法的试题库自动组卷问题的研究.pdf
基于遗传算法的试题库自动组卷问题的研究 - 第 18 卷第 3 期 2004 年
遗传算法实现试题库智能组卷方法研究.doc
遗传算法实现试题库智能组卷方法研究 - 遗传算法实现试题库智能组卷方法研究 【摘要】智能组卷方法是当今各大高校及相关单位试题库系统中的核心内 容。 本文提出了一...
基于遗传算法的试题库自动组卷问题的研究_图文.pdf
基于遗传算法的试题库自动组卷问题的研究 - 维普资讯 http://www.cq
基于遗传算法的智能组卷策略的研究综述.doc
回溯试探法是一种有条件的深 度优化法,对于状态类型和题量较小的题库系统而言,组卷成功率高,但占用内 基于遗传算法的智能组卷策略的研究综述 3 存。 这两类...
基于遗传算法的试题库智能组卷系统研究.pdf
(060-220 100220)28-40 基于 遗传 算法 的试 题库 智能 组卷 系统研 究朱玉祥 苗春生,孙承佼 , (.京 信息 工程大学大气科学系,苏南京 1南江2042华南...
基于遗传算法的组卷研究与设计.doc
基于遗传算法的组卷研究与设计 - 龙源期刊网 http://www.qikan.com.cn 基于遗传算法的组卷研究与设计 作者:徐涛 来源:《软件导刊》2014 年第 12 期 摘要:随....
基于遗传算法的自动组卷的研究.pdf
基于遗传算法的自动组卷的研究_IT/计算机_专业资料。遗传算法在自动组卷中的研究...并且这些属性指标都 进行编码表示成二进制形式, 而每一列是题库中某 一指标的...
基于遗传算法的组卷研究与设计_论文.pdf
基于遗传算法的组卷研究与设计 - 第1 3卷第1 2期 2Ol4年12月 软件导
基于遗传算法的组卷方法研究.doc
基于遗传算法的组卷方法研究 - 基于遗传算法的组卷方法研究 摘要 本文在分析了自动组卷算法研究的传统方法的基础上,根 据成卷技术指标要求,提出成卷前先进行组卷...
基于遗传算法的组卷系统的研究_论文.pdf
基于遗传算法的组卷系统的研究 - 本文对网络题卷库的优势和基本特点进行了介绍,对网络考试所涉及的题库设计、组卷算法等技术进行了讨论和研究,同时在研究的基础上...
基于遗传算法的智能组卷问题的研究_论文.pdf
基于遗传算法的智能组卷问题的研究 - 计算机考试系统主要是根据相同的考试要求在短时间内生成具有高信度但差别比较大的试卷。本文采用最优保存策略的遗传算法能有效地...
基于遗传算法的智能组卷的研究_论文.pdf
基于遗传算法的智能组卷的研究 - 智能组卷是计算机辅助教学(CAI)中一个重要的研究课题,本文针对试卷生成的目标要求,建立了智能组卷的数学模型,并给出了用改进的遗传...
基于遗传算法智能组卷系统的研究与实现_论文.pdf
基于遗传算法智能组卷系统的研究与实现 - 试题库智能组卷问题是一个在一定约束条件下的多目标参数优化问题,利用传统的数学方法求解较为困难,自动组卷的效率和质量取决...
基于改进遗传算法的智能组卷系统研究_论文.pdf
基于改进遗传算法的智能组卷系统研究 - 试题组卷是考试系统的重要组成部分。通过在编码策略、适应度函数、遗传算子、控制参数等方面的研究提出一种适应于试题智能组卷...
基于遗传算法的自动组卷研究_论文.pdf
基于遗传算法的自动组卷研究 - 随着基于网络的各种考试的引入和广泛应用。计算机组卷的算法得到了广泛的研究。计算机自动组卷是一个带约束的多目标优化问题,可以通过...
基于遗传算法的自适应题库系统的研究_论文.pdf
基于遗传算法的自适应题库系统的研究 - 在比较传统组卷算法优缺点的基础上,着重对遗传算法进行了可行性论述,通过将实数编码的遗传算法应用于自动组卷,全面增强了自...
基于改进遗传算法的智能组卷系统的研究.doc
基于改进遗传算法的智能组卷系统的研究 - 龙源期刊网 http://www.qikan.com.cn 基于改进遗传算法的智能组卷系统的研究 作者:石慧升 韩志丽 刘沛叶 来源:《商情...
基于遗传算法的自动组卷系统研究与实现.pdf
电脑编程技巧与维护 基于遗传算法的自动组卷系统研究与实现夏爱月( 河北廊坊武警学院计算机教研室,廊坊 065000 )摘要: 自动组卷系统是在已有的题库基础上,按照考核...
基于遗传算法的高校试题组卷系统的研究_论文.pdf
基于遗传算法的高校试题组卷系统的研究 - 阐述了高校组卷系统的原理,重点研究了作
更多相关标签: