Поиск по шаблону (оптимизация)

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

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

• 1 История
• 2 Конвергенция
• 3 См. Также
• 4 Ссылки

Название «поиск по образцу» придумали Гук и Дживс. Ранний и простой вариант приписывается Ферми и Метрополису, когда они работали в Национальной лаборатории Лос-Аламоса. Дэвидон описывает это следующим образом:

Они изменяли один теоретический параметр за раз с шагом одинаковой величины, и когда такое увеличение или уменьшение какого-либо одного параметра не улучшало соответствие экспериментальным данным, они вдвое уменьшали размер шага и повторял процесс до тех пор, пока шаги не были сочтены достаточно маленькими.

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

• Поиск по золотому сечению концептуально напоминает PS в своем сужении диапазона поиска, только для одномерные поисковые пространства.
• Метод Нелдера – Мида aka. симплексный метод концептуально напоминает PS в его сужении диапазона поиска для многомерных пространств поиска, но делает это за счет сохранения n + 1 точек для n-мерных пространств поиска, тогда как методы PS вычисляют 2n + 1 точку (центральная точка и 2 точки в каждом измерении).
• Луус – Яакола выбирает из равномерного распределения, окружающего текущее положение, и использует простую формулу для экспоненциального уменьшения диапазона выборки.
• Случайный поиск - это родственное семейство методов оптимизации, которые выбирают из гиперсферы, окружающей текущее положение.
• Случайная оптимизация - родственное семейство методов оптимизации, которые выбирают из нормального распределения окружающей среды. текущее положение.