系统组卷算法

系统组卷算法（精选8篇）

系统组卷算法 篇1

0 引言

随着计算机技术的发展及计算机的日益普及,无纸化考试系统的自动组卷、自动评阅、计分、成绩存档与考试统计分析等功能将有效地避免资源的浪费,如何合理地利用试题库中的试题组成一份科学的试卷,是网上考试系统设计中的重要环节,也是一大难题,本文介绍了一种改良后的遗传算法来解决这一问题。

1 组卷算法分析

组卷算法是针对考试系统中的组卷问题所提出的一种解决问题的算法,该算法会根据考试系统对组卷问题所提出的要求,采用遗传算法思想,合理和快速地生成相应的试卷,因此,研究组卷算法的关键在于研究相关的试题参数和组卷目标,再结合遗传算法来解决问题。

1.1 试题参数说明

在组卷问题中,每一道试题都有若干个属性来描述其基本特征,被选择的试题的特征值将直接参与试题适应度的计算。下面分别介绍几个重要的参数[1,2,3]。

(1)难度:即答题的难易程度,难度越大,得分越少;难度越小,得分越多,定义为公式(1)。

式(1)中,Dqp为难度系数;Sqa为该试题所得的平均分;Sqf为该试题分值。

试卷的难度可以利用试题的难度求得,试卷难度计算公式如下:

式(2)中,Ded是试卷难度;Dqdi是第i道试题的难度系数;Sqfi是第i道试题的分值;Sef是试卷的总分;n表示该试卷有n道试题。

(2)鉴别度:是最大限度区分被试者的特性和能力的指标,区分度好的试卷,不仅对学生的特性、能力和学业水平有较高的鉴别能力,而且可以说明试题难易搭配合理,能区分学生的等级。为了估计区分度,将考生分成高分组和低分组两个组,分别统计高分组和低分组的得分率,把区分度定义为:

式(3)中,Dqp是试题的鉴别度;Rhs是高分组的得分率;Rls为低分组的得分率。

试卷的鉴别定义如下:

