模式搜索术语
模式
一个模式是向量的集合{v我},模式搜索算法使用它来确定在每次迭代中搜索哪些点。集合{v我}由目标函数中自变量的个数定义,N,正基集。模式搜索算法中常用的两个正基集是最大基,其中2N向量和最小基N+ 1的向量。
在GPS中,形成模式的向量集合是固定方向的向量。例如,如果优化问题中有三个自变量,默认为2N正基由以下模式向量组成:
一个N+1正基由以下默认模式向量组成。
使用GSS时,模式与GPS模式相同,除非存在线性约束且当前点靠近约束边界。有关GSS如何用线性约束形成模式的描述,请参阅Kolda、Lewis和Torczon[1].当有线性约束时,GSS算法比GPS算法更有效。有关显示效率增益的例子,请参见比较投票选项的效率.
在MADS中,形成模式的向量集合由算法随机选择。根据投票方法的选择,选择的向量的数量将为2N或N+ 1。在GPS中,2N向量由N向量和它们的N底片,N+1个向量组成N一个是其他向量的和的负数。
参考文献
科尔达,塔玛拉·G.,罗伯特·迈克尔·刘易斯,弗吉尼亚·托森。一种集合了一般约束和线性约束的发电机组直接搜索增强拉格朗日优化算法技术报告SAND2006-5315,桑迪亚国家实验室,2006年8月。
网格
在每一步,patternsearch
搜索一组点,称为a网,对于一个改进目标函数的点。patternsearch
形成网格
生成一组向量{d我},通过乘以每个模式向量v我一个标量Δ米.Δ米叫做筛孔尺寸.
添加 到当前点-上一步找到的最佳目标函数值的点。
例如,使用GPS算法。假设:
目前的情况是
(1.6 - 3.4)
.图案由向量组成
当前网目尺寸Δ米是
4
.
算法将模式向量乘以4
并将它们添加到当前点,得到下面的网格。
(1.6 - 3.4) + 4 * 1 [0] = [5.6 - 3.4] [1.6 - 3.4] + 4 * 1 [0] = [1.6 - 7.4] [1.6 - 3.4] + 4 * 1 [0] = [-2.4 - 3.4] [1.6 - 3.4] + 4 * 1 [0] = (1.6 - -0.6)
生成网格点的模式向量称为its方向.
轮询
在每一步中,算法通过计算当前网格中的点的目标函数值轮询它们。当完成调查选项具有(默认)设置从
,一旦发现目标函数值小于当前点的目标函数值的点,算法就停止轮询网格点。如果发生这种情况,将调用轮询成功的它找到的点成为下次迭代的当前点。
该算法只计算网格点及其目标函数值,直到停止轮询为止。如果算法不能找到一个改进目标函数的点,则调用轮询不成功的在下一次迭代中,当前点保持不变。
当完成调查选项的设置在
,算法计算所有网格点的目标函数值。然后将目标函数值最小的网格点与当前点进行比较。如果网格点的值小于当前点,则轮询成功。
扩张和收缩
轮询后,算法改变网格大小的值Δ米.默认值是乘以Δ米投票成功后加2,投票失败后加0.5。