模式搜索攀登华盛顿山

模式搜索的工作原理

模式搜索通过以下方法找到目标函数的局部最小值，称为轮询。在此描述中，描述模式搜索数量的词语以粗体显示。搜索从一个初始点开始，该初始点在第一步中作为当前点：

1.生成一个点的模式，通常是加减坐标方向，乘以网格大小，并将该模式置于当前点的中心。

2.在模式中的每个点评估目标函数。

3.如果模式中的最小目标低于当前点的值，则轮询成功，并发生以下情况：

3a.找到的最小点将成为当前点。

3b.网格大小增加了一倍。

3c.算法执行步骤 1。

4.如果轮询不成功，则会发生以下情况：

4a.网格大小减半。

4b.如果网格大小低于阈值，迭代就会停止。

4c.否则，保留当前点，算法从步骤 1 继续进行。

这个简单的算法经过一些小的修改，提供了一种强大而直接的优化方法。它不需要目标函数的梯度。它也适合于约束，但是这个例子和描述只处理无约束的问题。

准备模式搜索

为了准备模式搜索，请加载 mtWashington.mat 中的数据，其中包含 472 x 345 网格上的 USGS 数据。海拔 Z 以英尺为单位。向量 x 和 y 分别包含东和北方向的网格间距的基值。数据文件还包含搜索的起点 X0。

load mtWashington

有三个 MATLAB® 文件用于执行目标函数的计算和绘图例程。它们是：

1. terrainfun，求任意 xy 位置处高度的负数。terrainfun 使用 MATLAB 函数 interp2 进行二维线性插值。它采用 Z 数据并能够评估所有 x-y 点的高度负数。

2. psoutputwashington，绘制了华盛顿山的 3-d 效果图。此外，随着运行的进行，它会在每个比以前访问过的点更好（更高）的点周围绘制球体。

3. psplotwashington，绘制华盛顿山的等高线图，并监控控制运行速度的滑块。它通过在这些点上绘制 + 号来显示模式搜索算法寻找最优解的位置。它还会在每个比以前访问过的点更好的点周围绘制球体。

在示例中，patternsearch 使用 terrainfun 作为其目标函数，psoutputwashington 使用作为输出函数，psplotwashington 使用作为绘图函数。我们用匿名函数语法准备要传递给 patternsearch 的函数：

mtWashObjectiveFcn = @(xx) terrainfun(xx, x, y, Z);
mtWashOutputFcn    = @(xx,arg1,arg2) psoutputwashington(xx,arg1,arg2, x, y, Z);
mtWashPlotFcn      = @(xx,arg1) psplotwashington(xx,arg1, x, y, Z);

模式搜索选项设置

接下来，我们创建模式搜索的选项。这组选项使算法在网格大小缩小到 1 以下时停止，保持网格不缩放（各个方向的尺寸相同），将初始网格大小设置为 10，并设置输出函数和绘图函数：

options = optimoptions(@patternsearch,'MeshTolerance',1,'ScaleMesh',false, ...
    'InitialMeshSize',10,'UseCompletePoll',true,'PlotFcn',mtWashPlotFcn, ...
    'OutputFcn',mtWashOutputFcn,'UseVectorized',true);

观察模式搜索的进展

运行此示例时，您会看到两个窗口。其中一个显示了模式搜索算法在华盛顿山的二维等高线图上选择的点。该窗口有一个滑块，用于控制算法迭代之间的延迟（当它返回到模式搜索工作原理描述中的步骤 1 时）。将滑块设置到低位置以加快运行速度，或设置到高位置以减慢运行速度。

另一个窗口展示了华盛顿山的三维图，以及模式搜索算法的步骤。您可以在运行过程中旋转此图以获得不同的视图。

[xfinal ffinal] = patternsearch(mtWashObjectiveFcn,X0,[],[],[],[],[], ...
    [],[],options)

patternsearch stopped because the mesh size was less than options.MeshTolerance.

xfinal = 1×2

      316130     4904295

ffinal = 
-6280

最后一点 xfinal 显示了模式搜索算法的结束位置；这是华盛顿山顶的 xy 位置。最终目标函数 ffinal 是华盛顿山高度的负数，6280 英尺。（根据华盛顿山天文台的数据，这应该是 6288 英尺）。

检查文件 terrainfun.m、psoutputwashington.m 和 psplotwashington.m 以查看插值和图形如何工作。

模式搜索算法有很多可用的选项。例如，算法可以采用它发现的第一个可以改进的点，而不是轮询模式中的所有点。它可以按照各种顺序轮询这些点。并且它可以对轮询使用不同的模式，既有确定性的，也有随机的。有关详细信息，请参阅 Global Optimization Toolbox 用户指南。