式(4)中,De{为试卷的鉴别度;Depi为第i道题的鉴别度;Sqfi为第i道题的分值;Sef是试卷的总分;n表示试卷有n道试题;

(3)被组卷的次数:在组卷的时候,若某一试题被抽取参与组卷,则该参数加1,该参数是控制试卷之间差异性的重要标准。也即是说,在试题个体的选取中,将则重于被组卷次数少的试题。

1.2 组卷问题分析

组卷问题是属于多目标组合优化问题,主要考虑以下几个方面[4,5]:

(1)考试的难度和平均分须尽量满足试卷参数所设定的要求。

(2)考试成绩的分布图大致成正态分布。

(3)试卷中各章节所占的比例须尽量满足试卷参数所设定的要求。

以上三个方面是组卷时需要重点考虑的对象,也即是组卷生成后的试卷必须符合以上三个条件,下文的适应度函数章节将会解决这个问题。

2 组卷算法设计

本组卷算法基本上采用了遗传算法的运算步骤,不同之处在于补充了算法的预处理过程,该过程为算法的优化提供了基础,组卷算法流程图如图一所示。

2.1 算法预处理

预处理主要是对试题的搜索空间进行筛选和排序,需要考虑的因素有:排除一部分被指定课程和章节以外的试题、排除一部分被指定题型以外的试题、排除一部分鉴别度太低的试题和排除一部分被组卷次数太高的试题。试题的搜索空间大小可以定义为:

式(5)中,SI是搜索空间的大小;Ne是试卷的试题总数。Ndb是试题库中的试题总数;k为系数,用来控制搜索空间和试卷题目数之间的关系。

2.2 编码方法

二进制编码方法是遗传真法中最常用的一种编码方法,试题库中的每一道试题都会对应着二进制串中的每一位,而二进制串的长度即是试题库所有试题的总数目,若第i位二进制位为0的时候,即说明它所对应的试题库中第i道试题没被选中,若第位二进制位为1的时候,即说明它所对应的试题库中第i道试题被选中,因此,二进制串中1的总数即代表着试卷的试题总数。这种编码方法结构清晰,容易操作,变异操作也不会出现非法解。

2.3 初始化群体

初始群体的设计主要讨论两个问题,一个是如何产生初始化群体,另一个是初始群体的规模。为了体现所生成试卷的差异性,需要考虑采用试题被组卷次数这个参数,也就是说,试题被抽取组卷的命中率与这个参数有关,试题的命中率为:

式(6)中,Rsci是第i道题根据试题被组卷次数计算出来的试题被抽取组卷的命中率;Cqsmax是试题搜索空间中最高的被组卷次数;Cqsi是第i道题的被组卷次数。

初始群体可以按试题的命中率随机抽取试题组成第一代试卷,命中率高的试题,被抽取的概率就大。接着,还要考虑初始群体的规模问题,也就是说初始群体由多少个个体组成才比较合适?考虑到具体情况,可以把群体的默认规模Sc赋值为10。

2.4 适应度函数

根据组卷问题分析,可以将组卷的三个条件转换成目标函数,也即是适应度函数。

(1)解决难度和平均分约束条件问题,其实两者是同一个问题,只要考虑试卷的难度一个条件就可以了。试卷的难度计算公式在前面公式给出,因此试卷的难度适应度函数可以表示为:

式(7)中,fda是试卷难度的适应度;Ded是试卷的难度;Dc是组卷时手工预计指定的难度;δda是试卷难度适应度的控制参数,其默认值可以设置为0.1。

(2)解决成绩分布图成正态分布约束条件问题,最关键的是要防止成绩分布图出现驼峰的形状,为了防止出现这种现状,判断所抽取的试题中,某一难度的试题的分值的和占试卷总分的比例大于某一指定比例就可以近似地达到要求。因此,该条件的适应度函数可以表示为:

式(8)中,fsa是成绩正态分布的适应度;Sqfη表示难度为η的试题的分值;Sef表示试卷的总分;n是试卷的试题数;δsa是控制参数,用来控制被指定的某一难度的试题的总分占试卷总分的比例的大小δsa的默认值可以赋值为50%。

(3)解决各章节所占的比例问题,首先得求出试卷中各章节试题分值占试卷总分的比例,公式如下:

式(9)中,Pei是第i章试题的总分占试卷总分的比例;Sqfi是第i章试题的分值;Sef是试卷总分;

根据上述计算公式,便可以求得该目标条件的适应度函数,该条件的适应度函数可以表示为:

式(10)中,fca是章节比例的适应度;Pei是第i章试题的总分占试卷总分的比例;Pci是第i章手工预设置的比例;δca是控制参数,用来控制章节比例设置差异程度,该参数的默认值赋值为20%。

通过上述三个目标函数适应度的计算公式,便可以求得试卷群体的适应度函数了,计算方式采用将以上三个适应度加权相加的方法,计算公式如下:

式(11)中,λda是fda的权重系数;λsa是fsa的权重系数;λca是fca的权重系数。这三个权重系数决定了这三个适应度的重要程度,根据实际情况,难度适应度是最重要的,因此,它大小会很大程度上影响到试卷整体的适应度,默认取值为0.5,而其它两个适应度相对次要,它们的默认取值都为0.25。试卷适应度的值越小,说明试卷的适应度越强,也就是说当试卷的适应度的计算结果大于等于0,小于等于0.1的时候,试卷可以达到比较理想的状态,这时可以继续繁殖优化,也可以结束繁殖,输出试卷。

2.5 选择算子

根据组卷问题的实际情况,采用排序选择组合和最优保存策略相结合的思想进行选择算子的设计,具体的操作过程如下:

(1)对群体中的每份试卷的适应度按由好到差进行排序。

(2)淘汰适应度最差的若干份试卷个体。

(3)计算迄今为止最好适应度的试卷,复制该试卷,即生成新的试卷个体。

(4)从试题的搜索空间中,随机产生生成新的试卷个体。

2.6 交叉算子

采用多点交叉算子的设计思想,详细的交叉算子的操作步骤如下:

(1)确定试卷个体的配对方式,由适应度最高的试卷与适应度第2高的试卷进行配对,适应度第3高的试卷与适应度第4高的试卷进行配对,以此类推,在选择算子中,新产生的试卷也相互进行配对。

(2)设置各试卷的交叉点,以题型为划分标准,分别计算试卷中各题型段中试题的适应度。

(3)在配对的两份试卷中,把各对应的题型段中适应度高的抽取出来重组一份试卷,各对应的题型段中适应度低的抽取出来重组另一份试卷。

2.7 变异算子

采用基本位变异算子,操作步骤如下:

(1)按相关的统计建议,变异算子的变异概率一般不会取值大于0.1,考虑到试卷的试题数量有限,变异算子的变异概率默认取值为0.05。

(2)对于组卷问题来说,要保证题目数的固定不变,变异的位数必定是偶数,因此要保证二进制编码串中1的个数不变,假如二进制编码串中有一位0变成1,肯定会有另一位从1变成0,而且它们都属于同一个题型段里面的,这样才能保证每一种题型的题目数也是一定的。

3 组卷算法实验

采用本算法和随机抽取算法分别组5份试卷,并将实验结果作比较,如表一所示。

实验结果表明,随机抽取算法的组卷时间比较短,可是在试卷的难度、成绩分布、试卷差异度和章节比例几个方面分析,远远比不上遗传算法。特别是试卷的难度和章节比例这两个重要的条件更是无法估算,严格上说,比较正式的考试一般都不会采取该方法来组卷,因为它不科学,也不合理。

4 结束语

现有的标准化试题库和网上考试系统的研究才刚起步,没有统一的标准,各地和各学校的具体情况不大相同,一般考试系统的设计都是结合各自的情况而研究的,因而参差不齐。同样,组卷算法更是多种多样,就算采用同一种理论来解决组卷问题,它们的详细方式和步骤也不大相同,实现的效果也是不一样的。本文充分考虑了这些差异性,并力求研究和设计出符合一般情况下的网上考试系统和组卷算法,同时对算法优化做了充分的考虑,取得了比较理想的结果。

参考文献

[1]杨青.基于遗传算法的试题库自动组卷问题的研究[J].济南大学学报(自然科学版),2004,3(18).

[2]孙勇,柏云.基于遗传算法的试题组卷策略[J].淄博学院学报(自然科学版),2002,(3):27-28.

[3]全惠云,范国闯等.基于遗传算法的试题库智能组卷系统研究[J].武汉大学学报(自然科学版),1999,(5):758-760.

[4]于晓强,刘柏等,谢益武.基于改进遗传算法的组卷策略与实现[J].微电子学与计算机,2006,23(12).

[5]焦翠珍,戴文华.基于遗传算法的智能组卷方案研究[J].微电子学与计算机,2006,23(6).

系统组卷算法 篇2

关键词:试题库;组卷;遗传算法;伪并行;精英个体

中图分类号:TP18文献标识码:A文章编号:1000-8136(2009)17-0091-03

在国内,近年来题库的建设受到高度重视。目前,题库系统有3类:基于单机、基于局域网和基于WEB。基于单机的系统已经逐渐被淘汰,其缺点是题库的建立和维护非常困难;基于局域网的系统通常用于比较严格的考试,基本上都是由某一重要的大机关封闭运行,缺乏开放性,无法真正在教学过程中发挥其应有的作用。基于WEB的系统具有集中管理、共享使用、简单易用、开放性强的特点,可提供考试、自测、联机评卷等多项功能,还能提供强大的统计与分析功能,揭示全方位的教学过程信息。相对来说,现在的开发主流为基于WEB的系统。而作为该系统的组卷策略因其在整个系统中的核心地位成为研究的热点。

遗传算法是一种模拟自然选择和遗传机制的全局概率寻优算法,它的寻优过程是一个迭代过程,通过基因遗传机制将每一代的基本特征遗传到下一代。该方法能解决随机算法的盲目随机性,能从群体中选择更满足条件的个体,具有很强的智能性。同时,由于遗传算法具有内在的并行性,不会出现像回溯试探法一样计算量大的问题。许多研究人员对基于遗传算法的试题生成方法作了深入的研究,取得了比较好的效果。本文对标准的遗传算法进行了改进,提高了试卷生成的效率。

1 组卷问题分析

1.1 试题命题的基本原则

1.1.1 目的性原则

考试的功能是多方面的,目的不同,试卷编制的结构和试题的难度就不同。前面提到,平常的检测主要是诊断教学内容的掌握情况,期中、期末考试则主要是考查考生的学习水平。

1.1.2 科学性原则

编写的试题不但要求其本身没有科学性和知识性错误,而且试题表述要规范,尽可能采用学科术语。

1.1.3 简洁性原则

试题的语言表达要简洁、精练,每道试题应该清楚地提出一个或几个独立而明确的问题,学生阅读题干后能够明确他们要解答的内容,不存在理解题意的障碍。

1.1.4 层次性原则

层次性原则就是根据学生认知结构的差异性、教材内容的难易度、教学大纲要求,编制的试卷必须具有一定的梯度。

1.1.5 创新性原则

创新性主要体现在试题的新颖性上,而试题的新颖性则主要反映在取材的新颖性、创设情境的新颖性、设问的创新性以及考查角度的独到性等方面。严格来讲,在一份试卷中,至少应有20%~

30%的试题是新命题才算较好地体现了创新性原则。

1.2 试题分析

在智能教学系统的研究中,一个非常重要的课题是怎样在已生成的题库中自动生成满足教学和教师要求的试卷。通常,全部试题按内容分为若干篇章、题类和多个细目,每一道试题又包含多个属性,但过多的约束条件会增加实际自动组卷的难度、降低效率。由于多约束条件的重要性是不一样的,且它们之间存在内在的联系,有必要选择一些核心属性作为组卷的约束条件(总时间、试卷分数、试卷难度系数、题型比例、能力层次、知识点、区分度、已被选择次数、最近被选时间等),具体属性定义如下:

(1)题型:用正整数1～6分别代表选择题、填空题、判断题、简答题、作图题和计算题。

(2)难度系数:设P为试卷的难度系数,x为试卷平均分,w为试卷满分,则试卷的难度为: p=1-(1)

试题的难易程度分五级,难:0.8～1.0,较难:0.6～0.8,中等:0.4～0.6,较易:0.2～0.4,易:0.0～0.2。

(3)区分度:取值1～3,分别表示优秀、良、差3种状态。

(4)知识点:某道题属于某门课程的哪个知识点。用1～20代表学科的20个知识点。

(5)分值:某题的分数。

(6)答题时间,估计该题所需的时间。

(7)已被选择次数:某题被选重的次数。

(8)最近被选时间:某题最近被选的时间。

1.3 组卷模型的建立

组卷主要是根据给定的约束条件(总时间、试卷分数、试卷难度系数、题型比例、能力层次、知识点、区分度等)从大量的试题库中抽取出最优的试题组合,由此可见,组卷问题是一个具有多重约束的组合优化问题。因此,组一份m道试题的试卷,并且每道试题有n项属性,就相当于构建了一个m×n的目标矩阵。(本论文n=6)。

目标矩阵应满足以下的约束条件

(由用户给定,即试卷分数的约束);

(由用户给定,即试卷难度约束);

(由用户给定,即试卷区分度的约束);

我们设定整套试卷综合指标f来反映与用户要求的误差,实际试题生成工作中,上述各项指标的重要程度是不相同的,因此,整卷指标f就是各项指标与用户要求之间误差的加权和,为了避免各个误差的相互抵消,各指标与用户要求的误差都取绝对值,可以用如下方式表示:f=wi(e1+e3+e4)+w2e2+w3e5。(9)

在公式中wi表示第i个指标的权值,ei表示第i种约束条件与目标值的偏差(取绝对值)。

1.4 遗传算法求解

1.4.1 编码

采用分组实数编码策略,试卷初始种群也不是随机产生,而是根据题型比例、总分的要求随机产生,使得初始种群已经满足了题型和总分的要求。

1.4.2 选择操作

选择操作的目的是为了从当前群体中选择优良的个体,使它们有机会作为父代为下一代繁殖子孙。本文采用赌轮选择。

1.4.3 交叉操作

由于分段实数编码,结合单点交叉和一致交叉,我们采用段内/段间两种交叉方式实现种群中个体的交叉操作,具体操作方法如下:

(1)仿照单点交叉操作的一、二步,对种群中个体进行配对,并对每一对配对个体随机设置一个交叉点。

(2)根据交叉点所在的位置进行段间/段内交叉操作。

1.4.4 变异操作

本文将采用自适应变焦变异,以加强变异算子的局部搜索能力。

1.4.5 精英保留策略

在遗传算法搜索的过程中,对其所发现的最佳个体作适时“记录”,则全局最优个体总能被找到。在遗传算法中耦合这种最佳个体记录的策略,被称之为精英保留策略。

1.4.6 算法的基本流程

步骤1分段实数编码。

步骤2复制:为了避免最优基因丢失,提高全局收敛性和计算效率,将适应值最优的m条染色体复制到精英个体序列库中。

步骤3选择、分组:随机将种群按比例分组,并行进行改进的遗传算法和标准遗传算法的遗传操作(选择、交叉、变异);各组的最优值通过迁移算子传给下一代。

步骤4交叉。

步骤5变异。子代中,两种遗传算法伪并行运算,相互之间通过迁移算子进行信息交换,得出子代个体,选出同样数目的最优染色体与精英个体序列库进行比较,取50%高适应值的个体保留在库中,其余留给子代。

步骤6判断是否满足收敛准则,满足,输出搜索结果;否则,执行第二步。

改进的遗传算法的基本流程图见图1。

2 结论

我们通过模拟题库在MATLAB平台上对算法性能进行测试,以课程《电路基础》试卷为例。在测试中,题库中共设置4种题型,整个试题库根据题型分为4部分,每个题型对应的试题表中的试题数分别为100、100、50、50。各题的属性已经事先设定好。

取群体规模为50,对比标准遗传算法与改进的伪并行遗传算法在生成满足要求的组卷系统中的应用,见表1。

从实验结果可以看出,改进的伪并行遗传算法能更有效地解决试题库智能组卷问题,与其他方法相比,它能较早地找到满足条件的群体。同时,本文也为解决类似于该问题的多重约束目标的问题提供一种新的、有效的途径。

Research on an Intelligent Generating Papers based on the

Improved Pseudo-Parallel Genetic Algorithm

Guo Lixin,Xie Keming

Abstract:The traditional way of test paper composition has many flaws, for example the time test paper composition needed is long and the efficiency is low. This paper proposed a improved Pseudo-Parallel Genetic Algorithms, it needs short time in test papers composition and has a high success ratio, and has fine function and usability. Simultaneously it improved the test papers’ quality and the test becomes more scientific and objective, has a vital practical significance to implement the work smoothly.

在线考试系统中组卷算法研究 篇3

目前, 常用的自动组卷算法有:随机抽取算法、回溯试探算法、遗传算法。大多数考试系统组卷模块所采用的方法为随机抽取算法和回溯法。因为在九江学院历年考试分析中, 都要求给出学生的平均分, 并要求统计某个班级中高于平均分和低于平均分的人数, 基于此, 我们提出了一种新的组卷算法, 即“平均分算法”, 该算法的特点是:根据输入的平均分去抽卷, 得到的试卷可以使大部分学生的成绩在期望的平均分附近。这样就避免了老师主观上对试题难度的规定, 也提高了试卷的总体质量。

2. 目前常用的自动组卷算法

2.1 随机组卷算法

根据状态空间的控制指标, 由计算机随机的抽取一道试题放入试题库, 此过程不断重复, 直到组卷完毕, 或已无法从题库中抽取满足控制指标的试题为止。该方法结构简单, 对于单道题的抽取运行速度较快, 但是对于整个组卷过程来说组卷成功率低, 即使组卷成功, 花费时间也令人难以忍受。

2.2 回溯试探组卷算法

这是将随机选取法产生的每一状态类型纪录下来, 当搜索失败时释放上次纪录的状态类型, 然后再依据一定的规律 (正是这种规律破坏了选取试题的随机性) 变换一种新的状态类型进行试探, 通过不断的回溯试探直到试卷生成完毕或退回出发点为止。

回溯试探法在搜索过程中, 从上往下进行搜索, 若在某个节点上, 不能满足控制指标的要求, 则回溯, 此过程不断重复, 直至找到满足条件的解。这种方法是对随机选取法的改进, 保存了搜索的历史状态。

2.3 基于遗传算法的智能组卷算法

遗传算法是计算数学中用于解决最优化的搜索算法, 是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的, 这些现象包括遗传、突变、自然选择以及杂交等。

3. 本系统所用的组卷算法

一般情况下, 我们考虑一套试卷出的是否合理, 应该考虑下面几个因素:

(1) 知识点分布情况:知识点是否分布均匀, 是否重难点突出。

(2) 学生对每一章内容的掌握情况。

(3) 总的试卷的难度是否适中。

(4) 题量是否过大或者过小。

(5) 题型主要有哪几种等。

因此在本系统中, 我们给出了实际组卷过程中对试卷的约束条件:

(1) 试题惟一性:对某一份试卷而言, 试题是否具有惟一性, 不重复是很重要的。

(2) 试卷总分:试卷的总分是不是等于指定的分数, 一般为百分制。

(3) 题型分布:试卷的各类题型和题目数是否满足预先要求。

(4) 章节分布:试卷是否涵盖了各个章节的知识点。

(5) 难度分布:试卷总体难度是不是达到指定的难度系数。

(6) 试卷估计用时:试卷的估计用时与学生作答用时是否相差不大。

上述的这些约束条件在组卷过程中约束的程度是不相同的。如前三个约束条件是一般试卷必须满足的基本要求。而后三个条件就要按照用户的需求来设置哪个约束条件优先考虑, 在这里我们提出难度分布优先算法即“平均分算法”, 下面将详细介绍算法的基本原理和实现过程。

3.1 平均分算法基本原理

在试卷参数设置时, 我们需要给出试卷基本信息:总分、题目类型、和每一类题目的个数, 除此之外, 我们只需要给出一个期望值 (平均分的期望值) , 例如:70, 和各个章节题量分布参数, 那么系统将按照我们给出的期望值和章节题量分布参数组卷, 最后得到的试卷将使学生答卷的平均成绩在70分左右。

该算法的数学模型:

首先我们考虑难度系数, 给出公式 (5.1) :

现将上面公式中的参数进行说明:

A1i, A2i, A3i, A4i分别为四种题型中各道题目的难度系数, 在这里, 我们设置了4个难度系数分别为0.3, 0.5, 0.7, 0.9, 含义是:0.3表示有30%的同学可以做对这道题目, 这一般为比较难的题目, 0.5表示有50%的同学可以做对这道题目, 这类题目一般为中档难度的题目, 0.7表示有70%的同学可以做对这道题目, 这类题目一般为比简单的题目, 0.9表示有90%的同学可以做对这道题目, 这类题目一般为概念性题目, 属于送分题。

N1、N2、N3、N4分别为各类题目的个数。S1、S2、S3、S4分别为各类题目单个题目的分值。

经过计算后, 能得出M组满足条件的难度系数。

其次, 我们考虑章节分布, 可以在满足难度系数前提下的M种组卷方案中比较各章节分布情况, 取最接近章节分布参数期望值的那些组卷方案, 这样就可以完成整个组卷过程。

即:

其中, G11为单选题中第一章题目的个数, G12为多选题中第一章题目的个数, G13为判断题中第一章题目的个数, G14为填空题中第一章题目的个数, G21为单选题中第二章题目的个数, 依次下去, GN1为单选题中第N章题目的个数, GN2为多选题中第N章题目的个数, GN3为判断题中第N章题目的个数, GN4为填空题中第N章题目的个数。Z1、Z2…ZN为各章节分值的初始值。

这样, 可以得到若干种满足条件的方案, 随机从这些方案中选择一种去题库抽题, 就可以得到一份试卷。

需要说明的是M的值可以在系统中设定, M的值决定系统运行的速度, M的值越大, 系统运行速度越慢, 否则, 系统运行速度越快。

3.2 平均分算法实现过程

第一步:优先难度系数。即:实现每种难度系统的题目数的多个组合方案。

第二步:进一步优化。即:按期望值的特点, 从50种方案中优选出10种方案。

第三步:按章节优化得到最佳方案。即:根据章节的分布, 对第二步得到的10种方案 (二维数组X的前10行) 选出最佳的方案, 并保存在二维数组A中。

一维数组chapter[5]:保存规定的每章节分布题目数。例如:有5章节。

一维数组ch[5]:编写程序过程临时保存的每章节分布题目数。

二维数组A[100][3]:最佳方案数据的保存, 其二维表结构如表5.2所示:例如:抽100题。

5. 结语

本算法的特点是:考虑了两种试卷参数, 一是难度系数, 二是章节分布, 但在实现的过程中优先考虑难度系数, 本算法要建立在题库中每一种难度系数、每一章节都有足够的题目供随机抽取的基础之上, 所以对题库要求比较高, 题库里面的题目越全面 (即难度系数分布均匀、章节分布均匀) , 本算法的组卷质量就越高。本算法组卷科学, 组卷关键参数只有两个, 即期望的平均分和章节分布参数。操作简单, 面对用户的界面友好。对于算法运行的时间复杂度和空间复杂度还有待于提高。

摘要：本文主要介绍了目前比较常用的几种组卷算法, 并对各种算法的优缺点作了分析。根据九江学院公共课考试需求, 提出了一种平均分优先的算法, 该算法主要针对学生掌握知识的不同层次, 设置不同的难度系数, 最终得到教师所期望的平均分。

关键词：随机抽取算法,回溯试探算法,遗传算法,平均分算法

参考文献

[1]胡钰.基于网络教学平台的试题库组卷算法研究[D]: (硕士学位论文) .昆明:昆明理工大学电信工程学院, 2008.

[2]龚完全.基于最小回溯代价的智能组卷算法[D]: (硕士学位论文) .湖南:湖南大学软件学院, 2005.

在线考试系统自动组卷算法研究 篇4

智能组卷是网络考试系统的一个重要组成部分,而如何保证生成的试卷能最大程度地满足用户的不同要求,并具有随机性、科学性、合理性,是组卷的一个难点。

1 智能组卷

1.1 自动组卷问题分析

组卷就是按照给定的组卷策略,从题库中抽取适当的题目组成一份符合要求的试卷。为了考核学生对知识的掌握情况,每道试题主要设置如下属性 :知识点、题型、教学要求度、难度系数、区分度、估计答题时间、题分。因此,组一份n道试题的试卷就是从题库中抽取n道试题,每道试题的这些属性满足用户指定的试卷的总体要求,也就是 :各篇章所占的分数、试卷中各种题型的题数、反映不同教学层次要求的试题所占的分数比例、各种难度的试题所占的分数比例、各种区分度的试题 所占的分数比例、所有试题的估时总和、所有试题的分数总和这几个指标都应等于用户指定的要求,或者误差最小。

因此,组卷问题可被描述为一个约束的组合优化问题,该问题被定义为一个目标函数与一组约束条件的组合。

1.2 组卷问题中试卷的重要指标

1.2.1 试题的难度

难度通常就是指被试者完成题目或项目任务时所遇到的困难程度。试题库中试题的难度值在试卷中起着很重要的作用,它的确定不仅和老师的主观经验有关,还与不同能力的学生的答题情况有关。难度值的确定,可以用考生的得分率表示。

对于每一份试卷,在难度上应该满足以下要求 :

其中 :Σf(Wi) 表示Wi的题分

假设试题总分为100分

(2)根据均值公式, 试卷的平均难度值可以表示为 :

其中 :d(Wi) 为Wi的难度,K为试卷的总题数,p表示整个试卷的平均难度值。

试卷的平均难度将影响考试成绩的分布状态,当试卷的难度为0时,所有的考生都得零分 ; 当试卷的难度为1时,所有的考生都得满分。在这两种情况下,所有的分数都集中到0分或100分上,不能得到分数的合理分布。因此,试卷的难度过大或过小都会造成考试成绩偏离正态分布,而且使成绩的离散程度变小。故为了保证生成的试卷有合理的难度,试题库中各类试题的难度必须有一个合理的分布,一组试题中简单题与难题都应该占有一定的比例。

1.2.2 试题的区分度

试题的区分度是指试卷对被测试人群的区分能力。如果题目的区分度高,那么水平高的被试者在该题目上的得分就会高,而水平低的被试者得分就低,这样就可以把不同水平的被试者区分开来。

全卷区分度的数学表达式为 :

式中Qj—第j题的区分度 ;

Wj—第j题的满分值 ;

M—全卷的满分值,通常是100分。

由于试卷的区分度是指整个试卷对优劣学生的鉴别和区分的能力。所以一份区分能力较强的试卷,应是学习好的学生得高分,学习差的学生得低分。从而优劣学生的考分差距就大,即考分的标准差就大。

一般Q>0.3为好区分 度的试卷, 0.2≤Q≤0.3的试卷为良区分度试卷, Q<0.2的为差区分度试卷。

1.3 自动组卷问题数学模型的建立

根据以上对组卷约束条件的分析,可以构建组卷问题的数学模型。

组卷中决定一道试题,就要决定n项指标,这里我们考虑n维向量 ( 题型al, 知识点a2, 难度a3,区分度a4…),ai相当于第i项指标,决定一份试卷,就相当于决定一个m×n的矩阵。其中,m是试卷所含的题目数,n为试题控制指标的数目。

组卷问题求解的目标状态矩阵

S中的每一行由某一试题的控制指标组成,如知识点、题型、难度等,并且这些属性指标都进行编码表示成二进制形式, 而每一列是题库中的某一指标的全部取值。这些控制指标可大致分为以下七项 : 题型、难度、区分度、知识点、教学要求度、分数、答题时间等。

1.4 自动组卷的算法研究

自动组卷是用户根据试卷的要求,首先设置试卷的整体信息,包括考试时间、试卷整体难度,试卷整体区分度、试卷分数等。然后用户分别设置各种题型 (单选、多选、填空、判断、问答、计算)的数量、总分数,然后提交即可完成自动组卷的参数设置。系统按照用户设置的参数,利用遗传算法从试题库数据表中查找满足条件的试题,并将该试题的信息写入到试卷内容数据表中,完成试卷的自动组合。

1.4.1 染色体编码方法

题库中的待选试题数量为R,从R道试题中选出满足约束条件的试题组成试卷,可用一个长度为R的字符串表示,每一位的取值为0或1,0表示未选中某题, 1表示选中了某题,这样,每一道试题就对应一个0或1从而组成R位长字符串,成为染色体,这就形成了染色体的编码。

1.4.2 适应度函数的计算

(1)目标函数

在遗传算法中,以适应度函数的大小来区分群体中个体的优劣。一般情况下, 适应度函数是由目标函数变换而成的,其值越大,个体越好。

(2)适应度函数

本算法在实现时,将最小值问题转化为最大值问题,

1.4.3 产生初始种群

这里以随机方式产生初始种群,种群中每个个体的子染色体位串中“1”的数量固定为组卷条件中设置的对应题型的试题数量。

1.4.4 遗传算子设计

(1)选择算子

选择的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代产生后代个体。判断个体优良与否的标准就是各自的适应度。显然这一操作是借用了这样一种进化原则,即个体的适应度越高,其被选择的机会就越多。

(2)交叉算子的设计

在选中用于繁殖下一代的个体中,对两个不同个体相同位置的基因进行交换, 从而产生新的个体。首先要确定交叉概率Pc,交叉概率Pc控制着交换操作的频率。一般情况下,交叉概率Pc可取0.4-0.6。简单的交叉(即单点交叉)可分两部进行 :首先对配对库中的个体进行随机配对,并按预先设定的交叉概率Pc确定交叉对,然后在确定的交叉对个体中随机地选择交叉点,个体彼此交换交叉点前后的信息。

为了保证新的后代仍旧满足约束,改进单断点交叉算子,在交叉时采用相同题型段整体交叉。设计题型段交叉时采用在1到6整数内(一共有六种题型)按均匀分布产生一个随机整数作为交换的题型段。

(3)变异算子的设计

变异概率Pm是增大种群多样性的重要因素。Pm太小,不会产生新的基因块 ;Pm太大,会使遗传算法变成随机搜索。一般变异概率Pm取0.001 - 0.01。

为了保证染色体变异后产生的新个体仍能满足约束条件,在设计变异算子时,对变异算子采用在一个题型段内一次变异两位,即 :一位从1到0,另一位是从0变1,称之为段内两位变异。

1.4.5 遗传运算终止条件的设计

本算法中,终止条件是达到规定的迭代次数或者检查适应度值没有变化或变化很小时,令计算终止。

1.5 遗传算法的改进

本算法采用精英保留策略对遗传算法进行改进。精英保留策略也称为最佳个体保留策略,是指将当前解群体中的适应度最高的个体结构完整地复制到下一代种群中。其主要优点是进化过程中某一代的最优解可不被交叉和变异操作所破坏。 遗传算法终止时得到的最后结果一定是历代出现的最高适应度的个体。在算法实现时,让适应度最高的个体直接进入到下一代中,并将其设为种群中的第一个个体,其它不足种群数量的个体通过轮盘法进行选择,直到达到原始种群的数目。这种方法既可以保证能够使优良品种的个体得到更多的繁殖机会,又可以防止少数几个优良品种由于过度繁殖而控制整个种群,使得算法陷入到局部最小。

2 结论

在线考试系统的组卷算法研究 篇5

基于网络的在线考试系统的组卷问题是整个考试系统的核心问题,要求用户根据考试要求设置相应的组卷条件,然后使用合适的组卷算法,从原来做好的试题库中抽取满足条件并且按照最优组合的方式生成一份合格的考试试卷。如何组成试卷是在特定的多约束条件下的许多目标参数的如何组合优化问题。在这当中,组卷的算法问题是基于网络的在线考试系统能否成功设计并应用的核心问题。下面介绍目前最为流行的四种组卷算法。

1 回溯试探法

回溯试探法是在考试系统随机抽取试题的时候,首先验证一下系统所选择的试题是否满足给定的条件,然后再做决定看是否抽取此试题。如果没有满足给定条件的试题,并且考试试卷又未完全生成,考试系统回溯试探,舍掉刚才所做的一部分操作,然后重新再组卷。因为只是舍掉了一小部分的操作,大大降低了无用组卷的次数。回溯试探法组卷的成功率虽然高,但这是在消耗了大量的时间的基础上的。回溯试探法是下面将要介绍的随机抽题方法的一种改良算法。

回溯试探法在随机抽题法的基础上抽取试题,如果搜索失败,就会舍掉该状态掉,重新开始下一轮的试卷组成。回溯法的工作流程如图1所示。

考试系统如果采用回溯法来抽取试题,则会造成整个程序的结构设计非常复杂,抽取的试题随机效果不明显,生成的试卷时间较长,与许多考试系统生成试卷的要求不符,但是对一些小型的考试系统效果还是比较好的。

2 随机抽题法

目前大部分的考试系统都在使用随机抽题法作为考试系统的算法。此算法是采用随机函数对题库中的满足条件的题目逐一的抽取出来,组成试卷。使用这种组卷算法实现起来比较简单,而且使用也比较广泛。此算法要求建立两个数组,一个数组用来存储试卷的状态空间,一个数组用来存储试卷题目,是空数组。第一步把试卷的某些控制参数存放到试卷状态的数组里面,如题目的难易程度、题目类型、题目分值等等。第二步由考试系统根据数组试卷的控制参数,随机抽题。第三步把抽出来的题目放到空数组里面。如此反复的抽取题目,直到试卷最终生成为止。需要注意的是,考试系统每当抽取完一道题目,需要设置抽取标识,表明该题目已经被抽取,防止下次再被抽到。以下是抽取题目的公式。

抽取试题的公式:

公式中的N表示的是试卷中的试题数,M表示的是在试题库里面符合条件的题目数,而rand则表示的是随机函数。

其实在现实的情况里,组卷要对题目的抽取有着某些特定的要求。那么怎样才能合理地使用rand随机函数,能够在相同的题库中组成适合不同要求的试卷呢?显然rand函数并不能解决所有的问题,但却能够创造出一个良好的组卷环境,在这个环境里rand函数利用计算公式和算法来组成适应不同要求的试卷。而这种环境是由两个方法来实现的,一个是修改表的结构,另一个是建立一个界面,来适应不同要求的试卷抽取条件。

现在的大多数的网络考试系统是现场抽取题目的,采用刚才介绍的算法来随机抽取,题目是不同的,当然也有的网络考试系统中的题目是提前抽取的,所有考生的题目都一样,只是题目的顺序不同而已。对于这种方式,实现起来也比简单,先用随机抽题法抽取一套试题,然后再利用随机函数从抽出来的题目里再重新抽取,这样题目的顺序就不同了。

随机抽题法适合那些比较简单的网络考试系统,对试卷的组成要求不是很高的考试系统。此算法比较容易实现,而且组卷速度快,因为它没有最优化的思想在里面。但是此算法的缺点是,随着题目一步一步的被抽取出来,它很难再界定剩下哪些区域适合再次抽题,从而进入了死循环,试卷最终无法生成。此算法抽取的题目重复率比较高,成功率也低,智能性较差。

3 启发式搜索法

此种方法是在存放试题状态空间的数组里,首先对每个搜索位置进行测评,找到一个最好的最合适的位置,然后在此位置继续进行搜索,直到找到目标为止。使用此种算法能够省去一些无用的工作量,大大提高了组卷工作效率。在这种算法里,对每个位置的测评是重中之重,用不一样的方法测评会得到不一样的效果。那么测评是如何表示出来的呢?启发式搜索法的测评用的是测评函数。f(n)=g(n)+h(n),在这里f(n)是n的测评函数,而g(n)是在状态空间数组里从初始节点到n节点的实际路径,h(n)则是从n到目的节点的最佳的测评路径。在这个函数里面,h(n)主要体现了搜索的启发的信息,在这当中g(n)是已知的。

启发式搜索法相比起回溯试探法和随机抽题法,它的成功率要比后两者高,适合需要抽取各种复杂题目的网络考试系统。但是使用启发式搜索法设计开发程序比较的复杂,花费的时间长,所以生成试卷的效率不如后两者算法好。

4 遗传算法

遗传算法是在1975年美国密歇根州大学由John H.Ho Uand教授第一次提出来的算法。此算法是模拟自然界的生物进化过程的自由随机搜索的方法,它是一种新型的优化算法。遗传算法利用比较简单的编码表示各式的复杂结构,而且用编码来表示一些遗传操作,再利用优胜劣汰的自然选择指导搜索方向。此算法是一种群体式的操作方式,把所有个体作为操作对象。它的三个主要操作运算分别是遗传、交叉、变异。进行完操作运算后下一代种群就保留了上一代的优良个体基因,体现出符合自然界规律的“自然选择、适者生存”的生存原则。

首先进行选择操作,它的作用是大大提高了种群的平均适应值,但是这个操作只是选择,并没有产生出新的个体,所以在种群中最好的适应值并没有改进。第二步交叉是把在交配池当中的个体进行随机的配对,再把配对好的个体用特定的方式来相互交互一部分的基因,此操作产生出新的个体,因此它决定了整个算法的搜索能力的强弱。第三步变异是针对个体的,把个体中的某个或者某部分基因按照特定的较小概率,进行改变,从而产生了新的个体的辅助方法。第二步交叉和第三步变异互相配合操作,从而完成了整个遗传算法的全局搜索能力。

遗传算法的主要的操作步骤如下:

A. 开始生成初始的种群;

B. 计算出种群当中个体的适应度值是多少;C.

C对种群当中的个体使用遗传操作,比如说选择、交叉、变异;

D. 当符合条件时,叠代就停止,输出结果,得到解决问题的的最优解;如果不满足条件,则继续转向步骤C,如此反复。2

遗传算法流程图,如图2所示。

在整个遗传算法当中,“生成+检测”的搜索算法运用在迭代过程里。用一些编码方案表示出空间里的一个一个的个体,并且把目标函数的值转变成适应的值。用它来评价每个个体的优劣,以此当做遗传的依据。

种群方式搜索是遗传算法采用的搜索方法。此方式能够搜索出空间里面的多个区域,所以它具有内在并行性的特点,它可以解决程序计算量比较大的问题,从而提高了效率。适者生存,还有比较简单的遗传操作让遗传算法不再受到搜索空间的限制,搜索过程不会轻易的陷入局部的最优点。因此,遗传算法组卷的效率比较高,操作起来比较简单。但是遗传算法也有两个较为明显的缺点。第一,对一些特殊情况遗传算法计算的速度比较慢。第二,比较容易产生试卷早熟的情况。正因为有这两个缺点,所以很多专家提出了一些改良方案。比如编码改进方案、交叉算子或者变异算子的自适应改进等等。

5 结束语

系统组卷算法 篇6

组卷系统的建模方法和算法设计直接影响到它的组卷效率和组卷质量。传统的组卷算法如随机组卷算法和回溯组卷算法通常都存在组卷时间过长, 组卷质量失控以及组卷失败等问题。遗传算法由于其自身具有并行性和全局空间搜索的优势[1], 非常适合用于解决智能组卷的问题而被很多该领域学者所关注, 已经成为学者们所关注的一个研究重点。但是, 遗传算法存在易早熟及后期的搜索效率低下等一些问题, 故本文基于一种改进的遗传算法提出设计开发《计算机应用基础》课程的组卷系统的方案。

1 组卷问题的分析与描述

组卷系统是从试题库中抽取试题组成试卷, 试题库中的试题本身含有特定的属性, 组卷系统的质量和效率由组成试卷的每个试题的属性直接确定。

试题指标体系是对试题外在特征、内在属性的描述, 它是建立组卷系统的关键。试题的指标体系越充分, 组卷的准确性和成功率就越高。通常试题的指标体系包括以下属性:题号、题型、知识点、难度、区分度、认知层次、分值、曝光度等。在本系统中, 各属性设置如下:

1) 题号是试题在数据库中的编号, 是唯一的。

