MATLAB算法の爬山算法

巴山学长

发布于 2019-07-15 15:06:31

2.5K0

发布于 2019-07-15 15:06:31

文章被收录于专栏：巴山学长

图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

效果图