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

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


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

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

关键词:组卷 遗传算法 试题库 计算机辅助测验 中图分类号: 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.


相关文章:
基于遗传算法的自动组卷问题研究
基于遗传算法的自动组卷问题研究 - 龙源期刊网 http://www.qikan.com.cn 基于遗传算法的自动组卷问题研究 作者:李阿红 张建锋 来源:《电脑知识与技术》2016 年...
基于JSP的考试题库管理系统的设计与实现
基于遗传算法的自动组卷系统是利用遗传算法对自动组卷功能进行研究,以提高试卷的质量及系 统运行效率。 本系统可以在试题库中按照试题类型、试题数量、曝光度等约束...
毕业论文_基于遗传算法的在线考试系统论文(终稿)
基于遗传算法的在线考试系统论文 在考试系统中,自动组卷是关键的部分.随着人工智能的快速发展,这个问题已经 被越来越多的科学家所关注.在题库技术和组卷策略知识的...
遗传算法在自动组卷系统中的应用
假设试题库中有 k 道题 ,随着 k 的增大 ,计算的复杂度无论在空间上还是在...[2,3], 且理论研究较为成熟,所以本文使用遗传算法作为组卷算法,较好 地解决了...
改进型遗传算法智能组卷系统的研究(小论文11.5)
智能组卷算法研究(完整) 3页 免费 基于遗传算法的试题库智能... 2页 免费...本文研究了测试理论和组卷过程的数学模型,分析了利用遗传算法来实现智能组卷的目标...
考试系统中的组卷算法
然后依据组卷算法试题库中抽取一 定数量并且满足...(1)试卷总分为Z: %%一 z=Σ研, (5.2) (2)...设计 在考试系统中, 采用了基于遗传算法的组卷算法...
遗传算法在智能组卷中的实现
龙源期刊网 http://www.qikan.com.cn 遗传算法在智能组卷中的实现 作者:肖衡...而要实现智能组卷主要在于组卷算法 的研究。在组卷算法的设计中,试题库系统的...
智能组卷系统的研究
本文研究智能组卷系统,针对传统遗传算法极易未成熟收敛和后期搜索效率低的 情况,...针对计算 机基础课题库,按照上述思想用就 java 语言编制了程序,进行组卷试验。...
自动组卷技术论文
一套试卷中各种题型的试题量很大,而且当试题 库的试题数量很大时,二进制编码...3 基于遗传算法的自动组卷 +申请认证 文档贡献者 中国学术期刊网 中国规模最...
一种在线评测系统组卷算法
本文通过分析组卷问题约束条件,提出了题库 模型,在生成试题库基础上,采用合理编码和预设成卷目标,使用遗传算法实现了抽题成卷, 实际测试了各种预设值对算法的影响...
更多相关标签: