Постепенная оптимизация - Graduated optimization
Поэтапная оптимизация - это метод глобальной оптимизации , который пытается решить сложную проблему оптимизации путем первоначального решения значительно упрощенной задачи и постепенного преобразования этой проблемы (при оптимизации) до тех пор, пока она не станет эквивалентной сложной задаче оптимизации.
Описание техники
Поэтапная оптимизация - это усовершенствование лазания по холмам, которое позволяет альпинисту избежать принятия местных оптимумов. Он разбивает сложную задачу оптимизации на последовательность задач оптимизации, так что первая задача в последовательности является выпуклой (или почти выпуклой), решение каждой задачи дает хорошую отправную точку для следующей задачи в последовательности, а последняя задача. Проблема в последовательности - это сложная задача оптимизации, которую она в конечном итоге стремится решить. Часто постепенная оптимизация дает лучшие результаты, чем простое восхождение на холм. Кроме того, при наличии определенных условий можно показать оптимальное решение последней проблемы в последовательности. Эти условия таковы:
- Первая задача оптимизации в последовательности может быть решена с учетом начальной отправной точки.
- Локально выпуклая область вокруг глобального оптимума каждой задачи в последовательности включает точку, которая соответствует глобальному оптимуму предыдущей задачи в последовательности.
Индуктивно можно показать, что если эти условия выполняются, то альпинист достигнет глобального оптимума для решения сложной проблемы. К сожалению, найти последовательность задач оптимизации, удовлетворяющих этим условиям, может быть сложно. Часто постепенная оптимизация дает хорошие результаты, даже если невозможно доказать, что последовательность задач строго удовлетворяет всем этим условиям.
Некоторые примеры
Постепенная оптимизация обычно используется при обработке изображений для поиска объектов в большом изображении. Эту проблему можно сделать более выпуклой , размыв изображения. Таким образом, объекты можно найти, сначала выполнив поиск по наиболее размытому изображению, затем начав с этой точки и найдя менее размытое изображение, и продолжая таким образом до тех пор, пока объект не будет точно локализован на исходном резком изображении. Правильный выбор оператора размытия зависит от геометрического преобразования, связывающего объект на одном изображении с другим.
Постепенная оптимизация может использоваться во множественном обучении. Алгоритм Manifold Sculpting, например, использует постепенную оптимизацию для поиска вложения многообразия для нелинейного уменьшения размерности. Он постепенно масштабирует дисперсию дополнительных измерений в наборе данных при оптимизации остальных измерений. Он также использовался для расчета условий фракционирования с опухолями, для отслеживания объектов в компьютерном зрении и других целей.
Подробный обзор метода и его приложений можно найти в.
Связанные методы оптимизации
Имитация отжига тесно связана с постепенной оптимизацией. Вместо сглаживания функции, по которой выполняется оптимизация, моделируемый отжиг случайным образом изменяет текущий раствор на уменьшающуюся величину, что может иметь аналогичный эффект. Однако, поскольку имитация отжига основана на случайной выборке для поиска улучшений, сложность ее вычислений экспоненциально зависит от количества оптимизируемых измерений. Напротив, постепенная оптимизация сглаживает оптимизируемую функцию, поэтому методы локальной оптимизации, которые эффективны в многомерном пространстве (например, методы на основе градиента, альпинисты и т. Д.), Все еще могут использоваться.