Main Content

本页采用了机器翻译。点击此处可查看英文原文。

轮询类型

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

作为示例，考虑以下函数。

f(x1,x2)={x12+x22−25for x12+x22≤25x12+(x2−9)2−16for x12+(x2−9)2≤160otherwise.

下图显示了该函数的图。

 用于生成图窗的代码

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

要创建计算函数的文件，请将以下代码复制并粘贴到 MATLAB® 编辑器中的新文件中。

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

将文件作为 poll_example.m 保存到 MATLAB 路径上的某个文件夹中。

要对函数运行模式搜索，请输入以下内容。

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

MATLAB 返回迭代表和解方案。

x =

     0     9


fval =

   -16

算法首先在初始点 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     f-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);

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

f((0, 5) + (1, 0)) = f(1, 5) = 0

f((0, 5) + (0, 1)) = f(0, 6) = -6

f((0, 5) + (-1, 0)) = f(- 1, 5) = 0

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

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

Iter     f-count     f(x)      MeshSize     Method
    0        1         0             1      
    1        5        -9             2     Successful Poll

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

下图比较了 Complete 轮询设置为 Off 时返回的点序列与 Complete 轮询为 On 时返回的点序列。

 用于生成图窗的代码

比较轮询选项的效率

此示例显示了多个轮询选项在迭代和总体函数计算方面如何相互作用。主要结果包含：

  • 对于线性约束问题，GSS 比 GPS 或 MADS 更有效。

  • 将 UseCompletePoll 设置为 true 是否会提高效率或降低效率尚不清楚，尽管它会影响迭代次数。

  • 类似地，2N 轮询是否比 Np1 轮询更有效或更无效也不清楚。最有效的轮询是 GSS Positive Basis Np1，并将完整轮询设置为开启。效率最低的是将 MADS Positive Basis Np1 与 Complete 轮询设置为 on。

注意

算法的效率取决于问题。GSS 对于线性约束问题非常有效。然而，预测其他轮询选项的效率影响是困难的，同样困难的是知道哪种轮询类型在其他约束下效果最好。

问题设置

该问题与 在优化实时编辑器任务中使用 patternsearch 进行求解 中的问题相同。这个线性约束问题有一个二次目标函数。

  1. 在您的 MATLAB 工作区中输入以下内容。

    x0 = [2 1 0 9 1 0];
Aineq = [-8 7 3 -4 9 0];
bineq = 7;
Aeq = [7 1 8 3 3 3; 5 0 -5 1 -5 8; -2 -6 7 1 1 9; 1 -1 2 -2 3 -3];
beq = [84 62 65 1];
H = [36 17 19 12  8 15; 
     17 33 18 11  7 14; 
     19 18 43 13  8 16;
     12 11 13 18  6 11; 
      8  7  8  6  9  8; 
     15 14 16 11  8 29];

f = [ 20 15 21 18 29 24 ]';
 
fun = @(x)0.5*x'*H*x + f'*x;

  2. 设置初始选项和目标函数。

    options = optimoptions('patternsearch',...
    'PollMethod','GPSPositiveBasis2N',...
    'PollOrderAlgorithm','consecutive',...
    'UseCompletePoll',false);

  3. 运行优化，将 output 结构体命名为 outputgps2noff。

    [x,fval,exitflag,outputgps2noff] = patternsearch(fun,x0,...
    Aineq,bineq,Aeq,beq,[],[],[],options);

  4. 设置选项以使用完全轮询。

    options.UseCompletePoll = true;

  5. 运行优化，将 output 结构体命名为 outputgps2non。

    [x,fval,exitflag,outputgps2non] = patternsearch(fun,x0,...
    Aineq,bineq,Aeq,beq,[],[],[],options);

  6. 继续以类似的方式为其他轮询方法创建输出结构体，其中 UseCompletePoll 设置 true 和 false：outputgss2noff、outputgss2non、outputgssnp1off、outputgssnp1on、outputmads2noff、outputmads2non、outputmadsnp1off 和 outputmadsnp1on。

检查结果

您获得了 12 次优化运行的结果。下表显示了运行的效率，以总函数数和迭代次数来衡量。由于 MADS 是一种随机算法，因此您的 MADS 结果可能会有所不同。

算法函数计数迭代次数
GPS2N，完全轮询关闭1462136
GPS2N，完全轮询打开139696
GPSNp1，完全轮询关闭864118
GPSNp1，完全轮询打开1007104
GSS2N，完全轮询关闭75884
GSS2N，完全轮询打开88974
GSSNp1，完全轮询关闭53394
GSSNp1，完全轮询打开49170
MADS2N，完全轮询关闭922162
MADS2N，完全轮询打开2285273
MADSNp1，完全轮询关闭1155201
MADSNp1，完全轮询打开1651201

例如，要获取表中的第一行，请输入 gps2noff.output.funccount 和 gps2noff.output.iterations。您还可以通过双击工作区浏览器中的选项，然后双击 output 结构体来检查变量编辑器中的选项。

或者，您可以从输出结构体访问数据。

[outputgps2noff.funccount,outputgps2noff.iterations]
ans =

        1462         136

从表中得出的主要结果是：

  • 将 UseCompletePoll 设置为 true 通常会降低 GPS 和 GSS 的迭代次数，但函数计算次数的变化是不可预测的。

  • 将 UseCompletePoll 设置为 true 不一定会改变 MADS 的迭代次数，但会大幅增加函数计算的次数。

  • 最有效的算法/选项设置，效率意味着最少的函数数量：

    1. 'GSSPositiveBasisNp1' 将 UseCompletePoll 设置为 true（函数计数 491）

    2. 'GSSPositiveBasisNp1' 将 UseCompletePoll 设置为 false（函数计数 533）

    3. 'GSSPositiveBasis2N' 将 UseCompletePoll 设置为 false（函数计数 758）

    4. 'GSSPositiveBasis2N' 将 UseCompletePoll 设置为 true（函数计数 889）

    其它轮询方法的函数数量都超过 900。

  • 对于这个问题，最有效的轮询是将 'GSSPositiveBasisNp1' 与 UseCompletePoll 设置为 true，尽管 UseCompletePoll 设置只会产生很小的差别。效率最低的轮询是 'MADSPositiveBasis2N'，其中 UseCompletePoll 设置为 true。在这种情况下，UseCompletePoll 设置会产生很大的不同。

相关主题