在交叉算子中,精英主义优于非精英主义吗?

人工智能 遗传算法 进化算法 交叉运营商 精英主义
2021-10-28 02:06:18

在遗传算法中执行交叉操作时有两种可能的方法。

  1. 只使用池中的精英,可能也将直接传递给下一代。

  2. 使用池中存在的所有人口。

是否有任何证据表明仅与人群中的精英交叉会使 GA 更快地收敛到一个好的解决方案?我想,为了摆脱局部最小值,需要与所有人口交叉。另一方面,我们为什么要与最不适合的个体进行交叉?

任何的想法?

1个回答

首先,您的问题的答案很大程度上取决于您尝试解决的问题、人口规模、问题搜索空间的大小以及 GA 的其余超参数,例如突变率。

  • 如果问题的搜索空间很大,那么应用您上面描述的精英策略很可能会导致您的算法永远无法达到最佳解决方案,或者经过太多次迭代才能达到最佳解决方案。这样做的原因是,如果您的搜索空间很大,那么由于您的初始种群的初始化是随机的,因此前几次迭代中“最合适”的个体不一定会引导您到最优解。因此,过早地应用精英策略可能会让你永远或太长时间陷入局部最优。我个人发现对这种情况有效的方法是让您的算法尽早探索尽可能大的搜索空间(即使用“池中存在的所有人口” )然后逐步介绍你上面描述的精英策略(这是一个类似于神经网络中的动量的想法)。简而言之,你想更早地探索,然后当你逐渐开始利用你所发现的东西时。
  • 如果搜索空间比较小,我认为精英策略会是一个非常好的主意。你也可以尝试一下,如果你真的想坚持使用精英,可以尝试变异精英个体(这样可以让你稍微探索一下),或者选择更高的精英率(即个体数量)成为精英)。

现在回答你其他问题:

是否有任何确定的信念,即只对人口中的精英进行交叉,更快地收敛解决方案?

不,但我没有这方面的参考,所以我想我的说法有待纠正,但我会解释为什么我说不:

纯粹精英主义的问题在于它导致遗传算法收敛到局部最大值而不是全局最大值。基本上,纯粹的精英主义只是与最近的局部最大值的竞赛,一旦你到达局部最大值,如果你继续精英主义,你几乎不会从那里得到任何改进。

我想为了摆脱局部最小值,需要对所有人口进行交叉;另一方面,我也说为什么要对弱人口进行交叉?

“为什么要对人口中较弱的个体进行交叉?” - 探索。希望是对较弱的个体应用交叉或突变将产生更健康的个体。