基于离散变量自适应遗传算法的改进

吕秀芹

（江苏农林职业技术学院，江苏句容 212400）

遗传算法(Genetic Algorithm，GA)是一种基于模拟自然界生物遗传演化规律的随机探索和优化算法[1]。算法将问题对象进行编码，形成类似生物学上的染色体，通过对染色体的遗传进化，从而得到问题的优化解。算法能有效地处理大量离散参数，在求解之初可以采取一些方法使得初始种群在解空间合理分散，并且通过基因交叉和变异操作，增加了全局寻优的能力。遗传算法目前已广泛地应用于函数优化、组合优化、自动控制、图像处理、生产调度等多个行业。

算法的基本运算过程[2]为：将问题对象以二进制或实数等形式进行编码，把问题的单个可行解看成是一个符号串，从而形成类似生物学上的染色体或个体。然后随机生成M个个体作为初始群体P(0)，用已设计好的适应度函数计算当前群体中每个染色体的适应度值，系统根据问题域中个体的适应度大小选择新的染色体，使用选择算子将适应度高的染色体选择进入下一代，然后再利用这些已选择的染色体进行交叉、变异等操作，产生出代表新的解集的群体P(t)。上述生成新群体P(t)的过程不断重复，直到找到问题的解满足用户的要求为止。由于交叉、变异后产生的新种群与其父种群相比，更能适应于环境，当算法结束后，将末代种群中包含的最优个体进行解码即可得到问题的较优解。

遗传算法通过计算比较个体染色体的适应度与群体平均适应度决定该个体进化或淘汰，但进化到了后期，算法搜索到最优解附近时，要确定最优解要花费大量时间，甚至无法精确定位最优解的位置，且算法容易出现“早熟”。针对算法的这些缺点，有不少学者在遗传算子的改进方面做了不少研究并取得了丰硕的成果，引入了自适应策略改善遗传的性能。

1 自适应遗传算法

遗传算法中遗传算子影响进化的进行，其中交叉概率Pc和变异概率Pm对种群的优化起着决定性的作用。交叉概率和变异概率大，则新个体产生的速度快，有利于保持种群的多样性，但过大又会使优选出的个体被坏，不利于选择算子的作用。交叉概率和变异概率过小，容易产生局部收敛，算法出现早熟。遗传算法按照优胜劣汰的规则,将适应度较高的个体更多地遗传到下一代，算法使得种群后期的适应度要高于初期的适应度。Srinvivas等提出根据种群进化程度自适应遗传算法的策略，即算法根据种群的适应度动态调整交叉概率Pc和变异概率Pm，具体见公式1和公式2。算法的基本思想是：对于适应度高于群体平均适应度的个体，取较小的交叉概率Pc和变异概率Pm，使得该解得以保护进入下一代；对于适应度低于群体平均适应度的个体，取较大的交叉概率Pc和变异概率Pm，使该解被淘汰[2]。

其中fmax为群体中最大的适应度值；fave为群体的平均适应值；f′为要交叉的两个个体中较大的适应度值；f为要变异个体的适应度值；k1，k2，k3，k4取值在[0，1]区间，根据不同的问题特征，可根据实验或经验确定其值的大小。

可以看出，当个体的适应度值大于平均适应度值时，交叉概率Pc和变异概率Pm随着个体的适应度增大呈线性递减。当适应度越接近最大适应度时，即当前解越接近最优解，交叉概率和变异概率越小；当个体的适应度值接近或等于最大适应度值时，交叉概率和变异概率接近或等于零，算法停止收敛操作，将当前个体作为最优解[3]。上述的自适应过程在算法执行到后期有很好的收敛效果，但在算法运行的初期，由于此时的种群可能集中在解集的某个区域，优良个体可能是某一个区域的相对优解，而不是全局的最优解。因此，上述的自适应算法在进化初期容易产生局部收敛，产生“早熟”。

2 自适应遗传算法的改进

在进化初期，为了保持种群的多样性，应增加种群的交叉和变异操作。随着遗传算法进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，种群已经接近最优解。为了使种群的一些好的特性不被破坏，此时的交叉和变异操作应降低。在进化后期，个体间的相似度增加，容易过早的收敛，此时应适当增加变异概率[4]。对于离散变量，初始种群一般以一定的方法尽量分散在解集中，其离散程度较大，进化若干代后，新的个体已经接近最优解，其离散程度明显减小。本文设计根据个体的离散程度来送别其进化的程度，从而得到不同的遗传概率。

