基于改进随机抽取策略的智能组卷算法

王 东

(贵州师范学院 数学与计算机科学学院,贵州 贵阳 550018)

基于改进随机抽取策略的智能组卷算法

王 东

(贵州师范学院 数学与计算机科学学院,贵州 贵阳 550018)

针对随机抽题过程中出现的重复抽选问题，设计了一种优化的数据结构，实现了无回溯快速组卷.基于该方式，抽题前预先评估已抽取试题的分布情况，确定待抽取试题的章节范围，再从其候选集合中随机抽选试题，进而有效解决组卷过程中试题分布不合理的问题.该算法已经在试题库考试系统中得到成功应用.

自动组卷；试题库系统；随机组卷算法；组卷策略

自动组卷就是根据组卷策略指定的约束条件，从题库中随机抽取出试题，从而取代人工选题的过程.自动组卷的核心问题之一就是设计良好性能的组卷算法.由于组卷约束条件之间的相互牵制以及试题库题量的限制，要生成一份符合要求的试卷不是一件容易的事件.目前，自动组卷过程中使用的组卷算法大致分为三类：随机组卷算法[1-2]，回溯算法[3]和基于遗传算法[4-7]的组卷方法.其中，随机组卷算法易于理解，运行速度快，在实际的试题库管理软件系统中应用广泛，并在实践中得到不断的改进，如金汉均等提出了分段随机抽选法[2]，该方法在录入试题时生成一个随机数，在组卷时按顺序从候选集合中抽取给定数量的试题.与传统随机算法相比，该方法效率有所提升，但随机数的维护代价很大，对一条记录的修改将导致与之相关记录集的修改.王萌等提出集合随机抽选法[8]，该方法使用备选集合来避免回溯，当从备选集合中抽取一个题后再重新生成一个不包含已选试题的备选集，再抽选试题时不会与已抽选试题产生重复.但该方法的主要问题是每抽选一个题就要重新生成备选集，降低了组卷算法的执行效率.本文将通过设计高效的数据结构并对组卷算法进行优化，实现无重复、无回溯随机抽题，在抽题时借助章节可分配数组动态确定抽取试题的章节范围，以期较好地解决试题分布不合理的问题，提高命题组卷的客观性和科学性.

1 组卷算法数据结构

1.1 设置组卷策略

设置组卷策略就是为自动组卷设定组卷参数，构造试卷结构的过程.设置的组卷策略存储在数据库表中，一组组卷策略由存储在数据库表中的多条记录组成，每条记录表示试卷中的一种题型，包括题型号、试题数、单题分值、总分值、各难度试题数等.设置组卷参数时，部分参数由用户明确设定，如每种题型的试题数、单题分值，部分参数可通过计算得到，如试题难度，文献[9]中就提出了一种依据正态分布函数计算试卷中试题难度分布的方法，通过试卷平均难度推导出各难度题所占比例.文献[10]提出了基于难度级别的分割递归算法.根据每类题型的难度级别和抽题总量，确定不同难度级别试题的抽题数量.

1.2 确定章节分值

组卷前设置试卷中各章节所占的分值是常见的约束条件之一.各章节所占的分值分配可根据命题者的经验手动设定，或者根据各章节在课程大纲中所占的学时比例自动计算.对于后者，为提高组卷的成功率，各章节分配分值不宜设置为固定值，而采用浮动分配方式，即允许在标准分配的基础上左右浮动一定比例.例如：某章按学时比例计算，若试卷满分为100分，该章可分配标准分值为20分，按浮动比例5%计算，则该章组卷时实际分配分值在15到25分之间都是符合组卷要求的.

具体实现时，章节可分配分值用一个二维数组ChapterScore存储.数组元素ChapterScore(i, 0)的值Si表示可分配标准分值，ChapterScore(i, 1)中的值Ci表示章号(见表1).

表1 章节分值分配数组

组卷时，首先计算每章的可分配分值，按分值大小降序排序存储到ChapterScore数组中，下标为0的存储单元中存储的章节号为优先抽题的试题范围，若该章节范围内没有满足条件的试题，则以下标为1的存储单元存储的章节号为抽题范围，依此类推.当遍历完ChapterScore数组中的所有单元后，仍没有满足条件的试题，则组卷失败.当每抽选一个题后，根据试题所属章节号修改ChapterScore数组对应元素的分值，再对ChapterScore进行排序, 保持ChapterScore数组按分值大小降序排序.

1.3 随机抽题算法数据结构设计

确定了组卷的具体要求，将这些要求转化成试卷中每类或每个题目的难度、知识点、分值等量化参数，然后根据一定的算法抽取试题.

