Массив - это набор векторов {vi}, которые алгоритм поиска массива использует для определения точек для поиска в каждой итерации. Множество {vi} определяется количеством независимых переменных в целевой функции, N, и положительным набором базиса. Два обычно используемых положительных набора базиса в алгоритмах поиска шаблона являются максимальным базисом, с 2N векторами, и минимальным базисом, с N + 1 векторами.
При использовании GPS совокупность векторов, формирующих шаблон, представляет собой векторы с фиксированным направлением. Например, если в задаче оптимизации есть три независимые переменные, то значение по умолчанию для 2N положительного базиса состоит из следующих векторов массива:
Положительный базис N + 1 состоит из следующих векторов шаблона по умолчанию.
В GSS шаблон идентичен шаблону GPS, за исключением случаев, когда существуют линейные ограничения и текущая точка находится вблизи границы ограничения. Описание способа формирования GSS-массива с линейными ограничениями см. в разделе Кольда, Льюис и Торкзон [1]. Алгоритм GSS эффективнее алгоритма GPS при наличии линейных ограничений. Пример повышения эффективности см. в разделе Сравнение эффективности параметров опроса.
При использовании MADS набор векторов, образующих шаблон, выбирается алгоритмом случайным образом. В зависимости от выбора метода опроса число выбранных векторов будет равно 2N или N + 1. Как и в GPS, 2N векторы состоят из N векторов и их N негативов, в то время как N + 1 векторы состоят из N векторов и один из них отрицательный из суммы других.
[1] Кольда, Тамара Г., Роберт Майкл Льюис и Вирджиния Торкзон. «Генерирующий набор прямого поиска увеличил алгоритм Лагранжа для оптимизации с комбинацией общих и линейных ограничений». Технический отчет SAND2006-5315, национальные лаборатории Сандии, август 2006 года.
На каждом шаге patternsearch ищет в наборе точек, называемом сеткой, точку, которая улучшает целевую функцию. patternsearch формирует сетку по
Формирование набора векторов {di} путем умножения каждого вектора шаблона vi на скалярный Δm. Δm называется размером сетки.
Добавление к текущей точке - точке с наилучшим значением целевой функции, найденной на предыдущем шаге.
Например, с помощью алгоритма GPS. предположим, что:
Текущая точка - [1.6 3.4].
Шаблон состоит из векторов
Текущий размер ячейки Δm равен 4.
Алгоритм умножает векторы шаблона на 4 и добавляет их в текущую точку для получения следующей сетки.
[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]
Вектор массива, который создает точку сети, называется ее направлением.
На каждом шаге алгоритм опрашивает точки в текущей сетке, вычисляя их значения целевой функции. Если параметр «Завершить опрос» имеет значение (по умолчанию) Offалгоритм прекращает опрос точек сети, как только он находит точку, значение целевой функции которой меньше значения текущей точки. Если это происходит, опрос называется успешным, и точка, которую он находит, становится текущей точкой на следующей итерации.
Алгоритм вычисляет только точки сети и их значения целевой функции вплоть до точки, в которой он останавливает опрос. Если алгоритму не удается найти точку, которая улучшает целевую функцию, опрос называется неуспешным, и текущая точка остается прежней при следующей итерации.
Если параметр «Завершить опрос» имеет значение Onалгоритм вычисляет значения целевой функции во всех точках ячеистой сети. Затем алгоритм сравнивает точку сетки с наименьшим значением целевой функции с текущей точкой. Если эта точка сети имеет меньшее значение, чем текущая точка, опрос будет успешным.
После опроса алгоритм изменяет значение размера Δm ячейки. По умолчанию Δm умножается на 2 после успешного опроса и на 0,5 после неудачного опроса.