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

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

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

История

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

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

Конвергенция

Сходимость - это метод поиска по образцу, предложенный Ю., который доказал его сходимость с помощью теории положительных базисов.[3] Позже Торчон, Лагариас и соавторы[4][5] использовали методы положительного базиса, чтобы доказать сходимость другого метода поиска по образцу на конкретных классах функций. Вне таких классов поиск по образцу - это эвристический которые могут предоставить полезные приблизительные решения для некоторых проблем, но могут дать сбой для других. Вне таких классов поиск по образцу не является итерационный метод что сходится к решению; действительно, методы поиска по образцу могут сходиться к нестационарным точкам в некоторых относительно простых задачах.[6][7]

Смотрите также

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

Рекомендации

  1. ^ Hooke, R .; Дживс, Т. (1961). ""Прямой поиск «решение числовых и статистических задач». Журнал ACM. 8 (2): 212–229. Дои:10.1145/321062.321069.
  2. ^ Дэвидон, W.C. (1991). «Метод переменной метрики для минимизации». SIAM Journal по оптимизации. 1 (1): 1–17. CiteSeerX  10.1.1.693.272. Дои:10.1137/0801001.
  3. ^ * Юй, Вэнь Ци. 1979. «Позитивная основа и класс методов прямого поиска ”. Scientia Sinica [Чжунго Кэсюэ]: 53—68.
  4. ^ Торчон, В.Дж. (1997). «О сходимости алгоритмов поиска по образцу» (PDF). SIAM Journal по оптимизации. 7 (1): 1–25. CiteSeerX  10.1.1.50.3173. Дои:10.1137 / S1052623493250780.
  5. ^ Dolan, E.D .; Lewis, R.M .; Торчон, В.Дж. (2003). «О локальной конвергенции поиска по образцу» (PDF). SIAM Journal по оптимизации. 14 (2): 567–583. CiteSeerX  10.1.1.78.2407. Дои:10.1137 / S1052623400374495.
  6. ^ * Пауэлл, Майкл Дж. Д. 1973. ”О направлениях поиска алгоритмов минимизации.” Математическое программирование 4: 193—201.
  7. ^ * Маккиннон, К. И. М. (1999). «Сходимость симплекс-метода Нелдера – Мида к нестационарной точке». СИАМ Дж. Оптим. 9: 148–158. CiteSeerX  10.1.1.52.3900. Дои:10.1137 / S1052623496303482. (краткое изложение алгоритма онлайн).