2) 题型:试题的类型, 有很多种分类方式。本系统的试题类型有:选择题、判断题、填空题、简答题、计算题、综合题六类。

3) 知识点:试题考查的知识;一般是按课程的章节进行划分的。该文的章节组织为:计算机基础知识、操作系统、文字处理软件、电子表格软件、演示文稿软件、计算机网络、多媒体基础、网页设计与制作、数据库技术基础、程序设计基础。

4) 难度:是衡量试题的一个重要指标。通常试题难度分为五个档次, 具体如表1所示。初始难度由有经验的教师设定。后由试卷考试结果计算更新之。

5) 区分度:是指试题对受试者水平高低的鉴别能力。同难度相同初始区分度由有经验的教师设定。后由试卷考试结果计算更新之。

6) 认知层次:是反映学生独立获取和驾驭知识的程度。该文采用布鲁姆的理论, 将认知层次为记忆、理解、应用、分析、综合、评价六个层次。

7) 分值:是每道试题的分数, 一套试卷中所有题目的分值之和等于试卷的满分值。为简化程序, 各类题型分值固定, 如选择题均为1分。

8) 曝光度:试题曾在以往试卷中出现过的次数。出现过的次数越多, 该试题的曝光度就越大。

9) 答题时间:考生完成该试题所需的平均时间。考试均是有时间限制的, 故在抽取试题时也需考虑考试的答题时间, 保障绝大多数学生在规定时间内能答完试题。每题的答题时间初始值由有经验的教师估计指定, 后期考虑获取学生平均答题时间修正该属性。当前系统未做修正。

