Поиск по шаблону (оптимизация)
Поиск по шаблону (также известный как прямой поиск, поиск без производных или поиск по черному ящику) — это семейство методов численной оптимизации , не требующих градиента . В результате его можно использовать для функций, которые не являются непрерывными или дифференцируемыми . Одним из таких методов поиска шаблонов является «конвергенция» (см. ниже), основанная на теории положительных базисов. Оптимизация пытается найти лучшее совпадение (решение с наименьшим значением ошибки) в пространстве многомерного анализа возможностей.
История [ править ]
Название «поиск по образцу» было придумано Гуком и Дживсом. [1] Ранний и простой вариант приписывается Ферми и Метрополису , когда они работали в Национальной лаборатории Лос-Аламоса . Это описано Давидоном, [2] следующее:
Они изменяли по одному теоретическому параметру шагами одинаковой величины, и когда такое увеличение или уменьшение какого-либо параметра не улучшало соответствие экспериментальным данным, они уменьшали размер шага вдвое и повторяли процесс до тех пор, пока шаги не считались достаточными. маленький.
Конвергенция [ править ]
Сходимость — это метод поиска шаблонов, предложенный Ю, который доказал, что он сходится, используя теорию положительных базисов. [3] Позже Торчон , Лагариас и соавторы [4] [5] использовал методы положительного базиса, чтобы доказать сходимость другого метода поиска шаблонов для определенных классов функций. За пределами таких классов поиск по шаблону представляет собой эвристику , которая может предоставить полезные приблизительные решения для некоторых проблем, но может потерпеть неудачу в других. За пределами таких классов поиск по шаблону не является итеративным методом , сходящимся к решению; действительно, методы поиска шаблонов могут сходиться к нестационарным точкам в некоторых относительно несложных задачах. [6] [7]
См. также [ править ]
- Поиск по золотому сечению концептуально напоминает PS в сужении диапазона поиска, только для одномерных пространств поиска.
- Метод Нелдера-Мида, он же метод. Симплексный метод концептуально напоминает PS в сужении диапазона поиска для многомерных пространств поиска, но делает это за счет сохранения n + 1 точек для n -мерных пространств поиска, тогда как методы PS вычисляют 2 n + 1 точек (центральную точку и 2 точки в каждом измерении).
- Луус-Яакола производит выборку из равномерного распределения, окружающего текущую позицию, и использует простую формулу для экспоненциального уменьшения диапазона выборки.
- Случайный поиск — это родственное семейство методов оптимизации, которые производят выборку из гиперсферы, окружающей текущую позицию.
- Случайная оптимизация — это родственное семейство методов оптимизации, которые выбирают из нормального распределения, окружающего текущую позицию.
Ссылки [ править ]
- ^ Гук, Р.; Дживс, Т. А. (1961). « Прямой поиск» решения численных и статистических задач» . Журнал АКМ . 8 (2): 212–229. дои : 10.1145/321062.321069 . S2CID 10905054 .
- ^ Дэвидон, WC (1991). «Метод переменной метрики для минимизации». SIAM Journal по оптимизации . 1 (1): 1–17. CiteSeerX 10.1.1.693.272 . дои : 10.1137/0801001 . S2CID 1819475 .
- ^ *Ю, Вэнь Ци. 1979. « Позитивный базис и класс методов прямого поиска ». Scientia Sinica [ Чжунго Кэсюэ ]: 53–68.
- Ю, Вэнь Ци. 1979. « Конвергентное свойство симплексной эволюционной техники ». Scientia Sinica [ Чжунго Кэсюэ ]: 69–77.
- ^ Торчон, виджей (1997). «О сходимости алгоритмов поиска по образцу» (PDF) . SIAM Journal по оптимизации . 7 (1): 1–25. CiteSeerX 10.1.1.50.3173 . дои : 10.1137/S1052623493250780 .
- ^ Долан, Эд; Льюис, РМ; Торчон, виджей (2003). «О локальной сходимости поиска по образцу» (PDF) . SIAM Journal по оптимизации . 14 (2): 567–583. CiteSeerX 10.1.1.78.2407 . дои : 10.1137/S1052623400374495 . hdl : 2060/20000109966 . S2CID 4226940 .
- ^ * Пауэлл, Майкл Дж. Д. 1973. « О направлениях поиска алгоритмов минимизации ». Математическое программирование 4: 193–201.
- ^ * Маккиннон, КИМ (1999). «Сходимость симплексного метода Нелдера – Мида к нестационарной точке». СИАМ Дж. Оптим . 9 : 148–158. CiteSeerX 10.1.1.52.3900 . дои : 10.1137/S1052623496303482 . (сводка алгоритма онлайн).