抽题算法主要数据结构包括两个部分，第一部分为章节结构向量，每个向量元素含3个信息，章节ID号、试题数、试题ID列表向量指针，第二部分为各章试题ID列表向量，每个元素存储试题ID号.图1为抽题算法数据结构.章节结构向量结点结构定义如下：

PublicStructurenode

DimchapterIDAsInteger

DimnumAsInteger

DimrefAsObject

EndStructure

图1 抽题算法数据结构

2 随机组卷算法描述

2.1 创建候选试题数据结构

组卷时，先将数据库中的试题信息读入内存中，生成供随机选题用的候选试题数据结构(图1)，生成该数据结构需完成以下步骤：(1)以题型、难度为参数，生成章节结构向量;(2)分别以题型、难度、章节ID为参数，生成各章节的试题ID列表向量.

创建候选试题数据结构的算法描述：

输入：章节数row，题型qtypeID,难度系数diff

输出：候选试题数据结构M

FunctioncreateM(ByValrowAsInteger,ByValdiffAsString,ByValqtypeIDAsInteger)AsArray

DimM(row- 1)Asnode‘声明包含row个结点的章节结构向量

DimstrsqlAsString= ""

Dimdv,dv1AsDataView

DimdbAsDataBase=NewDataBase

‘给定难度和题型条件下获取数据库各章节试题数量

strsql= "selectchapterID,count(*)numfromquestionwheredifficult=@diffandquestiontypeID=@qtypeIDgroupbychapterID"

dv=db.RunSelectSQL(strsql)

DimiAsInteger

Fori= 0Todv.Count- 1

M(i).chapterID=dv(i)("chapterID")‘初始化章节ID

M(i).num=dv(i)("num") - 1‘试题数量

dv1 =db.RunSelectSQL("selectIDfromquestionwheredifficult=@diffandquestiontypeID=@qtypeIDandchapterID=@chapterID")‘给定难度、题型及章节条件下获取数据库试题ID

Dimqlist(dv1.Count- 1)AsInteger‘声明试题向量

‘初始化试题向量

Forj= 0Todv1.Count- 1

qlist(j) =dv1(j)("ID")

Next

‘章节结点指针指向试题向量

M(i).ref=qlist

Next

ReturnM

EndFunction

2.2 无重复随机抽题

抽题时，根据章节ID在章节结构向量中顺序查找到对应的元素M(i)，取得试题数M(i).num,根据试题ID列表指针取得试题ID列表qlist.在qlist的下标0到M(i).num-1范围内随机产生一个下标，该下标的数组元素值为抽取的试题ID，把这个元素值跟M(i).num-1下标的元素值交换，把随机产生过的位置替换为未被选中的值.并将M(i)的试题数域减1.使下一次随机抽题在下标0到M(i) .num-2范围内进行,保证每次随机抽取的试题不重复.

无重复随机抽题算法描述：

输入：候选试题数据结构M，章节ID

输出：随机抽取的试题ID

FunctionsearchM(ByValM()Asnode,ByValchapterIDAsInteger)AsInteger

DimiAsInteger

DimqIDAsInteger= -1

DimIndexAsInteger

竣工后高层建筑变形监测中应用GPS技术的价值探究……………………………………………………… 姚建东（6-30）

‘顺序扫描候选试题数据结构M

Fori= 0ToM.count- 1

‘若章节向量章节域与章节ID相等且该章节候选试题数大于0，从中随机抽取试题

IfM(i).chapterID=chapterIDAndM(i).num> 0Then

Randomize()

'在0到dv1.count-1之间随机取下标

Index=CInt(Int((M(i).num) *Rnd()))

'在0到dv1.count-1之间随机取下标CInt(Int((upperbound-lowerbound+ 1) *Rnd() +lowerbound))

DimqlistAsObject=M(i).ref

qID=qlist(Index)‘取得选择试题ID

‘把这个元素值跟m-1下标的元素值交换，把随机产生过的位置替换为未被选中的值

DimxxAsInteger=qlist(Index)

qlist(Index) =qlist(M(i).num)

qlist(M(i).num) =xx

M(i).num=M(i).num- 1‘将该章节候选试题数域减1

EndIf

Next

ReturnqID‘返回试题ID，未抽取成功返回-1

EndFunction

2.3 生成章节分配分值

ChapterScore数组用于存储按课时比例生成的可分配分值，在执行组卷算法前进行初始化，从数据库中获取当前题库各章节的学时分布数据，进行统计后存储到ChapterScore数组中，并对数组按可分配分值降序排序.

生成章节分配分值算法描述如下：

输入：题库ID，章节分配分值数组ChapterScore，章节数chapterCount

输出：章节分配分值数组ChapterScore

