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

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

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 руководство пользователя.