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

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽
本文为转载文章,若有侵权或违规行为,请联系我,会及时处理相关内容。

支付宝微  信

 简言

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

 目录

1. 爬山算法简单描述

2. 爬山算法的主要算法

2.1 首选爬山算法

2.2 最陡爬山算法

2.3 随机重新开始爬山算法

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

3. 实例求解

 正文

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

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

1

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

2

图像的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)

对于上面这个问题,我们使用爬山算法该如何求解呢? 下面我们从爬山算法中的几种方式分别求解一下这个小题.

1. 首选爬山算法

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

那么解题思路就有:

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

对比几次运行的结果:

3

4

5

6

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

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

78

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

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

简单的描述:

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

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

4.模拟退火算法

简单描述:

 

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

        9

式中T为温度,然后从(0,1)区间均匀分布的随机数中挑选一个数R,若R<Pk,则将变化后的状态作为下次的起点;否则,将变化前的状态作为下次的起点。
(3)转第(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))

效果:

10

11


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


分类: 技术, 算法 | 标签: , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。