简言

机器学习的项目,不可避免的需要补充一些优化算法,对于优化算法,爬山算法还是比较重要的.鉴于此,花了些时间仔细阅读了些爬山算法的paper.基于这些,做一些总结.

 目录

1. 爬山算法简单描述

2. 爬山算法的主要算法

2.1 首选爬山算法

2.2 最陡爬山算法

2.3 随机重新开始爬山算法

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

3. 实例求解

 正文

爬山算法,是一种局部贪心的最优算法. 该算法的主要思想是:每次拿相邻点与当前点进行比对,取两者中较优者,作为爬坡的下一步.

举一个例子,求解下面表达式的最大值. 且假设 x,y均按为0.1间隔递增.

1

为了更好的描述,我们先使用pyhton画出该函数的图像:

2

图像的python代码:
[code lang=”python”]
# 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)
[/code]
对于上面这个问题,我们使用爬山算法该如何求解呢? 下面我们从爬山算法中的几种方式分别求解一下这个小题.

1. 首选爬山算法

依次寻找该点X的邻近点中首次出现的比点X价值高的点,并将该点作为爬山的点(此处说的价值高,在该题中是指Z或f(x,y)值较大). 依次循环,直至该点的邻近点中不再有比其大的点. 我们成为该点就是山的顶点,又称为最优点.

那么解题思路就有:

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

下面是我们实现的代码:

[code lang=”python” collapse=”true”]
# 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))
[/code]

对比几次运行的结果:

3

4

5

6

从上图中,我们可以比较清楚的观察到,首选爬山算法的缺陷.

2.那么最陡爬山算法呢?

简单描述:

最陡爬山算法是在首选爬山算法上的一种改良,它规定每次选取邻近点价值最大的那个点作为爬上的点.

下面我们来实现一下它:

[code lang=”python” collapse=”true”]
# 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))
[/code]

78

从这个结果来看,因为范围扩大了一点,所以效果会好一点点,当依旧是一个局部最优算法.

3.随机重新开始爬山算法呢?

简单的描述:

随机重新开始爬山算法是基于最陡爬山算法,其实就是加一个达到全局最优解的条件,如果满足该条件,就结束运算,反之则无限次重复运算最陡爬山算法.

由于此题,并没有结束的特征条件,我们这里就不给予实现.

4.模拟退火算法

简单描述:

 

(1)随机挑选一个单元k,并给它一个随机的位移,求出系统因此而产生的能量变化ΔEk
(2)若ΔEk0,该位移可采纳,而变化后的系统状态可作为下次变化的起点;
ΔEk>0,位移后的状态可采纳的概率为

        9

式中T为温度,然后从(0,1)区间均匀分布的随机数中挑选一个数R,若R<Pk,则将变化后的状态作为下次的起点;否则,将变化前的状态作为下次的起点。
(3)转第(1)步继续执行,知道达到平衡状态为止。

代码实现为:
[code lang=”python” collapse=”true”]
# 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))
[/code]
效果:

10

11


原文链接:http://www.cnblogs.com/gongxijun/p/5873643.html

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.