改进遗传算法在组卷问题中的应用

苏玉慧　龚威

[摘要]结合遗传算法的原理和思想，对考试系统自动组卷的问题进行了分析和研究，利用遗传算法求解试题库自动组卷问题的方法。讨论运用遗传算法求解在一定约束条件下的多目标参数优化问题，给出了功能块的概念，并采用了新的编码方式、交叉算子和变异算子对其进行优化。

[关键词]遗传算法 组卷策略 交叉运算

引言

一个完备的在线考试系统可以使用户在网上学习过后及时检验自己的学习效果，发现自己的不足，使得学习效率得到很大提高。而在线考试系统的试题库系统建设，组卷策略是一个非常重要的环节，本文提出一种用改进的遗体算法来求解试题组卷问题。

一、传统遗传算法的问题求解

遗传算法的群体搜索策略为多目标优化提供了非常合适的解决方案。一般来说，多目标优化问题并不存在一个最优解，所有可能的解都称为非劣解，也称为Pareto解。传统优化技术一般每次能得到Pareto解集中的一个，而用遗传算法来求解，可以得到更多的Pareto解，甚至是整个的解都成为Pareto解。

式中：C为个体的编码方法； E为个体适应度评价函数；Po为初始群体；M为群体大小；Φ为选择算子；Г为交叉算子；Ψ为变异算子； T为遗传运算终止条件。遗传算法的基本步骤：确定编码方案、确定适应函数、确定选择策略、控制参数的选取、遗传算子的设计、算法终止准则的确定等。用进化方法处理多目标优化问题的关键是进化选择机制。多目标优化的遗传算法与单目标优化的进化算法基本相同，仅在计算适应值上有差别。

遗传算法框架中的参数往往与待解决的具体问题密切相关。针对自动组卷问题，我们给出相应的算法步骤如下：

步骤1：染色体的编码

假设试题库中有m道题，可用一个m位的二进制串来表示，形式为：xl x2 x3…xm其中若xi为1，则表示该题被选中，若xi为0则表示该题未被选中，即

当第i道题被选中

当第i道题未被选中

若一份试卷中有n道试题，则xl x2 x3…xm串中应有n个1。

步骤2：初始化群体

通过随机的方法生成初始化的串群体。在串群体中，串的长度是相同的，群体的大小根据需要按经验或实验给出。

步骤3：计算当前种群每个个体的适应度值

本问题的适应度函数可定义为

fi表示第i个属性指标与用户要求的误差的绝对值。

wi表示第i个指标对组卷重要程度的权值。

f是所有指标与用户要求的误差绝对值之和。

步骤4：选择

按照一定的选择概率对种群进行复制，选择较好的串生成下一代（个体的适应度函数值越小，该串的性能越好，选择概率越大），去掉较差的串。

步骤5：交叉

交叉是两个串按照一定的概率（交叉概率Pc），从某一位开始逐位互换。首先，对每个二进制串产生一个在0～1的随机数，若该数小于Pc，则选择该串进行交叉否则不选择。随机地对被选择的二进制串进行配对，并根据二进制串的长度n，随机产生交叉位置i，i为[1，n-1]上的一个整数，然后按下面的方式交叉：

步骤6：变异

变异是二进制串的某一位按照一定的概率（突变概率Pm）发生反转，1变为0，0变为1。这里Pm较小，Pm可小于0.001。但在实践中发现，在有些遗传算子中，Pm为0.1时更好。

步骤7：终止

记录进化的代数，并判断是否满足终止条件。若满足，则输出结果，否则转向步骤3继续执行。终止条件如下：

（a）出现种群满足f=0；

（b）某个个体适应度值达到指定要求；

（c）达到指定的进化代数；

（d）当前种群中最大适应度值与以前各代中最大适应度值相差不大，进化效果不显著。

二、改进的遗传算法

（1）编码的改进

