基于遗传算法的自动组卷算法的设计

摘要： 自动组卷系统中组卷算法的好坏直接影响到组卷的效率和质量，本文分析了各种常用的组卷算法，提出将改进的自适应遗传算法用于解决组卷问题，以提高组卷效率。并详细论述了基于遗传算法的自动组卷策略的实现过程。

Abstract: Test paper composition algorithm in system of automatic test paper construction can affect the efficiency and the quality of test paper composition. In this paper, a variety of commonly used test paper composition algorithm was analyzed, and the improved adaptive genetic algorithm used to solve issues of test paper composition was proposed, so as to improve its efficiency. The implementation process of strategies for automatic test paper composition based on genetic algorithm was discussed in detail.

关键词： 自动组卷；组卷算法；遗传算法

Key words: automatic test paper composition；test paper composition algorithm；genetic algorithm

中图分类号：TP39 文献标识码：A 文章编号：1006-4311（2012）20-0223-02

0 引言

自动组卷就是利用计算机在试题库中按照用户要求抽取相应的试题组成试卷。而如何保证计算机生成的试卷能最大程度的满足用户的不同需要，并具有随机性、科学性、合理性，这是实现中的一个难题[1]。目前存在一些组卷系统，但由于课程科目繁多，即使同一门课程，各类学校、各种专业课程目标不同，也使组卷系统的应用很难推广普及。

1 自动组卷算法

组卷系统中决定试卷质量的关键是抽题算法，目前出现的自动组卷系统中所采用的抽题算法大致分为三种，即随机算法、回溯试探法和遗传算法。

基于随机法的自动组卷利用系统提供的随机函数，在试题库中抽取符合要求的试题组成试卷。这种方法实现简单，并已经有很多实际应用。[2]随机法组卷过程中，容易出现由于某个要求未满足，如预计考试时间超过给定时间，而会使整个组卷过程失败的情况，这样导致很多无效试卷，降低了组卷效率。

回溯法是在随机抽取试题的过程中，验证所选试题是否满足给定条件从而决定是否抽出该试题，当无满足条件的试题而组卷又未完成时，采用回溯试探废弃前一段时间所做的操作重新进行组卷，由于仅是部分操作废弃，降低了无效组卷次数。[3]回溯法虽然组卷成功率比较高，但它是以大量的时间作为代价的。

遗传算法是一种新型的、模拟自然界生物进化过程的随机搜索、优化方法。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法采用一种群体型操作，该操作以群体中的所有个体为对象，选择、交叉和变异是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作[4]。遗传算法的操作步骤如下：①生成初始群体；②计算群体中个体适应度值；③对群体中个体进行遗传操作（即选择、交叉和变异）；④如果满足停止搜索条件，叠代停止，输出问题的最优解；否则，转向步骤③。

由于组卷问题是一个典型的多重约束目标问题，而约束目标的多样性，造成采用传统的搜索算法往往存在成功率低、组卷时间长，缺乏专家知识的启发性搜索等缺点。遗传算法具有的全局寻优、智能搜索技术和收敛速度快等特性正好满足自动组卷的需要。但基本的遗传算法会产生早期的盲目搜索、过早收敛、收敛于局部最优解、局部搜索能力不强等弊端，目前已有研究人员将改进的遗传算法应用到组卷中，文献[5]提出稳态策略的单亲遗传算法，使整个种群保持在最有可能获得成功的状态，加快了算法向全局最优值的逼近速度。本文结合遗传算法理论，将编码方法、遗传算子进行改进后的遗传算法用于试题组卷中，得以在组卷问题上获得良好的解。

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

2.1 改进的遗传算法 遗传算法应用时的关键问题在于串的编码方法、适应度函数的确定、遗传算法自身参数设定，不同的编码方案、选择策略和遗传算子相结合，构成了不同的遗传方法。

2.1.1 改进选择算子 改善选择算子操作的目的是为了避免有效基因的缺失，提高遗传算法的全局收敛性和搜索效率。本文将最优法和轮赌法相结合，采用最优保存策略进行优胜劣汰操作，轮赌法确保全局搜索。

2.1.2 改进交叉算子Pc和变异算子Pm 交叉算子主要作用是产生新个体，实现算法的全局搜索能力，变异算子主要起维持种群多样性、抑制早熟的作用。本文中，采用如下的改进自适应遗传算法[6]:

交叉概率计算公式：

mtmp=pcmax×e■

Pc=mtmp mtmp＞pcminpcmin mtmp?燮pcmin

式中，mtmp是一个中间计算变量；Tgen为预设的最大进化代数；t为当前进化代数（0≤t≤Tgen）；Pcmax是预置的最大交叉概率，Pcmin是预置的最小交叉概率。

变异概率的设计的总趋势应该是能逐渐减小而使群体能够迅速集中。另外，对于劣质个体，其变异概率应加大，而优秀个体应给予较小的变异概率。为此设计了如下的与遗传进化代数和个体适应度相关的自适应变异概率：