Поиск шаблона поднимается на Гору Вашингтон

Этот пример показывает визуально, как поиск шаблона оптимизирует функцию. Функция является высотой ландшафта около Горы Вашингтон как функция x-y местоположения. Для того, чтобы найти верхнюю часть Горы Вашингтон, мы минимизируем целевую функцию, которая является отрицанием высоты. (Гора Вашингтон в этом примере является самым высоким пиком в северо-восточных Соединенных Штатах.)

Геологическая служба США обеспечивает данные по высоте ландшафта как функция x-y местоположения на сетке. Для того, чтобы смочь оценить высоту в произвольной точке, целевая функция интерполирует высоту от соседних узлов решетки.

Это было бы быстрее, конечно, чтобы просто найти максимальное значение высоты, как задано на сетке, с помощью max функция. Точка этого примера должна показать, как алгоритм поиска шаблона действует; это работает над функциями, определяемыми по непрерывным областям, не только узлами решетки. Кроме того, если в вычислительном отношении дорого выполнить целевую функцию, затем выполняя эту оценку на полной сетке, как требуется max функционируйте, будет намного менее эффективным, чем использование алгоритма поиска шаблона, который производит небольшое подмножество узлов решетки.

Как работы поиска шаблона

Поиск шаблона находит локальный минимум целевой функции следующим методом, названным опросом. В этом описании слова, описывающие количества поиска шаблона, полужирным. Поиск запускается в начальной точке, которая взята в качестве текущей точки в первом шаге:

1. Сгенерируйте шаблон точек, обычно плюс и минус координатные направления, времена размер mesh, и сосредоточьте этот шаблон на текущей точке.

2. Выполните целевую функцию в каждой точке в шаблоне.

3. Если минимальная цель в шаблоне ниже, чем значение в текущей точке, то опрос успешен, и следующее происходит:

3a. Минимальная найденная точка становится текущей точкой.

3b. Размер mesh удвоен.

3c. Алгоритм переходит к Шагу 1.

4. Если опрос не успешен, то следующее происходит:

4a. Размер mesh разделен на два.

4b. Если размер mesh ниже порога, остановки итераций.

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, который чертит 3D рендеринг Mt. Вашингтон. Кроме того, в то время как запуск прогрессирует, он чертит сферы вокруг каждой точки, которая лучше (выше), чем ранее посещаемые точки.

3. psplotwashington, который чертит контурную карту Mt. Вашингтон и мониторы ползунок, который контролирует скорость запуска. Это показывает, где алгоритм поиска шаблона ищет optima путем рисования + знаки в тех точках. Это также чертит сферы вокруг каждой точки, которая лучше, чем ранее посещаемые точки.

В примере, 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);

Настройки параметров поиска шаблона

Затем мы создаем опции для поиска шаблона. Этот набор опций имеет останов алгоритма, когда размер mesh уменьшается ниже 1, сохраняет mesh немасштабированной (тот же размер в каждом направлении), устанавливает начальный размер mesh на 10 и устанавливает выходную функцию и функцию построения графика:

options = optimoptions(@patternsearch,'MeshTolerance',1,'ScaleMesh',false, ...
    'InitialMeshSize',10,'UseCompletePoll',true,'PlotFcn',mtWashPlotFcn, ...
    'OutputFcn',mtWashOutputFcn,'UseVectorized',true);

Наблюдение прогресса поиска шаблона

Когда вы запускаете этот пример, вы видите два окна. Каждый показывает точки, которые алгоритм поиска шаблона выбирает на двумерной контурной карте Горы Вашингтон. Это окно имеет ползунок, который управляет задержкой между итерациями алгоритма (когда это возвращается к Шагу 1 в описании того, как поиск шаблона работает). Установите ползунок на низкое положение ускорять запуск, или к высокому положению, чтобы замедлить запуск.

Другое окно показывает 3D график Горы Вашингтон, наряду с шагами, которые делает алгоритм поиска шаблона. Можно вращать этот график, в то время как запуск прогрессирует, чтобы получить различные взгляды.

[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, отрицание высоты Горы Вашингтон, 6 280 футов. (Это должно быть 6 288 футов по данным Обсерватории Горы Вашингтон).

Исследуйте файлы terrainfun.m, psoutputwashington.m, и psplotwashington.m чтобы видеть, как интерполяция и графическая работа.

Существует много опций, доступных для алгоритма поиска шаблона. Например, алгоритм может взять первую точку, это находит, что это - улучшение, вместо того, чтобы опросить все точки в шаблоне. Это может опросить точки в различных порядках. И это может использовать различные шаблоны в опросе, и детерминированном и случайном. Консультируйтесь с Руководством пользователя Global Optimization Toolbox для деталей.

Документация