代理优化算法
串行surrogateopt算法
串行surrogateopt算法概述
代理优化算法在两个阶段之间交替进行。
构建代理——创建
选项。MinSurrogatePoints范围内的随机点。在这些点上计算(昂贵的)目标函数。通过插值a来构造目标函数的代理函数径向基函数通过这些点。寻找最小值-通过在边界内抽样几千个随机点来搜索目标函数的最小值。基于这些点的替代值以及它们与(昂贵的)目标函数已被评估的点之间的距离来评估价值函数。选择最好的点作为候选人，作为衡量的价值函数。在最佳候选点评估目标函数。这个点叫做an自适应点。使用此值更新代理并再次搜索。
在构造代理阶段，算法从准随机序列中构造样本点。构造一个插值径向基函数至少需要据nvar+ 1个样本点，其中据nvar是问题变量的个数。的默认值。选项。MinSurrogatePoints是据nvar 2 *或20.取较大的。
当所有的搜索点都太接近(小于选项)时，算法停止搜索最小值阶段MinSampleDistance)到目标函数先前评估过的点。看到搜索最小细节。这个从搜索最小值阶段开始的开关被调用代理重置。
代理优化的定义
代理优化算法描述使用以下定义。
当前-目标函数最近被评估的点。
在位-自最近一次代理重置以来所有评估的目标函数值中最小的点。
最佳-在所有评估中目标函数值最小的点。
初始-如果有的话，你传递给解算器的点
InitialPoints选择。随机点——求解器在构建代理阶段评估目标函数的点。通常，求解器从准随机序列中取这些点，并进行缩放和移位以保持在边界内。准随机序列类似于伪随机序列，如
兰德返回，但间隔更均匀。看到https://en.wikipedia.org/wiki/Low-discrepancy_sequence。然而，当变量的数量大于500时，求解器从拉丁超立方序列中取点。看到https://en.wikipedia.org/wiki/Latin_hypercube_sampling。自适应点-在搜索最小值阶段的点，求解器评估目标函数。
绩效函数-见优点函数定义。
求值点-所有已知目标函数值的点。这些点包括初始点、构造代理点和搜索求解器评估目标函数的最小点。
采样点。伪随机点，求解器在搜索最小值阶段对价值函数进行评估。这些点不是解算器计算目标函数的点，除非在搜索最小细节。
构造代理细节
为了构造代理，算法在边界内选择准随机点。如果你传递一个初始的点集合InitialPoints选项，算法使用这些点和新的准随机点(如有必要)来达到总数选项。MinSurrogatePoints。
当BatchUpdateInterval> 1，用于创建代理的随机样本点的最小数量是其中较大的一个MinSurrogatePoints和BatchUpdateInterval。
请注意
如果某个上界和下界相等，surrogateopt在构造代理之前，从问题中删除那些“固定”变量。surrogateopt无缝地管理变量。例如，如果你传递初始点，传递完整的集合，包括任何固定的变量。
在随后的构造代理阶段，算法使用选项。MinSurrogatePointsquasirandom点。该算法在这些点处评估目标函数。
该算法构造一个代理作为目标函数的插值径向基函数(RBF)插入器。RBF插值有几个方便的属性，使其适合于构造代理:
该算法在第一个Construct proxy阶段中仅使用初始点和随机点，并且在随后的Construct proxy阶段中仅使用随机点。特别是，该算法在此代理中不使用Search for Minimum阶段的任何自适应点。
搜索最小细节
求解器通过一个与局部搜索相关的过程来搜索目标函数的最小值。求解器初始化a规模对于值为0.2的搜索。尺度类似于模式搜索中的搜索区域半径或网格大小。求解器从在位点开始，在位点是自上次代理重置以来目标函数值最小的点。求解器搜索a的最小值优值函数这涉及到代理和到现有搜索点的距离，试图在最小化代理和搜索空间之间取得平衡。看到优点函数定义。
求解器将数百或数千个长度按比例缩放的伪随机向量添加到在位点以获得采样点。这些向量具有正态分布，通过每个维度的边界进行平移和缩放，并乘以尺度。如有必要，求解器会改变样本点，使其保持在边界内。求解器在样本点处评估价值函数，而不是在样本点内的任何点选项。MinSampleDistance一个先前计算过的点的。优点函数值最小的点称为自适应点。求解器在自适应点计算目标函数值，并用该值更新代理。如果自适应点处的目标函数值小于在位值，则求解器认为搜索成功，并将自适应点设为在位值。否则，求解器认为搜索不成功，不改变在位者。
当满足以下第一个条件时，求解器会改变尺度:
自上次规模更改以来，进行了三次成功的搜索。在这种情况下，刻度加倍，最大刻度长度为
0.8乘以由边界指定的框的大小。据nvar马克斯(5)自上次规模更改以来发生不成功的搜索，其中据nvar是问题变量的个数。在这种情况下，比例减半，减少到最小比例长度为1 e-5乘以由边界指定的框的大小。
这样，随机搜索最终集中在目标函数值较小的在位点附近。然后求解器以几何方式将尺度减小到最小尺度长度。
求解器不评估内部点的价值函数选项。MinSampleDistance求值点的(参见代理优化的定义）.当所有样本点都在范围内时，求解器从搜索最小值阶段切换到构造代理阶段(换句话说，执行代理重置)MinSampleDistance求值点。通常，这种重置发生在求解器减小尺度之后，这样所有的样本点都紧密地聚集在在位点周围。
当BatchUpdateInterval期权大于1，求解器生成BatchUpdateInterval在更新代理模型或更改在位者之前的自适应点。更新包括所有的自适应点。有效地，算法不使用任何新的信息，直到它产生BatchUpdateInterval自适应点，然后算法利用所有信息更新代理。
优点函数定义
价值函数f优点（x)是两个项的加权组合:
按比例缩小的代理。定义年代最小值作为样本点之间的最小代理值，年代马克斯为最大值，且年代（x)作为该点上的代理值x。然后缩放代理年代（x)是
年代（x)是非负的，并且在点处为零x在样本点中代理值最小。
按比例缩小的距离。定义xj，j= 1,…,k随着k评估点。定义dij为到样本点的距离我求值点k。集d最小值= min (dij),d马克斯= max (dij)，其中最小值和最大值被全部取走我和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为的指定边界移动intcon点，使它们是整数。同时,surrogateopt确保提供的初始点是整数可行的，并且在边界上可行。然后，该算法像非整数算法一样生成准随机点，将整数点舍入为整数值。该算法生成的代理与非整数算法完全相同。
最小值的整数搜索
寻找最小值的过程使用与之前相同的价值函数和权重序列。区别在于surrogateopt使用三种不同的随机点采样方法来定位价值函数的最小值。surrogateopt根据下表选择与权重相关联的周期采样器。
取样器循环
| 重量 | 0.3 | 0.5 | 0.8 | 0.95 |
| 取样器 | 随机 | 随机 | OrthoMADS | 全球定位系统(GPS) |
尺度-每个采样器在在位器周围的一个尺度区域内采样点。整数点的尺度从边界宽度的1 / 2倍开始，并精确地调整为非整数点，除非宽度低于1，否则将增加到1。连续点的尺度发展与非整数算法完全相同。
随机-采样器在一个尺度内均匀随机地产生整数点，以在位者为中心。采样器根据高斯分布从在位者处生成均值为零的连续点。整数点的样本宽度乘以尺度，连续点的标准差也是如此。
OrthoMADS -采样器均匀随机地选择一个正交坐标系。然后，该算法在在位者周围创建采样点，对当前尺度乘以坐标系统中的每个单位向量进行加减。该算法将整数点四舍五入。这将创建2N个样本(除非一些整数点四舍五入)，其中N是问题维度的数量。OrthoMADS还使用比2N个固定方向多两个点，一个在[+1，+1，…，+1]，另一个在[-1，-1，…，-1]，总共2N+2个点。然后采样器重复将2N + 2步减半，在现有节点周围创建越来越精细的点集，同时将整数点四舍五入。当有足够的样本或舍入导致没有新样本时，此过程结束。
GPS -采样器类似于OrthoMADS，除了GPS使用非旋转坐标系，而不是随机选择一组方向。
树搜索
在对价值函数的成百上千个值进行采样后，surrogateopt通常选取最小点，并对目标函数进行评价。然而，在两种情况下，surrogateopt在评估目标之前执行另一个称为树搜索的搜索:
自从上次的树搜索(称为情况A)以来，已经有2N步了。
surrogateopt即将执行一个称为Case B的代理重置。
树搜索的过程如下所示，类似于intlinprog，如分支与定界。该算法通过找到一个整数值来生成树，然后创建一个新的问题，这个问题的边界在这个值上，或者高一个，或者低一个，然后用这个新边界来解决子问题。在解出子问题后，算法选择一个不同的整数以1为上界或下界。
情况A:使用缩放的采样半径作为总体边界，并运行最多1000步的搜索。
情形B:使用原始问题边界作为总体边界，并运行最多5000步的搜索。
在本例中，解决子问题意味着运行fmincon“sqp”算法对连续变量，从任职者具有指定的整数值开始，从而搜索一个局部最小值的功绩函数。
树搜索可能很耗时。所以surrogateopt有一个内部时间限制，以避免在此步骤中花费过多的时间，从而限制了情况A和情况B步骤的数量。
在树状搜索结束时，算法将树状搜索找到的点与之前搜索找到的点中较优的点进行最小值计算，并通过价值函数来衡量。算法在这一点评估目标函数。整数算法的余数与连续算法完全相同。
线性约束处理
当问题具有线性约束时，算法修改其搜索过程，使所有点在这些约束和每次迭代的边界下都是可行的。在构造和搜索阶段，算法通过类似于patternsearch“GSSPositiveBasis2N”调查显示算法。
当问题具有整数约束和线性约束时，算法首先生成线性可行点。然后，该算法尝试通过使用启发式算法将线性可行点四舍五入到整数的过程来满足整数约束，该启发式算法试图保持这些点线性可行。当此过程无法获得足够的可行点来构造代理时，算法调用intlinprog试图找到更多的点，这些点在边界、线性约束和整数约束下是可行的。
surrogateopt非线性约束算法
当问题有非线性约束时，surrogateopt从几个方面修改前面描述的算法。
初始和每次重置代理后，算法创建目标和非线性约束函数的代理。随后，根据构造代理阶段是否找到可行点，算法会有所不同;找到一个可行点相当于在构造代理时现有点是可行的。
在位者不可行——这种情况称为阶段1，包括寻找可行点。在遇到可行点之前的搜索最小值阶段，
surrogateopt改变价值函数的定义。该算法计算每个点违反约束的数量，并只考虑违反约束数量最少的点。在这些点中，算法选择最大约束违反最小的点作为最佳(最低价值函数)点。最好的一点是现任者。随后，直到算法遇到一个可行点，它使用这个修改的优点函数。当surrogateopt计算一个点，发现可行点，可行点成为在位点，算法进入阶段2。在位者是可行的——这种情况称为阶段2，以与标准算法相同的方式进行。为了计算价值函数，该算法忽略了不可行的点。
算法根据混合整数surrogateopt算法通过以下更改。在每一个据nvar 2 *算法评估目标和非线性约束函数的点，surrogateopt调用fmincon函数最小化代理，服从代理的非线性约束和边界，其中边界由当前比例因子缩放。(如果现任者不可行，fmincon忽略目标，试图找到满足约束条件的点。)如果问题同时具有整数约束和非线性约束，则surrogateopt调用树搜索而不是fmincon。
如果问题是可行性问题，也就是说它没有目标函数，那么surrogateopt在找到可行点后立即执行代理重置。
平行surrogateopt算法
并行surrogateopt算法与串行算法的区别如下:
并行算法维持一个点的队列，在这个队列上对目标函数求值。这个队列比并行工人的数量大30%(四舍五入)。队列大于工作线程的数量，以最大限度地减少工作线程空闲的可能性，因为没有可用的计算点。
调度器以先进先出的方式从队列中获取点，并在工作线程空闲时异步地将它们分配给它们。
当算法在阶段(搜索最小值和构造代理)之间切换时，正在评估的现有点仍在服务中，队列中的任何其他点将被刷新(从队列中丢弃)。因此，一般来说，算法为Construct proxy阶段创建的随机点的数量最多为0
选项。MinSurrogatePoints + PoolSize,在那里PoolSize是并行工人的数量。类似地，在代理重置之后，算法仍然具有PoolSize - 1员工正在评估的适应性点。
请注意
目前，由于并行计时的不可再现性，并行代理优化不一定能给出可再现的结果，这可能导致不同的执行路径。
并行混合整数surrogateopt算法
当并行运行一个混合整数问题时，surrogateopt在主机上执行树搜索过程，而不是在并行工作线程上执行。使用最新的代理，surrogateopt在每个工作者返回一个自适应点后搜索代理的较小值。
如果目标函数不昂贵(耗时)，那么这个树搜索过程可能是主机的瓶颈。相反，如果目标函数是昂贵的，那么树搜索过程只占用总体计算时间的一小部分，并且不是瓶颈。
参考文献
鲍威尔，m.j. D。1990年提出径向基函数逼近理论。《光明》，W. A.(编辑);数值分析进展，第二卷:小波，细分算法和径向基函数。克拉伦登出版社，1992年，第105-210页。
Regis, r.g.和c.a. Shoemaker。昂贵函数全局优化的随机径向基函数方法。计算机学报，2007，第497-509页。
bbbbo Wang, Y.和C. A. Shoemaker。基于代理模型和灵敏度分析的最小化昂贵黑箱目标函数的通用随机算法框架。v1 arXiv: 1410.6271(2014)。可以在https://arxiv.org/pdf/1410.6271。
H.-M.古特曼一种径向基函数全局优化方法。全球优化学报，2001年3月19日，第201-227页。
