基于遗传算法的自动组卷研究与应用

施俊+缪勇

摘要：随着在线考试系统的广泛应用，组卷算法决定了自动组卷的性能。为提高组卷成功率，提出基于遗传算法的自动组卷模型，根据总分、题型、难度、区分度等要求建立多目标、多约束条件的数学模型。采用ASP.NET编程实现，并进行编码、选择、交叉、变异等操作，使遗传算法能满足自动组卷要求。

关键词：在线考试；自动组卷；遗传算法；数学模型

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）34-8160-03

随着信息化建设的推广，在线考试系统成为教学考试的有效补充，一份组卷质量高的试卷，能够准确评价学生的学习情况，在考试系统中，组卷主要分为手动组卷和自动组卷。自动组卷是指利用组卷策略从试题库中抽取试题，组成一份符合总分、题型、难度、区分度等约束条件的试卷，组卷算法设计决定了组卷的质量和效率。研究智能组卷算法，设计出合理的组卷算法一直是当前研究的热点和难点。

常用的自动组卷算法有：随机法组卷和回溯法组卷，对于求解复杂度较高或试题量较大时有明显的缺陷。采用遗传算法（Genetic Algorithm，GA）实现自动组卷可取得较好的效果。该文利用遗传算法作为智能组卷问题的策略，并将该算法应用于在线考试系统的自动组卷中。

1 组卷理论与数学模型

1.1 质量指标选择

在教育测量学理论中，有“难度、区分度、效度、信度”指标体系，分别代表统计中的百分数、平均数、相关系数、标准差结果[1]。在组卷操作之前进行分析，确定试题应包含哪些属性。

1） 试题难度，指完成某条试题时，所面对的困难程度，通过在该题上的失分率来体现。

试题i 的难度系数Ei 公式为：Ei = 1 - Ri/Ki

其中，Ri 为试题 i 的平均得分值，Ki 为试题i 的分值。

2） 试题区分度，指对不同层次学生的鉴别能力大小的指标，用通过该试题测试和未通过该试题测试的学生的平均分值和该试题的满分值来计算。

试题i 的区分度Di 公式为：Di =（RH - RL ）/Ki

其中，RH 表示通过该试题测试学生的平均分值，RL表示未通过该试题测试学生的平均分值，Ki为试题i的分值。

在最初建立课程试题库的时候，就准确确定好试题的难度和区分度是困难的，教师往往根据经验设置一个初始值，而后根据学生的考试情况逐年进行修正。

3） 试卷信度和效度

试卷信度是指测试结论与数据的可靠性程度，试卷质量稳定性和可靠性通过试卷信度来衡量；试卷效度是指试卷内容与教学大纲的吻合程度[2]。

1.2 自动组卷的数学模型

自动组卷是指从相应的试题库中抽选出符合约束条件的试题组成试卷，并且需要满足总分约束，题型约束、题量约束、难度约束、区分度约束、分值约束等多个方面的要求。

假设一份试卷包含 m 道试题，每道题有 n 个属性，则生成一份试卷就可用m × n 矩阵表示，即：

1） 试卷总分约束， [S=i=1mai2]，[ai2]表示第i 道题的分值，S是由用户设定试卷的总分，默认满分为100；

2） 题型分值约束，[Tt=i=1mC1i×ai2]，其中，[C1i=1（ai2=t）0（ai2≠t）]，t表示题型号，[Tt]表示第t种题型所要求的分数，[C1i]表示单择、判断、多选、填空、分析、简答、计算等题型；

3） 章节分值约束，[Zt=i=1mC2i×ai2]，其中，[C2i=1（ai2=t）0（ai2≠t）]，t表示章节号，[Zt]表示第t章所要求的分数；

4） 知识点分值约束，[ZSt=i=1mC3i×ai3]，其中，[C3i=1（ai3=t）0（ai3≠t）]，第t个知识点分值；知识点覆盖面为：[R=已选的知识点数应包含的知识点数≥r]，一般情况下，为了使知识点覆盖面广，这里r取80%较为适宜；

5） 难度约束，[E=i=1mai2ai4S']，其中，[ai4]为第 i 道试题的难度，[S']为试卷的总分；

6） 区分度约束，[D=i=1mai2ai5S']，其中，[ai5]为第 i 道试题的区分度，[S']为试卷的总分；

1.3 组卷目标函数

组卷是多目标条件的组合优化问题，生成一份质量较好的合格试卷，需要满足题型、分值、难度、区分度等多方面条件的约束，同一个解通常无法同时达到多个目标最优，故为每个目标给定一个权重，进行累加后生成一新的目标函数：[F（x）=i=1nwifi（x）]，其中，[fi（x）]为对应[ai]属性对组卷约束的误差，[wi]为第i 项组卷因素在组卷中所占权重。

