应用背景
考虑以下场景,给定平面上的固定点,找到点使得取最小值。
从数学的角度来看,这只是一个求多元函数极值的问题,但的解并不容易计算。
在应用层面,我们考虑近似解。
爬山算法 Hill Climbing
背景:
你去爬山,你是怎么爬到山顶的?只需在附近走两步,然后到它变得更高的地方去。
算法:
围绕当前解进行搜索,将本次搜索得到的最优解作为,进行迭代。
梯度下降 Gradient Descent
背景:
当你上山时,你需要走两步才能知道从哪里爬得更高吗?不是瞎子。你站在原地环顾四周,找到地平线上的最高点,然后朝那个方向走。
算法:
求当前解处的梯度,沿梯度的(反)方向走一步得到,从而进行迭代。
题:
这个步长不容易确定。你是一个步子很大的巨人,你可以翻过这座山,转身退后一步。大山一直在你的胯下,但你不能踩到它。
模拟退火 Simulated Annealing
背景:
可以发现,以上两种算法只能收敛到局部最优解:更高的山在视线之外,而周围的山都在视线之内。
名字的由来这里就不介绍了,上面的例子可以说明算法。
如何找到更高的峰?
您不再只是爬到山顶看低处,有时您还可以找到通往更高山峰的新途径。
算法:
如果可以找到更好的本地解决方案,则必须对其进行更新。
如果没有找到,以概率用更差的解更新当前的解。
其中,这里假设找到最小值。
其中,代表你的体力。体力会逐渐下降(这会收敛),你也不愿意四处走动。
一般来说,我们让以指数速率减少,例如。
地毯式搜索 Combing
这个名字是我编的。
背景:
可以发现SA的参数很多,非常难调。而引入SA就是为了解决局部最优解的问题。我们为什么不尝试取遍所有的局部最优解,来得到全局最优解?也就是说在山区里随机空降一些人,让他们都走到视线内的最高峰然后汇报给总部。
当然你硬要说这种方式在分形(如Weierstrass函数)上会遭遇挫折的话我也没办法。
事实上,可以摆脱这种方法。
但是还是有一定的实用价值的。
算法:
取几组初始解,尽量均匀分布(否则一个局部区域的多个点没有意义),分别进行梯度下降,最后取极值集中的最大值。
版权声明:本文为博主LugarTang原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/LugarTang/article/details/123442199