智能组卷系统的核心算法比较

姚玉阁

（集宁师范学院计算机系，内蒙古 乌兰察布 012000）

智能组卷系统的核心算法比较

姚玉阁

（集宁师范学院计算机系，内蒙古 乌兰察布 012000）

从目前考试改革的进程看，考试将逐渐向人性化、自动化过渡，通过计算机进行智能组卷是其中的关键技术，而要得到优质的试卷不仅要建立合理的数学模型，还要有高效的组卷算法。该文将选用几种常用智能算法进行分析比较，力求找到一个能够提高组卷成功率，取得满意组卷效果的最优算法。

试题库；智能组卷；遗传模拟退火算法

1、前言

随着计算机辅助教学 （Computer Assistant Instruction-CAI）在高等教育的普及，无纸化考试、远程网络在线考试等机考已经成为高校的新宠。机考的基础是智能组卷系统，所谓智能组卷系统，是将传统的、优秀的组卷知识和经验与计算机智能技术结合起来，由计算机来完成试卷内容的设计，且保证所生成的试卷是高质量的。组卷算法是实现智能组卷系统的核心技术。为了开发一个能够生成具有较好的信度和效度的优质试卷的智能组卷系统，不但要有高质量的试题库，而且更重要的是所采取组卷算法的合理性。目前，国内有关组卷算法的文章也比较多，大多数都是针对随机抽取算法[1]、模拟退火算法、遗传算法和遗传模拟退火算法等几大常用算法进行研究，各钟算法都有优缺点。本文主要从这几种常用算法入手，逐个进行分析比较，通过实验比较选出哪些算法最适合在组卷系统中使用。

2、常用组卷算法

2.1 随机算法

随机算法（Randomized Algorithm，RA）的起源可追溯到20世纪40年代，由Monte Carlo在进行数值计算时提出的。将随机算法应用在组卷中又叫做随机抽取算法，首先初始化随机抽取的约束条件，随机抽取次数、试题包含的题型以及试题总量等，从给定的试题库中随机抽取满足约束条件的试题，并加入到试卷中，不断重复此抽取过程，直到整套试卷抽取完成或提示无法按约束条件完成组卷。如果随机抽取成功，再用给定的试卷评价函数进行评价，如果评价函数值在允许范围内，组卷成功，否则组卷失败。该算法较容易实现，虽然抽取单个试题的速度很快，但是依照评价函数进行整套试卷的抽取其成功率较低，如果约束条件复杂组卷更难成功。

2.2 模拟退火算法

模拟退火算法（Simulated Annealing，SA）是由N.Metropolis根据固体退火原理首先提出的[2]。其原理是模拟将固体升温及降温的过程，在固体逐渐加热时，固体内部粒子随着温度的升高逐渐变为无序的状态，并且内能增大，当温度达到足够高时，再让其徐徐冷却，固体内部粒子逐渐趋于有序，最后在常温时恢复常态。根据Metropolis准则， 粒子在温度 T时趋于平衡的概率为 e-ΔE/（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数[3]。把固体退火原理应用在组合优化问题中，将组合优化问题中的目标函数值f和控制参数t分别模拟成退火原理中的内能E和温度T，也就得到模拟退火算法的原型了，具体步骤如下:

（1）给定初始值：初始温度T，迭代次数L和初始模型 P0，并计算得到 P0的目标函数值 E（P0）;

（2）通过扰动产生新的模型P1，计算其目标函数值E（P1），并产生增量ΔE=E（P1）-E（P0）；

（3）if ΔE<0 P0=P1Else P1以概率

P=exp（-ΔE/T） 进行接受，T为温度;

（4）在温度T下，重复步骤（2）和（3），直至 L次;

（5）给T缓慢降温;

（6）重复步骤（2）至（5），直至满足收敛条件为止。

模拟退火算法是一种通用的、高效的、健壮的优化算法，并且可以通过并行实现来进一步提高运行效率。模拟退火算法的主要不足是得到一个最优解的时间花费较多，并且随着问题规模的不断增大，难于承受的运行时间将使算法丧失可行性[4]。

2.3 遗传算法