根据标准化试卷中每种题型所占分数和题数是相同的特地点，给出采用独立编码的策略。独立编码策略就是将以往的合成编码分解成多个相对独立的编码，在本问题中就是根据各个题型各自编码，然后对每一种题型再采用传统编码策略进行处理，但组与组之间的编码是独立的。其中每一组反映一个题型。每一组长度由题库内该题型数所定。这样，可以将整个二进制串按照题目的类型划分为不同的功能块。每个功能块采用独立的二进制编码。也就是说，每个功能块对应一种特定的题型，而该功能块中，“1”代表该题被选中，“0”代表该题未被选中，“1”的数目即该种题型的试题数目。显然，按这种规则产生的初始种群已满足试题对题型、分数和答题时间的要求。

因为每一组反映一个题型，每一组长度由题库内该题型数决定，分别共有k1，k2…kn编码长度由题库中所含试题数决定，n是题型数。设试题库中共有k道试题，编码形式如下：b1b2…bk，随机生成初始化串种群，串长度都是相同的.

且满足 ，其中，m是试卷所含的题目数。

其中，ml，m2，…分别为试卷中各个题型所出题目数。

本问题适应度函数定义为：

其中：wi对应为第i组卷因素对组卷重要程度的权值，ei对应为第i组卷因素对组卷目标的误差。

在实际实现时，在资源有限的情况下，必须进行“优胜劣汰”的选择，使用的是比例选择。设H为任一个染色体，Pt（H）表示t时染色体H出现的概率。在选择阶段，每个染色体根据它的适应值被选择，因此染色体H在t+1时刻的概率为：

其中 为群体适应值，可以看到，染色体H的适应值越高，他被选中的概率越大。种群规模N：N值大进化较慢，但易搜索到全局最优解，而N值小时进化速度快，却不易搜索到最优解，权衡效率和性能。一般N取值为200左右。

（2）交叉运算的改进

由于种群中每一个功能块对应着一个题型，所以，为了保证每个题型的数目不变，交叉点的选择不能破坏功能块的完整性。假设交叉点位于第i个功能块内，则前i个功能块保持不变，从第i+1个功能块开始逐位交换。

（3）变异运算的改进

由于在每个功能块中，“1”的数目即是该题型试题的数目，因此在变异过程中应保证整个种群所有功能块中“1”的数目不变。可执行如下过程，首先，由变异概率决定某位取反；然后，检查、修正字符串中“1”的数目，保证不发生变化。

（4）用全局最优解替换本次迭代的最差解

为保证好的字符串不至于流失，每次遗传操作前记录本次迭代的最优解，若该解优于全局最优解则替换全局最优解，否则全局最优解保持不变。此次遗传操作后，用全局最优解换本代的最差解。遗传算法组卷的算法描述如下：

主要算法段描述

三、实验

四、结束语

对比表3-2、表3-3的实验结果可知，在不同种群下，采用功能块的改进的遗传算法性能优于传统的遗传算法，而且指标有很大的提高，这说明改进的遗传算法降低了问题的求解难度，提高了问题的求解效率。组卷是组成一份误差在可接受范围内的试卷，并非要求此试卷的整体指标一定是全局最优，尤其是在改进的遗传算法中，整个试卷的题目类型、题目数量、题目分数不会产生误差，而在篇章、难度、区分度上的一定范围内的误差是可以接受的。由表3-4可知适当地放大误差可较大幅度缩短求解时间。对比表3-5可知传统的遗传算法效率好于普通的随机算法，而改进的遗传算法在时间上又优于传统的遗传算法。

[参考文献]

[1]曾凌峰.基于遗传算法的自动组卷策略与实现[J].辽宁科技大学学报，2010，（03）.

[2]吴金华，戴淼等.基于遗传神经网络的陕西省土地利用结构模型研究[J].安徽农业科学，2008，（36）.

[3]尹文彬，许腾等.基于遗传算法的舰艇编队火力分配问题研究[J].兵工自动化，2010，（05）.

（作者单位：江西财经职业学院 江西九江）