SubCreateChapterScore(ByValquestionbankIDAsInteger,ByrefChapterScore(,)asinteger,byvalchapterCountasinteger)

'从数据库中获取课时分布

Dimksfb_dvAsDataView=db.RunSelectSQL("selectB.ks,A.chapterfromksfbAinnerjoinquestionbankoutlineBonA.questionbankID=B.questionbankIDandA.chapterID=B.IDwhereA.questionbankID=" &questionbankID)

DimiAsInteger

'累加各章课时，统计总课时

Dimks_sumAsInteger= 0

Fori= 0Torow- 1

ks_sum=ks_sum+ksfb_dv(i)("ks")

Next

'按课时比例计算可分配分值存储到ChapterScore数组，ChapterScore(i, 0)表示可分配标准分值，ChapterScore(i, 1)表示章号，

Fori= 0Torow- 1

DimksAsDecimal=Convert.ToDecimal(ksfb_dv(i)("ks"))

ChapterScore(i, 0) =CInt(ks/ks_sum* 100)

ChapterScore(i, 1) =ksfb_dv(i)("chapterID")

Next

SelectSort(ChapterScore,chapterCount) '对可分配分值数组按可分配分值大小降序排序

Endsub

2.4 改进的随机组卷算法

自动组卷按各种题型分别抽题的方式进行.优先处理单题分值大的题型，如分析题较单选题优先处理，因为题型的单题分值大小反应了知识点的教学要求和试卷平均难度系数的权重，按题型单题分值从大到小的顺序进行各种题型的抽题组卷，有利于满足组卷约束条件.抽题时根据ChapterScore数组优先在可分配分值大的章节中抽题.分值大的试题将优先分布到可分配分值大的章节中.而且，由于可分配分值随抽题过程而不断动态调整，抽取试题不断跳跃分布到不同的章节中，从而使同一题型的试题均匀分布到各章节中.

随机抽题组卷算法详细描述如下：

'生成章节分配分值

CreateChapterScore(questionbankID,ChapterScore,chapterCount)

'从数据库中查询组卷策略明细，返回记录集

DimdvAsDataView=db.RunSelectSQL("selectB.*fromstrategyAinnerjoinstrategydetailBonA.ID=B.paperstrategyIDwhereA.ID=@strategyorderbyB.singscoredesc")

'若组卷策略明细不为空，则执行

Ifdv.Count> 0Then

Dimj,h,r,kAsInteger

'依次对每个题型进行抽题，优先处理单题分值大的题型

Fori= 0Todv.Count- 1

'取得不同难度的试题数存储到diff数组

DimdifficultpreAsString=dv(i)("difficultpre")

Dimdiff()AsString=difficultpre.Split(",")

DimdifstrAsString() = {"易", "中", "难"}

'声明questionlist变量存储已抽取的试题ID，试题ID之间用逗号分隔

DimquestionlistAsString= ""

'按“难”、“中”、“易”依次抽取试题

Forj= 0To2

'若当前难度下要抽取的试题数大于0，则执行

Ifdiff(j) > 0Then

'声明arr数组存储要抽取的试题ID

Dimarr(diff(j) - 1)Asinteger

'创建候选试题数据结构

DimM()Asnode=createM(row,difstr(j),dv(i)("questiontypeID"))

'反复抽选试题

Forh= 0Todiff(j) - 1

' 根据ChapterScore数组依次检测每章

Forr= 0Torow-1

' 随机抽题，返回题号

DimIndexAsInteger=searchM(M,ChapterScore(r, 1))

DimkfpAsDecimal= (ChapterScore(r, 0) +ChapterScore(r, 0) *xs)

' 随机抽题成功且可分配分值大于单题分值

IfIndex<> -1AndCInt(kfp) >=dv(i)("singscore")Then

' 更新ChapterScore数组

ChapterScore(r, 0) =ChapterScore(r, 0) -dv(i)("singscore")

' 对ChapterScore数组排序

SelectSort(ChapterScore,row)

arr(h) =Index

ExitFor

EndIf

Next

'结束本次循环

Ifr>row- 1Then

ExitFor

EndIf

Next

'形成试题号列表字符串

Fork= 0Toh

questionlist=questionlist+arr(k) + ","

Next

EndIf

Next

Ifquestionlist.Length> 0Then

questionlist=Left(questionlist,questionlist.Length- 1)

'将当前题型抽选的试题列表保存到试卷明细表

insert(dv(i)("questiontypeID"),dv(i)("num"),dv(i)("singscore"),dv(i)("description"),questionlist)

EndIf

Next

EndIf

