图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;
% 定义计算精度
ep = 1e-4;
% 定义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);
gg=1 *1;
title(['爬山算法演示 ——','第',num2str(gg),'次搜素']);
xlabel('x轴');
ylabel('y轴');
zlabel('z轴');
hold on;
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;
end
% 绘制最终极大值点
plot3(x0,y0,val2,'ro');
hold off
效果图
图3 爬山路径三维立体图
图4 爬山路径俯视图