在实际组卷中，较理想的状态是实际各指标的满足率与理论上各指标的满足情况的差异尽量最小，即偏差值最小，因此目标函数可以表示为min[F（x）]；一般情况下，试卷的约束条件很难做到同时满足，应该合理设置权重，优先考虑一些重要指标。

2 遗传算法的自动组卷模型与应用

遗传算法是一种模拟自然届生物进化的计算模型，是一种较好的搜索最优解的方法，全局搜索能力较强，最初的提出者是美国的J.Holland教授。

2.1 基于遗传算法的自动组卷

基于遗传算法的自动组卷方法，包括染色体编码、生成初始种群、计算适应度函数，以及通过对当前群体实施选择、交叉、变异等遗传操作，生成下一代群体，逐步靠近最优解状态，具体的组卷方法如下[3]。

1） 染色体编码，目前基于遗传算法的自动组卷比较多的是采用二进制编码，每道题有两个状态，即“选中”和“未选中”，用“1”和“0”表示。二进制编码方式编码不灵活，编码太长，因此，该文采用分组自然数编码，使编码长度缩短。假设试卷要求有四种题型A、B、C和D组成，数量分别为m1、m2、m3、m4，试题库中待选试题数量为分别为n1、n2、n3、n4。组卷时从每种题型的题库中选择题号组成染色体，选中的题号作为染色体的一个基因，长度就是试卷中试题的数量。试卷的染色体编码，如图1所示。endprint

2） 生成初始种群，初始种群是遗传算法中的一个重要参数，设为N 。若N太小，则每代能够处理的染色体数量少，搜索效率偏低，也容易陷入局部最优解；若N太大，则每代都要计算较大量的适应度值，计算效率偏低。因此，种群大小根据实际情况选取，该文主要以题型为单位来随机生成初始种群，简化了遗传运算过程，实现更快更高效的组卷。

3） 适应度函数，一般情况下通过目标函数变换得到，个体适应度值的大小决定了群体中个体的优劣程度。适应度值越大，表示个体适应能力越强，问题的解越优；反之，适应度值越小，表示个体遗传到下一代的概率也就越小，甚至面临淘汰。适应度函数使用组卷目标函数的倒数，表示为：f（x）=1/F（x）。

4） 选择操作，是以个体的适应度函数为基础，选择优秀的个体遗传到下一代中，在这里我们使用轮盘选择算法，根据适应度函数值将个体进行升序排序，保留m 个适应度值高的试题，淘汰适应度值低的试题，由此重新组成一个新群体，选择的概率为： [Ps=f（bi）j=1mf（bj）] （i=1， 2， … ， N） 。

5） 交叉操作，是对种群中的两个染色体的相同位置进行交换得到新的个体。在已满足题型要求的情况下，染色体交叉操作，将按照题型进行分段，在段内单点交叉。这里设定交叉概率Pc，从群体中先选定Pc[×]N 个体，利用随机函数生成一个（0， 1）区间的数r ，若果r < Pc，随机从群体中抽选一条试题与它配对，在题型分段中随机生成一个交叉点，对两份试卷交叉点后的染色体进行交叉操作。假若有四种题型，那么就有四个段内交叉点，进行交叉前父个体的染色体编码为：

6） 变异操作，是指改变染色体中的部分基因值，从而使种群个体的多样性得以保持，提升算法的局部搜索能力。这里采用在同一题型的段内，有条件的进行单点变异。这里设定变异概率为Pm ，在组卷中，对每个题型的题号范围已经确定，在第i 段题号范围内，产生一个随机试题号，若该试题号个体已经被选择，那么就再次生成一个新的试题号，直到生成的随机试题号代表的个体未被选中，则变异操作结束。

7） 设置终止条件，因不同的用户需求，以及不同的初始种群，在使用遗传算法进行组卷时，很难判断何时能得到最优的个体（即获得最优试卷）。常见的终止条件有，一是满足给定的遗传迭代次数；二是目标适应度值和实际适应度值之差小于预先设定的阈值。

8） 设置遗传算法的参数，对遗传算法的组卷效率非常重要。在使用改进的遗传算法进行自动组卷时，通过实验，遗传算法中的参数设置如下：种群大小N一般为20-100；交叉概率Pc一般为0.4-0.98；变异概率Pm一般为0.0001-0.1，终止条件迭代次数一般取100-1000。

2.2 遗传算法自动组卷实施流程图

通过对遗传算法自动组卷问题的分析，自动组卷的实施流程，如图2所示。

2.3 自动组卷系统实现

本在线考试系统自使用以来，已在几门课程考试组卷过程中应用，从实际使用效果看，生成的试卷知识点覆盖合理，组卷成功率和效率均较高。

3 结束语