遗传算法（Genetic Algorithm，GA）[5-6]是由美国的J.Holland教授于1975年根据生物界优胜劣汰、适者生存的遗传法则提出的概率性寻优方法。遗传算法的应用原理主要是根据问题的解产生初始种群，初始种群是由根据二进制编码产生的带有特征的一组染色体个体组成。初始种群生成之后，根据优胜劣汰、适者生存的生物遗传原理，每一代根据个体的适应度大小搜索最优的个体，并在演化的过程中，每一代个体通过自然遗传学的遗传算子进行组合交叉和变异，产生下一代种群。在整个演化过程中将使种群像自然界遗传进化一样，每一个新的一代会更适应环境，最后一代的最优个体，就是我们寻找到的最优解。遗传算法的基本运算过程如下：

（1）生成初始种群，设置最大进化代数等初始化设置；

（2）计算每个个体的适应度；

（3）根据个体的适应度产生选择算子，选择优化的个体形成新的中间种群；

（4）通过交叉算子对中间种群进行交叉组合运算，即将被选中的若干对个体的基因链按某一概率进行交叉运算，生成新的个体；

（5）通过变异算子对中间种群进行变异运算，即对个体的基因链的各位按某一概率进行变动生成新的个体。中间种群经过选择、交叉、变异运算之后得到下一代新生种群；

（6）重复步骤（2）至（5），直至达到最大进化代数T，并输出具有最大适应度的个体作为最优解。

遗传算法从初始种群开始搜索，搜索覆盖面广，利于全局寻优；遗传算法是对多个个体同时进行的评估和操作，使搜索陷入局部最优的风险大大降低了；并且遗传算法可以进行分布式计算，从而加快求解速度。但是由于遗传算法较差的局部搜索能力，导致算法在执行过程中比较消耗时间，尤其在进化后期搜索时效率较低。早熟收敛是遗传算法在实际应用中较容易出现的问题。

2.4 遗传模拟退火算法

遗传模拟退火算法 （Genetic-Simulated Annealing Algorithm，GSA）是将遗传算法与模拟退火算法相互糅合而构成的一种混合寻优方法[7]。遗传算法采用从初始种群开始搜索最优解，搜索覆盖面广，把握搜索全局的能力较强，但局部搜索能力较差，耗费搜索时间较长；而模拟退火算法使用随机概率方式进行最优解的搜索，局部收敛快、搜索能力强，但模拟退火算法不能很好的在全局范围内进行搜索，不容易进入最优的搜索区域，导致模拟退火算法不能有效的搜索。遗传模拟退火算法巧妙地结合了遗传算法与模拟退火算法，即发挥了各自所长，又互补了各自所短。

遗传模拟退火算法基本运算过程如下[8]：

（1）创建由N个符合条件的个体组成的初始种群；

（2）对有效个体进行编码；

（3）根据个体的适应度产生选择算子，选择优化的个体形成新的中间种群；

（4）对中间种群进行解码；

（5）对中间种群应用模拟退火算子，根据当前条件进行退火运算；

（6）对模拟退火运算后的中间种群再次进行编码；

（7）对中间种群应用遗传算子进行选择，交叉和变异运算，遗传产生新生代；

（8）重复步骤（3）至（7），直至达到最大遗传代数或符合退出条件，找到最优解，并对最优解解码。

遗传模拟退火算法的流程图如下：

遗传模拟退火算法的主要特点是[9-10]收敛速度快、算法运行效率高、适用范围广等。这些优点是其他智能算法无法比拟的，非常适合在大规模和有约束的优化问题中应用。

3、分析比较

本文对试卷的染色体编码采用了实数编码方式，实数编码与二进制编码相比，实数编码具有搜索空间大、运算效率高、转换误差小、求解精度高等明显优点。针对四种算法分别进行以下初始化：随机抽取算法——种群数为20；模拟退火算法——初始温度80、退火速率 0.5，退火内层循环5；遗传算法——迭代次数为 100、种群数20、交叉概率0.68、变异概率0.006；遗传模拟退火算法，初始值是遗传算法与模拟退火算法的结合。

测试数据为《C语言》试题库，由500道试题组成，共有题型五种；章节六个；难度等级四级；掌握程度四种。算法的初始约束条件有：试卷总分、考试时间、预期平均分、试题总数、题型分布、掌握程度分布以及各章节的分布等。现从章节分布和适应度两方面摘录实验结果如下：

图2 各算法生成试卷在章节分布上的对比

图3 各算法生成试卷的适应度函数值对比

