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

杨勋

摘要：在现代教学活动当中，网络应用也将成为越来越普遍地一个重要的发展趋势。但是，在教学活动中的有一个重要环节就是考试，如何让一些课程的考试在网络中进行却是一个难题。其中，组卷算法更是考试系统能否设计成功的关键所在。自动组卷系统中组卷算法的好坏直接影响到组卷的效率和质量，所以如何选择一个高效、科学、强壮的算法是自动组卷的核心问题。该文详细介绍了目前经常使用的几种组卷算法。

关键词： 在线考试；自动组卷；组卷算法； 随机抽题；遗传算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）32-7621-03

Abstract：Modern social development is inseparable from Internet，Network application has increasingly become an important development trend in modern teaching activities. However， how to conduct examination on Internet is a difficult problem since it's an important procedure in teaching activities. And moreover， test paper composition algorithm is the key of online examination 's success. Test paper composition algorithm in system of automatic test paper construction can affect the efficiency and the quality of test paper composition.So， How to choose an efficient and scientific and strong algorithm is the core problem of automatic test paper composition.In this paper， some of test paper composition algorithm which are often used are introduced in detail.

Key words： online examination； automatic test paper composition； test paper composition algorithm； choosing questions at random； genetic algorithm

我们国家传统的各种类型考试，从开始生成试卷，印刷，然后安排考务，学生正式考试，收取试卷，再到阅卷，最后成绩发布，涵盖了诸多复杂的环节。这样造成整个工作量复杂而繁重，要消耗非常大的人力资源和物力资源。开发设计使用网络考试系统，可以使得考试没有这么多复杂繁重的环节，可以在各个试题库中抽取适当的试题来组成质量合格的试卷。这样组卷的效果好，比较灵活，并且节省了大量的成本。考试的知识点覆盖面也更加地广泛，可以全方位的对学生的学习效果进行比较全面的考察。此外，在线考试系统可以进行自动评分，这样可以有效地避免了人工统计分数过程中出现的差错问题，确保整个考试的公平和公正，大大降低了教师的工作量，提高了教学效率。在线考试系统具有自动化的程度高、稳定性好、评分快速、公正、准确，保密性高和便于组织大规模在线考试等优势。在线考试系统还可以对学生的考试成绩进行统计和分析，考察整个课程学生的学习效果，对教师的教学手段和方法的改进提供了良好的数据支持。

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

1 回溯试探法

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

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

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

2 随机抽题法

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

抽取试题的公

其实在现实的情况里，组卷要对题目的抽取有着某些特定的要求。那么怎样才能合理地使用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.HoUand教授第一次提出来的算法。此算法是模拟自然界的生物进化过程的自由随机搜索的方法，它是一种新型的优化算法。遗传算法利用比较简单的编码表示各式的复杂结构，而且用编码来表示一些遗传操作，再利用优胜劣汰的自然选择指导搜索方向。此算法是一种群体式的操作方式，把所有个体作为操作对象。它的三个主要操作运算分别是遗传、交叉、变异。进行完操作运算后下一代种群就保留了上一代的优良个体基因，体现出符合自然界规律的“自然选择、适者生存”的生存原则。

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

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

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

5 结束语

智能组卷算法是实现快速组卷、科学组卷的基本保障。如何组成试卷是在特定的多约束条件下的许多目标参数的如何组合优化问题。而这些约束条件用数学的方法很难进行描述，所以用传统的数学方法解决起来比较困难。该文详细介绍了在网络考试系统中常见的四种组卷算法，通过分析可以发现，遗传算法是比较适合网络考试系统采用的组卷算法，是最优化组卷最为合适的一种算法。

参考文献：

[1] 焦瑞，李祥生.试卷自动生成系统的设计与实现[J].山西医科大学学报，2005（4）.

[2] 王灿辉.计算机自动组卷算法研究[J].福州大学学报，2001（S1）.

[3] 李敏强，寇纪淞.遗传算法的基本理论与应用[M].北京：科学出版社，2002.

[4] 徐运玲.在线考试系统的设计与实现[J].科技信息，2010（9）.

[5] 文娴.试题库系统智能组卷与试卷分析的研究[D].长沙：湖南师范大学，2007.

[6] 刘亚琼.基于加强学习的自动组卷算法的研究[D].天津：天津大学，2006.

