模式搜索术语
模式
一个模式是向量的集合{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一个是向量,另一个是其他向量和的负数。
参考文献
[1]科尔达,塔玛拉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)
生成网格点的模式向量称为网格向量方向.
轮询
在每一步中,算法通过计算当前网格中的点的目标函数值轮询它们。当完成调查选项具有(默认)设置从
时,一旦发现目标函数值小于当前点的点,算法立即停止轮询网格点。如果发生这种情况,将调用轮询成功的它找到的点就会成为下一次迭代的当前点。
该算法只计算网格点及其目标函数值,直到它停止轮询。如果算法无法找到一个改善目标函数的点,就会调用轮询不成功的当前点在下一次迭代中保持不变。
当完成调查选项的设置在
时,算法计算各网格点的目标函数值。该算法将目标函数值最小的网格点与当前点进行比较。如果该网格点的值小于当前点,则轮询成功。
扩张与收缩
轮询之后,算法会改变网格大小Δ的值米.默认值是Δ的乘积米投票成功后增加2,投票失败后增加0.5。