上面的程序主要执行以下几步操作:(1)调用CreateChapterScore函数生成章节分值分配数组ChapterScore；(2)执行数据库访问方法RunSelectSQL返回组卷策略记录集；(3) 依次对每个题型进行抽题，优先处理单题分值大的题型；(4)调用createM函数生成候选试题数据结构；(5)调用searchM函数生成不重复的试题；(6)生成试题号列表字符串questionlist；(7)调用insert方法将当前题型抽选的试题列表保存到试卷明细表.

3 算法分析

应用改进的随机组卷与传统算法在生成试卷的执行效率上进行了比较, 其中试题科目为《数据库原理与应用》和《高级语言程序设计》,试题库题量分别为400个、1 200个， 试题库试题构成如表2所示.

测试环境：处理器为i5-4200M2.5GHz,内存为4GB,操作系统为64位windows10.算法基于.NET框架，采用VB.NET语言实现, 试题存储数据库选用SQLServer2008R2.不同算法执行的比较结果如表3所示.

表2 试题库试题构成统计表 个

表3 两种算法执行效率的比较

测试结果中，当题量为400时，传统算法抽取10套含30个题的试卷的平均用时为0.42s，改进的组卷算法平均用时0.14s.当题量为1 200时，传统算法抽取10套含90个题的试卷平均用时0.76s，改进的组卷算法平均用时0.43s.可以看出，当题量较小时，由于抽题时发生重复而回溯降低了算法性能，对传统算法的执行效率影响较大，而改进的组卷算法在抽题过程中不会产生重复抽题现象，执行效率的稳定性较好.同时，两组测试中，本文算法的组卷效率明显优于传统算法.

此外，观察每种题型的试题在各章节中的分布情况可知，传统算法生成的20套试卷，其中有4套试卷出现试题分布不合理的情况，同类题型的试题过度集中到某个章节中.而使用改进的组卷算法生成的试卷，均未出现试题堆积现象，试题分布合理性较好.

4 结束语

组卷是试题库建设和无纸化考试系统的核心内容.本文对组卷过程中的重复性抽题以及分布不合理的问题，提出了针对性的解决方案.

通过构造高效的数据结构，实现了无重复随机抽题.使用可分配分值数组提供的信息，避免了相同题型试题过度集中于部分章节中，从而提高了试题分布的合理性.使用本算法的试题库管理系统在实际应用中运行稳定，完全满足大批量在线组卷需求.

[1]唐朝舜,董玉德,熊蓉.在线随机组卷算法研究及实现 [J].合肥工业大学学报(自然科学版),2006,29(3):296-299.

[2]金汉均,郑世珏,吴明武.分段随机抽取选法在智能组卷中的研究与应用[J].计算机应用研究,2003,20(9):102-103.

[3]李大辉.基于广度优先回溯算法的试题搜索算法[J].大庆石油学院学报,2006,30(3):100-101.

[4] 张琨，杨会菊.基于遗传算法的自动组卷系统的设计与实现[J].计算机工程与科学，2012，34(5)：178-183.

[5] 朱婧, 戴青云,王美林.自适应遗传算法在工程训练在线考试中的应用[J].计算机工程与应用,2013,49(14):227-230.

[6] 肖桂霞,赵武初,朱伟,等. 基于遗传算法智能组卷的去重题方法[J].计算机工程, 2012, 38(11): 150-152.

[7]陈国彬,张广朱. 基于改进遗传算法的快速自动组卷算法研究[J].计算机应用研究,2015,10(32):2 996-2 998.

[8]王萌, 金汉均,王晓荣. 集合随机抽选法在智能组卷中的研究[J].计算机工程与设计, 2006, 18(27): 3 583-3 585.

[9]毛秉毅. 一种计算试卷中试题难度分布的有效方法[J].计算机工程, 2002, 28(6): 280-281.

[10]曾一，冉忠，郭永林. 试题库中自动组卷的算法及试卷测评策略[J]. 计算机工程与设计, 2006, 27(16): 3 024-3 027.

(编辑：郝秀清)

Intelligent test paper generating algorithm based on improved random selection strategy

WANG Dong

(Mathematics and Computer Science Institute, Guizhou Education University, Guiyang 550018, China)

Aiming at the repeated problems in the process of random extraction, an optimized data structure is designed, which can realize the rapid test paper generation without backtracking. Based on this method, the distribution of the test questions is pre evaluated in advance, so as to determine the scope of the section to be extracted. Then questions are randomly selected from the candidates, so as to effectively solve the problem of the irrational distribution in test questions. The algorithm has been successfully applied in the examination question system.

auto-generating test paper; the examination question system; random generating paper algorithms; paper-making strategy

2016-09-23

贵州省2014年本科教学质量工程项目(黔教高发[2014]378号)

王东,男,wd_gz@163.com

1672-6197(2017)04-0019-05

TP

A