基于遗传算法智能组卷方案的调整

谢志伟

引言：本文介绍了传统遗传算法的组卷方案，针对遗传算法的“早熟”现象分析传统遗传算法组卷的缺点，并提出了改进方案，是对遗传算子合理设置，通过实际组卷评估，此方案能大大减少组卷时间，并能组出较高质量的试卷，大大提高工作效率。

一、传统遗传算法

传统遗传算法是使用二进序列组合进行编码的。有一个最初的编码集合，我们称为初始种群。在此基础上，采用适应度函数进行策略选择，使用交差和变异两种操作来产生下一代种群，就这样，一代一代的遗传下去，直到出现满足条件时候为止。

二、传统遗传算法“早熟”现象分析

随着种群进化的不断扩大，就会产生很多高适应度模式的个体，并且是呈指数幂次的速度递增，这样就会导致种群个体相应部位的基因趋于收敛，最终种群个体的多样性就会受到影响。在理论上，遗传算法的种群规模是不受限制的，上一代群体中的优秀模式一定能够在下一代中，因此，随着种群多样性的减小，种群必然收敛到问题的最优解。但我们在实际应用中，由于时间、资源、种群规模等各种因素的制约，就不可避免的造成种群个体多样性过早的趋于一致，会使搜索算法停滞不前，最终收敛于一个局部最优解，而无法收敛于全局最优解，这就是“早熟”现象。

“早熟”现象原因：

（1） 群体规模：当群体规模较小时，就会使群体中先天的等位基因不足，即便是人为的调整变异算子，生成具有较好的基因群体的几率也会很小。随着变异算子调整操作的加强，对群体中已有的优秀个体的破坏力也在增加。

（2） 选择算子：如果选择群体中最优个体的比例大的话，个体选择压力加强，导致群体的多样性迅速降低，很快就保持一致，趋于收敛；相反，如果抽样选择当前群体中最优个体比例小的话，个体选择压力太小，模式竞争能力就会减小，遗传算子重组生成优秀模式的能力降低，也会尽早的出现“早熟”现象。

（3） 变异算子：如果变异算子调整到比较小时，群体的多样性就会大大减小，容易将优秀模式的基因丢失，并且是不可恢复；如果变异算子设置较大时，可以使群体多样性保持在较高水平，但优秀模式被破坏的概率也會大大增大。

（4） 适应度函数：适应度函数如果保持高度非线性，染色体基因是高度相关，优秀模式更容易被破坏，多样性迅速降低，很快就会趋于一致。

（5） 群体初始化：群体初始化时候要相对保持均匀，不要出现局部分布现象，这样会导致局部收敛，很快的就会使个体趋于一致。

三、避免“早熟”现象发生的参数调整

（1） 合理初始化种群，做到分配均匀

种群初始初始化情况对遗传算法的计算有着重大的影响，要做到全局最优，种群在解空间中应尽量的均匀分布。

具体方法是：

子空间分割是分别对m维变量在其可行解空间进行均匀分割得到n个变量子空间（n值的大小可以根据可行解空间的大小和计算的精度要求确定，考虑到计算效率，一般不宜过大）。对这m*n个变量子空间进行组合得到n^m个可行解子空间。

产生子空间初始种群是依上述思路在可行解子空间内对m维变量进行均匀分割产生k个子区间，设某一变量子区间的边界为[b1，b2]，则以b1+（b2-b1）/2作为该子区间的均值。采用变量子区间均值的组合作为初始种群，初始种群为k^m。这种办法产生初始种群的优势在于不仅使初始种群[24]中包含最优解组合的概率增强，而且可以避免性能接近的个体入选，以减小种群大小。该方法与后面的遗传算子相结合，可提高搜索效率和收敛于全局最优解的概率。

当然，也可不进行后面子空间分割直接依上述思路在可行解空间产生初始种群。

（2） 交叉算子和变异算子参数的动态调整

交叉算子可以使基因更加优化，产生新生个体。传统的遗传算法中，交叉率Pc是个常数，实际上交叉率Pc与遗传代数的有着密切的关系。遗传迭代初期，Pc如果选的大，可以造成足够的扰动，从而增强遗传算法的适应能力；而在后期，Pc选的小，会破坏优良基因，加快收敛速度。所以我们要根据情况适时调整交叉算子，才能使遗传的后代为优良的后代。

以上分析表明，种群进化情况可以根据自适应函数来动态地调整交叉算子Pc和变异算子Pm，交叉率和变异率与个体的适应度在种群平均适应度和最大适应度之间呈线性关系。在进化初期，采用较大的群体规模，较大的交叉概率和较小的变异概率，这样可以有效的增加群体的多样性，提高算法的全局收敛性，克服早熟现象。在进化后期，减小群体规模和交叉概率，提高算法效率和局部搜索能力，提高变异概率，提高群体的多样性，避免陷入局部极值点。

小结：上面讲了传统遗传算法的组卷方案，分析传统遗传算法组卷的不足，并提出了改进措施，进而给出了改进遗传算法的流程，通过反复实验加以验证，改进措施确实在很大程度提高了算法的效率和试卷的质量。

参考文献

[1]毛秉毅.基于遗传算法的智能组卷系统数据库结构的研究，计算机工程与应用.2003，28（6），230-232页.

[2]徐江涛.基于遗传算法的试题库智能组卷研究.湖南师范大学硕士论文.2007：9-47页.

[3]王萌，金汉均，王晓荣.集合随机抽选法在智能组卷中的研究.计算机工程与设计.2006，27（19）：353-358页.

（作者单位：黑龙江农垦职业学院 ）