БРСТ-алгоритм
Алгоритм Бендера-Риннуя-Стуги-Тиммера (BRST) — это алгоритм оптимизации, подходящий для поиска глобального оптимума функций черного ящика . В своей статье Boender et al. [1] описывают свой метод как стохастический метод, включающий комбинацию выборки, кластеризации и локального поиска, заканчивающийся диапазоном доверительных интервалов для значения глобального минимума.
Алгоритм Boender et al. был изменен Тиммером. [2] Тиммер рассмотрел несколько методов кластеризации. По результатам экспериментов наиболее точным признан метод под названием «многоуровневая одиночная связь».
Тихие алгоритмы [3] являются реализациями алгоритма [Boender et al. ] [1] и создал общедоступный программный продукт GLOBAL. представляют Используемые локальные алгоритмы собой алгоритм линейного поиска случайного направления, также используемый Торном, и алгоритм квазиньютона, не использующий производную функции. Результаты показывают зависимость результата от использованного вспомогательного локального алгоритма.
Фон
[ редактировать ]Расширение класса функций за счет мультимодальных функций делает задачу глобальной оптимизации вообще неразрешимой. Для того чтобы функция была разрешима, помимо непрерывности необходимо знать некоторые условия гладкости функции.
Существование нескольких локальных минимумов и неразрешимость в целом являются важными характеристиками глобальной оптимизации. Неразрешимость здесь означает, что решение не может быть гарантировано за конечное число шагов.Есть два пути решения проблемы неразрешимости. Сначала ставятся «априорные» условия на f и A, которые превращают задачу в разрешимую или, по крайней мере, позволяют точно сказать, что решение найдено. Это ограничивает рассматриваемый класс функций.Второй подход, который позволяет рассмотреть более широкий класс целевых функций, состоит в том, чтобы отказаться от требования разрешимости и попытаться получить только оценку глобального минимума. При таком «вероятностном» подходе было бы желательно также получить некоторые результаты о достоверности полученной оценки. Некоторые из решаемых задач могут попасть в этот класс, поскольку количество шагов, необходимых для гарантированного решения, может быть непомерно большим.
При ослаблении требования к разрешимости кажется рациональным потребовать, чтобы вероятность получения решения приближалась к 1, если процедуре разрешено продолжаться вечно. Очевидная вероятностная процедура глобального поиска состоит в использовании локального алгоритма, начиная с нескольких точек, распределенных по всей области оптимизации. Эта процедура называется «Мультистарт». Мультистарт, безусловно, является одной из первых используемых глобальных процедур. Его даже использовали при локальной оптимизации для повышения уверенности в полученном решении. Одним из недостатков Multistart является то, что при использовании большого количества начальных точек один и тот же минимум в конечном итоге будет определяться несколько раз. Чтобы повысить эффективность Multistart, этого следует избегать.
Чтобы избежать повторного определения локальных минимумов, используются методы кластеризации. Это реализуется в три этапа, которые можно использовать итеративно. Три шага:
- (а) Точки отбора проб в интересующем регионе.
- (б) Преобразуйте выборку, чтобы получить точки, сгруппированные вокруг локальных минимумов.
- (c) Используйте метод кластеризации для распознавания этих групп (т.е. окрестностей локальных минимумов).
Если процедура, использующая эти шаги, окажется успешной, то запуск одной локальной оптимизации для каждого кластера определит локальные минимумы, а, следовательно, и глобальный минимум. Преимущество использования этого подхода состоит в том, что работа, сэкономленная при вычислении каждого минимума только один раз, может быть потрачена на вычисления в (a) и (b), что увеличит вероятность того, что глобальный минимум будет найден.
Будучи методом кластеризации , их эффективность выше для задач малой размерности и становится менее эффективной для задач, имеющих несколько сотен переменных.
Ссылки
[ редактировать ]- ^ Jump up to: а б Бендер, CGE; AHG Риннуй Кан; Л. Строуги; Г.Т. Тиммер (1982). «Стохастический метод глобальной оптимизации» (PDF) . Математическое программирование . 22 : 125–140. дои : 10.1007/BF01581033 . S2CID 5450000 .
- ^ Тиммер, GT (1984). Глобальная оптимизация: стохастический подход (кандидатская диссертация). Университет Эразма Роттердама.
- ^ Сендес, Т. (1988). «Нелинейная оценка параметров путем глобальной оптимизации. Эффективность и надежность» . Акта Кибернетика . 8 (4): 361–370.
Внешние ссылки
[ редактировать ]- http://www.abo.fi/~atorn/Globopt.html С разрешения автора текст скопирован дословно.
- Янка Сравнивает различные алгоритмы глобальной оптимизации, из которых BRST показывает превосходную производительность.
- Янка Представляет количество оценок функций, выполненных на наборе тестов Диксона-Сегё. Наряду с алгоритмом MCS , BRST требует наименьшего количества оценок.