什么是局部最优?


局部最优(Local Optimum):如果不努力通过系统思考来更好地理解复杂的系统,你就会陷入追逐局部最优解的境地,这固然是好的解决方案,但不是最好的。如果你想努力实现最佳解决方案,那就去找全局最优。

在数学和计算机科学中,局部最优是在可能解决方案的小邻域内解决问题的最佳解决方案。这个概念与全局最优相反,全局最优是考虑每一个可能的解决方案时的最优解。

在开发解决问题的算法时,模拟褪火等启发式方法可以最大限度地减少局部最优而非全局最优的解决方案。

模拟褪火
模拟褪火、模拟退火(Simulated annealing, 也称为 SA)是一种用于优化复杂搜索算法的技术。它被用来寻找有最佳表现机会的算法,即使它们可能不是保证的最佳解决方案。SA被用于许多计算机科学和数学的优化中。

这个术语起源于冶金学,其中退火是指控制金属的加热和冷却,以逐渐减少其缺陷。在SA中,这个过程是通过随着搜索空间的增大而逐渐减少次优解的概率来模拟的。

SA的一个很好的用途是用于旅行推销员寻找相互连接的城市之间的最佳路径。SA对于推销员是有帮助的,因为随着问题规模的增加,可能的解决方案的搜索空间会呈指数级增长。

连续域
当要优化的函数是连续的时,可以使用微积分来找到局部最优值。如果一阶导数处处存在,则可以等于零;如果函数有一个无界 域,要使一个点成为局部最优,它必须满足这个方程。然后二阶导数检验提供了点为局部最大值或局部最小值的 充分条件。

搜索技术
用于解决优化问题的局部搜索或爬山方法从初始配置开始,并反复移动到改进的相邻配置。生成搜索空间中的轨迹,它将初始点映射到局部最优,局部搜索被卡住(没有改进的邻居可用)。因此,搜索空间被细分为吸引力盆地,每个盆地由所有初始点组成,这些初始点具有给定的局部最优值作为局部搜索轨迹的最终点。局部最优可以是孤立的(被非局部最优点包围)或高原的一部分,即具有多个等值点的局部最优区域。