前言

爬山法（climbing method）是一种优化算法，它一般从一个随机某一点开始，然后逐步计算每一点的函数值直到找到一个最优解（局部最优），所以它是一种局部搜索算法，这意味着它适用于单峰优化问题或在应用全局优化算法后使用。

爬山法有以下3个缺点：

（1）局部最优：该算法的性质决定了其极容易陷入局部最优，且很难跳出；

（2）平顶：

平顶是状态空间中评估函数值基本不变的一个区域，在某一局部点周围F（x）为常量。一旦搜索到达了一个平顶，搜索就无法确定要搜索的最佳方向，会产生随机走动，这使得搜索效率降低。

（3）山脊：

山脊可能具有陡峭的斜面，所以搜索可以比较容易地到达山脊的顶部，但是山脊的顶部到山峰之间可能倾斜得很平缓，搜索的前进步伐会很小。

针对上述问题，如果要获得更好的解，传统做法是多次使用爬山算法（需要从不同的初始解开始爬山），从多个局部最优解中找出最优解，而这个最优解有可能是全局最优解。

文章对经典爬山算法做出了改进，使该算法不需产生多个随机初始解进行”爬山“，只需一次“爬山”就能找到最高的山峰。

提示：以下是本篇文章正文内容，下面案例可供参考

一、爬山算法

爬山算法是模拟爬山的过程，随机选择一个位置爬山，每次朝着更高的方向移动，直到到达山顶，即每次都在临近的空间中选择最优解作为当前解，直到局部最优解。这样算法会陷入局部最优解，能否得到全局最优解取决于初始点的位置。初始点若选择在全局最优解附近，则就可能得到全局最优解。

算法描述：

从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。

算法实现：

后期更新>>>

二、算法改进-探测器

这里做个比喻，将经典爬山算法比作随机在山上的随机点放m只蚂蚁，蚂蚁根据当前位置（x*）与其相距L个单位长度范围内点对应的高度（x*）来选择前进与否，若以当前位置（x*）为圆心，L为半径上的各点对应的高度F(x*+L)均小于当前点（x*）的高度F（x*），则将该位置视为最优值（局部），蚂蚁不再移动。否则，蚂蚁继续向临近的更高点继续前进，直到它所处的位置再也没有比它更高的点。m只蚂蚁经过这样的爬山过程后，都会找到一个最高点（局部），即共找到m个最高点（局部），这m个位置中的最大值有可能是全局最优值（蚂蚁数越多，找到全局最优值的概率越大）。

文章对传统爬山算法做了改进，以使其能一次性找到全局最优值，同时该算法不会陷于平原（某点（x^)领域内高度f(x)为常数）。

算法描述:

首先对蚂蚁赋能：①蚂蚁有探测器功能（类似雷达）；②蚂蚁会飞。

步骤一：在经典爬山算法的基础上，蚂蚁爬向山顶（局部最优值）：

步骤二：探测远方有没有比当前位置更高的点，若有，飞到更高的位置，并进行步骤一。若无，此点为全局最优值。

同样对于平原问题，当蚂蚁位于平面时，探测周围有无更高的点，若有，前更高点爬去并进行步骤一和步骤二，直到爬到最高点。

算法示意图：

1.递归寻找局部最优值

爬山法代码如下（示例）：

def cycle(i,r,R2,T2):if(i>=5 or i<=-5):if(i>5):obj.append(i-r)ax2.scatter(i-r,fun(i-r))returnif(i<-5):obj.append(i+r)ax2.scatter(i+r,fun(i+r))return #超出定义域退出循环y_i=fun(i)ax1.scatter(i,y_i)plt.pause(0.02)if(fun(i+r)<=y_i and fun(i-r)<=y_i):radiation(i,r,R2,T2)##ax1.scatter(i,fun(i))elif(fun(i+r)<y_i and fun(i-r)>=y_i):##r=abs(r+0.02)cycle(i-r,r,R2,T2)#从x轴负方向寻找最优值elif(fun(i+r)>=y_i and fun(i-r)<y_i):##r+=0.02#从x轴正向寻找最优值cycle(i+r,r,R2,T2)else: #如果当前点位于谷底，双向探测 cycle(i+r,r,R2,T2)cycle(i-r,r,R2,T2)#从x轴负方向寻找最优值return

2.探测器搜索全局最优值

代码如下（示例）：