设抽取试题组的属性指标组成矩阵S, 如式1所示。

其中, S中的每一列代表试题的一个属性, 从第1列到第7列依次为:知识点、题型、分值、难度系数、区分度、认知层次和答题时间, 每一行代表一道试题的属性值, n为试卷的总题量, 具体的约束条件为知识点-分数分布约束Bt、题型-分数分布约束Tt、总分约束M、难度-分数分布约束Dt、区分度-分数分布约束Kt、认知层次-分数分布约束Lt、答题时间约束TM。知识点分数分布约束Bt的计算公式为:

Bt为第t个知识点要求的分数 (若知识点为章节, 则1≤t≤12) , ai3为第i题的分数。其他各约束类似, 不再一一列举。

在实施组卷过程中, 约束的实际值与用户的期望值之间总会有一定距离, 称之为偏差。知识点约束偏差的计算公式为:

其中, Bi为试卷的第i个知识点的目标分值, n1为知识点数。其他偏差计算类似, 不再重复列举。

组卷的目标是从试题库中搜索到最接近用户需求的试题子集。因此, 目标函数就是要使生成的试卷中的各指标分布最接近用户要求的各指标分布, 即偏差最小。组卷的最终目标就是求目标函数f的最小值。令:

其中, Wi为各指标的权重。且