考虑到种群在不断的进化，交叉和变异操作不能盲目进行，相互之间应配合进行。本文对上述的自适应过程进行人工干预，引入两个概率系数c和m分别影响交叉概率和变异概率的取值，从而有效防止其在进化初期陷入局部寻优，具体见公式(3)和公式(4)。

其中c，m为分别为交叉概率系数和遗传概率系数，且c≤1，m≤1，其余参数含义同上。

随着迭代进化的进行，每一代种群中个体适应度值的差异是不同的，概率系数c和m随着进化的进行而变化的。在进化初期，种群的个体差异大，各染色体之间的适应度差别也较大，为了增加种群的多样性，实现全局收敛性，此时c和m均取较大值，即交叉概率和变异概率取较大值，以加快进化的速度。随着进化的发展，此时的解已经接近取优解的雏形，为了保让优质个体被选择复制到下一代遗传，c和m的取值均应适当降低。到了进化的后期，种群中个体的适应度差别变小，交叉概率进一步变小，进化速度变慢，易陷入局部最优，此时应适当增加变异操作，避免进入种群“早熟”。

给概率系数c和m取值前，首先要判断种群的进化程度，本文根据种群的离散程度系数Df和平均适应度与最优适应度之间的差值系数Dv进行衡量。离散程度以种群中个体的适应度的均方差表示，具体见公式(5)和公式(6)。

其中，Df为离散程度系数，Dv为平均适应度与最优适应度之间的差值；N为种群规模，ffit为系统设置的目标最优适应度，fi为种群中个体的适应度值。Df反映的是当前种群中个体间适应度的相似程度的大小。在进化初期，个体间离散大，其适应度值差异大，Df和Dv的值较大。进化到后期，个体接近最优解，种群中个体的相似度增大，Df和Dv的值较小。具体操作时，综合这两个系数衡量种群进化程度，引入进化程度系数D，令D=Df+Dv。通过比较D与第一代种群进化系数Df1的关系，从而得到当前种群的进化程度，以决定概率系数c和m的值，函数公式如下：

由于进化过程不断进行，在进化初期，种群的进化程度系数接近Df1；；到最化后期，个体接近最优解，故进化系数接近0，故上面的公式中进化系数D在(0,Df1)间取值。对于不同特征的问题，c和m的值会有变化，本文以典型的离散问题——组卷问题为例，给出c和m的分段取值。可以看出，函数依据进化系数判断进化的程度，从而决定概率系数c和m的不同取值，得到不同进化时期的交叉概率和变异概率，可以很好地控制进化过程，提高算法的性能。

3 算法性能验证

为了验证算法经过改进后其执行的效率和效果，本文应用改进前后的算法进行组卷试验。试验题库包括600道题目，其中单选题300道，多选题100道，判断题200道，按各种题型采用分段实数编码的方案，设定知识点覆盖率、难度系数、各题型题量等要求。使用Visual Studio.net提供的C#语言进行编程设计，程序在Xeon E5506 2.13GHZ，4GBDDR3，WindowServer2003环境下执行。通过设定不同的初始种群规模和最大迭代次进行组卷试验，结果表明，算法经改进后在不同的遗传代数其最优个体的适应度明显高于改进前，提高了组卷成功率，降低了组卷时间。

4 结论

本文基于遗传算法进化的特征，结合自适应遗传算法提出的自动调整交叉概率和遗传概率的理念，提出判断每代个体的进化程度的方法，设计根据进化程度赋予个体的不同的交叉概率系数和遗传概率系数，从而得到不同进化时期的交叉概率和遗传概率，对个体的遗传进行进化，实现算法的快速收敛，并避免了“早熟”现象。将算法用于处理典型的离散问题——组卷问题，算法性能有了较大的提高，其收敛速度明显加快，组卷的成功率也有了提高。

[1]陈晓东,王宏宇.一种基于改进遗传算法的组卷算法[J].哈尔滨工业大学学报,2005(9):1174-1175.

[2]张京钊,江涛.改进的自适应遗传算法[J].计算机工程与应用,2010(46):54.

[3]张国强,彭晓明.自适应遗传算法的改进与实现[J].船舶电子工程,2010(1):83-84.

[4]卢长娜,王如云,陈耀登.自适应遗传算法[J].计算机仿真,2006(1):172-175.