代理优化算法- MATLAB & Simulink - 卡塔尔世界杯8强比赛直播

代理优化算法

串行`surrogateopt`算法

串行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无缝地管理变量。举个例子，如果你通过初始点，就通过整个集合，包括任何固定变量。

在随后的Construct代理阶段，算法使用选项。MinSurrogatePointsquasirandom点。算法在这些点处对目标函数求值。

该算法通过构造一个代理函数作为目标函数的插值径向基函数(RBF)插入器。RBF插值有几个方便的特性，使它适合构造代理:

RBF插值器是用同样的公式在任意多个维度和任意多个点上定义的。
RBF插值器在计算的点处取规定的值。
计算RBF插值器需要很少的时间。
向现有插值中添加一个点所需的时间相对较少。
构造一个RBF插值器需要求解一个N × N的线性方程组，其中N是代理点的数量。正如鲍威尔[1]表明，该系统对许多rbf具有唯一解。
surrogateopt使用具有线性尾部的立方RBF。这种RBF最大限度地减少了凹凸不平的程度。看到古特曼[4]．

该算法在第一个Construct代理阶段只使用初始点和随机点，在后续的Construct代理阶段只使用随机点。特别地，该算法在代理中不使用搜索最小值阶段的任何自适应点。

搜索最小细节

该求解器通过遵循与局部搜索相关的过程来搜索目标函数的最小值。求解器初始化a规模对于值为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 ）＝ \frac{年代（ x ） - {年代}_{最小值}}{{年代}_{马克斯} - {年代}_{最小值}} ．$

年代（x)是非负的，并且在点处为零x它们在样本点中代理值最小。
按比例缩小的距离。定义x_j，j= 1,…,k随着k评估点。定义d_ij作为到样本点的距离我评估点k．集d_最小值= min (d_ij),d_马克斯= max (d_ij)，其中最小值和最大值被全部取代我和j．按比例缩小的距离D（x)是

$D （ x ）＝ \frac{d_{马克斯} - d （ x ）}{d_{马克斯} - d_{最小值}} ，$

在哪里d（x)为该点的最小距离x到一个评估点。D（x)是非负的，并且在点处为零x最大程度上远离评估点。所以,最小化D（x)将算法引导到距离评估点很远的点。

价值函数是缩放代理和缩放距离的凸组合。对于一个重量w0 <w< 1时，值函数为

$f_{优点} （ x ）＝ w 年代（ x ） + （ 1 - w ） D （ x ）．$

的大值w赋予代理值以重要性，使搜索最小化代理值。的小值w给予离评价点很远的点以重要性，引导搜索到新的区域。在搜索最小值阶段，权重w循环通过这四个值，如Regis和Shoemaker所建议的[２]: 0.3, 0.5, 0.8, 0.95。

混合整数`surrogateopt`概述

类中指定的部分或全部变量为整数时intcon参数,surrogateopt改变了某些方面的串行surrogateopt算法．这个描述主要是关于变化，而不是整个算法。

算法开始

如果有必要,surrogateopt移动指定的边界intcon点，所以它们是整数。同时,surrogateopt确保提供的初始点是整数可行的，并且相对于边界是可行的。然后，该算法像非整数算法中那样生成准随机点，将整数点舍入为整数值。该算法与非整数算法中生成的代理完全相同。

整数最小值搜索

这部分算法和搜索最小细节．整型约束的修改将在该部分中出现。

树搜索

在对价值函数的成百上千个值进行抽样后，surrogateopt通常选择最小值点，并对目标函数求值。然而，在两种情况下，surrogateopt在评估目标之前执行另一个称为树搜索的搜索:

从上次树搜索到现在已经有2N个步骤了，称为案例A。
surrogateopt即将执行一个称为Case B的代理重置。

树搜索的过程如下，类似于intlinprog，详见分支界限法．该算法通过找到一个整数值并创建一个新问题，该问题在这个值上有一个更高或更低的边界，然后用这个新边界解决子问题。在解决了子问题之后，算法选择一个不同的整数作为上界或下界。

情况A:使用缩放的采样半径作为总体边界，并运行多达1000步的搜索。
情况B:使用原始问题边界作为整体边界，并运行高达5000步的搜索。

在本例中，解决子问题意味着运行fmincon“sqp”算法上的连续变量，从任职者开始与指定的整数值，因此搜索一个局部最小值的价值函数。

树搜索可能很耗时。所以surrogateopt有一个内部迭代限制，以避免在这个步骤中花费过多的时间，限制Case A和Case B步骤的数量。

在树搜索结束时，该算法将树搜索找到的点和前面搜索找到的点中最好的一个取最小值，用价值函数来衡量。算法在这一点上计算目标函数。整数算法的余数与连续算法完全相同。