2 使用精英交叉的遗传算法改进智能组卷系统

针对传统的遗传算法的种种缺陷, 以及它在组卷问题这一具体应用, 在综合研究了其他研究者特别是袁慧梅、王淑佩、郑日荣、李鹏等[20]的研究成果, 该文提出采用基于精英交叉的精英保留遗传算法在智能组卷领域的整套系统解决方案。

1) 编码:本系统对试卷染色体编码采用实数编码方式。考虑试题在试题数据库中保存的特性, 采用实数编码克服了采用二进制编码造成算法搜索空间过大和试卷染色体编码过长的缺点。编码时可将试卷染色体进行实数编码, 试卷染色体中的每个编码对应试题存放在试题库中的试题编号。试卷染色体的长度是试卷的总题量。

2) 初始化种群:在组卷问题中, 种群中每个个体即是一份试卷。初始种群采用随机方式产生。具体做法:根据约束条件在数据库中均匀采样, 随机生成一定数目的个体, 然后计算每个个体的适应值, 从中挑出适应度高的个体构成初始种群P (0) 。在抽取试题的过程中可通过设置标志位, 以避免同一个染色体中出现重复试题的情况。

3) 适应函数:区分种群中个体好坏的标准是适应函数值的大小。组卷的目标是从试题库中搜索到最接近用户需求的试题子集。

