Терминология поиска по шаблонам

Шаблоны

Шаблон является набором векторов {_vi}, которые алгоритм поиска шаблонов использует для определения точек поиска при каждой итерации. Набор {_vi} определяется количеством независимых переменных в целевой функции, N, и набором положительного базиса. Два обычно используемых положительных базиса в алгоритмах поиска шаблона являются максимальным базисом с 2N векторами и минимальным базисом с N + 1 векторами.

С GPS набор векторов, которые образуют шаблон, являются векторами фиксированного направления. Для примера, если в задаче оптимизации три независимые переменные, то по умолчанию для 2N положительного базиса состоят из следующих векторов шаблона:

$\begin{matrix} v_{1} = [\begin{matrix} 1 & 0 & 0 \end{matrix}] & v_{2} = [\begin{matrix} 0 & 1 & 0 \end{matrix}] & v_{3} = [\begin{matrix} 0 & 0 & 1 \end{matrix}] \\ v_{4} = [\begin{matrix} - 1 & 0 & 0 \end{matrix}] & v_{5} = [\begin{matrix} 0 & - 1 & 0 \end{matrix}] & v_{6} = [\begin{matrix} 0 & 0 & - 1 \end{matrix}] \end{matrix}$

N + 1 положительный базис состоит из следующих векторов шаблона по умолчанию.

При использовании GSS шаблон идентичен шаблону GPS, за исключением случаев, когда существуют линейные ограничения и текущая точка находится вблизи границы ограничений. Описание способа формирования шаблона с линейными ограничениями смотрите в Kolda, Lewis и Torczon [1]. Алгоритм GSS эффективнее, чем алгоритм GPS, когда у вас есть линейные ограничения. Для примера, показывающего увеличение эффективности, см. «Сравнение эффективности опций опроса».

С помощью MADS набор векторов, которые образуют шаблон, случайным образом выбирается алгоритмом. В зависимости от выбора метода опроса, количество выбранных векторов будет 2N или N + 1. Как и в GPS, 2N векторы состоят из N векторов и их N негативов, в то время как N + 1 векторов состоят из N векторов и один, который является отрицательным из суммы других.

Ссылки

[1] Колда, Тамара Г., Роберт Майкл Льюис и Вирджиния Торчзон. «Генерирующий набор прямого поиска увеличил алгоритм Лагранжа для оптимизации с комбинацией общих и линейных ограничений». Technical Report SAND2006-5315, Sandia National Laboratories, август 2006 года.

Сетки

На каждом шаге, patternsearch ищет в наборе точек, называемом mesh, точку, которая улучшает целевую функцию. patternsearch формирует сетку mesh

Сгенерирование множества векторов {_di} путем умножения каждого вектора шаблона _vi на скаляр^m. Δ^m называется размером сетки.
Добавление ${d_{i}}$ до текущей точки - точка с лучшим значением целевой функции, найденным на предыдущем шаге.

Например, с помощью алгоритма GPS. предположим, что:

Текущая точка [1.6 3.4].
Шаблон состоит из векторов
$\begin{array}{l} v_{1} = [\begin{matrix} 1 & 0 \end{matrix}] \\ v_{2} = [\begin{matrix} 0 & 1 \end{matrix}] \\ v_{3} = [\begin{matrix} - 1 & 0 \end{matrix}] \\ v_{4} = [\begin{matrix} 0 & - 1 \end{matrix}] \end{array}$
Размер текущей сетки^m является 4.

Алгоритм умножает векторы шаблона на 4 и добавляет их к текущей точке, чтобы получить следующий mesh.

[1.6 3.4] + 4*[1 0] = [5.6 3.4] 
[1.6 3.4] + 4*[0 1] = [1.6 7.4] 
[1.6 3.4] + 4*[-1 0] = [-2.4 3.4] 
[1.6 3.4] + 4*[0 -1] = [1.6 -0.6]

Вектор шаблона, который создает точку сетки, называется его направлением.

Опрос

На каждом шаге алгоритм опрашивает точки в текущем mesh путем вычисления их значений целевой функции. Когда опция Complete poll имеет настройку (по умолчанию) Offалгоритм останавливает опрос mesh, как только находит точку, значение целевой функции которой меньше, чем значение текущей точки. Если это происходит, опрос называется успешным, и точка, которую он находит, становится текущей точкой при следующей итерации.

Алгоритм вычисляет только точки mesh и их значения целевой функции до точки, в которой он останавливает опрос. Если алгоритм не может найти точку, которая улучшает целевую функцию, опрос называется неудачным, и текущая точка остается прежней при следующей итерации.

Когда опция Complete poll имеет настройку Onалгоритм вычисляет значения целевой функции во всех точках mesh. Затем алгоритм сравнивает точку сетки с наименьшим значением целевой функции для текущей точки. Если эта точка сетки имеет меньшее значение, чем текущая точка, опрос будет успешным.

Расширение и заключение контрактов

После опроса алгоритм изменяет значение размера сетки^m. Значением по умолчанию является умножение^m по 2 после успешного опроса и по 0,5 после неудачного опроса.

Документация