爬山算法

目录

一，问题实例

二，暴力求解

三，首选爬山算法

四，最陡爬山算法

五，不同的搜索起点

一，问题实例

求解函数的最大值。

我们可以用python画出图像

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, 5, 5) 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') plt.show() if __name__ == '__main__': X = np.arange(-5, 10, 0.1) Y = np.arange(-5, 10, 0.1) show(X,Y)

二，暴力求解

求整数级自变量的最大值

double f(double x, double y) { double a = -x * x - y * y; double b = -(x - 5)*(x - 5) - (y - 5)*(y - 5); return exp(a) + 2 * exp(b); } int main() { double ans = 0; for (int i = -5; i <= 10; i++)for (int j = -5; j <= 10; j++) { if (ans < f(i, j)) { ans = f(i, j); cout << i << " " << j << " " << ans< 
   

输出：

即（5,5）附近是第一高峰，（0,0）附近是第二高峰。

算法缺陷：

（1）计算量大，效率低

（2）要想求更精确的值，更加复杂

三，首选爬山算法

首选爬山算法就是每次选择4个邻居，从中选择最优的点，一直持续下去，直到爬到某个山顶。

int dx[] = { 0, 1, -1, 0, 0 }; int dy[] = { 0, 0, 0, 1, -1 }; int main() { double x = 1, y = 5, d = 0.1; while (true) { int ansDir = 0; for (int dire = 1; dire < sizeof(dx) / sizeof(dx[0]); dire++) { if (f(x + d * dx[dire], y + d * dy[dire]) > f(x + d * dx[ansDir], y + d * dy[ansDir]))ansDir = dire; } x += d * dx[ansDir], y += d * dy[ansDir]; cout << x << " " << y << " " << f(x, y) << endl; if (ansDir == 0)break; } return 0; }

输出：

四，最陡爬山算法

每次不只是选择四邻居，每次选择一个邻域内的所有点，从中选择最优的点。

int main() { double x = 1, y = 5, d = 0.1; while (true) { int ai = 0, aj = 0; for (int i = -3; i < 3; i++)for (int j = -3; j < 3; j++) { if (f(x + d * i, y + d * j) > f(x + d * ai, y + d * aj))ai = i, aj = j; } x += d * ai, y += d * aj; cout << x << " " << y << " " << f(x, y) << endl; if (ai == 0 && aj == 0)break; } return 0; }

输出：

迭代次数少一些，但是每次迭代的计算量大一些。

五，不同的搜索起点

如果搜索起点换成（1,1）：

int main() { double x = 1, y = 1, d = 0.1; while (true) { int ansDir = 0; for (int dire = 1; dire < sizeof(dx) / sizeof(dx[0]); dire++) { if (f(x + d * dx[dire], y + d * dy[dire]) > f(x + d * dx[ansDir], y + d * dy[ansDir]))ansDir = dire; } x += d * dx[ansDir], y += d * dy[ansDir]; cout << x << " " << y << " " << f(x, y) << endl; if (ansDir == 0)break; } return 0; }

输出结果：

求出来的局部最优解（0,0）不是全局最优解，即使是最陡爬山算法也会走到这个点。

要想尽量避免这种情况，需要其他算法。