一般情况下, 适应度函数是由目标函数变换而来的, 其值越大个体越好, 而上式目标函数f则是越小越好。故应该由目标函数变换得到适应度函数:。当试卷个体对各项组卷约束条件的误差越小时, 其适应度值就越大, 表示试卷个体越接近组卷目标。

4) 遗传算子

简单遗传算法的操作算子包括选择、交叉和变异三种基本形式。算子的设计是遗传策略的主要组成部分, 也是控制进化过程、调整进化方向的基本工具。

1) 选择

本文采用轮盘赌策略与精英选择相结合的选择方式M。具体操作步骤如下:首先轮盘选择个体, 计算T代种群中每个个体的适应值fi, 并将所有个体的适应值叠加, 得到总适应值, 其中M为种群中个体个数。每个个体的适应值除以F得到每个个体被选择的概率pi, 由个体的累积概率构造轮盘, 选择进入交配池的个体。重复以上步骤, 直到生成M个个体结束选择。

对于精英个体, 采用精英选择方式直接进入下一代。精英选择策略的思想:经过后续交叉、变异后产生的T+1代种群的最佳个体适应值小于T代种群最佳个体的适应值, 则将T种群最佳个体或适应值大于T+1代最佳个体适应值的多个个体直接复制到下一代, 随机替换或替换最差的T+1代种群中的相应数量的个体。

2) 交叉

交叉操作是遗传组卷算法产生新试卷个体的主要途径。该文交叉策略采用传统交叉与精英交叉相结合的交叉策略。

精英交叉的工作原理:给定一个精英交叉概率Pkc, 对于第T代群P (t) 中的每一个个体ai (t) , 产生一个[O, 1]之间的随机数R, 若R小于精英交叉概率Pkc, 则ai (t) 被选中与保存起来的当前代最佳个体k (t) 进行交叉;注意不是以概率l复制到群体P (t) 中的精英个体k (t) 。精英交叉的方法是:把al (t) 和k (t) 放到一个小的交配池中, 根据选定的交叉策略对ai (t) 和k (t) 进行交叉操作, 得到一对子代个体:a'i (t) 和k' (t) , 然后用a'i (t) 代替群体中的ai (t) , k' (t) 则丢弃不用。精英交叉算子与传统的交叉算子大体相同。所不同的是在精英交叉中, 发生交叉的2个父体来源与传统交叉不同;另外, 在进行精英交叉后, 仅ai (t) 发生了改变, 而保存的精英个体k (t) 及群体中的精英个体k (t) 均保持不变。

理论分析表明, 精英交叉遗传算法在局部搜索性能方面有较大的提高。精英交叉与传统的交叉功能各异, 任务不同, 不能相互替代, 对于选择步骤中选择出的精英个体, 将其作为一个小的交配池与一般个体进行精英交叉;原交配池内个体仍进行传统交叉。它们在算法中是互相配合, 在群体进化过程中发挥各自的作用, 共同促进群体的进化。

本文在编码方式上选择了实数编码, 故传统交叉方式采用较适合的算术交叉运算。在本文中a取固定值0.3。如果交叉后得到的结果不为整数, 则采取向下取整的处理, 保证得到的题号都为整数。传统交叉后选择精英个体进行上述的精英交叉过程。

3) 变异

采用均匀变异的方法, 其具体的操作过程如下:依次指定个体编码串中的每个基因座为变异点;对每个变异点, 以变异概率Pm从对应基因的取值范围内取一随机数来替代原有值。均匀变异操作比较适合于遗传算法的初级运行阶段, 它使得搜索点可以在整个搜索空间内自由地移动, 从而可以增加种群的多样性, 使算法处理更多的模式。因变异概率较低, 该文中未做太多改变。

5) 算法结束条件

系统采用算法达到最大迭代次数或适应度函数值F满足用户要求时算法终止的方式。

3 性能对比

采用《计算机基础试题库》来对本方法进行测试对比, 共计800道题, 包括选择题、填空题、判断题、计算题、简答题和综合题六类。各题型数量分布如下:

起始种群规模取值55, 试卷总分为100分, 答题时间为100分钟。通过实验后取得数据如下:

实践证明, 基于精英交叉和精英保留的遗传算法在智能组卷问题上表现优异。本方法可以在不影响群体整体结构的情况下进化性能更优。与传统方法相比, 本方案可在更小的迭代次数中更快的达到最大适应值。可疑有效避免了标准遗传算法易进入早熟收敛和进化缓慢的缺陷。同时, 其收敛速度也比传统的遗传算法要更加有效率, 耗时更低。

4 结束语

组卷工作是一项复杂而繁重的工作。为更好地解决智能组卷问题, 该文给出了一种基于改进遗传算法的组卷系统的设计及实现。该系统核心功能已开发完成, 并能生成质量较高的试卷。但也存在一些问题有待后续改进;如试题难度、区分度及考试时间的更新问题。先系统主要考虑生成试卷, 无在线考试功能, 后续试题属性的更新没有实现。在系统改进中考虑增加此部分内容。

参考文献

[1]应继儒, 胡立新, 龙毅.试题库随机选取数学模型的构建与实现[J].计算机应用, 2000, 20 (1) :46-47.

[2]龚完全.基于最小回溯代价的智能组卷算法[D].湖南大学, 2005.

[3]李书全, 孙雪, 孙德辉, 等.遗传算法中的交叉算子的述评[J].计算机工程与应用, 2012, 48 (1) :36.

系统组卷算法 篇7

1 智能组卷技术

组卷方法大致可以分为3类: (1) 将试题存入试题库,从库中选取符合约束条件的试题进行组卷, 此方法在实质上仍然是人工组卷, 费时费力, 组卷结果不理想;(2) 将试卷存放在数据库中, 需要时直接选取成型的试卷。此方法缺少灵活性, 对于组合好的试题结构无法更改;(3) 利用智能算法, 在试题库中搜寻符合条件的试题组合成试卷, 该方法利用了智能搜寻的优势, 搜索充分, 速度快, 结果理想。

