通用在线考试系统智能组卷遗传算法设计

吕海燕　周立军　宦婧　张杰

摘要：组卷算法设计是考试系统设计的核心。在分析通用在线考试系统的特点及组卷原则的基础上，首先建立一种改进的组卷数学模型；接下来依据该模型主要从编码方式选择、适应度函数的确定以及遗传算子的设计等方面详细设计通用在线考试系统采用的改进的遗传算法；最后，给出基于改进的遗传算法的智能组卷流程。应用表明，采用该算法实现的本系统的组卷功能在组卷的速度和成功率都得到显著提高，较好地满足了各类课程的组卷需求。

关键词：智能组卷；遗传算法；组卷数据模型；组卷流程；通用在线考试系统

中图分类号：TP311.13文献标识码：A

Abstract：Intelligent algorithm of assembling test taper is the core of the test system design. Based on analysis of the characteristics of the common online examination system and the general principles， firstly an improved test paper generated mathematical model was established. Then the improved genetic algorithm was designed mainly from the following three aspects： the coding scheme selection， the fitness function determination and the genetic operator design. Finally， the intelligent test paper process of the adopted improved genetic algorithm was shown. Applications show that the test paper speed and success rates have been significantly improved to better meet the needs of various courses of test paper.

Key words：intelligent generating；genetic algorithm；test paper generated mathematical model；test paper generate process；common online examination system

1引言

通用在线考试系统是我院自行开发，并且已经在军队院校以及各基层单位得到了广泛应用。在考试系统中，组卷算法设计的好坏将直接影响着考试系统性能的优劣。优秀的组卷算法不仅应该能够根据任课教师的各种要求及课程的特点智能生成考试试卷，还应满足考核不同层次学生的需要，以便能够真实、有效地反映学生的学习能力和教师的教学水平。

不论是在组卷质量还是在性能方面传统的组卷算法（如回溯试探法、随机抽题及误差补偿法等）都难以满足组卷要求。遗传算法（GA）是对自然现象或过程进行模拟而形成的，它通过模拟达尔文的自然选择学说和自然界的生物进化过程而形成的一种计算模型。它的收敛性也很好，可以有效解决计算量大的问题，而这些特点是处理智能组卷中所必需的，所以遗传算法已成为目前在线考试智能组卷的首选算法。[1-2]而传统的遗传算法在收敛速度和计算全局最优解之间存在矛盾，容易产生早熟现象、局部寻优能力差等缺点。因此，结合遗传算法的优点和缺点，通用课程在线考试系统在实现智能组卷时采用了一种改进的遗传算法来实现。

2智能组卷的数学建模

组卷问题的数学模型的建立是组卷算法实现的基础，它决定了组卷算法性能的好坏。结合通用在线考试系统的功能特点及组卷的原则，本文建立了一个适合于本系统的多目标优化组卷数学模型。

2.1试题属性的确定

通过遗传算法高效精确地完成组卷时，试题属性的设置要满足经典测量理论的需求。[2]试题属性的设置以能把整套试卷中的试题的情况说清楚即可，属性不能太多也不能太少。依据这一原则，本系统选取设置的试题属性主要有以下几个：

1）题号：区分试题的唯一属性，在数据库设计中设置为试题的主键。

2）题型：主要包含单选题、多选题、填空题、判断题、改错题、程序设计等多种题型，可根据课程特点对题型进行灵活地设计。

3）分数：该题目在试卷中所占的分值，主要依据题目的难度及所涉及的知识点来确定。

4）难度：反映试题的难易程度，从等级上大致分为容易、较易、中等、较难、难等多个等级，可通过设置范围为0.00～1.00的难度系数来体现。试题难度可以在系统启用初期由经验丰富的教师手动设置，也可以在系统使用一段时间后，根据学生测试的正确率自动调节（试题的回答正确率的近似值为其难度值）。

5）知识点：试题所考核的知识点的体现。通常情况下，如果试题属于相同知识点，则他们具有非常高的相似度，在生成试卷时，应最大限度地避免它们出现在同一试卷中。在考试系统数据库设计中，该属性作为外键。

6）曝光度：指本试题在历次考试中被选中的次数，该属性是进行考试评价和后期组卷策略调整的重要依据。

依据数学建模理论[3]，如果要组一套含有n道试题的试卷，假设每一道试题含有m项指标，那么要确定这份试卷，就要先确定一个n*m 的矩阵，如下图1所示：

其中，矩阵中每一行为一道试题，每一列为试题的一个属性。对于本系统而言，n为6，这6个属性依次是：题号、题型、分数、难度、知识点和曝光度。

2.2组卷的约束条件

