求最大点的近似解

应用背景

考虑以下场景,给定平面上的n固定点p_i,找到点p%3D%28x%2Cy%29使得%5Csum%5Climits_%7Bi%3D1%7D%5End%28p%2Cp_i%29取最小值。

从数学的角度来看,这只是一个求多元函数极值的问题,但%5Cfrac%7B%5Cpartial%20f%7D%7B%5Cpartial%20x%7D%3D%5Cfrac%7B%5Cpartial%20f%7D%7B%5Cpartial%20y%7D%3D0的解并不容易计算。

在应用层面,我们考虑近似解。

爬山算法 Hill Climbing

背景:

你去爬山,你是怎么爬到山顶的?只需在附近走两步,然后到它变得更高的地方去。

算法:

围绕当前解x_i进行搜索,将本次搜索得到的最优解作为x_%7Bi%2B1%7D,进行迭代。

梯度下降 Gradient Descent

背景:

当你上山时,你需要走两步才能知道从哪里爬得更高吗?不是瞎子。你站在原地环顾四周,找到地平线上的最高点,然后朝那个方向走。

算法:

求当前解x_i处的梯度,沿梯度的(反)方向走一步得到x_%7Bi%2B1%7D,从而进行迭代。

题:

这个步长不容易确定。你是一个步子很大的巨人,你可以翻过这座山,转身退后一步。大山一直在你的胯下,但你不能踩到它。

模拟退火 Simulated Annealing

背景:

可以发现,以上两种算法只能收敛到局部最优解:更高的山在视线之外,而周围的山都在视线之内。

名字的由来这里就不介绍了,上面的例子可以说明算法。

如何找到更高的峰?

您不再只是爬到山顶看低处,有时您还可以找到通往更高山峰的新途径。

算法:

如果可以找到更好的本地解决方案,则必须对其进行更新。

如果没有找到,以概率P用更差的解x_%7Bi%2B1%7D更新当前的解x_i

其中P%3De%5E%7B%5Cfrac%7Bf%28x_i%29-f%28x_%7Bi%2B1%7D%29%7D%7BT%7D%7D,这里假设找到最小值。

其中,T代表你的体力。体力会逐渐下降(这会收敛),你也不愿意四处走动。

一般来说,我们让T以指数速率减少,例如T_k%3DT_0%280.95%29%5Ek

地毯式搜索 Combing

这个名字是我编的。

背景:

可以发现SA的参数很多,非常难调。而引入SA就是为了解决局部最优解的问题。我们为什么不尝试取遍所有的局部最优解,来得到全局最优解?也就是说在山区里随机空降一些人,让他们都走到视线内的最高峰然后汇报给总部。

当然你硬要说这种方式在分形(如Weierstrass函数)上会遭遇挫折的话我也没办法。

事实上,f%28x%29%3Dxsinx可以摆脱这种方法。

但是还是有一定的实用价值的。

算法:

取几组初始解,尽量均匀分布(否则一个局部区域的多个点没有意义),分别进行梯度下降,最后取极值集中的最大值。

版权声明:本文为博主LugarTang原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/LugarTang/article/details/123442199

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
乘风的头像乘风管理团队
上一篇 2022年3月14日 下午12:24
下一篇 2022年3月14日 下午12:45

相关推荐