常用的智能组卷策略包括基于线性规划算法的随机抽取法、回溯试探法和基于智能算法的智能搜寻法, 随机抽取法和回溯试探法 (本质上基于随机抽取法) 都是从试题库中随机选取试题, 与约束条件比对判断, 保留符合约束项的试题, 直至组合出满足条件的试卷。这两种策略都会面临由于随机性产生重复抽取的问题, 因此效率不高。另外, 回溯试探法需要较大的存储空间, 算法复杂, 计算时间往往超出可接受的范围。智能搜寻法则依据一定的智能算法 (例如粒子群算法等), 利用算法中潜在的并行性和交互性, 实现快速精确求解[1]。

2 智能组卷模型

组卷要求选用最具代表性的、有难度层级的试题, 从而保证试题的信度和效度。试题本身有很多属性, 如题目类型、难度和曝光度等, 组卷模型必须对试题属性有所体现。同时,受答题总分、测试时间等诸多条件限制, 组卷问题实质上是一个多约束条件下的组合优化问题, 其本身的非劣解不止一个, 称之为非劣解集。

设非劣解集为S, 则S可以视为由m个试题组成的集合,其中, 每个试题具有n个属性, 则S的形式化定义为: S=a11a12…a1na21 a22…a2nam1 am2 amn(公式1)

上式中的ai1,ai2…ain分别对应 于第i个题目的 各个属性(分数、题型、 章节、难度、 区分度、能力层次等 ) , 一个非劣解集就是一份试卷, 一份试卷对应一个“粒子”, 多个“粒子”在解空间中搜寻最佳位置, 搜寻结束后, 处于最佳位置上的“粒子”就是最能满足用户要求的试卷[2]。

组卷还须满足以下约束条件:

(1) 总分约束P=i=1nai1 (公式2)

(2) 题型约束

Tk=i=1n C2ai2(公式3)

公式3中的C2用来表征题目ai是否为要求的题型, 如果是则C2=1, 反之C2=0。Tk为试卷中第k种题型要求的分数, k取 (1,2…n, 在实际中可表示填空、单选、多选等题型)。

(3) 章节约束

Ck=i=1n C3ai3(公式4)

公式4中的C3用来表征题目ai是否为要求的章节, 如果是则C3=1, 反之C3=0。Ck为试卷中第k个章节要求的分数 ,k取 (1,2…n, n为总章节数 )。

(4) 难度约束

Dk=i=1n C4ai4(公式5)

公式5中的C4用来表征题目ai是否为要求的难度, 如果是则C4=1, 反之C4=0。Dk为试卷中 第k个难度级 要求的分数, k取 (1,2…n, n为难度级的最大值)。

与难度约束类似的, 还有区分度约束和能力层次约束等[3]。

曝光度也是试题的一个属性, 原则上应当保持试题始终处于低曝光度状态, 在组卷模型中, 曝光度随着试题的选取而自增, 增加到一定程度时则考虑在试题库中废弃该 题目。在实际操作中, 曝光度与试题最后被抽取到的时间相 结合 ,考察题目的使用频次。

3 粒子群优化算法

粒子群优化算法是一种基于群体协作 的随机搜 索算法 ,1995年由Eberhart博士和kennedy博士提出。该算法利用个体对信息的共享使整个群体的运动在求解空间中产生从无序到有序的演化过程。其基本公式为

vid=w*vid+c1r1pid-xid+c2r2 (pgd-xid) (公式6)

xid=xid+vid (公式7)

公式6中的c1和c2称为学习因子, r1和r2为 [0,1] 的随机数, w为惯性权重 系数 , 表征粒子 保持自身 速度的趋 势 ,c1r1(pid-xid) 记录粒子自身历史经验 , c2r2(pgd-xid) 记录整个粒子群体的历史经验。vid是粒子的速度, 取值范围为 [-vmax,vmax][4]。组卷过程中 , “粒子”依据上述公式不断调整自身的位置, 向着空间内最优解的位置靠拢。

4 评价函数

组卷的目标是获得一个与用户期望值差距最小的试题的集合, 即组卷目标是求得函数f (x) 的最小值, 用di表示试卷的各项属性与用户需求的差值的绝对值, wi代表各项属性所占的重要程度, 从而得到评价函数[5]如下:

fx=i=1nwidi(公式8)

5 求解过程及结果分析

模拟用户需要对问题进行求解, 粒子数为50, 迭代5000次, 得到如图1所示。

采用粒子群算法可以快速地找到满足适应度要求的结果。在前500代, 搜寻结果向着最优解迅速优化, 2000代后, 优化结果趋于稳定, 最佳结果为0.63, 满足实验要求, 如图2所示。

与人工组 卷时间进 行对比 , 试卷总分100, 题量为45,平均结果如表1所示。

表1显示, 智能组卷在时间上优势较大, 计算机强大的检索功能使得组卷过程几乎不受题库规模影响, 而人工组卷需要从大量的试题库中选取符合多重限制条件的试题并进行分析, 随着试题库规模增大, 人工组卷会的效率会明显下降。

抽取20份试卷统计各项要求的符合度, 结果如表2, 表3, 表4所示。

综合分析表2、表3和表4, 组卷结果与用户要求均出现不同程度的差异, 原因在于试题库中的试题属性的量化值并不完全一致; 同时, 抽取的观测样本不同, 得到的结果会有所差异; 另外, 对不同的属性赋予不同的权重值也会影响最终的组卷符合度, 但总体结果与用户要求的符合度较高 (偏差最高为6.25%, 最低为0.6%)。结果表明, 采用粒子群算法可以快速地对组卷问题进行求解, 求解结果稳定, 组卷结果与用户要求的符合度较高, 在时间上具备人工组卷无法相比的优势。

6 结语

结合企业内部的人才培养考核需求, 对组卷问题进行了研究, 分析了组卷约束条件和需要达到的目标, 确定出组卷的数学模型, 采用粒子群算法对问题进行了求解, 并在系统层面予以实现, 测试结果表明粒子群算法可以用于解决组卷问题, 在组卷速度和准确性上具备优势, 有实际应用的价值和意义。在此研究的内容有限, 后续工作将围绕人工方式与智能方式相结合, 在线考试、试题库批量分析和导入等内容展开, 以提高组卷的准确度和自动化程度。

摘要：依据企业人才培养的考核要求,对组卷环节进行研究和改善,建立起规范高效的智能组卷系统。组卷问题是一个在多约束条件共同作用下的优化问题,难以用传统的计算方法进行求解。引入粒子群优化算法,实现了问题的快速求解。实现了基于粒子群算法的组卷模型,测试结果表明,基于粒子群算法的自动组卷系统成功率高、耗时短,系统界面友好,满足用户需求,有效地提高了工作效率。

系统组卷算法 篇8

在线考试题库系统研究中遇到的主要难题是如何保证生成的试题能最大程度地满足用户的不同需要, 并具有随机性、科学性和合理性, 因而智能组卷算法是实现智能组卷的关键技术, 是试题库系统的核心, 是衡量一个试题库系统优劣的主要依据。现已开发的试题库系统, 大多是采用随机选取算法结合回溯试探的方法实现自动组卷。回溯试探法组卷成功率高, 但其不断重复的过程, 是以牺牲大量的时间为代价的, 对组卷效率产生较严重的影响, 组卷成功率也不能得到很好的控制。对于现今越来越流行的考生网上随机即时调题的考试过程来说, 它已不符合要求。因此, 必须结合以上两种方法寻找一种新的改进算法, 于是就出现了第三种算法—标准遗传算法 (SGA) 。它是一种并行的、能够有效优化的算法, 具有全局寻优和收敛速度快的特点。但这一算法的弱点在于组卷前没有充分利用当前试题库中试题的类型、题量、难度、知识点等各类特征的分布信息。

1 编码方法的确定

SGA:采用HOLLAND的标准二进制编法方式, 定义如下:CH∈Bp, B∈{0, 1}, p表示二进制位串的长度, 在这里表示试题库中试题的数目。染色体上的每一个基因代表对应的试题是否被挑选:1为该试题被挑选, 0为该试题没有被挑选, 那么每一个染色体代表一组选题结果。例如, 试题库中共有10道题, 其中第1、4和5题被选中, 则与之对应的染色体为1001100000。该方法表示自然和清晰, 易于实现交叉与变异, 缺点是试题库很大时, 占据存储空间大和计算量大, 从而导致性能下降。

采用分段的浮点数编码, 染色体形如 (a1, a2, …, an) , 其中ai表示试题库中试题的题号, n为试卷要求的试题数。基因按照题型有序排序, 并且将同类型的试题放在同一个区间内, 如图1所示:

采用这种编码, 就自动满足了约束1和约束2, 而且减少了解码的过程, 因而加快了进化速度。

