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

Шаблоны

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

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

$\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, кроме тех случаев, когда существуют линейные ограничения, и текущая точка около границы ограничений. Для описания пути, которым GSS формирует шаблон с линейными ограничениями, смотрите Колду, Льюис и Торкзон [1]. Алгоритм GSS более эффективен, чем алгоритм GPS, когда у вас есть линейные ограничения. Для примера, показывающего увеличение эффективности, смотрите, Сравнивают КПД Опций Опроса.

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

Ссылки

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

Сетки

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

Генерация набора векторов _{di} путем умножения каждого вектора шаблона _vi скаляром Δ^m. Δ^m называется размером mesh.
Добавление ${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}$
Текущий размер mesh Δ^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, называется ее направлением.

Опрос

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

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

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

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

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

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