遗传算法的收敛

机器算法验证 遗传算法 收敛
2022-03-20 11:52:50

有谁知道决定何时完成遗传算法的任何方法?在 MCMC(例如,BUGS)中,多个链从不同的随机点开始。当它们看起来都一样时,它就完成了。这种方法是否曾在 GA 中尝试过?还有其他想法吗?

4个回答

一个简单而常见的测试是衡量目标函数的改进:如果在一定数量的迭代中不再改进(一定量),你也可以停止。其他优化算法也使用这种方法。

如果您对适应度没有任何线索,即是否存在局部最优、高原、山谷等,则很难理解 GA(或其他进化算法,EA)是否找到了全局最优。您可以使用多种群方法,例如基于岛屿的遗传算法,然后使用特定的迁移策略检查所有种群何时收敛到相同的解决方案。这只是您的问题的一个可能答案,避免局部最优的问题是 EA 设计的关键问题,尤其是在高维方面。

遗传算法固有的随机性使它们成为如此强大的工具,然而,这种特性也使得很难知道何时找到了全局最小值。例如,您可以长时间坐在局部最小值上的一代人,然后幸运的突变将您踢出局并寻求更好的解决方案。

当然要进行多次训练(如果搜索空间相当小),以了解推荐 GA 生成的解决方案。尝试绘制获得的解决方案的分布。较高的突变率可能会减慢训练速度,但也会使算法有更多机会跳出局部最小值。

一种可能的解决方案是查看最后预测的标准差,并在它低于阈值时停止训练。如果足够大,这应该提供一个合理的方法,表明您已经 足够接近全局最小值。请注意,追求绝对最小成本值可能并不总是会产生无法很好地概括新数据的解决方案。nn

理论上(可能具有讽刺意味),如果您不知道最优值的数量和出现的位置,则无法确定您的 GA 的最终解决方案是局部最优、全局最优还是其他任何解决方案。

但是您可以减少所有可能的结果,也就是说,在执行 GA 搜索之后,如果您应用本地搜索算法(牛顿法等),并以 GA 的最终解决方案作为起点,那么生成的结果要么是本地的,要么是全局最优。

用不同的随机种群重新启动 GA 将有助于搜索搜索空间的不同方面,本地优化器将执行“微调”操作,如果幸运的话,您还将获得新的本地或全局解决方案。在执行多次 GA 搜索后,您可以选择最佳的作为全局解决方案。

最后,您仍然不确定。