依据前述智能组卷基本原则及构建的组卷数学模型，本系统确定组卷的几个重要约束条件如下几个：试卷总分值约束；考试时间约束；题型和各题型的题量约束；考试范围约束；知识点分数分布约束；试卷的难度约束；试卷的区分度约束：区别不同层次学生能力水平的主要标准，也是衡量试卷质量的一个重要指标。

3多目标优化的数学模型的建立

如前所述，要组成一份试卷需要满足多个约束条件，整张试卷需要满足的所有约束条件集合构成了一个多维变量空间。而矩阵的维数越多求解就越复杂，也就是说，如果组卷玉树矩阵的维数设计不合理，会在很大程度上增加组卷算法设计的难度，同时也会降低组卷的效率。[3-5]为此，本系统采用的组卷算法在设计时，基于以下前提：试卷的总分、完成时间、包含的题目类型、各题型的题目数量、各题型中每小题的分值由教师设置的（或者由系统默认）。如对于《大学计算机基础》课程，考试通常包括选择、填空和应用设计三种题型，同一类题型中各小题分值是一样的，题量的设置可以根据考试时间来确定。因此，一旦固定了题量，算法就不再考虑各小题的分值和每个小题的做题时间。也就是说，可将试题的约束条件简化到“难度”、“知识点”、“区分度”和“曝光度”这四个属性。此时，试卷的约束条件简化到了一个四维空间，如下图2所示。

其中，矩阵中n行代表一套试卷的n 道试题，每一行表示一道试题相应的四个约束条件，分别是：难度、知识点、区分度和曝光度。

4算法的设计

在应用遗传算法解决组卷问题时，将一份试卷当成一个个体或者是染色体，而试卷中的每道题当作一个基因，多份试卷则称为一个种群。遗传算法的组成主要有编码方式、初始化种群、适应度函数、遗传算子（遗传、交叉、变异）以及终止条件（控制参数）的设定五个方面。下面主要从这个五个方面介绍本考试系统所采用的改进的遗传算法的设计。

4.1编码方式的选择

应用遗传算法完成组卷时，首先要解决的是个体的编码问题，编码用于产生初始种群。由于每道试题在题库中按照题型不同都有唯一的自然数编号，依据该特点本系统组卷算法采用整数分段编码方案。其主要思想是，整个编码分成独立的几段，其中每类题型对应一段，而每段的长度则由每个题型在待生成试卷中题目的数量决定；各题型间的编码是相互独立，各自按照整数编码方式进行编码；编码串的总长度等于待生成试卷要求的试题总数量。

整数分段编码的优点是：克服了二进制编码长度过长和搜索空间过大的缺点，从而节省了个体解码的时间，提高了遗传算法的计算效率；同时，由于同类型的试题放在同一段内，交叉和遗传操作均在段内进行，这样可以在一定程度上确保优化目标中题型匹配的正确性。

如前所述，在整数分段编码中，每一段代表一种题型，而每个基因就是被选中的试题编号。如《大学计算机基础》课程试题库中共有4种题型：单项选择题、填空题、判断题和应用设计题，共600道题，它们分别用符号X、K、P和Y表示，X类题型有300个，K类题型有100个， P类题型有100个，Y类题型有100个。各类题型在待组试卷中的试题数分别是s1（1≤s1≤300），s2（1≤s2≤100），s3（1≤s3≤100），s4（1≤s4≤100），编码的总长度S为待组试卷中的总题数，即s=∑4i=1si。编码方案如下表1所示。

4.2初始化种群的生成

在遗传算法搜索过程中，种群规模大小的设置对算法的收敛速度和求解最优解的几率有很大影响。通用在线考试系统为了加快算法的收敛速度，在生成初始种群时，采用了不完全随机的方式，使初始种群中的个体一开始就满足时间、题量、题型和分数的要求，从而在一定程度上提高了算法的搜索效率。种群初始化后，再对种群中个体的相似度进行比较，将相似度高的个体进行删除，从而避免了初始种群中出现过多的相似度高的个体，使初始种群的规模进一步减小。

4.3适应度函数的确定

组卷要求与染色体之间的差别是通过适应度函数来反应的，适应度函数是指导遗传算法的主要信息来源，同时它也是区分优劣个体的一个很好的工具。[5-7]要想保持群体多样性需要有一个良好的适应度函数，它能有效防止群体的早熟问题。通常情况下，个体的好坏与适应度函数值成正比，即适应度函数值越大，则个体越好。