2 初始化种群

SGA:通过随机的方法生成初始化的串种群。在串种群中, 串长度都是相同的即试题库中试题数p, 但是保证基因位为1的数目为n即试卷要求的试题数。

本文组卷算法是依据组卷要求从每一类题型中随机产生相应数目的题号, 按题型有序地存入个体的染色体中。保证同种题型的各题号必须相异, 以免在同一份试卷中出现重复的试题, 而且每个题号均在相应题型的题号定义域中产生。

3 适应度函数的确定

通过采用分段实数编码, 从而自动满足了约束1和2, 因而适应函数的确定只要考虑另外7个约束。

3.1 教学层次比例的约束

对相应层次所占的分数与用户输入值相减所得的绝对值求和再除总分, 就得到教学层次比例不满足命题要求的程度fl, 如果引入PAM, 则

其中t_num为题型的数目, fl∈[0, 1], fl越小说明教学层次比例约束满足得越好, 当fl=O时, 完全满足教学层次比例。

3.2 章节比例的约束

同理可得章节比例不满足命题要求的程度f2, 如果引入RAM,

其中s_num为章节的数目, f2∈[0, 1], 越小说明章节比例的约束满足得越好, 当f2=0时, 完全满足教学层次比例。

3.3 难度级比例的约束

同理可得难度不满足命题要求的程度f3, 如果引入PAM,

其中d_num为难度级的数目, f3∈[0, 1], f3越小说明难度级比例的约束满足得越好, 当f3=0时, 完全满足该约束。

3.4 区分度的约束

同理可得区分度不满足命题要求的程度f4, 如果引入PAM

f4∈[0, 1], f4越小说明区分度的约束满足得越好, 当f4=0时, 完全满足该约束。

3.5 考试时间的约束

同理可得考试时间不满足命题要求的程度f5, 如果引入RAM,

f5∈[0, 1], f5越小说明考试时间的约束满足得越好, 当f5=0时, 完全满足该约束。

3.6 知识点分布的约束

知识点分布不满足命题要求的程度f6为:

其中S (TPKV, RTKV) 表示试卷知识点向量TPKV与关联目标知识点向量RTKV的相似度。f6∈[0, 1], f6越小说明知识点分布的约束满足得越好, 当f6=0时, 完全满足该约束。

3.7 成批组卷重复率的约束

成批组卷重复率不满足命题要求的程度f7为:

其中

getnum (tp, tpi) 表示新生成的第F+1套试卷tp与已经生成的试卷集TP (试卷套数为F) 中试卷tpi中试题的重复率, TP_LIMIT为设定的任意两套试卷中试题的重复率阈值。

综上所述, 目标函数为:

其中wi是根据约束的类别的不同而选择不同的权值, 强约束的权值最大取1, 次约束的权值取0.5, 弱约束的权值最小取0.1。根据f的定义可知0≤f≤1, 因而定义适应度函数为:

0≤fitness≤1, 其值越大, 表示该组卷的方案越满足命题的要求。当fitness=1, 组卷方案完全满足命题要求时。

与标准遗传算法相比, 本文组卷算法适应度函数考虑的约束减少, 因而对于加快进化速度有利。

4 遗传操作

4.1 选择

这里采用适应值比例选择中的轮盘赌方法进行选择。首先将种群中的个体按照适应度的值由大到小进行排序, 根据个体的适应度来分配其选择概率 (适应度越大, 被选择的概率越大) 。在选择过程中, 产生一个介于0到1之间的随机数, 当随机数落在适应值所在的概率区域, 那么对应的个体被选择用来进化后代。

4.2 交叉

SGA:从群体中随机选择2个染色体, 按照固定的交叉率PC从某一位基因位开始逐位进行互换。在这里同样采用单点交叉, 交叉之后得到的染色体中, 可能在同一题型里包含相同题目的情况, 可以通过采用在相应题号定义域中随机产生相异的题号来替换原有题号的方法解决。

4.3 变异

SGA:为了在满足被选择的试题数与试卷要求的试题数n相同的基础上完成真正意义上的变异, 采用2种变异机制:

(l) 当染色体中基因值为1的数目不等于期望试卷试题数n时, 要求其经过变异后使得被选择试题数与试卷试题数n相同, 即通过产生从1到染色体长度L之间随机数, 并将染色体相应位置的基因值变为1或0, 直到染色体中基因值为1的数目等于试卷试题数n;

(2) 产生1到染色体长度之间的两个不同基因值的变异点, 将其基因值进行互换, 从而在满足被挑选的试题数等于n的基础上实现了真正意义上的变异。

该组卷算法中因为自动满足约束2, 因而变异相比SGA要简单。通过变异后, 染色体中可能在同一题型里包含相同题目的情况, 同样采用在相应题号定义域中随机产生相异的题号替换原有题号的方法来解决。

4.4 交叉率Po和变异率Po的选择

交叉率PC和变异率Pm是影响遗传算法行为和性能的关键所在, 直接影响遗传算法的收敛性。

SGA:采用固定的PC和Pm, 因而不能根据当前种群自适应度的变化趋势自适应调整交叉和变异的频率。在这里将自适应性引入交叉率PC和Pm即:

其中, fmax—种群中最大的适应度值;

favg—每代群体的平均适应度值;

f’—交叉的两个个体中较大的适应度值;

f—变异个体的适应度值;

cl、c2、ml、∈[0, 1]。

基因的交叉和变异实质上是对染色体结构的一种破坏, 进化应该多保留优秀的个体, 而使不良个体较多地被破坏, 从而使得在有限的迭代数内搜索更大的空间。根据 (1) 和 (2) 式, 交叉率PC和变异率Pm随染色体适应度值自适应改变, 将有助于实现这个目的。

4.5 最优保存策略

进行选择、交叉和变异操作后, 比较新一代的最好个体与上一代的最好个体的适应度值, 如下降, 则以上一代最好个体替换新一代的最差个体。此策略可以保证迄今为止的最优个体不会被交叉和变异等遗传运算破坏, 它是遗传算法收敛的一个重要保证条件。

4.6 迭代终止条件

满足下列2个条件之一终止进化:

(l) 新种群中个体的最大适应度值FITNEss-fitness≤e, 其中Fitness为期望的适应度值, e为期望的误差精度;

(2) 进化到指定的最大迭代次数g_max。

4.7 算法描述

题库系统中, 往往需要单套或成批组卷, 利用自适应遗传算法实现组卷的算法 (Generating test paper_Algorithm) 如下所示:

输入:种群数N

最大迭代次数g-max

期望的误差精度e

目标关联知识点向量TKV

知识点层次差矩阵KHDM要求生成的试卷套数TP_NUM

任意两套试卷中试题的重复率阈值TP_LIMIT

输出:符合条件的单套或成批试卷

STEP1.判断题库中各题型中小于限定抽取次数的试题数都大于试卷相应题型的要求试题数的条件是否满足, 若不满足则转STEP13;

STEP2.根据TKV和HDM计算关联目标知识点向量RTKV;

STEP3.随机产生种群数为N的初始化种群, 保证每个个体基因值所代表的相应试题的抽取次数都小于限定抽取次数, I=O;

STEP4.判断TP_NUM-i大于O的条件是否满足, 若不满足则转STEP13;

STEP5.根据产生的种群个体生成试卷属性矩阵PAM和试卷知识点矩阵TKPM, 并计算试卷知识点向量TPKV;

STEP6.计算TPKV和RTKV的相似度, 并根据适应度函数计算群体中每个个体的适应度值;

STEP7.判断算法迭代终止条件是否满足, 若满足则转STEP12;

STEP8.根据各个体的适应度值进行选择操作;

STEP9.按照自适应交叉概率PC进行交叉操作, 保证交叉后同一题型的试题编号互异;

STEP10.按照自适应变异概率Pm进行变异操作, 保证变异后同一试题库系统智能组卷与试卷分析的研究题型的试题编号互异, 且保证变异后个体的基因值所代表的相应试题的抽取次数小于限定抽取次数;

STEP11.若己得到由N个新个体构成的新一代种群, 则执行最佳保存策略, 并转STEPs, 否则转STEP7;

STEP12.按照同一题型难度系数由小到大的顺序依次输出所选择的试题, 并将所选择试题的抽取次数Q_TIMES加1, i++, 并转STEP4;

STEP13.终止程序。

5 结束语

以上介绍的算法实现过程就是在对试卷结构数学描述的基础上, 利用遗传算法的自适应全局优化特性在传统组卷算法基础上设计出来的。它能克服其他算法的缺陷, 真正意义上实现智能组卷。

摘要：在对试卷结构作数学描述的前提下, 利用遗传算法的自适应全局优化特性, 在传统组卷算法基础上设计出了自适应遗传算法, 它能克服某些传统算法的缺陷, 真正意义上实现智能组卷。