初始各章所占分值比例为第一章5分、第二章15分、第三章30分、第四章25分、第五章15分、第六章10分。分析各算法生成试卷在章节上的分布可以发现随机抽取算法误差为 22，模拟退火算法误差为8，遗传算法误差为4，遗传模拟退火算法误差为 0，由此得出随机抽取算法在满足章节分布上性能最差，遗传模拟退火算法在满足章节分布上性能最好。

通过适应函数值的比较可以看出，遗传模拟退火算法和其他算法相比，其适应函数值有了明显的下降。试卷质量的优劣是用户组卷关注的首要因素，适应函数值能够直接反映出试卷的质量，用它可以直接分析试卷质量的优劣。试卷的适应函数值越小，说明误差越小，试卷质量越高。通过实验结果可见，在初始环境相同的情况下遗传算法生成试卷的质量明显高于随机抽取算法，遗传模拟退火算法生成试卷的质量明显高于遗传算法。经过综合分析可以得出，遗传模拟退火算法在智能组卷系统中的应用要优于遗传算法和模拟退火算法等传统算法，将遗传模拟退火算法应用在实际的组卷系统中会更适合、更完美。

4、总结

本文通过对以上四种算法的分析及实验，得出如果试题库中的试题量不大，可以采取随机抽取算法进行组卷，因为在较高的随机代数抽取下，随机抽取算法的组卷成功率还是较高的。但是如果题库中试题量较大，就不宜采取随机抽取算法，在庞大的题型组合中会产生较大的评价函数值，大大降低组卷效率。遗传模拟退火算法与传统遗传算法的收敛准则（最大遗传代数）相比，所使用的收敛判断既能保证搜索的全面性，又能有效地缩短算法的运行时间，因此实用性非常强。将遗传模拟退火算法应用于智能组卷系统中，将会充分发挥遗传算法和模拟退火算法的各自优点，互补缺点，既能在全局范围内搜索出最优区域，又能在最优区域找出最优解。

［1］李目海.组卷中的随机抽取算法分析与实现［J］.枣庄学院学报，2007，（02）：39-41.

［2］石利平.模拟退火算法及改进研究［J］.信息技术，2013，（02）：176-178.

［3］Steinbrunn M ，Moerkotte G，Kemper A.Heuristic and Ran2 domized Optimization for the Join Ordering Problem ［J］. The VLDB Journal，1997，（3）：8-17.

［4］蒋龙聪，刘江平.模拟退火算法及其改进[J].工程地球物理学报，2007，（02）：135-140.

［5］牛向阳，倪前月，高成修.基于遗传算法和模拟退火算法的混合算法［J］.昆明理工大学学报（理工版），2008，（02）：25-28.

［6］张峰，张兆印.一种基于改进遗传算法的组卷算法［J］.中国科技信息，2009，23：52-53.

［7］白东玲，郭绍永.改进的遗传算法在智能组卷系统中的应用研究［J］.计算机与现代化，2013，（03）：25-28.

［8］周艳聪，刘艳柳.遗传模拟退火智能组卷策略研究［J］.计算机工程与设计，2011，（03）：1066-1069.

［9］赵永虹.组卷算法研究与实现［J］.现代电子技术，2011，（04）：:42-45.

［10］陈晓东，王宏宇.一种基于改进遗传算法的组卷算法［J］.哈尔滨工业大学学报，2005，（09）.

The Comparison of the Core Algorithms in the System of Intelligently Composing Test Papers

YAO Yu-ge
（Department of Computing Science,Jining Normal University,Wulanchabu 012000,Inner Mongolia,China）

As far as the present process of examination reforms is concerned,the operations of exams are gradually transiting to humanization and automation and in this process,in which,the key technique is to automatically compose test papers by way of computers,and a reasonable mathematical model and a high efficient algorithm of composting test papers need to be formed to get high-quality papers.In the paper,several common intelligent algorithms are chosen to make a comparative study so as to find the optimal algorithm of both improving the success rate of combining test papers and achieving satisfactory results of the process.

bank of test papers;intelligent compositions of test papers;the Smart group volume;genetic simulated annealing algorithm

TP301.6

A

2095－3771（2014）04－0112－04

姚玉阁（1975—），男，副教授，硕士，研究方向：计算机科学教育、计算机软件技术。基金项目：“基于遗传模拟退火算法的智能组卷研究”（项目编号：NJZC13282）。