Алгоритм BRST - BRST algorithm

Боендер-Риннуа-Стуги-Тиммер алгоритм (BRST) - это алгоритм оптимизации, подходящий для поиска глобальный оптимум из черный ящик функции. В своей статье Боендер и другие. [1] описывают свой метод как стохастический метод, включающий комбинацию выборки, кластеризации и локального поиска, заканчивающийся диапазоном доверительных интервалов для значения глобального минимума.

Алгоритм Боендера и другие. был изменен Тиммером.[2] Тиммер рассмотрел несколько методов кластеризации. На основании экспериментов наиболее точным был признан метод под названием «многоуровневая одиночная связь».

Алгоритмы Чендеса [3] являются реализациями алгоритма [Boender и другие.][1] и положил начало программное обеспечение общественного достояния продукт ГЛОБАЛЬНЫЙ. Используемые локальные алгоритмы - это случайное направление, алгоритм линейного поиска, также используемый Торном, и алгоритм квази-Ньютона, не использующий производную функции. Результаты показывают зависимость результата от используемого вспомогательного локального алгоритма.

Фон

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

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

При ослаблении требования о разрешимости кажется рациональным потребовать, чтобы вероятность того, что решение будет получено, приближалась к 1, если процедура может продолжаться бесконечно. Очевидной процедурой вероятностного глобального поиска является использование локального алгоритма, начиная с нескольких точек, распределенных по всей области оптимизации. Эта процедура называется «Мультистарт». Мультистарт, безусловно, является одной из самых первых используемых глобальных процедур. Его даже использовали при локальной оптимизации для повышения уверенности в полученном решении. Одним из недостатков Multistart является то, что при использовании нескольких начальных точек один и тот же минимум в конечном итоге будет определяться несколько раз. Чтобы повысить эффективность Multistart, этого следует избегать.

Чтобы избежать повторного определения локальных минимумов, используются методы кластеризации. Это реализуется в три этапа, которые можно использовать итеративно. Три шага:

  • (а) Примеры точек в интересующей области.
  • (b) Преобразуйте образец, чтобы получить точки, сгруппированные вокруг локальных минимумов.
  • (c) Используйте метод кластеризации для распознавания этих групп (то есть окрестностей локальных минимумов).

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

Быть метод кластеризации, их эффективность выше для задач малой размерности и становится менее эффективной для задач с несколькими сотнями переменных.

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

  1. ^ а б Boender, C.G.E .; A.H.G. Риннуй Кан; Л. Струги; G.T. Тиммер (1982). «Стохастический метод глобальной оптимизации» (PDF). Математическое программирование. 22: 125–140. Дои:10.1007 / BF01581033. S2CID  5450000.
  2. ^ Тиммер, Г. (1984). «Глобальная оптимизация: стохастический подход» (кандидатская диссертация). Университет Эразма в Роттердаме. Цитировать журнал требует | журнал = (помощь)
  3. ^ Чендес, Т. (1988). «Нелинейная оценка параметров методом глобальной оптимизации - эффективность и надежность». Acta Cybernetica. 8 (4): 361–370.

внешняя ссылка

  • http://www.abo.fi/~atorn/Globopt.html С разрешения автора текст был дословно скопирован.
  • Янка Сравнивает различные алгоритмы глобальной оптимизации, из которых BRST показывает превосходную производительность.
  • Янка Представляет количество функциональных оценок, выполненных на тестовом наборе Dixon-Szegö. Вместе с Алгоритм MCS, BRST требует наименьшего количества оценок.