自动组卷需要满足一定约束条件下的多目标参数优化问题，传统方法求解困难。该文首先提出了组卷问题的数学模型，并结合自动组卷相关特点，应用遗传算法具有的优异全局搜索能力，提出了一种改进的遗传算法的实现自动组卷。通过编码、初始化、设置适应度函数，进行选择、交叉、变异等操作[5]，并在考试系统中实现智能组卷，提高了组卷效率和质量。

参考文献：

[1] 欧薇.基于遗传算法的在线考试系统的设计与实现[D].广州：华南理工大学，2012.

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

[3] 刘洋.遗传算法在考试系统中组卷算法的研究与设计[J].湖南城市学院学报：自然科学版，2013，22（1）：75-78.

[4] 张琨，杨会菊.基于遗传算法的自动组卷系统的设计与实现[J].计算机工程与科学，2012，34（5）：178-183.

[5] 张大胜.多目标人工蜂群算法及遗传算法的研究与应用[M].沈阳：东北大学出版社，2013.endprint

2） 生成初始种群，初始种群是遗传算法中的一个重要参数，设为N 。若N太小，则每代能够处理的染色体数量少，搜索效率偏低，也容易陷入局部最优解；若N太大，则每代都要计算较大量的适应度值，计算效率偏低。因此，种群大小根据实际情况选取，该文主要以题型为单位来随机生成初始种群，简化了遗传运算过程，实现更快更高效的组卷。

3） 适应度函数，一般情况下通过目标函数变换得到，个体适应度值的大小决定了群体中个体的优劣程度。适应度值越大，表示个体适应能力越强，问题的解越优；反之，适应度值越小，表示个体遗传到下一代的概率也就越小，甚至面临淘汰。适应度函数使用组卷目标函数的倒数，表示为：f（x）=1/F（x）。

4） 选择操作，是以个体的适应度函数为基础，选择优秀的个体遗传到下一代中，在这里我们使用轮盘选择算法，根据适应度函数值将个体进行升序排序，保留m 个适应度值高的试题，淘汰适应度值低的试题，由此重新组成一个新群体，选择的概率为： [Ps=f（bi）j=1mf（bj）] （i=1， 2， … ， N） 。

5） 交叉操作，是对种群中的两个染色体的相同位置进行交换得到新的个体。在已满足题型要求的情况下，染色体交叉操作，将按照题型进行分段，在段内单点交叉。这里设定交叉概率Pc，从群体中先选定Pc[×]N 个体，利用随机函数生成一个（0， 1）区间的数r ，若果r < Pc，随机从群体中抽选一条试题与它配对，在题型分段中随机生成一个交叉点，对两份试卷交叉点后的染色体进行交叉操作。假若有四种题型，那么就有四个段内交叉点，进行交叉前父个体的染色体编码为：

6） 变异操作，是指改变染色体中的部分基因值，从而使种群个体的多样性得以保持，提升算法的局部搜索能力。这里采用在同一题型的段内，有条件的进行单点变异。这里设定变异概率为Pm ，在组卷中，对每个题型的题号范围已经确定，在第i 段题号范围内，产生一个随机试题号，若该试题号个体已经被选择，那么就再次生成一个新的试题号，直到生成的随机试题号代表的个体未被选中，则变异操作结束。

7） 设置终止条件，因不同的用户需求，以及不同的初始种群，在使用遗传算法进行组卷时，很难判断何时能得到最优的个体（即获得最优试卷）。常见的终止条件有，一是满足给定的遗传迭代次数；二是目标适应度值和实际适应度值之差小于预先设定的阈值。

8） 设置遗传算法的参数，对遗传算法的组卷效率非常重要。在使用改进的遗传算法进行自动组卷时，通过实验，遗传算法中的参数设置如下：种群大小N一般为20-100；交叉概率Pc一般为0.4-0.98；变异概率Pm一般为0.0001-0.1，终止条件迭代次数一般取100-1000。

2.2 遗传算法自动组卷实施流程图

通过对遗传算法自动组卷问题的分析，自动组卷的实施流程，如图2所示。

2.3 自动组卷系统实现

本在线考试系统自使用以来，已在几门课程考试组卷过程中应用，从实际使用效果看，生成的试卷知识点覆盖合理，组卷成功率和效率均较高。

3 结束语

自动组卷需要满足一定约束条件下的多目标参数优化问题，传统方法求解困难。该文首先提出了组卷问题的数学模型，并结合自动组卷相关特点，应用遗传算法具有的优异全局搜索能力，提出了一种改进的遗传算法的实现自动组卷。通过编码、初始化、设置适应度函数，进行选择、交叉、变异等操作[5]，并在考试系统中实现智能组卷，提高了组卷效率和质量。

参考文献：

[1] 欧薇.基于遗传算法的在线考试系统的设计与实现[D].广州：华南理工大学，2012.

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

