文章原创,转载请注明出处

demo在这里,欢迎在线试玩:http://siida.cn/me/tuihuo/

说起来这是寒假的第一篇博客,因为定下了开学之后的网易offer所以就像实现了一个dream一样有种突然失去动力的感觉,过年的这几天都没有保持高效学习。今天在和好友讨论算法的时候突然谈到了退火,这名字一听就很牛逼,我又翻了翻书才重新回忆起退火。

-----什么是退火算法?-----

(手头没有书所以以下科普全部来自我的理解)

在讲退火之前,我们要提一个梯度下降算法:假如一只兔子站在一片群山中,它要找一个比较高的地方,兔子环视四周,发现向前跳一步,它能升高的高度最大,于是它向前迈一步。然后再次环视四周……重复以上过程。

经过许久的重复,兔子会跳到它所在的那座山的山顶,然后它无处可跳了。但是这座山并不是最高的山,我们就说这个兔子找到了一个局部最优解,而不是这片群山的全局最优解。

接下来讲退火算法,退火是什么意思呢?

退火在现实中的意思是,把一个东西猛然加热到高温,然后让他慢慢冷却的过程,我们知道一个铁块温度越高,那么组成他的原子运动就越不稳定,在冷却的过程中,他逐步稳定下来。计算机中的退火概念与之异曲同工。

退火算法中的兔子并不是一步一步跳的,开始的时候它就像喝醉酒了一样剧烈的跳,每一步都跳很远很远,这样她可能跳到高峰,也可能跳进低谷,但是他慢慢清醒了,慢慢向着最高的山峰跳去。

这样以来,兔子很可能找到全局的最优解。

-----我的代码怎样实现-----

先上图

因为数据一定要是连续的,我就自己写了几个分段函数并用canvas画了出来。为了复用,我把这个过程抽象了很多,感兴趣的同学可以直接从我的github下载然后改几个全局变量和表达式就能重画分段函数了。(我都是中文注释很好改的,虽然有点丑)

开始的时候是这样的

中间有个输入搜索次数,你输入的次数越多,我就找的越精确。如果你输入10次,我会把全局的横坐标取值范围分十份,然后第一次跳十份,第二次跳九份,第三次跳八份……,跳出右边界就从左边循环,这样模拟醉酒但是越来越清醒的兔子来寻找最大的值。

输入10的结果是这样的

输入1000结果就是最上面的图。

原理讲好了可能我这个不是完美的退火算法不过毕竟借鉴了退火的思路,卧槽当我看明白这个思路的时候我整个人都非常嗨。

写了一下午也是很开心。

当面临海量数据的时候,真的能很快的提升性能。

睡觉,晚安世界。