在模式搜索中使用完整轮询

打开实时脚本

patternsearch 求解器通过在模式中计算目标函数的值，试图找到极小值。求解器可以计算模式中的所有点，这被称为“完整采样”。或者，为了节省时间，patternsearch 可以在找到一个目标函数值更优的点后立即停止计算。本例展示了使用完整轮询的一些效果。

考虑以下目标函数。

$f (x_{1}, x_{2}) = {\begin{array}{llllllllllllllllllll} x_{1}^{2} + x_{2}^{2} - 25 & f o r x_{1}^{2} + x_{2}^{2} \leq 25 \\ x_{1}^{2} + {(x_{2} - 9)}^{2} - 16 & f o r x_{1}^{2} + {(x_{2} - 9)}^{2} \leq 16 \\ 0 & o t h e r w i s e . \end{array}$

该函数的全局最小值出现在点 (0, 0)，其值是 –25。然而，该函数在点 (0, 9) 处也有一个局部最小值，该处的值是 –16。

这段代码用于创建该函数。

function z = poll_example(x)
if x(1)^2 + x(2)^2 <= 25
    z = x(1)^2 + x(2)^2 - 25;
elseif x(1)^2 + (x(2) - 9)^2 <= 16
    z = x(1)^2 + (x(2) - 9)^2 - 16;
else z = 0;
end
end

绘制函数。

[X,Y] = meshgrid(-6:.1:6,-6:.1:14);
Z = zeros(size(X));
for i = 1:size(X,1)
    for j=1:size(X,2)
        Z(i,j) = poll_example([X(i,j),Y(i,j)]);
    end
end
surf(X,Y,Z,LineStyle="none");
view([-60,30])
annotation("textarrow",[0.24 0.38],...
    [0.11 0.47],String="Local minimum at [0,9]");
annotation("textarrow",[0.68 0.6],...
    [0.15 0.26],String="Global minimum at [0,0]");

Figure contains an axes object. The axes object contains an object of type surface.

要寻找极小值，请对该函数进行模式搜索。若要让 patternsearch 使用标准网格，请将 ScaleMesh 选项设置为 false。

options = optimoptions("patternsearch",Display="iter",...
    ScaleMesh=false);
[x,fval] = patternsearch(@poll_example,[0,5],...
    [],[],[],[],[],[],[],options)

Iter     Func-count       f(x)      MeshSize     Method
    0           1              0             1      
    1           3             -7             2     Successful Poll
    2           5            -15             4     Successful Poll
    3           9            -15             2     Refine Mesh
    4          13            -15             1     Refine Mesh
    5          15            -16             2     Successful Poll
    6          19            -16             1     Refine Mesh
    7          23            -16           0.5     Refine Mesh
    8          27            -16          0.25     Refine Mesh
    9          31            -16         0.125     Refine Mesh
   10          35            -16        0.0625     Refine Mesh
   11          39            -16       0.03125     Refine Mesh
   12          43            -16       0.01562     Refine Mesh
   13          47            -16      0.007812     Refine Mesh
   14          51            -16      0.003906     Refine Mesh
   15          55            -16      0.001953     Refine Mesh
   16          59            -16     0.0009766     Refine Mesh
   17          63            -16     0.0004883     Refine Mesh
   18          67            -16     0.0002441     Refine Mesh
   19          71            -16     0.0001221     Refine Mesh
   20          75            -16     6.104e-05     Refine Mesh
   21          79            -16     3.052e-05     Refine Mesh
   22          83            -16     1.526e-05     Refine Mesh
   23          87            -16     7.629e-06     Refine Mesh
   24          91            -16     3.815e-06     Refine Mesh
   25          95            -16     1.907e-06     Refine Mesh
   26          99            -16     9.537e-07     Refine Mesh
patternsearch stopped because the mesh size was less than options.MeshTolerance.

x = 1×2

     0     9

fval = 
-16

要理解 patternsearch 在其轮询中做了什么，请计算该算法的各个步骤。该算法首先在初始点 $f (0, 5) = 0$ 处计算该函数的值。该调查在最初的几次迭代中计算了以下内容。

$f ([0, 5] + [1, 0]) = f ([1, 5]) = 0$

$f ([0, 5] + [0, 1]) = f ([0, 6]) = - 7$

一旦搜索轮询网格点 (0, 6)，此时目标函数值小于初始点，它将停止轮询当前网格，并将下一次迭代的当前点设置为 (0, 6)。因此，在第一次迭代中，搜索向 (0, 9) 处的局部最小值移动。您可以通过查看命令行显示的前两行来看到这一点。

Iter Func-count f(x) MeshSize Method

0 1 0 1

1 3 -7 2 Successful Poll

请注意，模式搜索在第一次迭代中仅对目标函数执行两次评估，从而将总函数数从 1 增加到 3。

接下来，将 UseCompletePoll 选项设置为 true，然后重新运行优化。

options.UseCompletePoll = true;
[x,fval] = patternsearch(@poll_example,[0,5],...
    [],[],[],[],[],[],[],options)

Iter     Func-count       f(x)      MeshSize     Method
    0           1              0             1      
    1           5             -9             2     Successful Poll
    2           9            -21             4     Successful Poll
    3          13            -21             2     Refine Mesh
    4          17            -25             4     Successful Poll
    5          21            -25             2     Refine Mesh
    6          25            -25             1     Refine Mesh
    7          29            -25           0.5     Refine Mesh
    8          33            -25          0.25     Refine Mesh
    9          37            -25         0.125     Refine Mesh
   10          41            -25        0.0625     Refine Mesh
   11          45            -25       0.03125     Refine Mesh
   12          49            -25       0.01562     Refine Mesh
   13          53            -25      0.007812     Refine Mesh
   14          57            -25      0.003906     Refine Mesh
   15          61            -25      0.001953     Refine Mesh
   16          65            -25     0.0009766     Refine Mesh
   17          69            -25     0.0004883     Refine Mesh
   18          73            -25     0.0002441     Refine Mesh
   19          77            -25     0.0001221     Refine Mesh
   20          81            -25     6.104e-05     Refine Mesh
   21          85            -25     3.052e-05     Refine Mesh
   22          89            -25     1.526e-05     Refine Mesh
   23          93            -25     7.629e-06     Refine Mesh
   24          97            -25     3.815e-06     Refine Mesh
   25         101            -25     1.907e-06     Refine Mesh
   26         105            -25     9.537e-07     Refine Mesh
patternsearch stopped because the mesh size was less than options.MeshTolerance.

x = 1×2

     0     0

fval = 
-25

这一次，模式搜索在 (0, 0) 处找到全局最小值。本次运行与上次运行的区别在于：当 UseCompletePoll 设置为 true 时，在第一次迭代中，模式搜索会轮询所有四个网格点。

$f ([0, 5] + [1, 0]) = f ([1, 5]) = 0$

$f ([0, 5] + [0, 1]) = f ([0, 6]) = - 7$

$f ([0, 5] + [- 1, 0]) = f ([- 1, 5]) = 0$

$f ([0, 5] + [0, - 1]) = f ([0, 4]) = - 9$

由于最后一个网格点具有最低的目标函数值，模式搜索选择它作为下一次迭代的当前点。命令行显示的前两行显示了这一点。

Iter Func-count f(x) MeshSize Method

0 1 0 1

1 5 -9 2 Successful Poll

在这种情况下，目标函数在第一次迭代时被评估四次。因此，模式搜索向 (0, 0) 处的全局最小值移动。

下图比较了当完成轮询设置为“关闭”时返回的点序列，与完成轮询设置为“开启”时返回的点序列。该函数的代码出现在图窗之后。

graph_poll_example

Figure contains an axes object. The axes object contains 58 objects of type contour, line, text. One or more of the lines displays its values using only markers These objects represent Initial point, Complete poll off, Complete poll on.

function graph_poll_example
ff = [];
tt = [];
[X,Y] = meshgrid(-6:.1:14,-6:.1:14);
Z = zeros(size(X));
for i = 1:size(X,1)
    for j=1:size(X,2)
        Z(i,j) = poll_example([X(i,j),Y(i,j)]);
    end
end
contour(X,Y,Z);
hold on

h = plot(0,5,"ko");

opts = optimoptions("patternsearch", ...
    OutputFcn=@plotpnt, ...
    UseCompletePoll=false, ...
    Display="off",...
    ScaleMesh=false);
[thex,thefv] = patternsearch(@poll_example,[0,5],...
    [],[],[],[],[],[],[],opts);

opts.UseCompletePoll=true;
[thex,thefv] = patternsearch(@poll_example,[0,5],...
    [],[],[],[],[],[],[],opts);
hold off

line([0,6],[9,6],Color="k",LineStyle="--")
line([0,6],[0,3],Color="k",LineStyle="--")

text(6.2,6,"Local minimum")
text(6.2,3,"Global minimum")

legend([h,ff,tt],"Initial point","Complete poll off","Complete poll on")

    function [stop,opts,optchanged] = plotpnt(optimvalues,opts,flag)
        if strcmp(flag,"iter")
            if opts.UseCompletePoll == true
                tt = plot(optimvalues.x(1),optimvalues.x(2),"r+");
            else
                ff = plot(optimvalues.x(1),optimvalues.x(2),"b*");
            end
        end
        stop = false;
        optchanged = false;
    end

end

另请参阅

patternsearch

在模式搜索中使用完整轮询

另请参阅

主题