如前所述，由于考试时间、题量、题型和分数题型要求在初始化种群时已经考虑。因此，适应度函数在确定时，仅需再考虑难度系数、知识点分数分布和试卷区分度这几个指标即可。由此确定的适应度函数仅与试卷难度系数（用P表示）、知识点分数分布（SPD）和试卷区分度（用D表示）有关。也就是说，试卷期望难度系数EP与试卷实际难度系数P之差Ep、用户的期望知识点分数分布ESPD与实际知识点分数分布SPD之差ES、和试卷期望区分度ED与试卷实际区分度D之差ED，越小越好。系统的适应度函数设计如下：

F=（Esw1+Epw2+EDwa）（1）

适应度函数F的值越小，则个体的适应度就越高。其中，Es=∑ki=1|ESPD-SFD|，即各章节知识点分数分布期望值偏差的绝对值之和，Ed=|ED-D|，Ep=|EP-D|，w1+w2+w3=1。

4.4遗传进化中的选择操作

遗传算法模拟自然界中的选择机制对群体中的个体按照其适应度值的大小进行优胜劣汰操作时，是通过选择算子来实现的。选择算子的强度不能太大，也不能太小，选择强度要适中才有利于算法搜索问题最优解。选择强度太大的算子，会使群体丧失多样性从而陷入局部最优，影响问题求解结果；而选择强度过小算子，会使种群的进化速度会十分缓慢，影响问题求解速度。[12-13]本系统采用了最优保持策略与轮盘赌选择策略相结合的方法，从而在一定程度上避免了轮盘赌选择策略的随机性。

轮盘赌算法：

设种群由M个个体组成，其中个体Mi的适应度用Fi表示，则此个体的选中率用Pi表示，则：

Pi=Fi/∑Mi=1Fi（2）

轮盘赌算法的操作过程如下：首先根据公式（1）计算群体中各个个体（每套试卷）的适应度值Fi，根据公式（2）计算出每个个体被选中的概率Pi；接下来计算群体中各个个体的累积率Qk=∑ki=1Pi并以此构建一个轮盘；求出Qk之后，依据 Qk的值来选择参与进入下一代的个体：确定一个[0，1]之间的值r（可随机产生），比较Qk与r的值的大小，若r≤Qi，就选择个体M1；若Qk-1≤r≤Qk，则选择个体Mk参与下一代群体；如上反复执行，直到产生M个个体，即M套试卷。

在遗传算法的进化过程中，通过执行选择、交叉及变异等操作从而不断生成越来越多的优良个体。但是，由于选择、交叉及变异操作的随机性，会导致适应度好的个体经常被破坏，从降低算法的收敛性和执行效率。[8]因此，为尽可能地使适应度好的个体保留到下一代群体中。通用考试系统在实现选择操作时，将轮盘赌选择策略和最优保留策略结合起来实现进化过程中的选择操作。

4.5遗传进化中的交叉操作

传统遗传算法在实现交叉操作时，采用的是恒定不变的交叉概率，这会导致遗传算法在解决复杂的优化问题时，效率很低且容易出现早收敛现象。[9]本系统为了加速算法搜索速度，并有效地防止早收敛现象，采用了Srinvivas提出的自适应交叉概率Zc。自适应交叉概率Zc的计算公式如下：

Zc=11+exp（-k1（Fmax-Favg））（3）

其中，k1为大于0的常数，本系统选择的是k1=0.6，Fmax表示种群中个体的最大适应度值，Favg表示群体中大于平均适应度的那部分个体的平均适应度值，Zc在[0.6，1]之间取值。

在算法的进化过程中。交叉概率Zc会根据Fmax-Favg的不同而自动调整，当群体趋于分散时，也就是Fmax-Favg增大时，交叉概率Zc增大，而对应的变异概率减小，从而使种群生成优良个体的能力增强；反之，当群体趋于收敛时，也就是当Fmax-Favg减小时，交叉概率Zc减小，而对应的变异概率增大，从而使群体保持多样性的能力增强。

基于上述自适应调整交叉概率的交叉操作过程如下：

1）设种群规模为N，将群体中的个体随机进行两辆交配，则会产生[]对个体组；

2）对种群中的个体随机生成交叉点，如果个体的编码长度为L，则有L-1个位置会成为交叉点；

3）如前所述在整数分段编码方案中，每一种题型对应一段编码，交叉操作在编码段内独立进行，这样可以保证每种题型的试题数量不变。即若交叉点在第i个基因段内，则前i个基因段保持不变，只需从第i+1个基因段开始逐个基因进行交换。

采用此方式可避免基因段内进行交叉后出现试题重复的弊端。执行完交叉操后，再按照适应度函数分别计算两个新生个体的适应度，并将其与父代个体的适应度进行比较，若两者适应度相同，则将其丢弃；若不同则对它进行变异操作。

4.6遗传进化中的变异操作

