这个示例直观地展示了模式搜索如何优化函数。函数是华盛顿山附近地形的高度,作为x-y位置的函数。为了找到华盛顿山的山顶,我们将目标函数最小化它是高度的负函数。(本例中的华盛顿山是美国东北部的最高峰。)
美国地质调查局在网格上提供地形高度作为x-y位置的函数。为了能够评估任意点的高度,目标函数从附近的网格点插值高度。
当然,简单地找到网格上指定的高度最大值会更快,使用马克斯
函数。这个示例的重点是展示模式搜索算法是如何操作的;它适用于定义在连续区域上的函数,而不仅仅是网格点。此外,如果评估目标函数的计算代价很高,那么根据马克斯
函数,将比使用模式搜索算法效率低得多,后者对一小部分网格点进行抽样。
模式搜索通过以下方法查找目标函数的局部最小值,称为轮询。在这个描述中,描述模式搜索量的单词用粗体表示。搜索从一个初始点开始,取为当前点第一步:
1.生成一个模式点的集合,通常是加上或减去坐标方向,乘以a筛孔尺寸,并把这个图案集中在当前点.
2.对目标函数的每一点求值模式.
3.如果最小目标在模式小于当前点,那么民意调查是成功的,会发生以下情况:
3 a。找到的最小值点变成当前点.
3 b。的筛孔尺寸是翻了一倍。
3 c。算法继续执行步骤1。
4.如果投票不是成功的,然后发生以下情况:
4 a。的筛孔尺寸是减半。
4 b。如果筛孔尺寸低于阈值时,迭代将停止。
4 c。否则,当前点,算法从第1步开始。
这个简单的算法,经过一些小的修改,提供了一种健壮而直接的优化方法。它不需要目标函数的梯度。它本身也有约束条件,但是这个例子和描述只处理无约束的问题。
要准备模式搜索,请加载数据mtWashington.mat
,它包含了一个472 × 345的网格上的美国地质勘探局数据。标高Z以英尺为单位。向量x和y分别包含了向东和向北的网格间距的基值。数据文件还包含搜索的起始点X0。
负载mtWashington
有三个MATLAB文件,执行目标函数的计算和绘图例程。它们是:
1.terrainfun
,它计算任意x-y位置的负高度。terrainfun
使用MATLAB®函数interp2
进行二维线性插值。它获取Z数据,并使所有x-y点的高度为负。
2.psoutputwashington
该网站绘制了华盛顿山的3d效果图。此外,随着运行的进行,它会在每个点周围绘制比以前访问过的点更好(更高)的球体。
3.psplotwashington
,绘制华盛顿山的等高线地图,并监控控制跑步速度的滑块。它通过在这些点上画+符号来显示模式搜索算法寻找最优值的位置。它还在每个点周围画出了比以前访问过的点更好的球体。
在这个例子中,patternsearch
使用terrainfun
作为其目标函数,psoutputwashington
作为输出函数,和psplotwashington
作为一个绘图函数。我们准备好要传递的函数patternsearch
在匿名函数语法中:
mtWashObjectiveFcn = @(xx) terrainfun(xx, x, y, Z);mtWashOutputFcn = @(xx,arg1,arg2) psoutpuwashington (xx,arg1,arg2, x, y, Z); / /输入参数mtWashPlotFcn = @(xx,arg1) psplowashington (xx,arg1, x, y, Z); / /获取路径
接下来,我们创建模式搜索的选项。这组选项使算法在网格尺寸缩小到1以下时停止,保持网格不缩放(每个方向的尺寸相同),设置初始网格尺寸为10,并设置输出函数和plot函数:
选择= optimoptions (@patternsearch,“MeshTolerance”, 1“ScaleMesh”假的,...“InitialMeshSize”10“UseCompletePoll”,真的,“PlotFcn”mtWashPlotFcn,...“OutputFcn”mtWashOutputFcn,“UseVectorized”,真正的);
运行此示例时,您将看到两个窗口。其中一个展示了模式搜索算法在华盛顿山的二维等高线地图上选择的点。此窗口有一个滑块,用于控制算法迭代之间的延迟(当它返回到描述模式搜索工作方式的步骤1时)。将滑块设置为较低的位置以加速奔跑,或设置为较高的位置以减慢奔跑。
另一个窗口显示了华盛顿山的三维图,以及模式搜索算法的步骤。您可以在运行过程中旋转这个图以获得不同的视图。
[xfinal ffinal] = patternsearch (mtWashObjectiveFcn X0 ,[],[],[],[],[],...[]、[]选项)
优化终止:网格尺寸小于选项。网格公差。
xfinal =1×2316130 4904295
ffinal = -6280
最后一点,xfinal
,表示模式搜索算法完成的位置;这是华盛顿山顶的x-y坐标。最终的目标函数,ffinal
,是华盛顿山高度的负数,6280英尺。(根据华盛顿山天文台的数据,这个高度应该是6288英尺)。
检查文件terrainfun.m
,psoutputwashington.m
,psplotwashington.m
看看插值和图形是如何工作的。
模式搜索算法有许多可用选项。例如,算法可以选择它发现的第一个改进点,而不是轮询模式中的所有点。它可以按不同的顺序轮询点。它可以使用不同的投票模式,有确定性的,也有随机的。详细信息请参阅全局优化工具箱用户指南。