一、爬山算法简单描述
简介：爬山法是一种优化算法，一般从随机解入手，逐渐找到最优解(局部最优)。 假设求解的问题有多个参数，在通过爬山法获得最优解的过程中，可以一个接一个地增加或减少某个参数的值。
思想：每次比较邻点和当前点，都把两者中较好的作为爬坡的下一步。
主要使用：求解目标函数(机器学习的途径是给机器很多数据，告诉机器“目标函数”的学习方式是正确的) )。
二、爬山算法的主要算法
示例：求出以下表达式的最大值，假设x、y都以0.1间隔增加。
pyhton绘制函数的图像。
图像的python代码
# encoding 3360 utf8 frommatplotplibimportpyplotaspltimportnumpyasnpfrommpl _ toolkits.MP lot3dimportaxes3ddef func (x，x，y，x，x，y，x，x，y，x ) ) alis=1) : return alis * NP.exp (-(x * xy * y ) ) (return mul(X ) x，y ) (mul ) x ) ) x652 y 65: fig=y，1.7，1.7 ) PLT.title z，rstride=1，cstride=1，cmap='rainbow '，) ax.set_xlabel(xlabel )，color='r color='b ' ) #可以在help (help )函数(如help(ax.plot_surface ) ax.scatter，y，z ) )中查看具体的函数方法。 c='r ' ) #绘图点PLT.show (if _ name _=' _ main _ ' 3360 x=NP.arange (-2，4，0.1 ) y=NP.Arange ) )
流程概述：
随机选择一个符合条件的解，每间隔n给出一个解集合，找出解集合中的最优解，按照上面的方法构建另一个解集合，求出最优解，直到上次的最优解和下次的最优解相同为止，结束爬山码的实现：
# encoding : utf8 fromrandomimportrandom，randintfrommatplotlibimportpyplotaspltimportnumpyasnpfrommpl _ toolkits.MP lot3dot y_move=1.7 ) :defmul(x，y，alis=1) : return alis * NP.exp (-(x * xy * y ) ) return mul(X ) x， y ) mul ) x z ) :fig=PLT.figure(ax=axes3d ) fig ) PLT.title ) demo_hill_climbing ) ax.plot_surface(X color='g ' ) ax.set_zlabel ) ) z c='r ' ) #绘图点plt.show () def drawPaht(X，y，z，px，py，pz ) : cstride=1，cmap='rainbow '，) ax.set_xlabel(xlabel )，color='r ' ) ax.set_ylabel ) ) ylabel )。
ax.set_zlabel('z label', color='b') ax.plot(px,py,pz,'r.') #绘点 plt.show()def hill_climb(X, Y): global_X = [] global_Y = [] len_x = len(X) len_y = len(Y) # 随机登山点 st_x = randint(0, len_x-1) st_y = randint(0, len_y-1) def argmax(stx, sty, alisx=0, alisy=0): cur = func(X[0][st_x], Y[st_y][0]) next = func(X[0][st_x + alisx], Y[st_y + alisy][0]) return cur < next and True or False while (len_x > st_x >= 0) or (len_y > st_y >= 0): if st_x + 1 < len_x and argmax(st_x, st_y, 1): st_x += 1 elif st_y + 1 < len_x and argmax(st_x, st_y, 0, 1): st_y += 1 elif st_x >= 1 and argmax(st_x, st_y, -1): st_x -= 1 elif st_y >= 1 and argmax(st_x, st_y, 0, -1): st_y -= 1 else: break global_X.append(X[0][st_x]) global_Y.append(Y[st_y][0]) return global_X, global_Y, func(X[0][st_x], Y[st_y][0])if __name__ == '__main__': X = np.arange(-2, 4, 0.1) Y = np.arange(-2, 4, 0.1) X, Y = np.meshgrid(X, Y) Z = func(X, Y, 1.7, 1.7) px, py, maxhill = hill_climb(X, Y) print (px,py,maxhill) drawPaht(X, Y, Z,px,py,func(np.array(px), np.array(py), 1.7, 1.7)对比几次运行结果：
从上图中，我们可以比较清楚的观察到，首选爬山算法的缺陷：
因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。2.最陡爬山算法（局部最优）
描述：最陡爬山算法是在首选爬山算法上的一种改良，它规定每次选取邻近点价值最大的那个点作为爬上的点。
代码实现：
# encoding:utf8from random import random, randintfrom matplotlib import pyplot as pltimport numpy as npfrom mpl_toolkits.mplot3d import Axes3Ddef func(X, Y, x_move=1.7, y_move=1.7): def mul(X, Y, alis=1): return alis * np.exp(-(X * X + Y * Y)) return mul(X, Y) + mul(X - x_move, Y - y_move, 2)def show(X, Y, Z): fig = plt.figure() ax = Axes3D(fig) plt.title("demo_hill_climbing") ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap='rainbow', ) ax.set_xlabel('x label', color='r') ax.set_ylabel('y label', color='g') ax.set_zlabel('z label', color='b') # ax.scatter(X,Y,Z,c='r') #绘点 plt.show()def drawPaht(X, Y, Z, px, py, pz): fig = plt.figure() ax = Axes3D(fig) plt.title("demo_hill_climbing") ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap='rainbow', ) ax.set_xlabel('x label', color='r') ax.set_ylabel('y label', color='g') ax.set_zlabel('z label', color='b') ax.plot(px, py, pz, 'r.') # 绘点 plt.show()def hill_climb(X, Y): global_X = [] global_Y = [] len_x = len(X) len_y = len(Y) # 随机登山点 st_x = randint(0, len_x - 1) st_y = randint(0, len_y - 1) def argmax(stx, sty, alisx, alisy): cur = func(X[0][stx], Y[sty][0]) next = func(X[0][alisx], Y[alisy][0]) if cur < next: return alisx, alisy return stx, sty #return cur < next and alisx, alisy or stx, sty tmp_x = st_x tmp_y = st_y while (len_x > st_x >= 0) or (len_y > st_y >= 0): if st_x + 1 < len_x: tmp_x, tmp_y = argmax(tmp_x, tmp_y, (st_x + 1), st_y) if st_x >= 1: tmp_x, tmp_y = argmax(tmp_x, tmp_y, st_x - 1, st_y) if st_y + 1 < len_x: tmp_x, tmp_y = argmax(tmp_x, tmp_y, st_x, st_y + 1) if st_y >= 1: tmp_x, tmp_y = argmax(tmp_x, tmp_y, st_x, st_y - 1) if tmp_x != st_x or tmp_y != st_y: st_x = tmp_x st_y = tmp_y else: break global_X.append(X[0][st_x]) global_Y.append(Y[st_y][0]) return global_X, global_Y, func(X[0][st_x], Y[st_y][0])if __name__ == '__main__': X = np.arange(-2, 4, 0.1) Y = np.arange(-2, 4, 0.1) X, Y = np.meshgrid(X, Y) Z = func(X, Y, 1.7, 1.7) px, py, maxhill = hill_climb(X, Y) print(px, py, maxhill) drawPaht(X, Y, Z, px, py, func(np.array(px), np.array(py), 1.7, 1.7))从这个结果来看，因为范围扩大了一点，所以效果会好一点点。
3.随机重新开始爬山算法（全局最优）
描述：随机重新开始爬山算法是基于最陡爬山算法，其实就是加一个达到全局最优解的条件。如果满足该条件，就结束运算；反之则无限次重复运算最陡爬山算法。
由于此题，并没有结束的特征条件,我们这里就不给予实现。
4.模拟退火算法（全局最优）
转载于:https://www.cnblogs.com/xyp666/p/9042157.html