В этом примере визуально показано, как поиск шаблона оптимизирует функцию. Функция - высота местности у горы Вашингтон, как функция местоположения x-y. Чтобы найти вершину горы Вашингтон, мы минимизируем объективную функцию, которая является отрицательной от высоты. (Гора Вашингтон в этом примере является самой высокой вершиной на северо-востоке США.)
Геологическая служба США предоставляет данные о высоте местности в зависимости от местоположения x-y на сетке. Чтобы иметь возможность оценить высоту в произвольной точке, целевая функция интерполирует высоту из ближайших точек сетки.
Было бы быстрее, конечно, просто найти максимальное значение высоты, как указано на сетке, с помощью max функция. Смысл этого примера состоит в том, чтобы показать, как работает алгоритм поиска шаблона; он работает с функциями, определенными в непрерывных областях, а не только с точками сетки. Кроме того, если вычислительно дорого оценить целевую функцию, то выполнение этой оценки на полной сетке, как требуется max функция будет гораздо менее эффективной, чем использование алгоритма поиска шаблона, который выполняет выборку небольшого подмножества точек сетки.
Поиск шаблона находит локальный минимум целевой функции с помощью следующего метода, называемого опросом. В этом описании слова, описывающие величины поиска шаблона, выделены полужирным шрифтом. Поиск начинается в начальной точке, которая принимается как текущая точка на первом шаге:
1. Создайте массив точек, обычно плюс и минус направления координат, умножьте размер сетки и центрируйте этот массив по текущей точке.
2. Вычислите целевую функцию в каждой точке массива.
3. Если минимальная цель в шаблоне меньше значения в текущей точке, опрос будет успешным, и произойдет следующее:
3a. Минимальная найденная точка становится текущей точкой.
3b. Размер сетки удваивается.
3c. Алгоритм переходит к этапу 1.
4. Если опрос не был успешным, то происходит следующее:
4a. Размер сетки уменьшается вдвое.
4b. Если размер сетки ниже порогового значения, итерации прекращаются.
4c. В противном случае текущая точка сохраняется, и алгоритм переходит к этапу 1.
Этот простой алгоритм с некоторыми незначительными модификациями обеспечивает надежный и простой метод оптимизации. Она не требует градиентов целевой функции. Он также поддается ограничениям, но этот пример и описание касаются только неограниченных проблем.
Чтобы подготовить поиск шаблона, загрузите данные в mtWashington.mat, который содержит данные USGS в сетке 472 на 345. Отметка Z задается в футах. Векторы x и y содержат базовые значения интервалов сетки в восточном и северном направлениях соответственно. Файл данных также содержит начальную точку поиска, X0.
load mtWashingtonСуществует три файла MATLAB, которые выполняют вычисление целевой функции и процедуры печати. Это:
1. terrainfun, которая оценивает отрицательное значение высоты в любом положении x-y. terrainfun использует функцию MATLAB ®interp2 для выполнения двумерной линейной интерполяции. Он принимает данные Z и позволяет оценить отрицательное значение высоты во всех точках x-y.
2. psoutputwashington, который рисует 3-d рендеринг Mt. Washington. Кроме того, по мере прохождения пробега вокруг каждой точки рисуются сферы, которые лучше (выше), чем ранее посещаемые точки.
3. psplotwashington, которая рисует контурную карту города Вашингтон и отслеживает ползунок, который управляет скоростью пробега. Он показывает, где алгоритм поиска шаблона ищет оптимум, рисуя + знаки в этих точках. Он также рисует сферы вокруг каждой точки, которая лучше, чем ранее посещенные точки.
В примере: patternsearch использование terrainfun в качестве своей целевой функции, psoutputwashington в качестве функции вывода, и psplotwashington как функция графика. Мы готовим функции для передачи patternsearch в синтаксисе анонимной функции:
mtWashObjectiveFcn = @(xx) terrainfun(xx, x, y, Z); mtWashOutputFcn = @(xx,arg1,arg2) psoutputwashington(xx,arg1,arg2, x, y, Z); mtWashPlotFcn = @(xx,arg1) psplotwashington(xx,arg1, x, y, Z);
Далее мы создадим опции для поиска по образцу. Этот набор опций останавливает алгоритм, когда размер сетки уменьшается ниже 1, сохраняет сетку без масштаба (один и тот же размер в каждом направлении), устанавливает начальный размер сетки равным 10 и задает функцию вывода и функцию графика:
options = optimoptions(@patternsearch,'MeshTolerance',1,'ScaleMesh',false, ... 'InitialMeshSize',10,'UseCompletePoll',true,'PlotFcn',mtWashPlotFcn, ... 'OutputFcn',mtWashOutputFcn,'UseVectorized',true);
При выполнении этого примера отображаются два окна. Один показывает точки, которые алгоритм поиска шаблона выбирает на двухмерной контурной карте горы Вашингтон. Это окно имеет ползунок, который управляет задержкой между итерациями алгоритма (когда он возвращается к шагу 1 в описании того, как работает поиск шаблона). Установите ползунок в низкое положение для ускорения выполнения или в высокое положение для замедления выполнения.
В другом окне показан трехмерный график горы Вашингтон вместе с шагами, которые делает алгоритм поиска шаблона. Этот график можно поворачивать во время выполнения прогона, чтобы получить другие виды.
[xfinal ffinal] = patternsearch(mtWashObjectiveFcn,X0,[],[],[],[],[], ...
[],[],options)Optimization terminated: mesh size less than options.MeshTolerance.
xfinal = 1×2
316130 4904295
ffinal = -6280
Финальная точка, xfinalпоказывает, где алгоритм поиска шаблона завершен; Это x-y местоположение вершины горы Вашингтон. Конечная целевая функция, ffinal, является негативом высоты горы Вашингтон, 6280 футов. (Это должно быть 6288 футов по данным обсерватории Маунт Вашингтон).
Проверка файлов terrainfun.m, psoutputwashington.m, и psplotwashington.m для просмотра работы интерполяции и графики.
Для алгоритма поиска шаблона доступно множество опций. Например, алгоритм может взять первую точку, которую он находит, которая является улучшением, а не опрашивать все точки в шаблоне. Он может опрашивать точки в различных порядках. И он может использовать различные модели для опроса, как детерминированные, так и случайные. Для получения более подробной информации см. Руководство пользователя Global Optimization Toolbox.