自适应遗传算法

朱彦廷

（广西现代职业技术学院计算机系，广西河池 547000）

1 引 言

遗传算法[1]127-128由美国Michigan大学J. Holland教授1975年提出，它通过模拟生物进化过程搜索最优解，与传统算法相比具有高鲁棒性、全局搜索性、内在并行性等优点[2]94-97，因此，受到人们的普遍关注，被广泛应用到各个领域.

遗传算法的基本步骤[3]133-135如下：

（1）设置群体大小M、终止代数T、交叉概率Pc、变异概率Pm，进化代数t= 0，随机生成M（应为偶数）个个体，得到初始群体；

（2）计算群体中各个个体的适应度；

（3）交叉操作；

（4）变异操作；

（5）选择操作，得到下一代群体；

（6）如果t﹤T，t=t+ 1，转到（2），如果t=T，结束运算，将运算过程中得到的适应度最大的个体（即最优解）输出.

其中，适应度函数和群体规模、交叉概率、变异概率等参数对算法的性能有很大影响[4]79-83，如何确定得更合理一直是人们的研究方向.

通过研究对适应度函数、交叉概率和变异概率对遗传算法性能的影响，本文提出一种自适应的遗传算法，使得群体进化速度更快，并能避免发生早熟.

2 自适应遗传算法

2.1 适应度函数

适应度表示个体接近最优解的程度，个体的适应度越高，被选择（即遗传）的概率越大.选择运算一般采用比例选择[5]235-237，用个体的适应度与群体中个体的适应度的和的比值作为它被选择的概率，因而在设计适应度函数时，要保证值非负.

在进化的初期，个体的适应度普遍较低，可能出现个别适应度很高的个体，因此这样的个体被选择的概率远大于其它个体，可能一再被选择，从而充斥下一代群体，使进化难以进行（相同的个体交叉，得到的个体与原个体相同；相近的个体交叉，可能得到的个体与原个体相同），出现早熟现象；而在进化的后期，个体的适应度相近，较好的个体和较差的个体被选择的概率接近，也使进化难以进行.

为解决上述问题，可对适应度进行比例变换，如线性比例变换、幂比例变换和指数比例变换等[6]90，但这通常需要对问题有深刻的了解，且经多次试验，才能确定较好的变换方式及其参数.

本算法用适应度的差值来衡量适应度的差异大小，先定义

其中，Δf为当前群体中适应度的差值，ΔF为适应度的差值的理论最大值，fmin为当前群体中适应度的最大值，fmax为当前群体中适应度的最小值，Fmin为适应度的理论最小值，Fmax为适应度的理论最大值，易知β的取值范围为[0，1].

如果用适应度和其平均值的差值的绝对值的和（或差值的平方的和，即方差）等来衡量适应度的差异大小，当然更准确，但计算繁琐一些，在要求较高的情况下可以采用.这时理论上差值的绝对值（或差值的平方）的和的最大值出现在当一半个体的适应度均为Fmin，而另一半个体的适应度均为Fmax时.

然后对适应度进行变换：

其中，f（x）为原适应度，f'（x）为变换后的适应度，k是正常数，根据具体情况进行设置，越大则变换力度越大，但应尽量保证最后适应度值非负.

当群体中个体的适应度差异较大时（β>0.5），个体的适应度都增加k（β -0.5），则适应度小的个体增加的比例大，被选择的概率将增大，有利于维持群体的多样性，以对更广的解空间进行搜索，避免囿于局部极值；当群体中的个体适应度差异较小时（β< 0.5），个体的适应度都减少k（0.5- β）（这往往发生在进化后期，个体的适应度普遍较大，减少后多半仍非负，如果个别个体的适应度实在太小，减少后为负，可补充定义在这种情况下其为 0（意味着在下一代群体中不可能出现）或某个较小值（意味着在下一代群体中也可能出现，这有助于维持群体的多样性），则适应度大的个体减少的比例小，被选择的概率将增大，增强了搜索的导向性，避免随机搜索.

可以看出，该变换式只对个体之间的差异大小敏感，与单个个体适应度的取值无关，与原适应度函数的形式也无关.

2.2 交叉概率

