图1 爬山算法搜索极大值动态演示

没错,正如在图1中所见到的那样,今天给大家介绍爬山算法。顾名思义,爬山就是我们日常所理解的爬山运动,而目的就是要登上山顶,想要到达山顶,每一步应该是向着山顶迈进的,经过一步一个脚印终于到达了山顶,就能真正体会到什么是“山登绝顶我为峰”豪迈姿态。当然了也别忘了“山外青山楼外楼”,也许所登山峰在当地是最高峰,但再高也没有珠穆朗玛峰。

是的,以上的开场白也说明了爬山算法的优缺点,爬山算法可以很好地求解局域(当地)极大或极小值,但并不能求解全局(全世界)最大或最小值。

爬山算法是一种采用启发式搜索方式来完成局域优化的智能算法。爬山算法描述如下:对于目标函数f(x),随意选择定义域范围内的一个节点作为起始节点,计算当前的节点与周围的近邻节点的函数值f(x'),并进行比较。 假设寻找最大值,如果当前节点的函数值为最大,返回当前节点,并取其值为最大值 ,否则用最高的近邻节点来,替换当前节点,从而实现向山峰的高处攀爬的目的,如此循环直到达到最高点。(如果存在多个局域最大值,则所得结果对初始节点选择敏感,计算过程遇平台也会影响搜索结果,见图2)。

图2 爬山法搜索状态图

基于以上思想,完成求解f(x,y) = 1/(x^2+y^2+pi)的爬山法求极大值源代码。

源代码:

clc;close all;

format long;

% 定义目标函数

fun = @(x,y) 1./(x.^2 + y.^2+pi);

% 定义初始节点(x0,y0)

x0 = 2.3;y0 = -2.8;

% 定义近邻节点范围

dx = 0.1;dy = 0.1;

% 定义近邻节点划分份数

nX = 10;nY = 10;

% 定义计算精度

% 定义x,y区间

x=-4:0.2:4;

y=-4:0.2:4;

% 二维网格化区间

[xx,yy] = meshgrid(x,y);

zz = fun(xx,yy);

% 绘制目标函数三维图像

surf(xx,yy,zz);

title(['爬山算法演示 ——','第',num2str(gg),'次搜素']);

xlabel('x轴');

ylabel('y轴');

zlabel('z轴');

val1 = fun(x0,y0);

plot3(x0,y0,val1,'r.');

% 初始化搜索次数和函数差值

gg = 1;dlt = 1;

while(dlt > ep)

nx=linspace(x0-dx,x0+dx,nX*gg);

ny=linspace(y0-dy,y0+dy,nY*gg);

[nxx,nyy] = meshgrid(nx,ny);

valtmp = fun(nxx,nyy);

% 求解近邻节点最大值及其位置

[val2,loc] = max(valtmp(:));

% 当前函数值与最大值作差

dlt = abs(val1-val2);

x0 = nxx(loc);

y0 = nyy(loc);

val1 = val2;

plot3(x0,y0,val2,'r.');

title(['爬山算法演示 ——','第',num2str(gg),'次搜素']);

pause(0.1);       % 暂停0.1

gg = gg + 1;

% 绘制最终极大值点

plot3(x0,y0,val2,'ro');

图3 爬山路径三维立体图

图4 爬山路径俯视图

赞赏是一种动力 分享是一种美德