# 机器学习优化算法之爬山算法小结

## 目录

1. 爬山算法简单描述

2. 爬山算法的主要算法

2.1 首选爬山算法

2.2 最陡爬山算法

2.3 随机重新开始爬山算法

2.4 模拟退火算法(也是爬山算法)

3. 实例求解

## 正文

# encoding:utf8
from matplotlib import pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D

def func(X, Y, x_move=0, y_move=0):
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):
fig = plt.figure()
ax = Axes3D(fig)
X, Y = np.meshgrid(X, Y)
Z = func(X, Y, 1.7, 1.7)
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')
# 具体函数方法可用 help(function) 查看，如：help(ax.plot_surface)
# ax.scatter(X,Y,Z,c='r') #绘点
plt.show()

if __name__ == '__main__':
X = np.arange(-2, 4, 0.1)
Y = np.arange(-2, 4, 0.1)

show(X,Y)


1. 首选爬山算法

1.  随机选择一个登山的起点S(x0,y0,z0),并以此为起点开始登山.直至"登顶".

# encoding:utf8
from random import random, randint

from matplotlib import pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D

def 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=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:utf8
from random import random, randint

from matplotlib import pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D

def 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.模拟退火算法

(1)随机挑选一个单元

# encoding:utf8
from random import random, randint

from matplotlib import pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D

def 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, color='b' )
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 = []
# 初始温度
temperature = 105.5
# 温度下降的比率
delta = 0.98
# 温度精确度
tmin = 1e-10

len_x = len(X)
len_y = len(Y)

# 随机登山点
st_x = X[0][randint(0, len_x - 1)]
st_y = Y[randint(0, len_y - 1)][0]
st_z = func(st_x, st_y)

def argmax(stx, sty, alisx, alisy):
cur = func(st_x, st_y)
next = func(alisx, alisy)

return cur < next and True or False

while (temperature > tmin):
# 随机产生一个新的邻近点
# 说明: 温度越高幅度邻近点跳跃的幅度越大
tmp_x = st_x + (random() * 2 - 1) * temperature
tmp_y = st_y + + (random() * 2 - 1) * temperature
if 4 > tmp_x >= -2 and 4 > tmp_y >= -2:
if argmax(st_x, st_y, tmp_x, tmp_y):
st_x = tmp_x
st_y = tmp_y
else:  # 有机会跳出局域最优解
pp = 1.0 / (1.0 + np.exp(-(func(tmp_x, tmp_y) - func(st_x, st_y)) / temperature))
if random() < pp:
st_x = tmp_x
st_y = tmp_y
temperature *= delta  # 以一定的速率下降
global_X.append(st_x)
global_Y.append(st_y)
return global_X, global_Y, func(st_x, st_y)

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))