线性约束条件处理

当一个问题有线性约束时，算法修改它的搜索过程，使所有点在每次迭代时都对这些约束和边界保持可行。在构造和搜索阶段，该算法通过一个类似于patternsearch“GSSPositiveBasis2N”调查显示算法。

当问题同时具有整数约束和线性约束时，算法首先创建线性可行点。然后，该算法尝试通过将线性可行点四舍五入到整数的过程来满足整数约束，使用一种尝试保持这些点线性可行的启发式方法。当这个过程无法获得足够的可行点来构建代理时，算法调用intlinprog试着找出更多关于边界，线性约束和整数约束的可行点。

`surrogateopt`具有非线性约束的算法

当问题有非线性约束时，surrogateopt从几个方面修改了前面描述的算法。

在初始和每次代理重置之后，算法创建目标函数和非线性约束函数的代理。随后，根据Construct substitute阶段是否找到任何可行点，算法不同;找到一个可行点等价于在构建代理时，当前点是可行的。

现任者不可行——这种情况称为阶段1，涉及寻找一个可行点。在遇到可行点前的寻极小阶段中，surrogateopt更改价值函数的定义。该算法计算在每个点上被违反的约束的数量，并且只考虑那些被违反约束的数量最少的点。在这些点中，算法选择最大约束违反最小的点作为最佳(最低价值函数)点。最好的一点是在职者。随后，在算法遇到可行点之前，使用这种对价值函数的修改。当surrogateopt对一个点进行评估，发现它是可行的，可行点成为任职者，算法处于阶段2。
在位者是可行的——这种情况被称为阶段2，其处理方式与标准算法相同。该算法忽略不可行点，以计算价值函数。

算法根据混合整数surrogateopt算法进行以下更改。在每一个据nvar 2 *算法计算目标函数和非线性约束函数的点，surrogateopt调用fmincon函数最小化代理，受代理的非线性约束和边界限制，其中边界按当前比例因子缩放。(如果任职者不可行，fmincon忽略目标，试图找到一个满足约束条件的点。)如果问题既有整数约束又有非线性约束，则surrogateopt调用树搜索而不是fmincon．

如果问题是一个可行性问题，意味着它没有目标功能，那么surrogateopt在代理找到可行点后立即执行重置。

平行`surrogateopt`算法

并行surrogateopt算法与串行算法的区别如下:

并行算法维持一个点队列，在此队列上对目标函数求值。这个队列比并行工作的数量大30%，四舍五入。队列大于工作人员的数量，以最小化工作人员因为没有可用的点而处于空闲状态的可能性。
调度程序以先进先出的方式从队列中取点，并在工人空闲时异步地将它们分配给工人。
当算法在阶段之间切换(搜索最小值和构造代理)时，正在被评估的现有点仍处于服务状态，队列中的任何其他点将被刷新(从队列中丢弃)。因此，通常，算法为Construct代理阶段创建的随机点的数量最多选项。MinSurrogatePoints + PoolSize,在那里PoolSize是并行工人的数量。类似地，在代理重置后，算法仍然有PoolSize - 1它的工作人员正在评估的适应性点。

请注意

目前，由于并行计时的不可再现性，并行代理优化不一定能得到可再现的结果，这可能导致不同的执行路径。

并行混合整数`surrogateopt`算法

当并行计算混合整数问题时，surrogateopt在主机上执行树搜索过程，而不是在并行工作程序上。使用最新的替代品，surrogateopt在每个工作者返回自适应点后，搜索代理的较小值。

如果目标函数不昂贵(耗时)，那么这个树搜索过程可能成为主机上的瓶颈。相比之下，如果目标函数是昂贵的，那么树搜索过程只占用整个计算时间的一小部分，并不是一个瓶颈。

参考文献

[1]鲍威尔。1990年的径向基函数逼近理论。在光，W. A.(编辑)，数值分析的进展，卷2:小波，细分算法，和径向基函数。克拉伦登出版社，1992年，第105-210页。

[2]里吉斯，R. G.和C. A.苏梅克。求解昂贵函数全局优化的随机径向基函数方法。计算机学报19,2007，第497-509页。

[3]王，Y.和C. A.苏梅克。基于代理模型和灵敏度分析的最小化昂贵黑盒目标函数的一般随机算法框架。v1 arXiv: 1410.6271(2014)。可以在https://arxiv.org/pdf/1410.6271．

[4]古特曼,小时。全局优化的径向基函数方法。全球优化19,2001年3月，第201-227页。

另请参阅

surrogateopt

外部网站

https://en.wikipedia.org/wiki/Radial_basis_function