Введение

Алгоритм Boender Rinnooy Stougie Timmer (BRST) — это алгоритм оптимизации, подходящий для поиска глобального оптимума функций «черного ящика». В своей статье Boender et al. описывают свой метод как стохастический, включающий комбинацию выборки, кластеризации и локального поиска, завершающийся определением диапазона доверительных интервалов для значения глобального минимума. Алгоритм Boender et al. был модифицирован Timmer. Timmer рассмотрел несколько методов кластеризации. На основе экспериментов метод под названием «многоуровневая одиночная связь» был признан наиболее точным. Алгоритмы Csendes являются реализациями алгоритма [Boender et al.] и легли в основу программного продукта общественного достояния GLOBAL. В качестве локальных алгоритмов используются алгоритм случайного направления, линейный алгоритм поиска, также применяемый Törn, и квазиньютоновский алгоритм, не использующий производную функции. Результаты демонстрируют зависимость результата от используемого вспомогательного локального алгоритма.

Предыстория

Расширение класса функций до мультимодальных функций делает проблему глобальной оптимизации в общем случае неразрешимой. Для того чтобы проблема была разрешимой, необходимо знать некоторое условие гладкости функции в дополнение к непрерывности. Существование нескольких локальных минимумов и неразрешимость в общем случае являются важными характеристиками глобальной оптимизации. Неразрешимость здесь означает, что решение не может быть гарантировано за конечное число шагов. Существует два способа решения проблемы неразрешимости. Во-первых, на f и A накладываются "априорные" условия, которые превращают проблему в разрешимую или, по крайней мере, позволяют с уверенностью установить, что решение найдено. Это ограничивает рассматриваемый класс функций. Второй подход, позволяющий рассматривать более широкий класс целевых функций, заключается в отказе от требования разрешимости и попытке получить лишь оценку глобального минимума. В этом "вероятностном" подходе также желательно получать результаты относительно качества полученной оценки. Некоторые из разрешимых задач могут попадать в этот класс, поскольку число шагов, необходимых для гарантированного решения, может быть непомерно большим. При ослаблении требования к разрешимости представляется разумным требовать, чтобы вероятность получения решения приближалась к 1, если процедуре позволено продолжаться бесконечно. Очевидной вероятностной процедурой глобального поиска является использование локального алгоритма, стартующего из нескольких точек, распределенных по всей области оптимизации. Эта процедура называется "Multistart" (Многозапуск). Multistart, безусловно, является одной из самых ранних глобальных процедур, используемых. Он даже применялся в локальной оптимизации для повышения уверенности в полученном решении. Одним из недостатков Multistart является то, что при использовании большого числа начальных точек один и тот же минимум в конечном итоге может быть определен несколько раз. Для повышения эффективности Multistart этого следует избегать. Методы кластеризации используются для предотвращения повторного определения локальных минимумов. Это реализуется в три этапа, которые могут использоваться итеративно. Эти три этапа: (a) выборка точек в интересующей области; (b) преобразование выборки для получения точек, сгруппированных вокруг локальных минимумов; (c) использование метода кластеризации для распознавания этих групп (т.е. окрестностей локальных минимумов). Если процедура, использующая эти этапы, успешна, то запуск одной локальной оптимизации из каждого кластера позволит определить локальные минимумы и, следовательно, глобальный минимум. Преимущество использования этого подхода заключается в том, что ресурсы, сэкономленные за счет вычисления каждого минимума только один раз, можно направить на вычисления в (a) и (b), что повысит вероятность нахождения глобального минимума. Будучи методом кластеризации, их эффективность выше для задач с низкой размерностью и снижается для задач с несколькими сотнями переменных.