基于贪心算法的在线形成性考核系统组卷研究

摘　要：作业和测试的自动组卷是在线形成性考核系统的核心内容。本文在深入研究贪心算法的基础上，提出了基于贪心算法的自动组卷算法，分析了题库和作业库的约束条件，实现了快速高效的组卷过程。最后给出具体实例加以论证。该算法已经成功应用于实际的在线形成性考核系统中。

关键词：贪心算法；在线形成性考核；约束条件；组卷
一、引言
　　目前，常用的自动组卷算法有随机选取算法、回溯试探算法、蛮力法和遗传算法等，这些算法对在线考试系统确实具有一定的应用价值，但这些方法生成的作业卷和测试卷在试卷的科学性和合理性上考虑较少。在综合研究以上各种算法的优缺点后，保证达到较好时间效率和空间效率的基础上，采用贪心算法为核心和随机选取算法为辅助的组卷算法，应用于在线形成性考核系统在线作业和在线测试中，能够达到较好的组卷效果，并且达到教学辅助效果。决定组卷效率和作业卷质量的主要因素有两个：一是题库和作业库的结构；二是组卷算法的设计。
二、贪心算法简介
　　贪心算法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个全局的最优解。贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
　　贪心算法的基本要素。一是贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。二是最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。在题库组卷问题中，其最优子结构性质表现为：若A是对于E的题库组卷问题包含试题1的一个最优解，则相容作业卷集合A′= A-{1}是对于E′= {i∈E：si≥f1}的题库组卷问题的一个最优解。
三、基于贪心算法的在线形成性考核系统组卷算法
　　1、在线形成性考核系统结构
　　在线形成性考核是指对学生学习过程的测评，是对学生课程学习的阶段性考核，是加强教学过程管理、检验学习效果的重要措施。在该系统中，管理员模块主要负责数据导入导出和系统维护，按照学生的课程注册信息绑定学生的班级、课程、辅导教师及恢复误删除成绩；教师模块完成课程形成性考核方案设计，作业题设计，查询考核内容，作业管理，作业批阅，查询批阅结果，删除已批阅但学生要求重做的作业成绩，学生信息管理，查询作业完成情况，到课率录入；学生模块主要功能是查看形考方案、主持教师、辅导教师、导学教师，在线作业，在线测试，作业成绩及反馈查询。在线形成性考核系统结构如图1所示。
                 
    图1  在线形成性考核系统结构
　　2、题库设计
　　首先需要确定的是试题组织的方式。为了保证达标原则、全面性原则和主要性原则，最好将试题库与具体的知识内容进行关联，也即以课程知识点为核心组织试题库。然后就要考虑试题本身固有的特性参数，主要有题型、试题内容、答案、难度系数等。难度系数是试题难易程度的指标，也是试卷生成中的一个重要参数，它可以由教师录入试题时给定，并且在同一门课程中要坚持相同的标准，并且难度标准初始设定时要充分考虑到所要测试学生的程度范围。难度系数一般用等级来表示, 在五级难度系数中, 一级难度为最低, 五级难度为最高。题型分为客观题和主观题。客观题分单项选择题、多项选择选、判断题和填空题，主观题分计算题、简答题和论述题。
　　3、作业库设计
　　组卷方式可以按需求由主持老师进行客观题和主观题自由组卷。客观题在学生完成并提交成功后，系统自动阅卷并给出成绩。主观题在学生完成并提交后，由辅导老师阅卷并给出成绩。学生完成作业后如没把握，请不要提交，如提交确认后则不能重做。学生有成绩后要重做的，可以向辅导老师提出重做申请，辅导老师同意后，删除已取得的成绩即可。辅导老师删除学生成绩的记录将保留在系统，用于误删除成绩的恢复和保留删除痕迹。作业卷生成工作完成之后，将其保存入作业库中。
　　4、组卷的约束条件
    一是知识点约束。因为教学中的知识点一般与教材的章节内容对应，所以知识点约束可以看作章节范围约束。知识点约束还包括各章节在总试卷中所占的分值比例。
    二是题型约束。题型约束是指试卷中包含的试题类型，即以何种类型的试题组卷测试。
    三是题量约束。题量约束是指试卷中包含的试题的多少，具体到每一个题型，就是指每一题型中试题数量。该约束与答题时间约束呈正相关性。
    四是答题时间约束。答题时间约束是指完成解答试卷中所有试题所用的最长时间。一般情况下，答题时间约束长的试卷题量相对较大。若作业或测试的答题时间计算总和为90分钟，考虑网络延时，我们可以适当放宽到120分钟。
