第四章 关键算法研究
4.1 教学测试
教学测试的作用在于：系统中网络考试设计的一个基本目的是让学习者对指定的学习内容实现有效地学习，因此获取学生对指定内容的掌握情况是教学系统中的一个重要方面。当前，一种有效地获取学生对知识掌握情况的方法是对学习者进行测试，因此建立一个完善的试题库并在适当的情况下对学生进行合适的测试是非常必要的。一般而言测试具有以下几种功能：
l.控制教学过程：通过测试了解学生对指定内容的掌握情况，根据测试结果选择下一部分的学习内容。
2.进行错误诊断：通过测试获取学生所犯错误，并以此来调整教学内容、教学方法、教学步幅等。
3.为评价提供有力的依据。测试与教学是构成教学系统的两个重要不可分割的基本要素。
4.2 组卷相关算法研究
教学测试中试题抽取的基本依据是所选择的测试试题必须与学生所学习的知识点的教学目标相匹配。抽取试题的算法有多种，组卷质量好或坏，能如实地反映出学生对知识技能的掌握程度以及教师的教学水平。因此，抽题成卷后，要根据学生答题情况，应用试卷测评手段，根据各项质量指标全面评价试卷。
智能组卷的设计目标是在线考试系统自动化或半自动化地生成一份用于考试的试卷，由于用户在组卷时会对试卷提出多方面的要求，如总题量、难度、题型、章节比例、重点章节比例、知识覆盖面等，要在一个有限的题库中找出相应的试题同时最大程度的满足用户多方面的要求组成公平性、科学性、合理性的试卷并非易事。
国内外的许多科研单位、学校机构都在对组卷系统进行研究。组卷算法是一个被探讨了很长时间的问题，但还没有一个最优的解决方案。如何设计一个算法从题库中既快又好地抽取出符合要求的试卷，很多学者都在对其进行研究。
4.2.1 常用的组卷算法
遗传算法在发展的初期称为简单遗传算法（simpleGA,SGA）。 1962年 Holland 教授首次提出了 GA 算法的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面，并奠定了理论基础。它是一种模拟生物进化过程和自然遗传机制的过程搜索最优解的算法。它提供了一种与传统技术截然不同的求解问题的方法，其基本过程是：产生一个与问题相关的潜在解的种群，设计一些从旧解产生新解的变化算子，并应用选择机制保留那些最好的解到当前代。但遗传算法有如早熟、局部搜索能力弱等缺点。
随机选取法即随机从试题库中提取试题，其优点是：算法结构简单、运行速度快；缺点是：由于约束条件少，组卷中试题重复率、相似率高，试卷的总体难度难以把握，尤其是题库量较小时。对于整个组卷过程来说组卷成功率低，即使组卷成功，花费时间也令人难以忍受。
回溯试探法将随机选题产生的每一状态类型记录下来，当搜索失败时释放上次记录的状态类型，然后再根据一定的规律变换出一种新的状态类型进行试探，通过不停地回溯试探直到试卷生成完毕。该算法在理论上可以遍历每一种可能的状态组合，组卷成功率高，但它是以牺牲大量的时间为代价的，实际上当试卷总题量较大时，状态类型的组合数便成为天文数字，尤其当试卷生成到后来，符合约束条件的可选试题量的急剧减少，使得试卷生成的成功率大大降低。故该方法只能适用于状态类型和试卷总题量不多的题库系统，而且，该算法对内存占用量大，程序结构复杂，显然不适合在线组卷。对于现今越来越流行的考生网上随机即时调题的考试过程来说，它已不符合要求。
遗传算法有：如早熟、局部搜索能力弱等缺点，在本系统中不适合使用。回溯法最终结果是合理的，但时间代价太大，无法忍受。先抽题，后计算难度级别，需多次才能达到预期的目标，随机方法不能实现真正随机，不公平，且能被学生抓住规律，不合理。经过对常用组卷算法的分析，认为：一个较好的组卷算法应该结构简单、节省时间、成功率高，尽量降低重复率、避免花费时间长。当然，每一种算法都有其优劣性，但并不是优点越多、评价越高的算法，就越适用，而应该在实际应用时，根据所需要解决的问题来采用合适的算法。在本教学网站中采用了基于随机数的自动组卷算法。
4.2.2 组卷策略的基本要求
一个良好的组卷策略通常必须满足如下两个基本约束：
l.能提供灵活的组卷控制接口。以尽可能的满足不同出卷人的评价目标需求。
2.由组卷策略逻辑生成的试卷在应用中要经得起教育测量理论的检验。简单的说就是试卷的测试结果应该基本呈正态分布。
4.3 系统中自动组卷的算法设计
4.3.1 组卷原理
首先，系统将用户输入的对试卷的具体要求转化成试卷中题目的难度、知识点、分值等量化参数，然后根据难度等级及各参数确定各难度等级应抽题数，依据此数量抽题。试题抽选出来后，生成试卷供学生考试。
组卷流程如图 1 所示。
4.3.2 组卷算法
自动组卷是考试系统自动化或半自动化操作的核心目标之一，而如何保证生成的试卷能最大程度的满足用户的不同需要，并具有随机性、科学性、合理性，这是实现中的一个难点。尤其在交互式环境下用户对于组卷速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动组卷的关键。
目前大多数随机组卷算法都是采用基于题型的随机选题和组卷，这种组卷策略没有考虑试卷的难度等级以及每个题型的难度等级，不能很好地达到考试的目的，试卷的总体难度难以把握，花费时间也较长。针对这一情况，在实际开发中，采用了基于随机数的自动组卷算法，算法主要分两步来完成：首先，使用基于难度等级确定抽题数量算法，根据每类题型的难度等级和抽题总量，确定不同难度等级试题的抽题数量。然后，利用基于随机数的抽题算法，在确定各类题型不同难度等级试题抽取数量的基础上，随机自动组卷。这样，先根据期望的难度等级来组卷，避免了先组卷再判断难度等级。基于随机数的自动组卷算法既发挥了以往随机组卷的优点：算法结构简单、运行速度快，又避免了试题重复率、相似率高，试卷的总体难度难以把握，花费时间长的缺点。
在基于随机数的自动组卷算法中，要解决这样几个问题：为了实现抽题的公正性、随机性，让学生找不到规律，且均匀分布，采用了基于随机数生成算法；为了避免先组卷后判断难度等级而使组卷花费时间长，采用了基于难度等级确定抽题数量算法，最后，采用基于随机数的抽题算法抽题成卷。
下面就是本网站在采用随机数对题库中的单项选择题进行随机抽题生成试题所使用的代码：
<%
ran_seed=dx1_nook
dim dx1_ran（50），va_dan（50），va_danok（50）
dim i
i=0
do while i<dx1_no
randomize timer
dx1_ran（i）=int（rnd*ran_seed）+1
i=i+1
loop
k=0
do while k<dx1_no
tt=cint（dx1_id（dx1_ran（k）））
bpath=server.mappath（“/y3q/exam.mdb”）
set connt=server.createObject（“ADODB.Connection”）
connt.open “driver={Microsoft Access Driver （*.mdb）} ;
dbq=”&dbpath
set rst=server.createobject（“ADODB.Recordset”）
sqlt=“select * from e_tk where ID=” & tt & “”
rst.open sqlt,connt
if not rst.eof then
t_tm=Server.htmlencode（replace（rst（“e_t_text”），“‘”,“'’”））
t_da=Server.htmlencode（replace（rst（“e_t_answer”），“‘”,“'’”））
t_xxA=Server.htmlencode（replace（rst（“e_t_cA”），“‘”,“'’”））
t_xxB=Server.htmlencode（replace（rst（“e_t_cB”），“‘”,“'’”））
t_xxC=Server.htmlencode（replace（rst（“e_t_cC”），“‘”,“'’”））
t_xxD=Server.htmlencode（replace（rst（“e_t_cD”），“‘”,“'’”））
%>
图 2 是用户在进行模拟考试时进行试卷生成过程中，对试卷进行设置，主要包括设置题的类型，来自章节数，难度及题的个数的界面。
生成试卷的结果如图 3 所示。
4.4 本章小结
本章主要讨论了教学网站开发过程中出现的难点：教学测试。教学测试与教学是构成教学系统的两个重要的基本要素。在教学测试中采用基于随机数的自动组卷算法，该算法主要分两步来完成：首先，使用基于难度等级确定抽题数量算法，根据每类题型的难度等级和抽题总量，确定不同难度等级试题的抽题数量。然后，利用基于随机数的抽题算法，在确定各类题型不同难度等级试题抽取数量的基础上，随机自动组卷。在组卷算法中随机数的生成采用了随机数生成算法。先根据期望的难度等级来组卷，避免了先组卷再判断难度等级，如不符合该难度再重新组卷的麻烦，节省了时间。
