patternsearch находит последовательность точек, x0x1 x2 ..., тот подход оптимальная точка. Значение целевой функции или уменьшается или остается то же самое от каждой точки в последовательности к следующему. Этот раздел объясняет, как поиск шаблона работает на функцию, описанную в, Оптимизируют Используя Алгоритм GPS.
Чтобы упростить объяснение, этот раздел описывает, как обобщенный поиск шаблона (GPS) работает с помощью максимального положительного основания по умолчанию 2 Н с ScaleMesh набор опции к false.
Этот раздел не показывает как patternsearch алгоритм работает с границами или линейными ограничениями. Для границ и линейных ограничений, patternsearch изменяет точки опроса, чтобы быть выполнимым в каждой итерации, означая удовлетворять всем границам и линейным ограничениям.
Этот раздел не охватывает нелинейные ограничения. Понять как patternsearch работает с нелинейными ограничениями, смотрите Нелинейный Ограничительный Алгоритм решателя.
Поиск шаблона начинает в начальной точке x0 то, что вы обеспечиваете. В этом примере, x0 = [2.1 1.7].
В первой итерации размер mesh равняется 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 останавливает текущую итерацию, как только это находит точку mesh, значение фитнеса которой меньше, чем та из текущей точки. Следовательно, алгоритм не может опросить все точки mesh. Можно заставить алгоритм опросить все точки mesh путем установки UseCompletePoll опция к true.
После успешного опроса алгоритм умножает текущий размер mesh на 2, значение по умолчанию MeshExpansionFactor опции. Поскольку начальный размер mesh равняется 1 во второй итерации, размер mesh равняется 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]
Поскольку опрос успешен, алгоритм умножает текущий размер mesh на 2, чтобы получить размер mesh 4 в третьей итерации.
Четвертой итерацией текущая точка
x3 = [-4.9 1.7]
и размер mesh равняется 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;
В следующей итерации алгоритм умножает текущий размер mesh на 0,5, значение по умолчанию MeshContractionFactor опция, так, чтобы размер mesh в следующей итерации равнялся 4. Алгоритм затем опрашивает с меньшим размером mesh.
Установка PollMethod опция к 'MADSPositiveBasis2N' или 'MADSPositiveBasisNp1' причины patternsearch использовать и различный тип опроса и реагировать на опрос по-другому, чем другие алгоритмы опроса.
Опрос MADS использование недавно сгенерировал псевдослучайные векторы mesh в каждой итерации. Векторы являются случайным образом переставленными компонентами из столбцов случайной нижней треугольной матрицы. Компоненты матрицы имеют целочисленные размеры до 1/. В опросе векторы mesh умножаются на размер mesh, таким образом, точки опроса могут составить от текущей точки.
Неудачные опросы сокращают mesh на коэффициент 4, игнорирование MeshContractionFactor опция. Точно так же успешные опросы расширяют mesh на коэффициент 4, игнорирование MeshExpansionFactor опция. Максимальным размером mesh является 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, чтобы видеть, существует ли тот, значение функции которого меньше значения функции в текущей точке. Как Поиск Шаблона Опрос работ обеспечивает пример опроса. Можно задать шаблон, который задает mesh PollMethod опция. Шаблон по умолчанию, 'GPSPositiveBasis2N', состоит из следующих направлений на 2 Н, где 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 Тэска, алгоритм выполняет 1 588 вычислений функции с 'GPSPositiveBasis2N', PollMethod по умолчанию, но только 877 вычислений функции с помощью 'GPSPositiveBasisNp1'. Для большего количества детали смотрите, Сравнивают КПД Опций Опроса.
Однако, если целевая функция имеет много локальных минимумов, с помощью 'GPSPositiveBasis2N' как PollMethod может постараться не находить локальный минимум, который не является глобальным минимумом, потому что поиск исследует больше точек вокруг текущей точки в каждой итерации.
По умолчанию, если поиск шаблона находит точку mesh, которая улучшает значение целевой функции, это останавливает опрос и наборы, которые указывают как текущая точка для следующей итерации. Когда это происходит, некоторые точки mesh не могут быть опрошены. Некоторые из этих неопрошенных точек могут иметь значение целевой функции, которое является четным ниже, чем первый, который находит поиск шаблона.
Для проблем, в которых существует несколько локальных минимумов, иногда предпочтительно заставить поиск шаблона опросить все точки mesh в каждой итерации и выбрать ту с лучшим значением целевой функции. Это позволяет поиску шаблона исследовать больше точек в каждой итерации и таким образом потенциально избежать локального минимума, который не является глобальным минимумом. Имейте опрос поиска шаблона целая mesh, устанавливающая UseCompletePoll опция к true.
Алгоритм останавливается, когда любое из следующих условий происходит:
Размер mesh меньше MeshTolerance опция.
Количество итераций, выполняемых алгоритмом, достигает значения MaxIterations опция.
Общее количество оценок целевой функции, выполняемых алгоритмом, достигает значения MaxFunctionEvaluations опция.
Время, в секундах, запуски алгоритма, пока это не достигает значения MaxTime опция.
После успешного опроса расстояние между точкой, найденной в предыдущих двух итерациях и размером mesh, является оба меньше, чем StepTolerance опция.
После успешного опроса изменение в целевой функции в предыдущих двух итерациях меньше FunctionTolerance опция и размер mesh меньше StepTolerance опция.
ConstraintTolerance опция не используется в качестве останавливающегося критерия. Это определяет выполнимость относительно нелинейных ограничений.
Использование алгоритма MADS дополнительный параметр вызвало параметр опроса, Δp, в критерии остановки размера mesh:
где Δm является размером mesh. MADS останавливающийся критерий:
Δp ≤ MeshTolerance.
Алгоритм поиска шаблона устойчив относительно отказов целевой функции. Это означает patternsearch терпит вычисления функции, приводящие к NaNInf, или комплексные числа. Когда целевая функция при начальной точке x0 действительное, конечное значение, patternsearch обработки опрашивают отказы точки, как будто значения целевой функции являются большими, и игнорирует их.
Например, если все точки в опросе оценивают к NaN, patternsearch считает опрос неудачным, уменьшает mesh и переоценивает. Если даже одна точка в опросе оценивает к меньшему значению, чем кто-либо замеченный уже, patternsearch считает опрос успешным, и расширяет mesh.