　　五是难度约束。难度约束是指试卷的总体难度系数，对于不同课程的作业，选定不同的难度，该约束的选择还应与曝光度约束相配合使用才能达到较好的效果。假设难度约束为1到5，分为5个等级。若作业或测试卷难度为5，则先选择难度为5的各种类型题目，题数不够，则选择难度为4的各种类型题目，次之选择难度为4的各种类型题目，依次类推。
    六是曝光度约束。曝光度约束是指试卷中试题曾经被考过次数多少的量，试卷中试题曾被考过的次数愈多，该试题曝光度就愈大。一般要求试卷曝光度值越小越好，以保证试题的保密性和有效性。对于作业，结合难度约束，选择曝光度值中进行组合。
　　5、贪心算法组卷思路
　　根据贪心算法和随机算法，在线形成性考核系统的自动组卷算法的基本思路如下：
　　一是建立数学模型来描述问题。计算机自动组卷过程为在一定题量的试题库中搜索满足组卷目标要求的一组属性试题组合。自动组卷的实质是求目标状态矩阵的解，行数代表所需试卷的试题数，列数为所需的用以确定试卷质量或知识内容的约束 的数量。
　　二是把求解的问题分成若干个子问题。在自动组卷过程中，先根据题型分解，求得某一种题型的所有题目的子问题。在求得某一种题型的所有题目的问题时，根据题量、章节比例、难度约束和曝光度分解，求得某章节的某一种题型的所有题目的子问题。
　　三是对每一子问题求解，得到子问题的局部最优解。在对每一子问题求解时，尽可能符合矩阵中的所有约束条件，做到每一个子问题最优解。在每一个字问题解的过程中，必须采用随机算法，这里所谓的最优解不是唯一的。
　　四是把子问题的解局部最优解合成原来解问题的一个解。因为做到每一个字问题最优解，所以合成解也因该是解空间中一个最优解，但不是唯一最优解。
四、贪心算法实现
　　1、实验设计
　　为了检验贪心算法的正确性和效率，这里的效率指的是两种算法效率：时间效率和空间效率。时间效率指的是贪心算法运行有多快；空间效率指的是贪心算法需要的额外存储空间。随着计算机技术、互联网络技术和大容量存储技术的发展，一个算法所需要的额外存储空间已不是现在关注的重点问题，但时间效率却有进一步加强的迹象。因此，在线形成性考核组卷算法主要考虑贪心算法的正确性和时间效率。
　　在线形成性考核系统实验服务器为IBM3650，系统为Windows2003 Server + .NET 2.0 + C#，数据库Microsoft SQL Server 2005。在不同的题量比例、难度系数、知识点、题型、题量的条件下，实验设计题量倍数比例为1、2、5、10，难度系数为1、2、3、4、5，知识点为第1章、第1章至第2章、第1章至第3章、第1章至第4章、第1章至第5章，题型1为客观题，题型2客观题加主观题，题量1为25题，题量2为50题。根据流程图2共自动组卷了400次，分别记录组卷时间、答题时间误差和成功率。
　　2、实验数据统计
　　根据实验数据统计，基于贪心算法的组卷统计表情况如表1所示。表3说明，贪心算法运用在在线形成性考核系统是正确的，时间效率是稳定的，适合在线作业组卷和在线测试组卷。
表1　基于贪心算法的自动组卷统计表
题量比例难度系数知识点(章)题型题量答题时间误差组卷时间(s)成功率11-51-51、225、50021-51-51、225、5032%0.835100%51-51-51、225、5015%1.128100%101-51-51、225、5012%1.262100%…10%左右<1.500100%五、结束语
　　在线作业和在线测试是基于互联网的开放式教学平台中的一个重要组成部分，其组卷质量将直接影响学生平时学习质量评价和教学平台质量评价。基于贪心算法的组卷，具有一定的客观性、准确性和可靠性。该算法简单高效，服务器负担轻，网络时延少，适用性强。现已应用在某省电大的在线形成性考核系统中，也可应用于一般院校的在线作业和在线测试平台。
参考文献：
[1] 张因奎等.数据挖掘原理[M].北京:机械工业出版社, 2003:152-157
[2] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社, 2007:214-226
[3] 潘彦译.算法设计与分析基础[M].北京:清华大学出版社,2007:233-254
[4] 王晓东.计算机算法设计与分析[M]. 北京:电子工业出版社, 2001:83-110
[5] 肖洋,王骁等.在线考试组卷算法研究.北京化工大学学报[J],2006.33(4):53-54
[6] 曾一等.试题库中自动组卷的算法及试卷测评策略[J].计算机工程与设计,2006.27(16):3024-3027
[7] 王雍钧等.基于知识点题型分布和分值的智能组卷算法研究[J].计算机应用与软件,2004.21(8):111-113