def radiation(i,R1,R2,T2):# 望远函数，i目前的局部最优位置 R：辐射半径，T:发射次数y_i=fun(i)t_2=0r2=R2i_r=i+r2i_l=i-r2while True:if(i_r>5 or i_l<-5):obj.append(i)ax2.scatter(i,fun(i))breakif t_2==T2 :obj.append(i)ax2.scatter(i,fun(i))breaky_f=fun(i_r)y_b=fun(i_l)if(y_f>y_i and y_b>y_i):cycle(i_r,R1,R2,T2)cycle(i_l,R1,R2,T2)breakelif(y_f>y_i and y_b<y_i):cycle(i_r,R1,R2,T2)breakelif(y_f<y_i and y_b>y_i):cycle(i_l,R1,R2,T2)breakelse:t_2=t_2+1i_r=i_r+r2i_l=i_l-r2return

调用改进算法寻找最优值。

def rad_cyc(R_1,R_2,T_1,T_2,*objection):t_1=0while (t_1<T_1):point=round(np.random.uniform(-5,5),5)r=R_1cycle(point,r,R_2,T_2)t_1+=1print(obj)ax2.text(2,2,'number:%d'%len(obj))plt.show()rad_cyc(0.05,0.1,5,30,obj)

运行结果：

左图为蚂蚁前进路径点，右图为最终位置。由于代码有未知BUG，有时结果会陷于局部最优处，本人水平有限，正在处理中>>>

全部代码：

import numpy as npimport matplotlib.pyplot as pltx=np.arange(-5,5,0.01)y=[]obj=[]#用于存放局部最优值y=np.cos(x)+0.5*x+np.sin(x**2)def fun(x):##目标函数return np.cos(x)+0.5*x+np.sin(x**2)f=plt.figure()ax1=plt.subplot(1,2,1)ax2=plt.subplot(1,2,2)ax1.plot(x,y)ax2.plot(x,y)def radiation(i,R1,R2,T2):# 望远函数，i目前的局部最优位置 R：辐射半径，T:发射次数y_i=fun(i)t_2=0r2=R2i_r=i+r2i_l=i-r2while True:if(i_r>5 or i_l<-5):obj.append(i)ax2.scatter(i,fun(i))breakif t_2==T2 :obj.append(i)ax2.scatter(i,fun(i))breaky_f=fun(i_r)y_b=fun(i_l)if(y_f>y_i and y_b>y_i):cycle(i_r,R1,R2,T2)cycle(i_l,R1,R2,T2)breakelif(y_f>y_i and y_b<y_i):cycle(i_r,R1,R2,T2)breakelif(y_f<y_i and y_b>y_i):cycle(i_l,R1,R2,T2)breakelse:t_2=t_2+1i_r=i_r+r2i_l=i_l-r2returndef cycle(i,r,R2,T2):if(i>=5 or i<=-5):if(i>5):obj.append(i-r)ax2.scatter(i-r,fun(i-r))returnif(i<-5):obj.append(i+r)ax2.scatter(i+r,fun(i+r))return #超出定义域退出循环y_i=fun(i)ax1.scatter(i,y_i)plt.pause(0.02)if(fun(i+r)<=y_i and fun(i-r)<=y_i):radiation(i,r,R2,T2)##ax1.scatter(i,fun(i))elif(fun(i+r)<y_i and fun(i-r)>=y_i):##r=abs(r+0.02)#探测步长，逐次增大cycle(i-r,r,R2,T2)#从x轴负方向寻找最优值elif(fun(i+r)>=y_i and fun(i-r)<y_i):##r+=0.02#从x轴正向寻找最优值cycle(i+r,r,R2,T2)else: #如果探测器位于谷底，双向探测 cycle(i+r,r,R2,T2)cycle(i-r,r,R2,T2)#从x轴负方向寻找最优值return def rad_cyc(R_1,R_2,T_1,T_2,*objection):t_1=0while (t_1<T_1):#设置迭代次数，即探测器数point=round(np.random.uniform(-5,5),5)r=R_1#探测半斤归原值cycle(point,r,R_2,T_2)t_1+=1print(obj)ax2.text(2,2,'number:%d'%len(obj))plt.show()rad_cyc(0.05,0.1,5,30,obj)

针对有平原的情况，另外设置目标函数：

def fun(x):if(x>=-5 and x<-1):return -(x+2)**2+2elif(x>=-1 and x<=1):return 1else: return -2*(x-2)**2+3

运行结果：

代码有漏洞，正在处理中，解决完后会及时更新>>>