patternsearch находит последовательность точек, x0, x1, x2,..., что приближается к оптимальной точке. Значение целевой функции либо уменьшается, либо остается неизменным от каждой точки в последовательности до следующей. В этом разделе объясняется, как работает поиск шаблона для функции, описанной в Optimize Using the GPS Algorithm.
Чтобы упростить объяснение, в этом разделе описывается, как работает обобщенный поиск шаблона (GPS), используя максимальный положительный базис 2N по умолчанию, с ScaleMesh значение опции установлено в false.
В этом разделе не показано, как patternsearch алгоритм работает с границами или линейными ограничениями. Для границ и линейных ограничений, patternsearch изменяет точки опроса, чтобы быть допустимыми при каждой итерации, что означает удовлетворение всем границам и линейным ограничениям.
Этот раздел не охватывает нелинейные ограничения. Чтобы понять, как patternsearch работает с нелинейными ограничениями, см. «Алгоритм решателя ограничений».
Поиск шаблона начинается в начальной точке x0 что вы предоставляете. В этом примере x0 = [2.1 1.7].
При первой итерации размер сетки равен 1, и алгоритм GPS добавляет векторы шаблона к начальной точке x0 = [2.1 1.7] для вычисления следующих точек mesh:
[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]
Алгоритм вычисляет целевую функцию в точках mesh в порядке, показанном выше. Следующий рисунок показывает значение ps_example в начальной точке и точках mesh.
Алгоритм опрашивает mesh, вычисляя их значения целевой функции, пока не найдет значение, меньше 4,6347, значение при x0. В этом случае первая подобная точка, которую он находит [1.1 1.7], при котором значение целевой функции 4.5146, поэтому опрос на итерации 1 успешен. Алгоритм устанавливает следующую точку в последовательности равной
x1 = [1.1 1.7]
Примечание
По умолчанию алгоритм поиска шаблона GPS останавливает текущую итерацию, как только находит точку сетки, значение соответствия которой меньше, чем значение текущей точки. Следовательно, алгоритм может не опрашивать все сетчатый. Можно сделать алгоритм опрос всех сетчатый путем установки UseCompletePoll опция для true.
После успешного опроса алгоритм умножает текущий размер сетки на 2, значение по умолчанию MeshExpansionFactor опции. Поскольку начальный размер сетки равен 1, во второй итерации размер сетки равен 2. Mesh в итерации 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 и mesh точек вместе с соответствующими значениями ps_example.
Алгоритм опрашивает mesh, пока не найдет точку, значение которой меньше 4,5146, значение в x1. Первая такая точка, который он находит [-0.9 1.7], при котором значение целевой функции 3.25, поэтому опрос на итерации 2 снова успешен. Алгоритм устанавливает вторую точку в последовательности равной
x2 = [-0.9 1.7]
Поскольку опрос успешен, алгоритм умножает текущий размер сетки на 2, чтобы получить размер сетки 4 в третьей итерации.
К четвертой итерации текущая точка является
x3 = [-4.9 1.7]
и размер сетки 8, поэтому mesh состоит из точек
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]
Следующий рисунок показывает точки mesh и их значения целевой функции.
На этой итерации ни одна из точек mesh не имеет меньшего значения целевой функции, чем значение в x3, так что опрос неудачен. В этом случае алгоритм не изменяет текущую точку при следующей итерации. То есть,
x4 = x3;
При следующей итерации алгоритм умножает текущий размер сетки на 0,5, значение по умолчанию MeshContractionFactor опция, так что размер сетки при следующей итерации равен 4. Затем алгоритм опрашивает с меньшим размером сетки.
Установка PollMethod опция для 'MADSPositiveBasis2N' или 'MADSPositiveBasisNp1' причины patternsearch использовать как другой тип опроса, так и реагировать на опрос по-другому, чем другие алгоритмы опроса.
Опрос MADS использует вновь сгенерированные векторы псевдослучайной сетки при каждой итерации. Векторы являются случайным образом перетасованными компонентами из столбцов случайной нижней треугольной матрицы. Компоненты матрицы имеют целочисленные размеры до 1/. В опросе векторы сетки умножаются на размер сетки, поэтому точки опроса могут быть до от текущей точки.
Неудачные опросы сокращают mesh в множитель 4, игнорируя MeshContractionFactor опция. Точно так же успешные опросы расширяют mesh в множитель 4, игнорируя MeshExpansionFactor опция. Максимальный размер сетки 1, несмотря на любую настройку MaxMeshSize опция.
В сложение, когда идет успешный опрос, patternsearch запускается в успешной точке и снова опрашивается. Этот дополнительный опрос использует те же векторы mesh, расширенные на множитель 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.
По умолчанию поиск шаблона удваивает размер mesh после каждого успешного опроса и уменьшает его вдвое после каждого неудачного опроса.
Поиск шаблона выполняет 60 итераций перед остановкой. Следующий график показывает точки в последовательности, вычисленной в первых 13 итерациях поиска шаблона.
Числа ниже точек указывают на первую итерацию, при которой алгоритм находит точку. График показывает только номера итерации, соответствующие успешным опросам, потому что лучшая точка не меняется после неудачного опроса. Для примера лучшая точка в итерациях 4 и 5 является такой же, как и в итерации 3.
При каждой итерации поиск шаблона опрашивает точки в текущем mesh - то есть вычисляет целевую функцию в точках mesh, чтобы увидеть, есть ли та, чье значение функции меньше, чем значение функции в текущей точке. Как работает Pattern Search Polling предоставляет пример опроса. Можно задать шаблон, который задает mesh 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. Например, если вы запускаете поиск по шаблону в линейно ограниченном примере в Ограниченной Минимизации Используя patternsearch и Оптимизировать задачу Live Editor, алгоритм выполняет 1588 вычислений функции с 'GPSPositiveBasis2N', значение по умолчанию PollMethod, но только 877 вычисления функции с использованием 'GPSPositiveBasisNp1'. Для получения дополнительной информации смотрите Сравнение эффективности опций опроса.
Однако, если целевая функция имеет много локальных минимумов, использование 'GPSPositiveBasis2N' как PollMethod может избежать нахождения локального минимума, который не является глобальным минимумом, потому что поиск исследует больше точек вокруг текущей точки при каждой итерации.
По умолчанию, если поиск по шаблону находит точку сетки, которая улучшает значение целевой функции, он останавливает опрос и устанавливает эту точку в качестве текущей точки для следующей итерации. Когда это происходит, некоторые точки mesh могут не быть опрашены. Некоторые из этих несовпадающих точек могут иметь значение целевой функции, которое даже ниже, чем первое, которое находит поиск шаблона.
Для задач, в которых существует несколько локальных минимумов, иногда предпочтительно сделать поиск шаблона опрашивающим все точки mesh при каждой итерации и выбрать тот, который имеет лучшее значение целевой функции. Это позволяет поиску шаблона исследовать больше точек в каждой итерации и, таким образом, потенциально избегать локального минимума, который не является глобальным минимумом. Пусть поиск шаблона опрашивает весь mesh, задавая UseCompletePoll опция для true.
Алгоритм останавливается, когда происходит любое из следующих условий:
Размер сетки меньше, чем MeshTolerance опция.
Количество итераций, выполненных алгоритмом, достигает значения MaxIterations опция.
Общее количество вычислений целевой функции, выполненных алгоритмом, достигает значения MaxFunctionEvaluations опция.
Время, в секундах, алгоритм запускается, пока не достигает значения MaxTime опция.
После успешного опроса расстояние между точкой, найденной в предыдущих двух итерациях, и размером сетки меньше StepTolerance опция.
После успешного опроса изменение целевой функции в предыдущих двух итерациях меньше, чем FunctionTolerance опция, и размер сетки меньше, чем StepTolerance опция.
The ConstraintTolerance опция не используется в качестве критерия остановки. Он определяет допустимость относительно нелинейных ограничений.
Алгоритм MADS использует дополнительный параметр, называемый параметром poll, и p в критерии остановки размера сетки:
где И m - размер сетки. Критерий остановки MADS:
И p ≤ MeshTolerance.
Алгоритм поиска шаблона является устойчивым в отношении отказов целевой функции. Это означает patternsearch переносит вычисления функции, приводящие к NaN, Inf, или комплексные числа. Когда целевая функция в начальной точке x0 является вещественным, конечным значением patternsearch обрабатывает отказы точек опроса, как если бы значения целевой функции были большими, и игнорирует их.
Для примера, если все точки в опросе оцениваются как NaN, patternsearch считает опрос неудачным, сжимает mesh и переоценивает. Если даже одна точка в опросе оценивается с меньшим значением, чем любой еще замеченный, patternsearch считает опрос успешным и расширяет mesh.