patternsearch находит последовательность точек, x0, x1, x2,..., этот подход оптимальный момент. Значение целевой функции либо уменьшается, либо остается неизменным от каждой точки последовательности к следующей. В этом разделе объясняется, как поиск шаблона работает для функции, описанной в разделе Оптимизация с использованием алгоритма GPS.
Чтобы упростить объяснение, в этом разделе описывается, как работает обобщенный поиск шаблона (GPS), используя максимальную положительную основу 2N по умолчанию, с ScaleMesh параметр имеет значение false.
В этом разделе не показано, как patternsearch алгоритм работает с границами или линейными ограничениями. Для границ и линейных ограничений patternsearch изменяет точки опроса, чтобы они были выполнимы при каждой итерации, что означает удовлетворение всех границ и линейных ограничений.
Этот раздел не охватывает нелинейные ограничения. Чтобы понять, как patternsearch работает с нелинейными ограничениями, см. раздел Алгоритм решателя нелинейных ограничений.
Поиск шаблона начинается в начальной точке x0 которые вы предоставляете. В этом примере: x0 = [2.1 1.7].
При первой итерации размер сетки равен 1, и алгоритм GPS добавляет векторы шаблона к начальной точке. x0 = [2.1 1.7] для вычисления следующих точек сетки:
[1 0] + x0 = [3.1 1.7] [0 1] + x0 = [2.1 2.7] [-1 0] + x0 = [1.1 1.7] [0 -1] + x0 = [2.1 0.7]
Алгоритм вычисляет целевую функцию в узлах сети в порядке, показанном выше. На следующем рисунке показано значение ps_example в начальной точке и точках сетки.
Алгоритм опрашивает точки сетки путем вычисления их значений целевой функции до тех пор, пока не найдет ту, значение которой меньше 4,6347, значение при x0. В этом случае первым таким моментом, который он находит, является [1.1 1.7], при котором значение целевой функции равно 4.5146так что опрос в итерации 1 успешен. Алгоритм устанавливает следующую точку в последовательности равной
x1 = [1.1 1.7]
Примечание
По умолчанию алгоритм поиска шаблона GPS останавливает текущую итерацию, как только она находит точку сети, значение пригодности которой меньше значения текущей точки. Следовательно, алгоритм может не опрашивать все точки сети. Можно сделать так, чтобы алгоритм опрашивал все точки сетки, установив UseCompletePoll опция для true.
После успешного опроса алгоритм умножает текущий размер сетки на 2, значение по умолчанию MeshExpansionFactor варианты. Поскольку начальный размер сетки равен 1, во второй итерации размер сетки равен 2. Сетка в итерации 2 содержит следующие точки:
2*[1 0] + x1 = [3.1 1.7] 2*[0 1] + x1 = [1.1 3.7] 2*[-1 0] + x1 = [-0.9 1.7] 2*[0 -1] + x1 = [1.1 -0.3]
На следующем рисунке показана точка x1 и точки сетки вместе с соответствующими значениями ps_example.
Алгоритм опрашивает точки сетки до тех пор, пока не найдет точки, значение которых меньше 4,5146, значение при x1. Первый такой момент он находит [-0.9 1.7], при котором значение целевой функции равно 3.25, так что опрос на итерации 2 снова успешен. Алгоритм устанавливает вторую точку в последовательности равной
x2 = [-0.9 1.7]
Поскольку опрос успешен, алгоритм умножает текущий размер ячейки на 2, чтобы получить размер ячейки 4 в третьей итерации.
По четвертой итерации текущая точка равна
x3 = [-4.9 1.7]
и размер сетки равен 8, поэтому сетка состоит из точек
8*[1 0] + x3 = [3.1 1.7] 8*[0 1] + x3 = [-4.9 9.7] 8*[-1 0] + x3 = [-12.9 1.7] 8*[0 -1] + x3 = [-4.9 -1.3]
На следующем рисунке показаны точки сетки и их целевые значения функций.
В этой итерации ни одна из точек сетки не имеет меньшего значения целевой функции, чем значение в x3, так что опрос неудачный. В этом случае алгоритм не изменяет текущую точку при следующей итерации. То есть
x4 = x3;
При следующей итерации алгоритм умножает текущий размер сетки на 0,5, значение по умолчанию MeshContractionFactor , так что размер сетки при следующей итерации равен 4. Затем алгоритм опрашивает с меньшим размером сетки.
Установка PollMethod опция для 'MADSPositiveBasis2N' или 'MADSPositiveBasisNp1' причины patternsearch использовать и другой тип опроса, и реагировать на опрос иначе, чем другие алгоритмы опроса.
Опрос MADS использует вновь созданные псевдослучайные векторы сетки на каждой итерации. Векторы являются произвольно перетасованными компонентами из столбцов случайной нижнетреугольной матрицы. Компоненты матрицы имеют целочисленные размеры до . В опросе векторы сетки умножаются на размер сетки, так что точки опроса могут быть до от текущей точки.
Неудачные опросы сокращают сетку с коэффициентом 4, игнорируя MeshContractionFactor вариант. Аналогично, успешные опросы расширяют сетку в раз 4, игнорируя MeshExpansionFactor вариант. Максимальный размер сетки: 1, несмотря на любую настройку MaxMeshSize вариант.
Кроме того, когда есть успешный опрос, patternsearch начинается с успешной точки и снова опрашивает. В этом дополнительном опросе используются те же векторы сетки, увеличенные в раз 4 оставаясь ниже размера 1. Дополнительный опрос снова выглядит по тем же направлениям, которые были только что успешными.
Можно отобразить результаты поиска массива в каждой итерации, задав Display опция для 'iter'. Это позволяет оценить ход поиска массива и внести изменения в options при необходимости.
При этом параметре поиск массива отображает информацию о каждой итерации в командной строке. Первые четыре итерации:
Iter f-count f(x) MeshSize Method
0 1 4.63474 1
1 4 4.51464 2 Successful Poll
2 7 3.25 4 Successful Poll
3 10 -0.264905 8 Successful Poll
4 14 -0.264905 4 Refine MeshВход Successful Poll ниже Method указывает, что текущая итерация прошла успешно. Например, опрос в итерации 2 выполнен успешно. В результате значение целевой функции точки, вычисленной в итерации 2, отображается ниже. f(x), меньше значения в итерации 1.
В итерации 4 запись Refine Mesh сообщает, что опрос не удался. В результате значение функции в итерации 4 остается неизменным по сравнению с итерацией 3.
По умолчанию при поиске массива размер сетки удваивается после каждого успешного опроса и наполовину после каждого неудачного опроса.
Поиск массива выполняет 60 итераций перед остановкой. На следующем графике показаны точки в последовательности, вычисленной в первых 13 итерациях поиска массива.
Числа ниже точек указывают первую итерацию, при которой алгоритм находит точку. График показывает только числа итераций, соответствующие успешным опросам, потому что лучшая точка не меняется после неудачного опроса. Например, наилучшая точка в итерациях 4 и 5 такая же, как в итерации 3.
При каждой итерации поиск массива опрашивает точки в текущей сетке - то есть вычисляет целевую функцию в точках сетки, чтобы увидеть, есть ли та, значение функции которой меньше значения функции в текущей точке. Пример опроса: как работает поиск шаблона. Массив, определяющий сетку, можно задать с помощью команды PollMethod вариант. Шаблон по умолчанию, 'GPSPositiveBasis2N', состоит из следующих направлений 2N, где N - количество независимых переменных для целевой функции.
[1 0 0...0]
[0 1 0...0]
...
[0 0 0...1]
[–1 0 0...0]
[0 –1 0...0]
[0 0 0...–1].
Например, если целевая функция имеет три независимые переменные, GPS Positive basis 2N, состоит из следующих шести векторов.
[1 0 0]
[0 1 0]
[0 0 1]
[–1 0 0]
[0 –1 0]
[0 0 –1].
Кроме того, можно задать PollMethod опция для 'GPSPositiveBasisNp1', рисунок, состоящий из следующих направлений N + 1.
[1 0 0...0]
[0 1 0...0]
...
[0 0 0...1]
[–1 –1 –1...–1].
Например, если целевая функция имеет три независимые переменные, 'GPSPositiveBasisNp1' состоит из следующих четырех векторов.
[1 0 0]
[0 1 0]
[0 0 1]
[–1 –1 –1].
Поиск шаблона иногда выполняется быстрее с помощью 'GPSPositiveBasisNp1' вместо 'GPSPositiveBasis2N' в качестве PollMethod, поскольку алгоритм ищет меньшее количество точек в каждой итерации. Хотя это не рассматривается в этом примере, то же самое верно при использовании 'MADSPositiveBasisNp1' над 'MADSPositiveBasis2N', и аналогично для GSS. Например, при выполнении поиска массива в примере с линейным ограничением в разделе Минимизация с ограничением с помощью поиска массива и задания «Оптимизировать оперативный редактор» алгоритм выполняет 1588 оценок функций с помощью 'GPSPositiveBasis2N', значение по умолчанию PollMethod, но только 877 оценок функций с использованием 'GPSPositiveBasisNp1'. Дополнительные сведения см. в разделе Сравнение эффективности параметров опроса.
Однако, если целевая функция имеет много локальных минимумов, использование 'GPSPositiveBasis2N' в качестве PollMethod может избежать нахождения локального минимума, который не является глобальным минимумом, потому что поиск исследует больше точек вокруг текущей точки в каждой итерации.
По умолчанию, если поиск массива находит точку сетки, которая улучшает значение целевой функции, он останавливает опрос и устанавливает эту точку в качестве текущей точки для следующей итерации. В этом случае некоторые точки сети могут не быть опрошены. Некоторые из этих незаполненных точек могут иметь значение целевой функции, которое даже ниже первого, найденного при поиске шаблона.
Для задач, в которых существует несколько локальных минимумов, иногда предпочтительнее сделать так, чтобы поиск шаблона опрашивал все точки сетки в каждой итерации и выбирал точку с наилучшим значением целевой функции. Это позволяет при поиске массива исследовать больше точек в каждой итерации и тем самым потенциально избежать локального минимума, который не является глобальным минимумом. Пусть поиск массива опрашивает всю сетку, задав UseCompletePoll опция для true.
Алгоритм останавливается при возникновении любого из следующих условий:
Размер сетки меньше MeshTolerance вариант.
Количество итераций, выполняемых алгоритмом, достигает значения MaxIterations вариант.
Общее число оценок целевой функции, выполненных алгоритмом, достигает значения MaxFunctionEvaluations вариант.
Время, в секундах, выполнения алгоритма до достижения значения MaxTime вариант.
После успешного опроса расстояние между точкой, найденной в двух предыдущих итерациях, и размером сетки меньше, чем StepTolerance вариант.
После успешного опроса изменение целевой функции в двух предыдущих итерациях меньше, чем FunctionTolerance и размер сетки меньше, чем StepTolerance вариант.
ConstraintTolerance не используется в качестве критерия остановки. Определяет выполнимость в отношении нелинейных ограничений.
Алгоритм MADS использует дополнительный параметр, называемый параметром опроса Δp, в критерие остановки размера сетки:
опрос,
где Δm - размер сетки. Критерий остановки MADS:
Δp ≤ MeshTolerance.
Алгоритм поиска шаблона надежен по отношению к сбоям целевой функции. Это означает, что patternsearch допускает оценки функций, приводящие к NaN, Infили комплексные значения. Когда целевая функция в начальной точке x0 - действительное конечное значение, patternsearch обрабатывает ошибки точек опроса, как если бы значения целевой функции были большими, и игнорирует их.
Например, если все точки в опросе вычисляются как NaN, patternsearch считает опрос неуспешным, сжимает сетку и повторно оценивает. Если даже одна точка в опросе имеет меньшее значение, чем все еще видимые, patternsearch считает опрос успешным и расширяет сетку.