基于遗传算法的自动组卷系统的分析与设计

蒋　哲(湖北工业大学, 武汉430068)

基于遗传算法的自动组卷系统的分析与设计

蒋哲
(湖北工业大学, 武汉430068)

自动组卷系统中的关键环节在于组卷算法的选择，算法的好换直接关系着组卷的质量以及效率。本文对三种常用的组卷算法进行了分析，并将改进的遗传算法应用于自动组卷问题中，有效提高了组卷质量和效率。本文详细阐述了基于遗传算法的自动组卷算法的实现流程。

遗产算法；自动组卷；算法设计

0　引言

自动组卷指的是计算机考试系统自动从预先设定的题库中按照用户的特点需求抽取试题从而组成一套完整的试卷。自动组卷得到的试卷既要满足用户设定的要求，同时也需要具有合理性、随机性，这对组卷算法提出了很高的要求。目前已经有了一些自动组卷系统，然而由于科目众多、各专业的课程重点不同等因素的影响，这些自动组卷系统还无法有效满足用户的需求。

1　自动组卷算法分析

组卷算法的设计是影响组卷系统组卷质量的关键因素，目前现有的自动组卷系统采用的组卷算法主要包括三种类型：回溯试探法、随机算法以及遗传算法。

回溯试探法的思想是：首先随机抽取一个试题，对该试题进行分析，判断是否满足抽题要求，若满足条件则抽出该试题进入试卷，否则重新选题。当组卷未完成时，采用回溯的方法试探之前的操作进行继续组卷。回溯法操作废弃的频率较低，有效减少了无效组卷操作。因此，回溯试探法的组卷成功率很高，但需要花费大量的时间作为代价。随机组卷法是指计算机根据预先设定的随机函数从题库中抽取符合条件的试题组成一套完整的试卷。这种方法实现起来比较简单方便，在实践中得到了广泛的应用。然而随机组卷法组成的试卷一旦某个条件达不到要求时（如试卷的预期答题时间超标），则整套试卷作废，从而导致出现大量的无效试卷，极大地降低了组卷的成功率和效率。遗传算法是一种基于自然界进化理论的优化算法，它遵循优胜劣汰的自然法则。遗传算法中的编码技术可以表示各种复杂的现实问题，它通过对编码的遗传操作即可确定算法的学习方向和策略。遗传算法是以种群为操作对象的，对种群中的每个个体进行适应度评价、筛选、交叉和变异操作，从而实现个体的优胜劣汰。

2 　基于改进的遗传算法的组卷算法设计

2.1目标函数的确定

试卷组织过程中应综合考虑题目类型、知识点分布、试题难度等因素，用户给定这些指标的参考值后，对自动组卷系统得到的试卷的指标值进行比较，将指标误差加权求和，得到目标函数。

2.2 个体编码的确定

确定好遗传算法的目标函数后，需要对自动组卷问题进行编码。组卷问题的求解就是筛选试题组成合理的试卷。因此，首先将试题根据进行分类，如分为选择题、填空题、计算题等，然后将试题按题型分段编码，不同题型的编码相互独立。试卷个体则按照分库编号进行染色体编码，所选中的试题按照顺序排列好后，其试题代码则为试卷个体的代码。

2.3 种群初始化

遗传算法是基于种群的方法，因此需要设定初始种群，然后在初始种群的基础上不断进化。种群是所有试卷个体的集合，初始试卷个体通过计算机随机生成。随机生成初始试卷个体时，试卷总分、题型、均满足要求。

2.4 适应度函数设计

适应度函数是遗传算法中个体进化操作的依据，因此在设计适应度函数时，应当使得遗传算法的群体位于解空间内，同时方便其搜索方向接受指导。一个良好的适应度函数应当能反应每个个体本身质量的好坏。在组卷算法中，适应度函数可通过目标函数转换得到，本文采用的适应度函数如下：

式中，f为目标函数，F为适应度。从上式可知，f越小，则适应度值越高，即试卷评价指标的误差越校，试卷个体的适应度越高，即试卷更符合组卷要求。

2.5 组卷算法的选择操作

遗传算法以试卷个体为遗传操作的对象，具体过程为：首先计算种群中每个试卷个体的适应度值，并找出适应度最高的个体，用它直接替代本代群体遗传操作后生产的适应度最小的个体，即遵循“精英保留”原则。其他的试卷个体则使用轮盘法完成选择工作。将种群中每个个体的适应度值求和得到种群的整体适应值，然后计算每个试卷个体的选择概率，同时生产一个0~1之间的随机数，若选择概率小于随机数，则该试卷个体不选择。

2.6 组卷算法的交叉操作

个体交叉的概率使用自适应交叉概率。由于试卷个体最终应该符合题量以及题型的规定，因此试卷个体在完成交叉操作时应当在各自的编码组中进行，例如A个体与B个体进行交叉时，选择题只能与选择题交叉，而不同的题型不能混合交叉。对上一步筛选出的个体进行两两交叉操作。在进行交叉时，各题型编码段随机生成一个交叉点，然后将交叉点之后的编码互相交换，当各题型均完成交叉后，则表示两个个体之间的交叉操作完成。由于交叉之后可能出现编码重复的情况，因此需要将重复的编码替换为随机抽取非重复编码。

2.7 组卷算法的变异操作

个体变异的概率使用自适应变异概率。由自然法则可知，变异是小概率事件，其发生的情况较少，只有少部分个体会发生变异，每个试卷个体的变异概率决定了个体是否发生变异。每个个体随机产生一个0~1之间的随机数，若个体变异概率大于随机数，则该个体进行变异操作。变异操作具体如下：每个题型段随机产生一个变异位置，移除该位置上原有的试题编码，并补入新的未被选中的试题编码。当各题型均完成变异后，即产生新的变异个体。

2.8 组卷算法的迭代终止条件

本算法迭代终止判定：（1）平均适应度达到最高适应度值的95%；（2）迭代次数达到预定最大次数，则结束迭代循环。

3　 结束语

我们研究的热点和难点，遗传算法本身具有全局寻优和智能搜索的特性，将遗传算子自适应改进后的遗传算法应用于组卷中，能够很好地解决组卷的多重目标寻优问题。

[1]李玲.基于遗传算法的自动组卷系统设计[J].软件导刊,2013,04:52-54.

[2]刘慧梅.基于遗传算法的自动组卷算法的设计[J].价值工程,2012,20:223-224.

[3]董园.基于改进遗传算法的自动组卷系统的研究[J].三明学院学报,2012,06:17-22.

[4]施俊,缪勇.基于遗传算法的自动组卷研究与应用[J].电脑知识与技术,2014,34:8160-8162.

蒋哲(1986-)，男,江苏常州人，本科,研究方向：计算机方向。