爬山和退火

爬山算法

排山算法是一个贪心算法,每次从邻近空间中找到一个最优解,然后更新,因此最后可能达到一个局部最优解

爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解.如图1所示:假设C点外当前解,爬山算法搜索到A点这个局部最优解就会停止搜索,因为A点无论向哪个方向小幅度移动都不能得到更优的解

首选爬山算法:一次寻找该店的X的临近点钟首次出现比点X价值高的点,并将该店最为爬山的点.依次循环,直至该店的邻近点钟不再有比其大的点.我们就称该店是山的顶点
最陡爬山算法是在首选爬山算法上的一种改良,它规定每次选取邻近点价值最大的那个店最为爬上的点
随机重新开始爬山法:随机重新开始爬山算法是基于最陡爬山法,其实就是加一个全局最优解的条件,如果满足该条件,就结束运算,反之则无线重复运算最陡爬山法

退火算法

模拟退火算法,它是一种基于蒙特卡洛思想设计的近似求解最优问题

爬山法是完完全全的贪心法,每次都鼠目寸光的选择一个当前最优解,因此只能搜索到一个当前最优解.模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素.模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局最优解

这里的一定的概率的计算草稿了金属冶炼的退火过程,这也是退火算法的名称由来

伪代码

/*
* J(y)：在状态y时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min )
{
　　dE = J( Y(i+1) ) - J( Y(i) ) ; 
 
　　if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
       Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　else
　　{
       // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
      if ( exp( -dE/T ) > random( 0 , 1 ) )
      Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　}
　　T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
　　/*
　　* 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
　　*/
　　i ++ ;
}

爬山和退火