surrogateopt
算法surrogateopt
算法概述两两相之间的替代优化算法交替。
建设代孕- 创建options.MinSurrogatePoints
该范围内的随机点。评估这些点(昂贵的)目标函数。通过插入一个构建目标函数的替代径向基函数通过这些点。
搜索最小- 在范围内采样几千个随机点搜索最小的目标函数。评估基于在这些点处的替代值和其中(昂贵的)目标函数已经评估它们与点之间的距离优值函数。选择最好的点作为候选,通过评价函数测量。在评估的最佳候选点的目标函数。这一点被称为自适应点。更新使用此值替代并重新搜索。
在构建代孕阶段,算法从一个准随机序列构成的采样点。构建的插补径向基函数使用至少nvars
+ 1个采样点,其中nvars
问题是变量的数目。默认值options.MinSurrogatePoints
是2 * nvars
要么20
,以较大者为准。
该算法将停止为最小相位搜索时,所有搜索点太近(小于选项MinSampleDistance
),可在目标函数预先进行评价分。看到搜索最小详情。这从搜索最小相位开关被称为替代复位。
代孕优化算法描述采用下列定义。
电流 - 当目标函数最近一次评估点。
现任 - 用在所有的最小目标函数值,因为最近的替代重置评估点。
最好的 - 用在所有的最小目标函数值为止评估点。
初 - 中的点,如果有的话,你传递给求解器的InitialPoints
选项。
随机点 - 点在构建代孕阶段,其中解算器计算的目标函数。一般来说,求解器从准随机序列,缩放和偏移保持在界限内采取这些点。甲准随机序列类似于伪随机序列如兰特
回报,但更均匀分布的。看到https://en.wikipedia.org/wiki/Low-discrepancy_sequence。然而,当变量的数目高于500中,解算器从一个拉丁超立方序列需要点。看到https://en.wikipedia.org/wiki/Latin_hypercube_sampling。
自适应点 - 在搜索最低阶段,其中解算器计算的目标函数积分。
优异功能 - 见评价函数定义。
评价分数 - 在其目标函数值是已知的所有的点。这些点包括初始点,构建代孕点,搜索在该解算器计算的目标函数最小的点。
采样点。伪随机点中求解,在搜索最小相位过程中评估价值函数。在该解算器计算的目标函数,如所述,除了这些点不是点搜索最小详情。
为了构建替代,该算法选择的范围之内准随机点。如果您通过一组初始点在InitialPoints
选项,该算法使用这些点和新的准随机点(如有必要),以达到共options.MinSurrogatePoints
。
如果一些上界和下界是相等的,surrogateopt
构建替代之前将删除问题的“固定”的变量。surrogateopt
管理无缝的变量。因此,举例来说,如果你通过初始点,通过全套,包括任何固定的变量。
在随后的构建代孕阶段,该算法使用options.MinSurrogatePoints
准随机点。该算法计算在这些点的目标函数。
该算法通过使用构建的替代作为目标函数的内插径向基函数(RBF)内插器。RBF插了多种方便的特性,使其适合于构建代理:
该算法仅使用初始点,并在第一构建代孕相位随机点,并且在随后的构建代孕相用途仅随机点。特别是,算法不从这个替代的搜索最小相位使用任何自适应点。
最少的目标函数的求解器通过搜索以下是相关的本地搜索的过程。求解器初始化规模与值0.2搜索。规模等的搜索区域的半径或在模式搜索网格尺寸。求解器从现任点,这是自上次代理复位的最小目标函数值的点开始。最少一的求解器搜索评价函数这涉及到两个代理,并从现有的搜索点的距离,要尽量减少平衡替代和搜索空间。看到评价函数定义。
求解器增加了数百或数千伪随机向量的缩放与长度现任点以获得样本点。这些载体具有正态分布,由刻度偏移,并通过在每一维的边界调整大小,并且相乘。如果有必要,解算器改变采样点,让他们留在范围内。求解器在采样点评估价值函数,而不是在任意点options.MinSampleDistance
的先前估计的点。具有最低评价函数值的点被称为自适应点。求解器计算在自适应点的目标函数值,并用这个值更新替代。如果在自适应点上的目标函数值充分低于现任值,则求解器认为搜索成功,并且设置自适应点作为现任。否则,求解认为搜索失败,并且不改变义不容辞的责任。
求解器变化的时候,第一这些条件得到满足的规模:
自上次规模变化三个成功的搜索发生。在这种情况下,标度加倍,直至最大长度尺度0.8
倍框的大小由指定的范围。
最大(5,NVAR)
自上规模的变化,其中不成功的搜索,会出现NVAR
问题是变量的数目。在这种情况下,标度被减半,下降到最小规模长度1E-5
倍框的大小由指定的范围。
通过这种方式,随机搜索,最终精矿附近,有一个小的目标函数值现任点。然后求解器几何降低朝向最小刻度长度规模。
求解器不评估内的点的评价函数options.MinSampleDistance
一个评价点的(见定义为代孕优化)。解算器从要搜索的最小相到一个构建体,代孕相开关(换言之,执行的替代复位)当所有的采样点都是内MinSampleDistance
的评价分数。一般来说,解算器减少了规模后,使所有样本点都紧紧围绕现任聚集发生此复位。
该评价函数F值得(X)是两项的加权组合:
鳞甲替代。限定小号分作为采样点中最小的替代值,小号最大作为最大和小号(X)作为在该点的替代值X。然后缩放后的替代品小号(X)是
小号(X)为负,并且是零的点处X有采样点之间最小的替代价值。
缩放距离。限定XĴ,Ĵ= 1,...,ķ作为ķ评价分数。DefiinedIJ从采样点的距离一世以评估点ķ。组d分=分钟(dIJ)和d最大= MAX(dIJ),其中最小值和最大值接管所有一世和Ĵ。缩放距离d(X)是
哪里d(X)是该点的最小距离X到一个评估点。d(X)为负,并且是零的点处X这是从评价分数最大限度为止。因此,最大限度地减少d(X)导致的算法是远离评价分数点。
评价函数是经缩放的替代和缩放的距离的凸组合。对于重w ^其中0 <w ^<1,评价函数是
的较大值w ^给人重视替代价值,从而导致搜索,以尽量减少替代。小值的w ^给重要性是远离评价分数分,带领搜索到新的地区。在搜索最小相位,重量w ^通过这四个值的周期,如由吉斯和舒梅克建议[2]:0.3,0.5,0.8,和0.95。
surrogateopt
算法surrogateopt
概观当部分或全部变量都是整数,在指定的INTCON
的说法,surrogateopt
改变的某些方面串行surrogateopt算法。这说明主要是关于的变化,而不是整个算法。
如果有必要,surrogateopt
移动用于指定边界INTCON
点,使他们都是整数。也,surrogateopt
确保了提供的初始点是相对于边界整数可行和不可行的。然后,该算法生成准随机点作为在非整数算法,舍入整数指向整数值。该算法生成一个替代完全一样在非整数算法。
最少的搜索进行使用相同的评价函数和权重之前的序列。不同的是,surrogateopt
使用采样随机点来定位的最小的评价函数中的三种不同的方法。surrogateopt
选择采样器在根据下表进行权重相关联的周期。
采样周期
重量 | 0.3 | 0.5 | 0.8 | 0.95 |
取样 | 随机 | 随机 | OrthoMADS | 全球定位系统 |
规模 - 围绕现任缩放区域内的每个采样样本点。整数点具有其规模开始于边界的宽度的1/2倍,并调整完全一样的非整数分,不同之处在于宽度增大到1,如果它会永远低于1.连续点的规模开发正是因为在非整数算法。
随机 - 采样随机产生整数点均匀地分中,在现任居中。采样器根据与从现任均值为零的高斯生成连续点。整数点的样品的宽度由刻度相乘,由于是连续点的标准偏差。
OrthoMADS - 采样器在随机选择均匀的正交坐标系。然后该算法围绕现任创建采样点,在坐标系中添加和减去当前刻度倍每个单位向量。该算法轮整数关口。这创建2N个样本(除非一些整数点被四舍五入到现任),其中N是问题的维数。OrthoMADS也使用两个更多的点比2N固定方向,一个在[+ 1,+ 1,...,+ 1],而另一个在[-1,-1,...,-1],共计2N +的2分。然后采样反复减半2N + 2个步骤,创建一个越来越细的集合围绕现任点,而舍入整数点。这一过程结束时要么有足够的样本或四舍五入的原因没有新的样本。
GPS - 采样器等OrthoMADS,除了代替选择随机组方向,GPS使用非旋转坐标系。
采样的评价函数的值数百或数千之后,surrogateopt
通常选择最低点,并评估目标函数。然而,在两种情况下,surrogateopt
执行另一个搜索称为树搜索,估计所述目标之前:
已经有自上次树搜索2N步骤,称为案例A.
surrogateopt
即将执行的替代复位,称为情况B.
树搜索如下进行,类似于在过程intlinprog
,如在分枝限界(优化工具箱)。该算法通过寻找一个整数值,并创建一个含有束缚于该值是由一个较高或较低的一个新的问题,解决这一新的约束子问题做一棵树。解决子问题之后,算法选择一个不同的整数将被通过一个高于或低于界。
方案A:使用缩放采样半径为总边界,以及高达1000步搜索的运行。
案例B:使用原来的问题范围的整体范围,以及可容纳5000步搜索的运行。
在这种情况下,解决运行中的子问题的手段fmincon
“小数量议定书”
算法在连续的变量,从与指定的整数值现任开始,所以搜索局部最小值的评价函数的。
树搜索可能是费时。所以surrogateopt
有一个内部的时间限制,以避免过多的时间在该步骤中,限制的情况A和情况B的步骤两者的数目。
在树的搜索结束,算法采用该点的更好按树搜索结果和点发现由前述搜索最小,如由评价函数来测量。该算法在这一点上计算目标函数。的整数算法的其余部分是完全一样的连续算法。
surrogateopt
算法非线性约束当问题具有非线性的限制,surrogateopt
修改在几个方面先前描述的算法。
最初和每个代理复位之后,算法创建的目标和非线性约束函数替代物。随后,这取决于构建体代孕阶段是否发现任何可行点的算法不同;找到一个可行的点相当于现任点替代被构造时是可行的。
现任是不可行的 - 这种情况下,所谓的第一阶段,涉及的可行点的搜索。在遇到一个可行点之前,搜索最小相位,surrogateopt
改变评价函数的定义。该算法会统计每个点违反了人数的限制,并认为只有最少的违反约束那些点。在这些点,算法选择,最大约束违反为最佳(最低价值函数)最小点的点。这个最佳点是义不容辞的责任。随后,直到算法遇到可行点时,它使用的评价函数的本变形例。什么时候surrogateopt
计算一个点,并发现它是可行的,可行的点成为义不容辞和算法是在第2阶段。
现任是可行的 - 该情况下,所谓的第2阶段,以同样的方式作为标准算法进行。该算法忽略不可行点计算的优点功能的目的。
根据算法进行混合整数surrogateopt算法有以下改动。之后每2 * nvars
点,其中算法评估的客观和非线性约束函数,surrogateopt
调用fmincon
函数最小化的替代,受替代非线性约束和边界内,其中的边界由当前比例因子缩放。(如果现任是不可行的,fmincon
忽略了客观,试图找到一个点满足约束条件的。)如果问题具有整数和非线性约束条件,然后surrogateopt
电话树搜索代替fmincon
。
如果问题是可行性问题,这意味着它没有目标函数,然后surrogateopt
执行的替代复位它找到一个可行的点之后。
surrogateopt
算法并行surrogateopt
算法从串行算法不同之处如下:
并行算法保持在其上,以评估目标函数的点的队列。这个队列的长度大于平行工人数大30%,向上舍入。队列比工人的数量,工人处于闲置状态,因为没有点可用来评估,以尽量减少的机会较大。
调度从一个FIFO时尚和为它们分配到工人的队列中取出点,因为它们变得空闲,异步。
当算法相之间切换(搜索最小和构建代用),被评估的现有点保持在服务,并且在队列中的任何其它点被刷新(从队列丢弃)。所以,一般的,随机点的数量,该算法创建的构建代孕阶段最多options.MinSurrogatePoints + PoolSize
,其中PoolSize
平行工人的数量。同样,代孕复位后,该算法仍然有PoolSize - 1
自适应点,它的工人正在评估。
目前,平行替代优化不一定由于并行定时的nonreproducibility,这会导致不同的执行路径得到可重复的结果。
surrogateopt
算法当并行地对混合整数问题运行,surrogateopt
执行主机上的树搜索程序,而不是并行的工人。使用最新的替代,surrogateopt
搜索替代的具有自适应点每个工人返回后一个较小的值。
如果目标函数不贵(耗时),那么这棵树的搜索程序可以在主机上的瓶颈。相反,如果目标函数是昂贵的,那么树搜索过程需要的全部计算时间的一小部分,而不是瓶颈。
[1]鲍威尔,M. J. D.径向基函数逼近1990年的理论。在轻,W. A.(编辑),进展数值分析,第2卷:小波,细分算法和径向基函数。克拉伦登出版社,1992,第105-210。
[2]吉斯,R. G.,和C. A.制鞋。昂贵的函数的全局优化的随机径向基函数方法。INFORMS J.计算19,2007年,第497-509。
[3]王,Y.,和C. A.制鞋。一种通用随机算法框架最大限度地减少昂贵的黑盒子目标函数基于代理模型和敏感性分析。的arXiv:1410.6271v1(2014)。可在https://arxiv.org/pdf/1410.6271。
[4]古特曼,H.-M.用于全局优化的径向基函数方法。全球性优化19,2001年3月,第201-227的。