patternsearch находит последовательность точек, x0, x1, x2..., которые приближаются к оптимальной точке. Значение целевой функции или уменьшается или остается то же самое от каждой точки в последовательности к следующему. Этот раздел объясняет, как поиск шаблона работает на функцию, описанную в, Оптимизируют Используя Алгоритм GPS.
Чтобы упростить объяснение, этот раздел описывает, как обобщенный поиск шаблона (GPS) работает с помощью максимального положительного основания 2 Н с набором Scale к Off в опциях Mesh.
Этот раздел не показывает, как алгоритм 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 установкой Complete poll к On.
После успешного опроса алгоритм умножает текущий размер mesh на 2, значение по умолчанию Expansion factor в панели опций Mesh. Поскольку начальный размер 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, значение по умолчанию Contraction factor в панели опций Mesh, так, чтобы размер 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. Дополнительный опрос смотрит снова вдоль тех же направлений, которые были только успешны.
Можно отобразить результаты поиска шаблона в каждой итерации установкой Level of display к Iterative в опциях Display to command window. Это позволяет вам оценить прогресс поиска шаблона и внести изменения в 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 MeshSuccessful Poll записи ниже Method указывает, что текущая итерация была успешна. Например, опрос в итерации 2 успешен. В результате значение целевой функции точки, вычисленной в итерации 2, отображенный ниже f(x), является меньше, чем значение в итерации 1.
В итерации 4, запись Refine Mesh говорит вам, что опрос неудачен. В результате значение функции в итерации 4 остается неизменным от итерации 3.
По умолчанию поиск шаблона удваивает размер mesh после каждого успешного опроса и половин это после каждого неудачного опроса.
Поиск шаблона выполняет 60 итераций перед остановкой. Следующий график показывает точки в последовательности, вычисленной в первых 13 итерациях поиска шаблона.
Числа ниже точек указывают на первую итерацию, в которой алгоритм находит точку. График только показывает числа итерации, соответствующие успешным опросам, потому что лучшая точка не изменяется после неудачного опроса. Например, лучшая точка в итерациях 4 и 5 эквивалентна в итерации 3.
В каждой итерации поиск шаблона опрашивает точки в текущей mesh — то есть, это вычисляет целевую функцию при точках mesh, чтобы видеть, существует ли тот, значение функции которого является меньше, чем значение функции в текущей точке. Как Поиск Шаблона Опрос работ обеспечивает пример опроса. Можно задать шаблон, который задает mesh опцией Poll method. Шаблон по умолчанию, GPS Positive basis 2N, состоит из следующих направлений на 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].
Также можно установить Poll method на GPS Positive basis NP1, шаблон, состоящий из следующего N + 1 направление.
[1 0 0...0]
[0 1 0...0]
...
[0 0 0...1]
[–1 –1 –1...–1].
Например, если целевая функция имеет три независимых переменные, GPS Positive basis Np1, состоит из следующих четырех векторов.
[1 0 0]
[0 1 0]
[0 0 1]
[–1 –1 –1].
Поиск шаблона будет иногда запускать более быстрое использование GPS Positive basis Np1, а не GPS Positive basis 2N как Poll method, потому что алгоритм ищет меньше точек в каждой итерации. Несмотря на то, что не будучи обращенным в этом примере, то же самое верно при использовании MADS Positive basis Np1 по MADS Positive basis 2N, и так же для GSS. Например, если вы запускаете поиск шаблона на примере, описанном в Линейно Ограниченной проблеме, алгоритм выполняет 1 588 функциональных оценок с GPS Positive basis 2N, Poll method по умолчанию, но только 877 функциональными оценками с помощью GPS Positive basis Np1. Для большего количества детали смотрите, Сравнивают Эффективность Опций Опроса.
Однако, если целевая функция имеет много локальных минимумов, с помощью GPS Positive basis 2N, когда Poll method может постараться не находить локальный минимум, который не является глобальным минимумом, потому что поиск исследует больше точек вокруг текущей точки в каждой итерации.
По умолчанию, если поиск шаблона находит точку mesh, которая улучшает значение целевой функции, это останавливает опрос и наборы, которые указывают как текущая точка для следующей итерации. Когда это происходит, некоторые точки mesh не могут быть опрошены. Некоторые из этих неопрошенных точек могут иметь значение целевой функции, которое еще ниже, чем первый, который находит поиск шаблона.
Для проблем, в которых существует несколько локальных минимумов, иногда предпочтительно заставить поиск шаблона опросить все точки mesh в каждой итерации и выбрать ту с лучшим значением целевой функции. Это позволяет поиску шаблона исследовать больше точек в каждой итерации и таким образом потенциально избежать локального минимума, который не является глобальным минимумом. В приложении Оптимизации можно заставить поиск шаблона опросить целую установку Complete poll mesh к On в опциях Poll. В командной строке используйте optimoptions, чтобы установить опцию UseCompletePoll на true.
Критерии остановки алгоритма поиска шаблона перечислены в разделе Stopping criteria приложения Оптимизации:
Алгоритм останавливается, когда любое из следующих условий происходит:
Размер mesh является меньше, чем Mesh tolerance.
Количество итераций, выполняемых алгоритмом, достигает значения Max iteration.
Общее количество оценок целевой функции, выполняемых алгоритмом, достигает значения Max function evaluations.
Время, в секундах, выполнения алгоритма, пока это не достигает значения Time limit.
После успешного опроса расстояние между точкой, найденной в предыдущих двух итерациях и размером mesh, является оба меньше, чем X tolerance.
После успешного опроса изменение в целевой функции в предыдущих двух итерациях является меньше, чем Function tolerance и размер mesh являются меньше, чем X tolerance.
Nonlinear constraint tolerance не используется в качестве останавливающегося критерия. Это определяет выполнимость относительно нелинейных ограничений.
Использование алгоритма MADS дополнительный параметр вызвало параметр опроса, Δp, в критерии остановки размера mesh:
где Δm является размером mesh. MADS останавливающийся критерий:
Δp ≤ Mesh tolerance.
Алгоритм поиска шаблона устойчив относительно отказов целевой функции. Это означает, что patternsearch терпит функциональные оценки, приводящие к NaN, Inf или комплексным числам. Когда целевая функция при начальной точке, x0 является действительным, конечным значением, отказы точки опроса обработок patternsearch, как будто значения целевой функции являются большими, и игнорируют их.
Например, если все точки в опросе оценивают к NaN, patternsearch считает опрос неудачным, уменьшает mesh и переоценивает. Если даже одна точка в опросе оценивает к меньшему значению, чем кто-либо замеченный уже, patternsearch считает опрос успешным, и расширяет mesh.