当前位置: 代码迷 >> 综合 >> 几句话描述爬山法,模拟退火,遗传算法
  详细解决方案

几句话描述爬山法,模拟退火,遗传算法

热度:36   发布时间:2024-01-11 14:54:41.0

首先,这仨算法都是求成本函数最优的方法。

爬山法:成本函数抽象成了一座山(想象一下一个2维坐标系,横轴为变量,纵轴为成本函数,成本函数随着横轴的递增而上下起伏绵延不绝,好似一座山),某人可在山中一任意位置左右移动(取该函数中的一点),因此,随着某人水平方向的变化(变量的变化),这哥们的海拔高度也在变化(成本函数随着变量的变化而变化)。可惜,这哥们一心想去山的最底处。所以他总喜欢走下坡路,一旦发现各个方向再走都是上坡的时候,那这哥们认为他终于走到了山的最底处,他不再走了并返回此时他的位置。(该例子的成本函数仅和一个变量有关,但现实生活中,成本函数是和多个变量有关。道理也是一样,就好像这个哥们每次走路的时候有N个方向供他选择(N个变量))

明眼的人都能看出来,这哥们非常容易的会把局部最小值当成全局最小值。以为山的小凹谷就是整座山的最低处了(这座山绵延不绝,并不是两头连接大地的那种,是长度无限长的那种),too navie。

有什么办法呢?就是随机重复爬山法,让你每次初始位置都随机的多试几次。说不定还真能蒙到正确结果。

模拟退火算法:这哥们突然变聪明了,认为有时候退一步海阔天空,我有的时候稍微走点上坡路,指不定后面会有一个大下坡等着我呢,于是这哥们开始只要上坡路不是上升的特别离谱,他都会试着去尝试一下,走走看。不过,随着时间的流逝,这哥们开始越来越不愿意走上坡路,一开始可能这是上坡路还会去尝试着走一下呢。到后来,越来越不愿意去尝试。这个愿不愿意去尝试走上坡路的心态就跟刚出炉放在空气中的铁一样,随着时间的流逝而渐渐降温,渐渐冷却,渐渐退火。公式表示就是这样:.,如果新的成本函数降低了,当然欣然接受一开始,不多说。但是如果新的成本函数增高了,那么就开始考虑要不要试一下要不要走,一开始的时候,温度很高,高低成本之差显得很小,除了个温度接近为0,这个P值接近为1,一般程序当中都是用一个0和1之间的随机数与P值比较,如果比P小那么就尝试,如果比P大那么不尝试。所以很明显,一开始肯定是乐意尝试的,后来随着时间的增加,温度的下降,P值越来越小接近于0。因此,更加不愿意去尝试上坡路了。

这个方法的问题和爬山法其实差不多,每次结果可能都会不同,尝试着每次改下参数(初始温度和温度下降的速度)来试试。

遗传算法:这时候,想象成人类吧。人类的生存环境十分的残酷,只有优秀的一拨人才能活下来(优秀的人意为成本函数小的最优解),一代一代,每代之中会有变异(对既有解进行微小的,简单的,随机的改变)也会有交叉(选取最优解中的两个解,然后将他们按照某种方式进行结合)。很显然,变异和交叉会产生新的种群(会对成本函数产生或增或减的影响)。同样,这些新的种群有的能适应这个世界而存活下去,有的就消失在人类的进化长河里。正所谓物竞天择适者生存。真是残酷。

  相关解决方案