深入理解遗传算法:跳出局部最优

发布于 2021-07-05  173 次阅读


众所周知 遗传算法程序运行几次得到的结果不尽相同

原因就是 其陷入了局部最优解 无法跳出

为了更稳定地得到较优值,需要解决这个问题

那么,首先要了解的是遗传算法为什么会陷入局部最优?

或者说遗传算法是什么?

遗传算法的本质

遗传算法其实是一种随机搜索算法,只不过它不是毫无规则地随机搜索,而是基于一种假设:

函数的极值出现在一个较优值附近的概率要大于出现在一个较差值附近的概率

基于这个假设,遗传算法总是

以较大概率保留较优值所代表的搜索方向,而以较低概率保留较差值所代表的搜索方向

在出现一个局部最优值的情况下,算法保留(搜索)其他方向的概率极低,因此就会陷入局部最优

遗传算法的设计者 当然也考虑到了这点,所以才会有变异操作

理想化的变异

变异操作 就是为了扩大种群多样性 从而跳出局部最优

但两个问题也随之而来:

  1. 为什么变异概率通常在0.1以下?
  2. 是否增大变异概率就能跳出局部极值?

答案显然是否定的。变异操作其实是很理想化的操作:

  • 因为变异得来的后代往往不能和择优下来的子代比较(无法保留)
  • 而增大变异的概率只会让遗传算法成为无规则的随机搜索

所以,变异操作并不能很好的解决这个问题。

于是,就诞生了下面几种解决方案(博主仅知晓)

解决方案

修改的经典

传统遗传算法找到最优解的期望值是有限的,即使找到也可能被交叉变异选择所破坏。因此,找到最优解后应该让他一直保持下去,所以,出现了修改的经典遗传算法:

在每个群体加入一个超级个体,该个体不参与交叉变异选择(与精英选择法的区别就在于不参加选择) 找到一个更优的个体后就替换该超级个体,这个操作放在选择前后均可。

可证明修改后的遗传算法依概率收敛到全局最优解,而传统遗传算法不依概率收敛。证明过程自行百度。

适应度函数尺度化

定义:将适应度函数的值放大或缩小来重新定义适应度函数的过程

方法:

  1. 遗传初期缩小适应度差别(减小超级个体竞争力)
  2. 遗传后期增大适应度差异(加快收敛)

即f(x)=μ(F(x)),F(x)为适应度函数

μ(x)可以为一次函数,幂函数,指数函数等

灾变

是什么?

如果恐龙没有灭绝,灵长类动物是绝没有可能统治地球的。所以要跳出局部极值就必须杀死当前所有的优秀个体,从而让远离当前极值的点有充分的进化余地。这就是灾变的思想。

何时进行?

什么时候进行灾变,换句话说什么时候局部搜索已经充分?设置一个灾变倒计数:从500开始,每一代递减一次,如果出现新的最优值,就重新计数,如果倒计数完毕还没有新的最优值,就认为局部搜索已经充分,就发生灾变。

更合理的步长

如果出现新最优值的时候倒计数递减次数的2.5倍已经超过500则从新的初始值开始倒数。

例:初始倒数500,如果倒数到200时出现新最优值,则从(500 - 200) * 2.5 = 750开始从新倒数,下一次如果倒数到100时出现新最优值,则从(750 - 100) * 2.5 = 1625开始倒计数(这里的2.5是一个经验值,可以在全局参数设置里面调整)。也就是说倒计数的长度取决于进化的速度,进化速度越慢倒计数长度越长。

参考文献

文章部分参考《用遗传算法解决旅行商问题》,但因转载太多,已无从得知原作者