Этот пример визуально показывает, как поиск шаблона оптимизирует функцию. Функция является высотой местности около горы Вашингтон, как функция от местоположения 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, который рисует трехмерную передачу Mt. Washington. В сложение, когда запуск прогрессирует, он рисует сферы вокруг каждой точки, которая лучше (выше), чем ранее посещенные точки.
3. psplotwashington, который рисует контурную карту Mt. Washington, и контролирует ползунок, который управляет скоростью запуска. Он показывает, где алгоритм поиска шаблона ищет 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);
Далее создадим опции для поиска по шаблону. Этот набор опций имеет остановку алгоритма, когда размер сетки уменьшается ниже 1, сохраняет mesh без масштаба (тот же размер в каждом направлении), устанавливает начальный размер сетки равным 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 руководство пользователя.