替代优化算法
串行 surrogateopt 算法
串行 surrogateopt 算法概述
替代优化算法在两个阶段之间交替进行。
构建替代 - 在边界内创建
options.MinSurrogatePoints个随机点。在这些点处评估（昂贵的）目标函数。通过对这些点进行径向基函数插值来构建目标函数的替代。搜索最小值 - 通过在边界内采样数千个随机点来搜索目标函数的最小值。根据这些点的替代值以及它们与已评估（昂贵的）目标函数的点之间的距离来评估优化函数。选择最佳点作为候选点，由优化函数来衡量。在最佳候选点处评估目标函数。该点称为自适应点。使用该值更新替代并再次搜索。
在构建替代阶段，算法从准随机序列构建样本点。构建插值径向基函数至少需要 nvars + 1 个样本点，其中 nvars 是问题变量的数量。options.MinSurrogatePoints 的默认值是 2*nvars 或 20 中的较大者。
当所有搜索点都太接近（小于选项 MinSampleDistance）目标函数之前评估的点时，算法将停止搜索最小值阶段。请参阅 搜索最低限度的详细信息。从“寻找最小值”阶段进行的这种切换称为替代重置。
如果在计算目标函数或非线性约束函数时 surrogateopt 遇到 NaN 值，则 surrogateopt 拒绝该计算点并继续计算。
替代优化的定义
替代优化算法描述使用以下定义。
当前-最近一次评估目标函数的点。
现任者-自最近一次替代重置以来，所有评估点中目标函数值最小的点。
最佳-迄今为止评估的所有点中目标函数值最小的点。
初始 - 您在
InitialPoints选项中传递给求解器的点（如果有）。随机点-构造替代阶段中求解器评估目标函数的点。一般来说，求解器从准随机序列中获取这些点，并缩放和移动以保持在边界内。准随机序列与
rand返回的伪随机序列类似，但间隔更均匀。请参阅 https://en.wikipedia.org/wiki/Low-discrepancy_sequence。然而，当变量数量超过 500 时，求解器会从拉丁超立方体序列中取点。请参阅 https://en.wikipedia.org/wiki/Latin_hypercube_sampling。自适应点- 在寻找最小值阶段中求解器评估目标函数的点。
评价函数 - 请参阅 评价函数定义。
评估点- 已知目标函数值的所有点。这些点包括初始点、构造替代点和求解器评估目标函数的最小点。
采样点。求解器在寻找最小值阶段评估优化函数的伪随机点。这些点不是求解器评估目标函数的点，除非在 搜索最低限度的详细信息 中进行了描述。
构建替代细节
为了构建替代，该算法选择边界内的拟随机点。如果在 InitialPoints 选项中传递一组初始点，算法将使用这些点和新的准随机点（如果需要）来达到总数 options.MinSurrogatePoints。
当 BatchUpdateInterval > 1 时，用于创建替代的最小随机样本点数是 MinSurrogatePoints 和 BatchUpdateInterval 中较大者。
注意
如果某些上界和下界相等，surrogateopt 会在构建替代之前从问题中删除那些“固定”变量。surrogateopt 会无缝地管理变量。因此，例如，如果您传递初始点，请传递完整集合，包括任何固定变量。
在后续的构造替代阶段，该算法使用 options.MinSurrogatePoints 准随机点。该算法在这些点评估目标函数。
该算法利用径向基函数 (RBF) 插值器构建替代作为目标函数的插值。RBF 插值具有多种便捷的属性，使其适合于构建替代：
该算法在第一个构建替代阶段仅使用初始点和随机点，在后续的构建替代阶段仅使用随机点。特别是，该算法不使用来自此替代中“寻找最小值”阶段的任何自适应点。
搜索最低限度的详细信息
求解器按照与局部搜索相关的程序来寻找目标函数的最小值。求解器使用值 0.2 初始化搜索的比例。该比例就像模式搜索中的搜索区域半径或网格大小。求解器从现任点开始，该现任点是自上次替代重置以来目标函数值最小的点。求解器搜索与替代和与现有搜索点的距离相关的优化函数的最小值，以尝试在最小化替代和搜索空间之间取得平衡。请参阅 评价函数定义。
求解器将数百或数千个具有缩放长度的伪随机向量添加到现任点以获得样本点。有关详细信息，请参阅采样器周期表和相关讨论。这些向量根据每个维度的边界进行移动和缩放，然后乘以比例。如果有必要，求解器会改变样本点，以便它们保持在边界内。求解器在样本点处评估优化函数，但不会在先前评估的点的 options.MinSampleDistance 内的任何点处评估优值函数。优化函数值最低的点称为自适应点。求解器评估自适应点处的目标函数值，并使用该值更新替代。如果自适应点处的目标函数值足够低于现任值，则求解器认为搜索成功，并将自适应点设置为现任值。否则，求解器认为搜索不成功并且不会更改现任者。
当满足以下第一个条件时，求解器将改变比例：
自上次改变规模以来，已进行了三次成功的搜索。在这种情况下，比例加倍，最大比例长度为边界指定的框大小的
0.8倍。自上次规模改变以来，发生了
max(5,nvar)次不成功的搜索，其中nvar是问题变量的数量。在这种情况下，比例减半，最小比例长度为边界指定的框大小的1e-5倍。
这样，随机搜索最终集中在目标函数值较小的现任点附近。然后求解器以几何方式将尺度缩小至最小尺度长度。
surrogateopt 尝试寻找优化函数最小值的方式取决于问题类型。问题类型包括边界加可选线性约束、纯二进制、二进制加线性约束以及带线性约束的一般整数。（非线性约束不会影响这些问题类型。）每个采样器对现任者周围缩放区域内的点进行采样。任何整数点都有一个从边界宽度的 ½ 倍开始的比例，并像非整数点一样进行精确调整，但如果宽度低于 1，则宽度会增加到 1。
对于每种问题类型，surrogateopt 根据下表选择与权重相关的循环采样器。
采样器周期
| 权重 | 0.3 | 0.5 | 0.8 | 0.95 |
| 边界 + 可选线性 | 随机 | 随机 | OrthoMADS | GPS |
| 纯二进制 | 随机 | 随机 | 交叉 | 交叉 |
| 二进制 + 线性 | OrthoMADS | OrthoMADS | 交叉 | 交叉 |
| 整数 + 线性 | OrthoMADS | 交叉 | OrthoMADS | GPS |
随机 - 采样器以现任者为中心，在一个范围内均匀随机地生成整数点。采样器根据现任者的均值为零的高斯分布生成连续点。任何整数点的样本的宽度都乘以比例，连续点的标准差也是如此。
OrthoMADS - 采样器随机均匀地选择一个正交坐标系。然后，该算法在现任者周围创建样本点，在坐标系中加上和减去当前比例向量每个单位向量。这将创建 2N 个样本（除非某些整数点被四舍五入到现任者），其中 N 是问题维度的数量。OrthoMADS 还使用了比 2N 固定方向多两个点，一个在 [+1,+1,…,+1]，另一个在 [-1,-1,…,-1]，总共 2N+2 个点。然后，采样器重复将 2N + 2 个步骤减半，在现任者周围创建越来越精细的点集。当样本足够时，该过程结束。然后将应为整数值的点四舍五入为最接近的可行整数点。OrthoMADS 算法基于论文[6]。该论文使用一组准随机数来生成坐标系。相比之下，
surrogateopt使用标准 MATLAB® 伪随机数，其正交坐标由qr生成。GPS（广义模式搜索）-采样器类似于 OrthoMADS，只是 GPS 不是选择一组随机的方向，而是使用非旋转的坐标系。GPS 算法基于论文[5]。该算法在模式搜索轮询的工作原理中有详细描述。
交叉 - 采样器使用
ga'crossoverarithmetic'交叉函数（请参阅 交叉选项），其中交叉的种群是surrogateopt已评估的点。种群是使用'selectiontournament'选择函数（请参阅 选择选项）来选择的，共有四名玩家。样本中的点数取决于信赖区域大小；较小的信赖区域半径导致更多的点被采样来评估优化函数。
求解器不会评估评估点 options.MinSampleDistance 内的点的优化函数（请参阅替代优化的定义）。当所有样本点都在评估点的 MinSampleDistance 范围内时，求解器从搜索最小值阶段切换到构造替代阶段（换句话说，执行替代重置）。一般来说，这种重置发生在求解器缩小规模之后，以便所有样本点都紧密聚集在现任者周围。
当 BatchUpdateInterval 选项大于 1 时，求解器会在更新替代模型或更改现任者之前生成 BatchUpdateInterval 自适应点。此次更新涵盖了所有自适应点。实际上，该算法在生成 BatchUpdateInterval 自适应点之前不会使用任何新信息，然后该算法使用所有信息来更新替代。
当问题没有整数变量且具有非线性约束时，算法在每 K（接下来定义）步之后使用 MultiStart fmincon 对优化函数执行搜索。这与针对整数约束问题的树搜索算法类似。这个 fmincon 调用比较耗时，但是可以得到更优的可行目标函数值。K 的值取决于 N：
如果 N < 15，则 K = max(50,10*N)。
如果 N ≥15，则 K = max(50, 2*N)。
评价函数定义
优化函数 fmerit(x) 是两个项的加权组合：
缩放替代。定义 smin 为样本点中的最小替代值，smax 为最大值，s(x) 为点 x 处的替代值。然后缩放替代 S(x) 是
s(x) 为非负数，在样本点中具有最小替代值的点 x 处为零。
缩放距离。定义 xj, j = 1,…,k 为 k 评估点。将 dij 定义为从样本点 i 到评估点 k 的距离。设置 dmin = min(dij) 和 dmax = max(dij)，其中最小值和最大值取自所有 i 和 j。缩放距离 D(x) 为
其中 d(x) 是点 x 到评估点的最小距离。D(x) 为非负数，在距离评估点最远的点 x 处为零。因此，最小化 D(x) 会导致算法得出远离评估点的点。
优化函数是缩放替代和缩放距离的凸组合。对于权重 w 且 0 < w < 1，优化函数为
w 的较大值赋予了替代值重要性，从而导致搜索最小化替代。较小的 w 值会重视远离评估点的点，从而将搜索引向新的区域。在寻找最小值阶段，权重 w 会在以下四个值之间循环，正如 Regis 和 Shoemaker [2] 所建议的那样：0.3、0.5、0.8 和 0.95。
混合整数 surrogateopt 算法
混合整数 surrogateopt 概述
当部分或全部变量为整数时（如 intcon 参量中所指定），surrogateopt 会改变 串行 surrogateopt 算法 的某些方面。这个描述主要关于变化，而不是整个算法。
算法开始
如果有必要，surrogateopt 会移动 intcon 点的指定边界，使它们成为整数。此外，surrogateopt 确保所提供的初始点是整数可行且关于边界可行的。然后，该算法像非整数算法一样生成准随机点，将整数点四舍五入为整数值。该算法生成的替代与非整数算法完全相同。
整数搜索最小值
该部分算法与 搜索最低限度的详细信息 中的相同。对整数约束的修改出现在该部分中。
树搜索
在对优化函数进行数百或数千个值采样后，surrogateopt 通常会选择最小点，并评估目标函数。然而，在某些情况下，surrogateopt 在评估目标之前会执行另一个称为树搜索的搜索。这些情况不适用于纯二元问题或仅有边界且变量少于 15 个的问题。适用时，
自上一次树搜索以来，已经有 2N 步，称为案例 A。
surrogateopt即将执行替代重置，称为案例 B。
树搜索的进行方式如下，类似于 intlinprog 中的过程，如 分支定界 中所述。该算法通过查找一个整数值来生成一棵树，并创建一个新问题，该问题对该值的边界进行调整，该界限可以高出一个或低一个，然后用这个新的边界来解决子问题。在解决了子问题之后，该算法会选择一个不同的整数，将其限制在 1 以上或 1 以下。
案例 A：使用缩放的采样半径作为总体边界，并运行最多 30 步搜索。
案例 B：使用原始问题边界作为总体边界，并运行最多 60 步搜索。
在这种情况下，解决子问题意味着对连续变量运行 fmincon 'sqp' 算法，从具有指定整数值的现任者开始，从而搜索优化函数的局部最小值。
树搜索可能非常耗时。因此，surrogateopt 有一个内部迭代限制，以避免在此步骤中花费过多的时间，从而限制了案例 A 和案例 B 的步骤数。
在树搜索之后，算法使用 20 个点对 MultiStart 执行 MultiStart fmincon 搜索（N ≤ 10 时为 5 个点）。
在树搜索结束时，该算法将取树搜索找到的点和前一次搜索找到的点中的较好点作为最小值，以优化函数为衡量标准。此时算法会评估目标函数。整数算法的余数与连续算法完全相同。
线性约束处理
当问题具有线性约束时，算法会修改其搜索过程，使得每次迭代时所有点可行符合这些约束和边界。在构建和搜索阶段，该算法通过类似于 patternsearch 'GSSPositiveBasis2N' 轮询算法的过程仅创建线性可行点。
当问题具有整数约束和线性约束时，算法首先创建线性可行点。然后，该算法尝试通过将线性可行点四舍五入为整数来满足整数约束，该过程使用尝试保持点线性可行的启发式方法。当此过程无法获取足够的可行点来构建替代时，算法将调用 intlinprog 来尝试查找更多符合边界、线性约束和整数约束的可行点。
具有非线性约束的 surrogateopt 算法
当问题具有非线性约束时，surrogateopt 会通过几种方式修改前面描述的算法。
最初和每次替代重置之后，该算法都会创建目标和非线性约束函数的代理。随后，算法根据构建替代阶段是否找到任何可行点而有所不同；找到可行点相当于构建替代时现任点是可行的。请注意，如果目标函数或非线性约束函数在某一点的计算结果为 NaN，则 surrogateopt 将丢弃该点的目标函数值和约束，并且不会使用该点来创建或更新替代函数。
现任者不可行-这种情况称为第 1 阶段，涉及寻找可行点。在遇到可行点之前的寻找最小值阶段，
surrogateopt改变了优化函数的定义。该算法计算每个点违反的约束数，并仅考虑违反约束最少的点。在这些点中，算法选择最小化最大约束违反的点作为最佳（最低优化函数）点。这个最佳点就是现任者。随后，直到算法遇到可行点为止，它会使用此改进的优化函数。当surrogateopt评估某个点并发现其可行时，该可行点将成为现任者，算法进入第 2 阶段。现任者是可行的-这种情况称为第 2 阶段，其进行方式与标准算法相同。该算法在计算优化函数时忽略了不可行点。
该算法根据混合整数 surrogateopt 算法进行，但有以下变化。在每个 2*nvars 点之后，算法都会评估目标和非线性约束函数，surrogateopt 调用 fmincon 函数来最小化替代，但要遵守替代非线性约束和边界，其中边界由当前比例因子缩放。（如果现任者不可行，fmincon 将忽略目标并尝试找到满足约束的点。）如果问题同时具有整数和非线性约束，则 surrogateopt 调用 树搜索 而不是 fmincon。
如果问题是可行性问题，即它没有目标函数，那么 surrogateopt 在找到可行点后立即执行替代重置。
并行 surrogateopt 算法
并行 surrogateopt 算法与串行算法的区别如下：
并行算法维护一个用于评估目标函数的点队列。此队列比并行工作进程的数量大 30%（四舍五入）。队列大于工作进程的数量，以最大限度地减少工作进程因没有可供评估的点而闲置的机会。
调度程序以先进先出 (FIFO) 的方式从队列中获取点，并在工作人员空闲时异步地将这些点分配给工作进程。
当算法在各个阶段（搜索最小值和构造替代）之间切换时，正在评估的现有点仍在使用，并且队列中的任何其他点都将被刷新（从队列中丢弃）。因此，一般来说，算法为构造替代阶段创建的随机点的数量最多为
options.MinSurrogatePoints + PoolSize个，其中PoolSize是并行工作进程的数量。类似地，在替代重置之后，该算法仍然具有其工作进程正在评估的PoolSize - 1自适应点。
注意
目前，并行替代优化不一定能给出可再现的结果，因为并行时间的不可再现性可能导致不同的执行路径。
并行混合整数 surrogateopt 算法
当在混合整数问题上并行运行时，surrogateopt 在主机上执行树搜索过程，而不是在并行工作进程上执行。使用最新的替代，在每个工作进程带着自适应点返回后，surrogateopt 寻找较小的替代值。
如果目标函数不昂贵（耗时），那么这个树搜索过程可能会成为主机的瓶颈。相反，如果目标函数很昂贵，那么树搜索过程只占用总体计算时间的一小部分，并且不会成为瓶颈。
参考
[1] Powell, M. J. D. The Theory of Radial Basis Function Approximation in 1990. In Light, W. A. (editor), Advances in Numerical Analysis, Volume 2: Wavelets, Subdivision Algorithms, and Radial Basis Functions. Clarendon Press, 1992, pp. 105–210.
[2] Regis, R. G., and C. A. Shoemaker. A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions. INFORMS J. Computing 19, 2007, pp. 497–509.
[3] Wang, Y., and C. A. Shoemaker. A General Stochastic Algorithm Framework for Minimizing Expensive Black Box Objective Functions Based on Surrogate Models and Sensitivity Analysis. arXiv:1410.6271v1 (2014). Available at https://arxiv.org/pdf/1410.6271.
[4] Gutmann, H.-M. A Radial Basis Function Method for Global Optimization. Journal of Global Optimization 19, March 2001, pp. 201–227.
[5] Audet, Charles, and J. E. Dennis Jr. “Analysis of Generalized Pattern Searches.” SIAM Journal on Optimization. Volume 13, Number 3, 2003, pp. 889–903.
[6] Abramson, Mark A., Charles Audet, J. E. Dennis, Jr., and Sebastien Le Digabel. “ORTHOMADS: A deterministic MADS instance with orthogonal directions.” SIAM Journal on Optimization. Volume 20, Number 2, 2009, pp. 948–966.