通过交叉与变异操作的相互配合，使得遗传算法有了较高的搜索能力。交叉操作是算法的核心，在进化过程中对算法的局部搜索能力起关键性作用；而变异操作则是影响算法的全局搜索能力的主要因素。[10]在进化过程中，当算法的搜索过程陷入局部最优时，通过有效的变异操作可跳出局部最优，从而达到全局寻优的目的。但变异概率过大也有破坏掉最优解的可能，因此，不能盲目地进行变异操作。同交叉操作一样，本系统采用了Srinvivas提出的自适应变异概率，其计算公式如下：

Zm=11+exp（-k2（Fmax-Favg））（4）

同前述自动调整交叉概率的计算公式一样，其中，k2为大于0的常数，这里选择k2=0.9，Fmax表示种群中个体的最大适应度值，Favg表示群体中大于平均适应度的那部分个体的平均适应度值，Pm在[0，0.5]之间取值。

同交叉操作一样，在执行变异操作时，各种题型也是在各自对应的编码段内进行。首先对群体中的各个个体生成一个与其编码长度L相同的随机数序列R={r1，r2……r1}，其中，0≤r1≤1，0≤i≤1；对所有ri

1）查找出基因位i所在段对应的试题类型；

2）找出该基因位（题号）所代表的试题所对应的知识点、难度系数，然后随机生成一个新的满足要求的试题编号，从而产生一个新的染色体（试卷个体）；

3）判断该新的基因串是否已经存在，如果存在则转向步骤2，再次生成新的染色体。否则用此新的染色体替换原来的染色体。

4.7终止条件的设定

基于遗传算法的实现时，就是反复从试题库中搜索符合相应约束条件的试题直到找到最优解的过程。如果经过反复多次选择、交叉、变异操作后，仍然没有找到最优解，那么搜过过程不可能无休止地循环下去迭代下去。此时，需要设定一个终止条件来结束这种无休止无意义的搜索迭代过程。终止条件的设定主要需要考率以下三种情况：

1）设定进化迭代最大次数，当最大值出现时，算法终止。一般为150-600。

2）设定好一个适应度最高值，若该值出现，即可终止算法。

3）如果连续几代个体适应度平均值的差异小于某一极小阈值或者当所有个体适应度函数值的方差小于某一极限阈值时，也可考虑终止算法的进行。

根据以上算法终止条件的判断，本系统组卷算法采用了以下两种终止条件：

1）种群进化到指定的迭代数，系统设参考范围为500-1000代，默认值取600。

2）最优个体的适应度与期望的最好适应度比值为96%以上，即用户对生成的试卷满意度为96% 。

在迭代过程中，只要满足其中任意一个条件，都会终止算法的操作，并输出相应的试卷；

5基于改进算法的智能组卷流程

基于改进后的遗传算法的智能组卷流程如下图5所示。6结论

本系统采用的改进的遗传算法的智能组卷策略，主要是结合组卷问题本身的特点，在遗传算法的染色体编码方式选择、初始化种群的生成以及适应度函数、交叉和变异操作的设定等方面进行了相应的改进。其中，整数分段编码方式节省了个体解码的时间，提高了遗传算法的计算效率；分段交叉方式和自适应交叉概率、变异概率的应用，提高了算法的收敛速度，较好地避免了传统遗传算法的早熟问题。应用表明，本系统的组卷功能在组卷的速度和成功率都得到显著提高，较好地满足了各类课程的组卷需求。

参考文献

[1]肖理庆，徐晓菊.改进遗传算法智能组卷研究[J].计算机工程与设计，2012，（10）：35-39.

[2]唐启涛.基于改进的遗传算法的智能组卷算法研究[J].计算机技术与发展，2014，（12）：241-244.

[3]袁桂霞.自动组卷的建模和仿真研究[J].计算机仿真，2011，（28）：370-373.

[4]汪民乐.遗传算法的收敛性研究[J].计算技术与自动化，2015，（10）：52-56.

[5]王吉权，王福林.单点交叉多子代遗传算法[J].生物数学学报，2015，30（2）：305-311.

[6]李书全，孙雪.遗传算法中的交叉算子的述评[J].计算机工程与应用，2012，（1）：67-71.

[7]贺荣，陈爽.在线组卷策略的研究与设计[J].计算机工程与设计，2011，（6）：2183-2183.

[8]刘淳安，赵天绪，刘燚.智能组卷的优化模型及求解的遗传算法[J]，科学技术与工程，2010，（10）：2754-7456.

[9]张宗飞.网络化考试中智能组卷方法研究[J]，中国教育信息化，2015，（16）：79-81.

[10]柳良涛，谷林.自动组卷系统试题难度和知识点覆盖控制算法[J].西安工程大学学报，2015，（3）：320-324.