基本遗传算法的交叉概率是固定的，但在进化的初期，个体差异较大，交叉产生更好个体的可能性也较大，如果增大交叉概率，将加快进化进程；在进化的后期，个体差异较小，交叉产生更好的个体的可能性也较小（好比“近亲结婚”），如果减小交叉概率，可减少计算量，故定义交叉概率Pc=β，显见Pc的取值范围为[0，1].

2.3 变异概率

基本遗传算法的变异概率也是固定的，但当个体差异较大时，如果减小变异概率，可减少计算量，也能保持群体的多样性；当个体差异较小时，如果增大变异概率，将保持群体的多样性，故定义变异概率

变异概率一般取值较小（因为变异运算可能破坏较好的个体），故这里乘以0.1（根据具体情况，也可以选别的数值），可知Pm的取值范围为[0，0.1].

3 实 验

算法的在线性能定义为

其中f（t）是时刻t得到的适应度的平均值.它表示算法在到当前为止的时间内得到的所有性能值的平均值（因算法在运行过程中随机性较大，故用平均值），反映了算法的动态性能.

离线性能定义为

其中f*（t）是时间段[0，t]内得到的适应度的最小值.它表示算法在到当前为止的时间内得到的最优性能值的平均值，反映了算法的收敛性能.

分别用基本遗传算法和本算法求下列函数的最小值.

函数（1）是病态的，难以极小化，最小值为0（x1=1，x2=1）；

函数（2）含有高斯噪声，若不考虑噪声，最小值为0（x1=0，x2=0，…，x30=0）.设置M=50，T=100，基本遗传算法的Pc=0.6，Pm=0.05，性能比较如图l、图2所示.

图 l （a）、（b）分别为函数（1）、（2）的在线性能测试

图2 （a）、（b）分别为函数（1）、（2）的离线性能测试

从图1可以看出，本算法的在线性能比基本遗传算法稍好，这是因为本算法的变异概率是动态变化的，有效地保持了群体的多样性，能够向更广的解空间进行探索，并避免了过早收敛.

从图2可以看出，本算法的离线性能比基本遗传算法有了较大提升，这是因为：

（1）自适应的适应度函数能更好地推动群体的进化，当个体的差异大时，它尽量缩小差距，既让优秀的个体能充分发展，也给较差的个体一定的进化机会；当个体的差异小时，它尽量增大差距，使群体能继续进化，不致过早收敛（即早熟）；

（2）自适应的交叉概率能根据群体的状况灵活调整进化策略，当个体的差异大时，它适当增大，以更好地利用优秀个体的基因，充分发挥优秀个体对进化的积极作用；当个体的差异小时，由交叉产生更好个体的可能性减小，它适当减小，以减少计算量；

（3）自适应的变异概率在进化过程中作用微妙，在进化前期，个体的差异较大，只要很小的变异就足以保持群体的多样性，因此它适当减小，增强交叉的导向性（变异将改变交叉产生的个体）；而在进化后期，个体的差异较小，因此它适当增大，避免陷入局部极值.

还可以看出，本算法的收敛速度比基本遗传算法要快不少，基本遗传算法甚至发生早熟，这表明了本算法优良的自适应特性.

4 结 论

本算法把适应度、交叉率、变异率的变化都统一反映在了一个β因子的变化上，能够根据进化情况自动地调整适应度、参数，具有明显的自适应性，能避免早熟现象，更快地搜索到更优解，收敛性、收敛速度均比基本遗传算法好，且比较简单，和基本遗传算法十分接近，如果找到基本遗传算法程序，略加改变即可，容易实现.

[1]刘晓霞，窦明鑫.一种改进的自适应遗传算法[J].合作经济与科技，2012（5）.

[2]张瑜，娄卉芳，文良浩，等.一种改进的遗传算法交叉策略[J].湖南科技大学学报：自然科学版，2012（1）：94-97.

[3]苑士义，撒力.基本遗传算法设计及改进[J].微计算机信息，2011（12）：133-135.

[4]李擎，张伟，尹怡欣，等.一种新的调节交叉和变异概率的自适应算法[J].控制与决策，2008（1）：79-83.

[5]赵志鹏.董红斌.一种新的基于遗传操作的改进型遗传算法[J].计算机应用与软件，2008（1）：235-237.

[6]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1999.