代理优化算法
串行surrogateopt算法
串行surrogateopt算法概述
代理优化算法在两个阶段之间交替进行。
构建代理——创建
选项。MinSurrogatePoints边界内的随机点。在这些点上评估(昂贵的)目标函数。通过插值a来构造目标函数的替代物径向基函数通过这些点。搜索最小值-通过在边界内采样几千个随机点，寻找目标函数的最小值。基于这些点的代理值以及它们与(昂贵的)目标函数已被评估的点之间的距离来评估一个价值函数。选择最好的点作为候选点，用价值函数来衡量。在最佳候选点上评估目标函数。这个点叫做an自适应点．使用此值更新代理并再次搜索。
在构造代理阶段，算法从准随机序列构造样本点。构造插值径向基函数至少需要据nvar+ 1个采样点，其中据nvar是问题变量的数量。的默认值选项。MinSurrogatePoints是据nvar 2 *或20.，以较大者为准。
当所有搜索点都太接近(小于选项)时，算法停止搜索最小值阶段MinSampleDistance)到目标函数先前求值的点。看到搜索最少的细节．这个来自搜索最小值阶段的切换被调用代理重置．
代理优化的定义
代理优化算法描述使用以下定义。
当前-目标函数最近被求值的点。
在任点-自最近代理重置以来所有评估的目标函数值中最小的点。
Best -到目前为止，在所有评估的目标函数值中具有最小的点。
初始值-传递给求解器的点(如果有的话)
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无缝地管理变量。例如，如果你传递初始点，传递完整的集合，包括任何固定的变量。
在随后的Construct代理阶段，算法使用选项。MinSurrogatePointsquasirandom点。算法在这些点处对目标函数求值。
该算法构造一个代理作为目标函数的插值径向基函数(RBF)插入器。RBF插值有几个方便的属性，使它适合构造一个代理:
该算法在第一个Construct代孕阶段只使用初始点和随机点，在随后的Construct代孕阶段只使用随机点。特别地，该算法在此代理中不使用搜索最小值阶段的任何自适应点。
搜索最少的细节
求解器通过遵循与局部搜索相关的过程来搜索目标函数的最小值。求解器初始化规模对于值为0.2的搜索。尺度就像搜索区域半径或模式搜索中的网格大小。求解器从在位点开始，在位点是自上次代理重置以来目标函数值最小的点。求解器搜索a的最小值优值函数这与代理程序和到现有搜索点的距离有关，以尝试在最小化代理程序和搜索空间之间取得平衡。看到优点函数定义．
求解器将数百或数千个按比例长度的伪随机向量加到当前点上得到采样点．详细信息请参见取样器循环桌子和周围的讨论。这些向量按每个维度的边界进行移位和缩放，并乘以缩放。如果有必要，求解器会改变样本点，使它们保持在边界内。求解器在样本点上计算价值函数，而不是在样本点内的任何点选项。MinSampleDistance以前评估过的点。具有最低价值函数值的点称为自适应点。求解器计算自适应点的目标函数值，并用这个值更新代理。如果自适应点的目标函数值足够低于当前值，则求解器认为搜索成功，并将自适应点设为当前值。否则，求解器认为搜索不成功，不改变在位者。
当满足以下第一个条件时，求解器会改变比例尺:
自上次缩放更改以来，成功进行了三次搜索。在这种情况下，比例尺加倍，最大比例尺长度为
0.8乘以由边界指定的方框的大小。据nvar马克斯(5)不成功的搜索发生在上次缩放更改之后，其中据nvar是问题变量的数量。在本例中，刻度减半，缩小到最小刻度长度1 e-5乘以由边界指定的方框的大小。
这样，随机搜索最终集中在目标函数值较小的在位点附近。然后求解器以几何方式将尺度减小到最小尺度长度。
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使用非旋转的坐标系统。
求解器不计算内部点的价值函数选项。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)将算法引导到远离评估点的点。
优点函数是缩放代理和缩放距离的凸组合。对于一个权重w0 <w< 1时，优点函数为
很大的价值w重视代理值，使搜索最小化代理。一个很小的值w对远离评估点的点给予重视，引导搜索到新的区域。在搜索最小值阶段，权重w正如Regis和Shoemaker所建议的那样，在这四个值之间循环[２]: 0.3、0.5、0.8、0.95。
混合整数surrogateopt算法
混合整数surrogateopt概述
类中指定的部分或全部变量为整数时intcon参数,surrogateopt的某些方面的变化串行代理算法．这个描述主要是关于变化，而不是整个算法。
算法开始
如果有必要,surrogateopt移动的指定边界intcon点，它们是整数。同时,surrogateopt确保所提供的初始点是整数可行的，并且相对于边界可行。然后，该算法生成准随机点，就像在非整数算法中一样，将整数点舍入为整数值。该算法生成的代理与非整数算法完全相同。
最小值整数搜索
算法的这一部分和搜索最少的细节．整数约束的修改出现在该部分中。
树搜索
在对价值函数的数百或数千个值进行采样后，surrogateopt通常选择最小点，并对目标函数求值。然而，在两种情况下，surrogateopt在评估目标之前执行另一个称为树搜索的搜索:
自上次树搜索以来，已经有2N步，称为情况A。
surrogateopt将要执行代理重置，称为情况B。
树搜索的过程如下，类似于intlinprog，详见分支与边界．该算法通过找到一个整数值，然后创建一个新问题，这个问题的上界是高是低，然后用这个新上界来解决子问题。在解决子问题后，算法选择一个不同的整数，上下边界为1。
情况A:使用缩放采样半径作为整体边界，并运行高达1000步的搜索。
情况B:使用原始问题边界作为整体边界，并运行高达5000步的搜索。
在本例中，解决子问题意味着运行fmincon“sqp”算法在连续变量上，从任职者具有指定的整数值开始，从而搜索一个局部最小值的优点函数。
树搜索可能很耗时。所以surrogateopt有一个内部迭代限制，以避免在这一步中花费过多的时间，同时限制案例A和案例B步骤的数量。
在树搜索结束时，算法将树搜索找到的点和之前搜索找到的点中较好的点作为最小值，由价值函数衡量。算法在这一点上对目标函数求值。整数算法的余数与连续算法完全相同。
线性约束处理
当一个问题有线性约束时，算法在每次迭代中修改其搜索过程，使所有点都相对于这些约束和边界可行。在构造和搜索阶段，算法只创建线性可行点的过程类似patternsearch“GSSPositiveBasis2N”调查显示算法。
当问题有整数约束和线性约束时，算法首先创建线性可行点。然后，该算法尝试通过将线性可行点舍入为整数的过程来满足整数约束，该过程使用了一种尝试保持这些点线性可行的启发式方法。当这个过程无法获得足够的可行点来构造代理时，算法调用intlinprog试图找到更多的点在边界，线性约束和整数约束下可行。
surrogateopt非线性约束算法
当问题有非线性约束时，surrogateopt以几种方式修改前面描述的算法。
在初始和每次代理重置之后，算法创建目标和非线性约束函数的代理。随后，算法根据Construct Surrogate阶段是否找到任何可行点而有所不同;找到一个可行点等价于构造代理时现有点是可行的。
在任者不可行——这种情况，称为阶段1，涉及寻找一个可行点。在遇到可行点之前的“求最小值”阶段，
surrogateopt修改价值函数的定义。该算法计算在每个点上违反约束的数量，并且只考虑那些违反约束数量最少的点。在这些点中，算法选择最大约束违反最小的点作为最佳(最低价值函数)点。最好的一点是现任。随后，直到算法遇到一个可行点，它使用这种修改的优点函数。当surrogateopt对一个点进行评估并发现它是可行的，则可行点成为在位点，算法进入阶段2。在任者是可行的-这种情况，称为阶段2，以与标准算法相同的方式进行。该算法忽略了不可行点，计算了优值函数。
算法按照混合整数代理算法修改如下。在每一个据nvar 2 *算法计算目标函数和非线性约束函数的点，surrogateopt调用fmincon函数来最小化代理，服从代理的非线性约束和边界，其中边界按当前缩放因子缩放。(如果现任者不可行，fmincon忽略目标，试图找到一个满足约束条件的点。)如果问题既有整数约束又有非线性约束，则surrogateopt调用树搜索而不是fmincon．
如果问题是一个可行性问题，意味着它没有目标函数，那么surrogateopt在找到可行点后立即执行代理重置。
平行surrogateopt算法
并行surrogateopt算法与串行算法的区别如下:
并行算法维护一个点队列，在其上计算目标函数。这个队列比并行工作的数量大30%。队列大于工作人员的数量，以最小化工作人员空闲的机会，因为没有可用的点来计算。
调度器以FIFO方式从队列中获取点，并在它们空闲时异步地将它们分配给工作者。
当算法在阶段(搜索最小值和构造代理)之间切换时，被评估的现有点仍在服务中，队列中的任何其他点都被刷新(从队列中丢弃)。因此，通常，算法为Construct代理阶段创建的随机点的数量是最多的
选项。MinSurrogatePoints + PoolSize,在那里PoolSize是并行工作者的数量。类似地，在代理重置后，算法仍然具有PoolSize - 1工人们正在评估的适应性点。
请注意
目前，由于并行计时的不可再现性，并行代理优化不一定会给出可再现的结果，这可能导致不同的执行路径。
并行混合整数surrogateopt算法
当并行处理一个混合整数问题时，surrogateopt在主机上执行Tree Search过程，而不是在并行工作线程上。使用最新的代理，surrogateopt在每个工作人员返回一个自适应点后，搜索代理的较小值。
如果目标函数不昂贵(耗时)，那么这个Tree Search过程可能成为主机上的瓶颈。相比之下，如果目标函数是昂贵的，那么树搜索过程只需要整个计算时间的一小部分，并且不是瓶颈。
参考文献
鲍威尔，m.j.d.。径向基函数逼近理论，1990年。在Light, W. A.(编辑)，数值分析进展，第2卷:小波，细分算法和径向基函数。克拉伦登出版社，1992，第105-210页。
瑞吉斯，R. G.和C. A.舒梅克。求解昂贵函数全局优化的随机径向基函数方法。计算机学报，2007,pp. 497-509。
[3]王，Y.， C. A.鞋匠。基于代理模型和灵敏度分析的最小化昂贵黑盒目标函数的一般随机算法框架。v1 arXiv: 1410.6271(2014)。可以在https://arxiv.org/pdf/1410.6271．
[4]古特曼，h.m.。一种全局优化的径向基函数方法。中国机械工程学报(自然科学版)，2001年第4期，第1 - 4页。
另请参阅
相关的话题
外部网站
您也可以从以下列表中选择一个网站: