启发式寻解
原理讲解
启发寻解算法核心(必读)
作者 : 老饼 日期 : 2022-09-14 18:45:26 更新 : 2022-11-21 10:42:22


   一.问题    

已知  ,求一x ,使得最小。
备注:这里的不一定是一个数学表达式。



   二.寻解算法    

要解决以上问题,往往不能靠数学手段求得精确解,
此时,我们退之求其次,
不一定要求是最精确的解,只要求x 足够优秀即可。
通常我们会使用寻解算法, 
先给x 设一个初始值
然后通过迭代,不断调整x ,使f(x)的值越来越小,
直到达到迭代条件,停止迭代,
最后输出整个迭代中最优秀的x 。



   三.寻解算法的三个核心   

所谓寻解算法,就是设定一个机制,使得随着x 的调整,f(x) 能不断的下降。
这个机制,一般可以分解为三个小机制:
1.下降机制:要有个机制,使随着x 的迭代,越来越小。
2.未阶段局部最优机制:要有个机制,在未阶段,使 x 如果找到x',就能找到x' 最近的局部最优。
3.跳出局部最优机制:要有个机制,在到达局部最优时,仍有机会跳出这个局部最优(特别是要能跳出一些小的局部最优)。
以上,是以解的最终质量设定的机制。
另在寻解速度上,我们还希望,能以更少的迭代次数,找到更优质的解。
目前,已有很多成熟的寻解算法:梯度下降,模拟退火,蚁群算法等等



四.举例


   (一) 模拟退火   


算法机制简述:
每次用一个邻解作为新解,如果新解更优秀,接受新解,如果新解不如旧解,则根据一定概率(这个概率与两解质量差、当前迭代次数负相关)接受新解。
算法剖析:
1.下降机制:因为新解更好时一定接受,而新解质量越差,接受概率越小,所以随着迭代次数,在概率上,会渐渐越来越优秀。
2.局部最优机制:当迭代次数足够大时,将不再接受更差的解。而每次都用邻解来作新解,因此会一直沿着邻域更优秀的解迭代,直到局部最优。
3.跳出局部最优:算法中的“按概率接受差解”,正是为了跳出局部最优设置,让解在遇到局部最优时,还有一定的概率跳出局部最优。



   (二) 梯度下降算法   


算法机制简述:
每次往负梯度方向小步调整
算法剖析:
1.下降机制:负梯度方向,只要步长足够小,就会令f(x)下降
2.局部最优机制:每步调整都下降,只要一直调整下去,一定会达到局部最优。
3.跳出局部最优:无。(作为弥补,就诞生了动量梯度下降法,以增加梯度下降法没有跳出局部最优的机制。)



    五.总结    

以上仅为说明,寻解算法的核心就是以上三点,
学习任何一个寻解算法,必须围绕这三点,才能理解算法各个设计的目的。
备注:并且,围绕以上三点,也能自己设计一个寻解算法。
在具体学习了各个寻解算法后,我们再作深一步的剖析与探讨。





联系老饼