[3] 刘洋.遗传算法在考试系统中组卷算法的研究与设计[J].湖南城市学院学报：自然科学版，2013，22（1）：75-78.

[4] 张琨，杨会菊.基于遗传算法的自动组卷系统的设计与实现[J].计算机工程与科学，2012，34（5）：178-183.

[5] 张大胜.多目标人工蜂群算法及遗传算法的研究与应用[M].沈阳：东北大学出版社，2013.endprint

2） 生成初始种群，初始种群是遗传算法中的一个重要参数，设为N 。若N太小，则每代能够处理的染色体数量少，搜索效率偏低，也容易陷入局部最优解；若N太大，则每代都要计算较大量的适应度值，计算效率偏低。因此，种群大小根据实际情况选取，该文主要以题型为单位来随机生成初始种群，简化了遗传运算过程，实现更快更高效的组卷。

3） 适应度函数，一般情况下通过目标函数变换得到，个体适应度值的大小决定了群体中个体的优劣程度。适应度值越大，表示个体适应能力越强，问题的解越优；反之，适应度值越小，表示个体遗传到下一代的概率也就越小，甚至面临淘汰。适应度函数使用组卷目标函数的倒数，表示为：f（x）=1/F（x）。

4） 选择操作，是以个体的适应度函数为基础，选择优秀的个体遗传到下一代中，在这里我们使用轮盘选择算法，根据适应度函数值将个体进行升序排序，保留m 个适应度值高的试题，淘汰适应度值低的试题，由此重新组成一个新群体，选择的概率为： [Ps=f（bi）j=1mf（bj）] （i=1， 2， … ， N） 。

5） 交叉操作，是对种群中的两个染色体的相同位置进行交换得到新的个体。在已满足题型要求的情况下，染色体交叉操作，将按照题型进行分段，在段内单点交叉。这里设定交叉概率Pc，从群体中先选定Pc[×]N 个体，利用随机函数生成一个（0， 1）区间的数r ，若果r < Pc，随机从群体中抽选一条试题与它配对，在题型分段中随机生成一个交叉点，对两份试卷交叉点后的染色体进行交叉操作。假若有四种题型，那么就有四个段内交叉点，进行交叉前父个体的染色体编码为：

6） 变异操作，是指改变染色体中的部分基因值，从而使种群个体的多样性得以保持，提升算法的局部搜索能力。这里采用在同一题型的段内，有条件的进行单点变异。这里设定变异概率为Pm ，在组卷中，对每个题型的题号范围已经确定，在第i 段题号范围内，产生一个随机试题号，若该试题号个体已经被选择，那么就再次生成一个新的试题号，直到生成的随机试题号代表的个体未被选中，则变异操作结束。

7） 设置终止条件，因不同的用户需求，以及不同的初始种群，在使用遗传算法进行组卷时，很难判断何时能得到最优的个体（即获得最优试卷）。常见的终止条件有，一是满足给定的遗传迭代次数；二是目标适应度值和实际适应度值之差小于预先设定的阈值。

8） 设置遗传算法的参数，对遗传算法的组卷效率非常重要。在使用改进的遗传算法进行自动组卷时，通过实验，遗传算法中的参数设置如下：种群大小N一般为20-100；交叉概率Pc一般为0.4-0.98；变异概率Pm一般为0.0001-0.1，终止条件迭代次数一般取100-1000。

2.2 遗传算法自动组卷实施流程图

通过对遗传算法自动组卷问题的分析，自动组卷的实施流程，如图2所示。

2.3 自动组卷系统实现

本在线考试系统自使用以来，已在几门课程考试组卷过程中应用，从实际使用效果看，生成的试卷知识点覆盖合理，组卷成功率和效率均较高。

3 结束语

自动组卷需要满足一定约束条件下的多目标参数优化问题，传统方法求解困难。该文首先提出了组卷问题的数学模型，并结合自动组卷相关特点，应用遗传算法具有的优异全局搜索能力，提出了一种改进的遗传算法的实现自动组卷。通过编码、初始化、设置适应度函数，进行选择、交叉、变异等操作[5]，并在考试系统中实现智能组卷，提高了组卷效率和质量。

参考文献：

[1] 欧薇.基于遗传算法的在线考试系统的设计与实现[D].广州：华南理工大学，2012.

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

[3] 刘洋.遗传算法在考试系统中组卷算法的研究与设计[J].湖南城市学院学报：自然科学版，2013，22（1）：75-78.

[4] 张琨，杨会菊.基于遗传算法的自动组卷系统的设计与实现[J].计算机工程与科学，2012，34（5）：178-183.

[5] 张大胜.多目标人工蜂群算法及遗传算法的研究与应用[M].沈阳：东北大学出版社，2013.endprint