[7] 曾一，冉忠，郭永林.试题库中自动组卷的算法及试卷测评策略[J].计算机工程与设计，2006（16）.

[8] 武蕾娜.组卷算法的研究[J].福建电脑，2009（3）.

抽取试题的公

其实在现实的情况里，组卷要对题目的抽取有着某些特定的要求。那么怎样才能合理地使用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.HoUand教授第一次提出来的算法。此算法是模拟自然界的生物进化过程的自由随机搜索的方法，它是一种新型的优化算法。遗传算法利用比较简单的编码表示各式的复杂结构，而且用编码来表示一些遗传操作，再利用优胜劣汰的自然选择指导搜索方向。此算法是一种群体式的操作方式，把所有个体作为操作对象。它的三个主要操作运算分别是遗传、交叉、变异。进行完操作运算后下一代种群就保留了上一代的优良个体基因，体现出符合自然界规律的“自然选择、适者生存”的生存原则。

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

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

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

5 结束语

智能组卷算法是实现快速组卷、科学组卷的基本保障。如何组成试卷是在特定的多约束条件下的许多目标参数的如何组合优化问题。而这些约束条件用数学的方法很难进行描述，所以用传统的数学方法解决起来比较困难。该文详细介绍了在网络考试系统中常见的四种组卷算法，通过分析可以发现，遗传算法是比较适合网络考试系统采用的组卷算法，是最优化组卷最为合适的一种算法。

参考文献：

[1] 焦瑞，李祥生.试卷自动生成系统的设计与实现[J].山西医科大学学报，2005（4）.

[2] 王灿辉.计算机自动组卷算法研究[J].福州大学学报，2001（S1）.

[3] 李敏强，寇纪淞.遗传算法的基本理论与应用[M].北京：科学出版社，2002.

[4] 徐运玲.在线考试系统的设计与实现[J].科技信息，2010（9）.

[5] 文娴.试题库系统智能组卷与试卷分析的研究[D].长沙：湖南师范大学，2007.

[6] 刘亚琼.基于加强学习的自动组卷算法的研究[D].天津：天津大学，2006.

[7] 曾一，冉忠，郭永林.试题库中自动组卷的算法及试卷测评策略[J].计算机工程与设计，2006（16）.

[8] 武蕾娜.组卷算法的研究[J].福建电脑，2009（3）.

抽取试题的公

其实在现实的情况里，组卷要对题目的抽取有着某些特定的要求。那么怎样才能合理地使用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.HoUand教授第一次提出来的算法。此算法是模拟自然界的生物进化过程的自由随机搜索的方法，它是一种新型的优化算法。遗传算法利用比较简单的编码表示各式的复杂结构，而且用编码来表示一些遗传操作，再利用优胜劣汰的自然选择指导搜索方向。此算法是一种群体式的操作方式，把所有个体作为操作对象。它的三个主要操作运算分别是遗传、交叉、变异。进行完操作运算后下一代种群就保留了上一代的优良个体基因，体现出符合自然界规律的“自然选择、适者生存”的生存原则。

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

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

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

5 结束语

智能组卷算法是实现快速组卷、科学组卷的基本保障。如何组成试卷是在特定的多约束条件下的许多目标参数的如何组合优化问题。而这些约束条件用数学的方法很难进行描述，所以用传统的数学方法解决起来比较困难。该文详细介绍了在网络考试系统中常见的四种组卷算法，通过分析可以发现，遗传算法是比较适合网络考试系统采用的组卷算法，是最优化组卷最为合适的一种算法。

参考文献：

[1] 焦瑞，李祥生.试卷自动生成系统的设计与实现[J].山西医科大学学报，2005（4）.

[2] 王灿辉.计算机自动组卷算法研究[J].福州大学学报，2001（S1）.

[3] 李敏强，寇纪淞.遗传算法的基本理论与应用[M].北京：科学出版社，2002.

[4] 徐运玲.在线考试系统的设计与实现[J].科技信息，2010（9）.

[5] 文娴.试题库系统智能组卷与试卷分析的研究[D].长沙：湖南师范大学，2007.

[6] 刘亚琼.基于加强学习的自动组卷算法的研究[D].天津：天津大学，2006.

[7] 曾一，冉忠，郭永林.试题库中自动组卷的算法及试卷测评策略[J].计算机工程与设计，2006（16）.

[8] 武蕾娜.组卷算法的研究[J].福建电脑，2009（3）.