论文部分内容阅读
[摘要]针对非计算机专业C语言程序设计自动组卷中的几个问题，提出了解决方案，包括试题库的建库和维护原则，试卷的生成策略，以及采用遗传算法进行自动组卷的编码方案等问题。对传统的遗传算法进行了改进，基于十进制编码，使编码长度大大减少，并基于矩阵进行遗传操作，利用先验信息，使收敛速度加快。
[关键词]自动组卷 试题库 遗传算 十进制编码 矩阵编码
一、引言
目前C 语言仍然是国内外广泛使用的一种现代语言。C 语言不仅是计算机专业学生的必修课，同时也是理工科非计算机专业学生的必修课程[1]。
在我国高校，传统的学生成就测验方法和量化研究方法在教学活动中仍然占主导地位，因此生成公正、公平、合理的试卷就是很重要的教学活动了。同时，这也是国家在改变教育评价体系过程中非常重要的一环[2]。
二、试题库的建立和完善
建立试题库是自动生成试卷的必要前提，试题库应保证科学、有效、稳定、保密[3]。在建设一个成熟、完善的试题库之前，要保证提供成熟、稳定、明确的考试大钢，收集足够的试题来源，提供明确的分值分配原则和题型分配原则，并且提供合理的难度系数分配原则。建立C语言程序设计基础试题库的步骤可以分为以下四步。
1.命题规划
试题库的建设要建立在教育测量学原理的理论基础上，设计合理的题型。C语言程序设计试题库的题型包括客观性题目（包括单选题、判断题、填空题等）和主观性题目（包括编程题等）。每一个题目要确定难度和区分度等指标，在章节知识点、能力层次、难度水平及题型等主要方面分布要合理，而且要有足够数量的题目[4]。一般说来，题库中题目的总数量达到试卷题量的30倍以上是较为合适的。题目的难度级别可以按照认知目标进行分类，按照识记、理解判断、掌握应用三个层次来评定难度级别，分为易、较易、中等、较难、难。C语言程序设计试题库要涵盖教学大纲要求掌握的全部知识的80%以上，而且各个单元、各个题型的题目数量要形成一定的比例关系，使得章节比例分布和试卷的总体难度有合适的把握，保证考核的全面性、公平性、公正性。
依据上述的命题规划原则，每个试题包含7个属性参数：(1)知识范围，试题内容所属的知识层次范围；(2)题型；(3)题分；(4)认知分类，反映该题对教学内容的要求层次；(5)难度系数；(6)区分度；(7)估计答题时间。
2.试题采编及入库
采编试题过程可分为两步：先将试题数据信息存储于试题表中，然后进行试题属性参数的初始设定。在生成试卷过程中，课程专家组审阅试卷时可修改试题属性参数以符合考核要求。并且在考卷分析过程中，通过分析考生的实际考核效果，对试题的属性参数进行修正，进一步优化试题库。
系统应该允许试题在任意文本编辑器中进行试题录入，也允许多人对同一门课程的试题同时录入，只要按规定要求每题加上参数属性，以rtf、doc、txt文件存放，就可进行文档自动转换，转换到试题库系统中。
3.统计分析
为了更好地考查教学效果，分析所有考生的答卷并统计相关数据。统计分析可以分为细目统计和总体分析。（1）细目统计：对答案的每道试题的答题结果进行统计，主要的统计项目为：得分区间、正确率、得分率等。得分率是确定试题难度系数的主要依据。（2）总体分析：从所有考生答卷所涵盖整个课程的知识点角度进行统计分析，并对所有考生的考试成绩做出统计和评价。主要的统计项目可以包括：章节、知识点的得分率，可以为教学计划调整（如教学难点、重点、课时修正等）提供数据参考；成绩分布，考查成绩是否符合正态分布；平均成绩，可用于衡量考卷的预定义难度系数与考核后实际难度的误差。若误差范围小于0.1，则认为生成的试卷是合理的。
4.动态维护
经历一段较长的时间后，题库一般要做以下维护工作：不合时宜的题目应该被删除；重新调整题目的难度、区分度等统计参数；将反映新颖的知识的题目添加进去。
三、试卷生成策略
1.目标函数
在试卷生成过程中，先将满足曝光度的试题存入临时表中，然后在临时表中生成试卷。试卷必须满足用户指定的总体要求，也就是：各篇章所占的分数pz、试卷中各种题型的题数tx、反映不同教学层次要求的试题所占的分数比例rz、各种难度的试题所占的分数比例nd、各种区分度的试题所占的分数比例qfd、所有试题的估时总和sj、所有试题的分数总和fs这7个指标都应等于用户指定的要求，或者误差最小。
在实际应用中，设定试卷指标f来综合反映这7个指标与用户要求的误差，由于它们的重要程度不同，因此试卷的指标定义为7个指标的加权和，同时为了不至于各个误差相互抵消，这7个指标与用户要求的误差都取绝对值。可以用式(1)表示：
(1)
其中fi表示第i个指标与用户要求的误差的绝对值，wi表示第i个指标的权值。f值越小，越接近组卷的理想情况。可以设定为：
(2)
遗传算法的适应度函数fitness可以与f一致，认为小的值是好的适应度，也可以使fitness=1/(1+f)，认为适应度函数大的是好的个体。然后使用不同的试卷生成策略来满足试卷要求。
2.组卷策略
目前，常用的自动生成试卷方法有三种：基于随机抽取的试卷生成算法，这种算法的试卷成功率低，并且时间开销大；回溯试探法试卷生成算法，使用这种算法虽然使试卷性能得到了提高，但是内存的占用量大，程序结构比较复杂，而且选取试题缺乏随机性，试卷生成时间长；基于遗传算法的试卷生成算法，这种算法是比较合适的，因为组卷问题实际上是一个多重约束下寻最优解的问题，而遗传算法正好可以提供比较合适的解决方案[5][6][7]。
四、试卷生成系统中遗传算法的编码方案
遗传算法的编码方案是遗传算法进行遗传操作的基础。试卷生成系统中，常见的遗传算法编码方案有：基于二进制的编码方法，基于十进制的编码方法，基于矩阵的编码方法。本文提出了一种改进的遗传算法的编码方法，可以大大减少码长，减少空间复杂度，并且利用先验信息，较快地收敛到最佳解。
1.基于二进制的编码方法
假设试题库中总共有m道题，用x1，x2，…，xm表示，那么试卷就是从中选出n道题，使得生成的试卷指标f最小。在此，用一个m位的二进制串来表示问题解。形式为F1F2…Fm。如果Fi为l，则表示该题被选中，若为0，则表示该题未被选中。假设该套试卷要求有n道试题，则F1F2…Fm串中有n个l。
在计算个体的适应度函数时，先进行解码，得到每个试题的7个属性参数，放到一个矩阵s中：
(3)
其中sij表示第i道题的第j个属性。然后计算各个属性值的误差，得到适应度函数。
先产生初始种群，然后按照一定的概率进行交叉和变异。交叉和变异的过程中，可能会出现非法解的情况，例如：F1F2…Fm串中1的个数可能会超过n个，必须加以修正。
2.基于十进制的编码方法
基于十进制的编码方法是由不同类型的试题编号组合而成。每一类型的试题编号长度由该类型试题数量确定。例如:试题库中要求的各题型的试题量为选择题300，判断题150，填空题50，则每种类型编码范围分别为0～299、0～149、0～49，编码长度分别为3位、3位和2位。
假设生成试卷的题型分布为选择题50道、判断题20道、填空题10道，则每套试卷的染色体编码长度为3*50+3*20+2*10=230位。染色体的组合形式如图1所示：
图1：染色体编码形式
计算个体的适应度函数时，将相应题号的参数属性写入矩阵s中，这样矩阵的规模会大大地减少。
在进行交叉和变异的过程中，也可能会出现非法解的情况，例如：出现的题号非法，是试题库中没有的编号；出现重码。
3.基于矩阵的编码方法
基于矩阵的编码方法采用的是将遗传操作直接在属性参数矩阵中进行。将题库中每道题的属性参数存入矩阵s中，生成初始种群时，先按照知识范围、题型、题分来满足要求[8]。生成试卷时，由于满足前3个属性要求的题目容易得到，那么为了满足其他的要求，误差会出现在难度、区分度、认知分类、估计答题时间这4个属性上。所以，遗传操作所要的工作就是匹配这4个属性。因此，在进行交叉操作时，交换两个父本的第(3+random(4))(random(4)指的是从0到3的自然数中随机取一个)以后的列，否则，直接复制两个父本。通过互换可以达到全局搜索的目的。在进行变异时，从候选解(试卷参数矩阵s)中随机选一行，根据这一行第二列的值得到题型属性，然后从题库中选取另外一道同题型的试题的属性取代候选解的这一行。通过变异算子可以达到局部搜索的目的。这种方法达到最优解的迭代次数明显小于基于二进制的编码方法。
4.改进的遗传策略
在上述编码策略中，基于二进制编码和基于矩阵的编码方法，码长都比较长，因为编码方案是基于题库规模大小的。基于十进制的编码方法的码长虽然明显减少，但是解决非法解的问题时比较麻烦。改进的遗传策略是基于十进制编码，但是交叉和变异操作在矩阵s中进行，此时矩阵s的规模由生成试卷的规模决定，这样所需的内存空间将大大减少。生成初始种群时，利用先验信息，生成能满足知识范围、题型、题分的要求的试题，再在此基础上在矩阵s中进行交叉和变异。在进行交叉和变异操作时，采用自适应的方式，当适应度值低于平均适应度值时，说明该个体是性能不好的个体，采用较大的交叉率和变异率；如果适应度值高于平均适应度值，说明该个体性能优良，因而根据其适应度值取较小的交叉率和变异率。采用先验知识，减少了自适应函数的参数个数，从而减少遗传算法求解的收敛速度，可以较快地得到结果，因此能够适应于网络考试环境。
[参考文献]
[1]郭晓俐,汤克明.研究性教学模式在C语言教学中的实施[J],计算机教育,2010,(2).
[2]新华网.戴家干:国家级题库预计5年内完成[EB/OL].2007.4.18. http://news.xinhuanet.com/edu/2007-04/18/content_5992723.htm.
[3]唐自力.网上在线命题、出题及试题库系统[D].电子科技大学,硕士论文,2007.
[4]向华,万富明.试题库研制中的几个问题[J],医学教育探索,2010,(10).
[5]虞耀君,陈君,李靖.基于遗传算法的网络考试系统[J],计算机仿真, 2010,(6).
[6]肖连,崔杜武.基于遗传算法的试卷生成系统的设计与实现[J],计算机应用,2008,28(5).
[7]黄宝玲.自适应遗传算法在智能组卷中的应用[J],计算机工程,2011, 37(14).
[8]余胜泉,何克抗.网络题库系统的设计与实现[J],中国远程教育,2000, (164).
（作者单位：武汉科技大学计算机科学与技术学院 武汉）
[关键词]自动组卷 试题库 遗传算 十进制编码 矩阵编码
一、引言
目前C 语言仍然是国内外广泛使用的一种现代语言。C 语言不仅是计算机专业学生的必修课，同时也是理工科非计算机专业学生的必修课程[1]。
在我国高校，传统的学生成就测验方法和量化研究方法在教学活动中仍然占主导地位，因此生成公正、公平、合理的试卷就是很重要的教学活动了。同时，这也是国家在改变教育评价体系过程中非常重要的一环[2]。
二、试题库的建立和完善
建立试题库是自动生成试卷的必要前提，试题库应保证科学、有效、稳定、保密[3]。在建设一个成熟、完善的试题库之前，要保证提供成熟、稳定、明确的考试大钢，收集足够的试题来源，提供明确的分值分配原则和题型分配原则，并且提供合理的难度系数分配原则。建立C语言程序设计基础试题库的步骤可以分为以下四步。
1.命题规划
试题库的建设要建立在教育测量学原理的理论基础上，设计合理的题型。C语言程序设计试题库的题型包括客观性题目（包括单选题、判断题、填空题等）和主观性题目（包括编程题等）。每一个题目要确定难度和区分度等指标，在章节知识点、能力层次、难度水平及题型等主要方面分布要合理，而且要有足够数量的题目[4]。一般说来，题库中题目的总数量达到试卷题量的30倍以上是较为合适的。题目的难度级别可以按照认知目标进行分类，按照识记、理解判断、掌握应用三个层次来评定难度级别，分为易、较易、中等、较难、难。C语言程序设计试题库要涵盖教学大纲要求掌握的全部知识的80%以上，而且各个单元、各个题型的题目数量要形成一定的比例关系，使得章节比例分布和试卷的总体难度有合适的把握，保证考核的全面性、公平性、公正性。
依据上述的命题规划原则，每个试题包含7个属性参数：(1)知识范围，试题内容所属的知识层次范围；(2)题型；(3)题分；(4)认知分类，反映该题对教学内容的要求层次；(5)难度系数；(6)区分度；(7)估计答题时间。
2.试题采编及入库
采编试题过程可分为两步：先将试题数据信息存储于试题表中，然后进行试题属性参数的初始设定。在生成试卷过程中，课程专家组审阅试卷时可修改试题属性参数以符合考核要求。并且在考卷分析过程中，通过分析考生的实际考核效果，对试题的属性参数进行修正，进一步优化试题库。
系统应该允许试题在任意文本编辑器中进行试题录入，也允许多人对同一门课程的试题同时录入，只要按规定要求每题加上参数属性，以rtf、doc、txt文件存放，就可进行文档自动转换，转换到试题库系统中。
3.统计分析
为了更好地考查教学效果，分析所有考生的答卷并统计相关数据。统计分析可以分为细目统计和总体分析。（1）细目统计：对答案的每道试题的答题结果进行统计，主要的统计项目为：得分区间、正确率、得分率等。得分率是确定试题难度系数的主要依据。（2）总体分析：从所有考生答卷所涵盖整个课程的知识点角度进行统计分析，并对所有考生的考试成绩做出统计和评价。主要的统计项目可以包括：章节、知识点的得分率，可以为教学计划调整（如教学难点、重点、课时修正等）提供数据参考；成绩分布，考查成绩是否符合正态分布；平均成绩，可用于衡量考卷的预定义难度系数与考核后实际难度的误差。若误差范围小于0.1，则认为生成的试卷是合理的。
4.动态维护
经历一段较长的时间后，题库一般要做以下维护工作：不合时宜的题目应该被删除；重新调整题目的难度、区分度等统计参数；将反映新颖的知识的题目添加进去。
三、试卷生成策略
1.目标函数
在试卷生成过程中，先将满足曝光度的试题存入临时表中，然后在临时表中生成试卷。试卷必须满足用户指定的总体要求，也就是：各篇章所占的分数pz、试卷中各种题型的题数tx、反映不同教学层次要求的试题所占的分数比例rz、各种难度的试题所占的分数比例nd、各种区分度的试题所占的分数比例qfd、所有试题的估时总和sj、所有试题的分数总和fs这7个指标都应等于用户指定的要求，或者误差最小。
在实际应用中，设定试卷指标f来综合反映这7个指标与用户要求的误差，由于它们的重要程度不同，因此试卷的指标定义为7个指标的加权和，同时为了不至于各个误差相互抵消，这7个指标与用户要求的误差都取绝对值。可以用式(1)表示：
(1)
其中fi表示第i个指标与用户要求的误差的绝对值，wi表示第i个指标的权值。f值越小，越接近组卷的理想情况。可以设定为：
(2)
遗传算法的适应度函数fitness可以与f一致，认为小的值是好的适应度，也可以使fitness=1/(1+f)，认为适应度函数大的是好的个体。然后使用不同的试卷生成策略来满足试卷要求。
2.组卷策略
目前，常用的自动生成试卷方法有三种：基于随机抽取的试卷生成算法，这种算法的试卷成功率低，并且时间开销大；回溯试探法试卷生成算法，使用这种算法虽然使试卷性能得到了提高，但是内存的占用量大，程序结构比较复杂，而且选取试题缺乏随机性，试卷生成时间长；基于遗传算法的试卷生成算法，这种算法是比较合适的，因为组卷问题实际上是一个多重约束下寻最优解的问题，而遗传算法正好可以提供比较合适的解决方案[5][6][7]。
四、试卷生成系统中遗传算法的编码方案
遗传算法的编码方案是遗传算法进行遗传操作的基础。试卷生成系统中，常见的遗传算法编码方案有：基于二进制的编码方法，基于十进制的编码方法，基于矩阵的编码方法。本文提出了一种改进的遗传算法的编码方法，可以大大减少码长，减少空间复杂度，并且利用先验信息，较快地收敛到最佳解。
1.基于二进制的编码方法
假设试题库中总共有m道题，用x1，x2，…，xm表示，那么试卷就是从中选出n道题，使得生成的试卷指标f最小。在此，用一个m位的二进制串来表示问题解。形式为F1F2…Fm。如果Fi为l，则表示该题被选中，若为0，则表示该题未被选中。假设该套试卷要求有n道试题，则F1F2…Fm串中有n个l。
在计算个体的适应度函数时，先进行解码，得到每个试题的7个属性参数，放到一个矩阵s中：
(3)
其中sij表示第i道题的第j个属性。然后计算各个属性值的误差，得到适应度函数。
先产生初始种群，然后按照一定的概率进行交叉和变异。交叉和变异的过程中，可能会出现非法解的情况，例如：F1F2…Fm串中1的个数可能会超过n个，必须加以修正。
2.基于十进制的编码方法
基于十进制的编码方法是由不同类型的试题编号组合而成。每一类型的试题编号长度由该类型试题数量确定。例如:试题库中要求的各题型的试题量为选择题300，判断题150，填空题50，则每种类型编码范围分别为0～299、0～149、0～49，编码长度分别为3位、3位和2位。
假设生成试卷的题型分布为选择题50道、判断题20道、填空题10道，则每套试卷的染色体编码长度为3*50+3*20+2*10=230位。染色体的组合形式如图1所示：
图1：染色体编码形式
计算个体的适应度函数时，将相应题号的参数属性写入矩阵s中，这样矩阵的规模会大大地减少。
在进行交叉和变异的过程中，也可能会出现非法解的情况，例如：出现的题号非法，是试题库中没有的编号；出现重码。
3.基于矩阵的编码方法
基于矩阵的编码方法采用的是将遗传操作直接在属性参数矩阵中进行。将题库中每道题的属性参数存入矩阵s中，生成初始种群时，先按照知识范围、题型、题分来满足要求[8]。生成试卷时，由于满足前3个属性要求的题目容易得到，那么为了满足其他的要求，误差会出现在难度、区分度、认知分类、估计答题时间这4个属性上。所以，遗传操作所要的工作就是匹配这4个属性。因此，在进行交叉操作时，交换两个父本的第(3+random(4))(random(4)指的是从0到3的自然数中随机取一个)以后的列，否则，直接复制两个父本。通过互换可以达到全局搜索的目的。在进行变异时，从候选解(试卷参数矩阵s)中随机选一行，根据这一行第二列的值得到题型属性，然后从题库中选取另外一道同题型的试题的属性取代候选解的这一行。通过变异算子可以达到局部搜索的目的。这种方法达到最优解的迭代次数明显小于基于二进制的编码方法。
4.改进的遗传策略
在上述编码策略中，基于二进制编码和基于矩阵的编码方法，码长都比较长，因为编码方案是基于题库规模大小的。基于十进制的编码方法的码长虽然明显减少，但是解决非法解的问题时比较麻烦。改进的遗传策略是基于十进制编码，但是交叉和变异操作在矩阵s中进行，此时矩阵s的规模由生成试卷的规模决定，这样所需的内存空间将大大减少。生成初始种群时，利用先验信息，生成能满足知识范围、题型、题分的要求的试题，再在此基础上在矩阵s中进行交叉和变异。在进行交叉和变异操作时，采用自适应的方式，当适应度值低于平均适应度值时，说明该个体是性能不好的个体，采用较大的交叉率和变异率；如果适应度值高于平均适应度值，说明该个体性能优良，因而根据其适应度值取较小的交叉率和变异率。采用先验知识，减少了自适应函数的参数个数，从而减少遗传算法求解的收敛速度，可以较快地得到结果，因此能够适应于网络考试环境。
[参考文献]
[1]郭晓俐,汤克明.研究性教学模式在C语言教学中的实施[J],计算机教育,2010,(2).
[2]新华网.戴家干:国家级题库预计5年内完成[EB/OL].2007.4.18. http://news.xinhuanet.com/edu/2007-04/18/content_5992723.htm.
[3]唐自力.网上在线命题、出题及试题库系统[D].电子科技大学,硕士论文,2007.
[4]向华,万富明.试题库研制中的几个问题[J],医学教育探索,2010,(10).
[5]虞耀君,陈君,李靖.基于遗传算法的网络考试系统[J],计算机仿真, 2010,(6).
[6]肖连,崔杜武.基于遗传算法的试卷生成系统的设计与实现[J],计算机应用,2008,28(5).
[7]黄宝玲.自适应遗传算法在智能组卷中的应用[J],计算机工程,2011, 37(14).
[8]余胜泉,何克抗.网络题库系统的设计与实现[J],中国远程教育,2000, (164).
（作者单位：武汉科技大学计算机科学与技术学院 武汉）