Skip to content
Назад к результатам поиска

Имитация отжига — вероятностная оптимизация

Год
1983
Тип
Probabilistic metaheuristic / local search

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Имитация отжига — это вероятностная метаэвристика локального поиска, представленная Kirkpatrick, Gelatt и Vecchi в 1983 году.

Она моделирует процесс физического отжига в металлургии — когда материал нагревается, а затем медленно охлаждается для достижения кристаллического состояния с низкой энергией — и использует эту аналогию для выхода из локальных оптимумов в комбинаторных и непрерывных задачах оптимизации.

Интуиция метода

Представьте, что вы пытаетесь найти самую низкую точку на холмистом ландшафте с завязанными глазами. Чисто жадный поиск всегда движется вниз и застревает в первой найденной впадине, которая может оказаться не самой глубокой. Имитация отжига вводит контролируемую случайность: вначале, когда «температура» высока, алгоритм готов иногда двигаться вверх, принимая худшее решение случайно. По мере снижения температуры согласно графику охлаждения, алгоритм становится все более избирательным, сходясь к решению. Эта готовность принимать худшие шаги при высокой температуре позволяет методу избегать мелких локальных оптимумов и более тщательно исследовать ландшафт.

История

Имитация отжига была представлена Kirkpatrick, Gelatt и Vecchi в их знаковой статье 1983 года в журнале Science, которая провела явную аналогию между термодинамическим отжигом твердых тел и комбинаторной оптимизацией. Та же идея была независимо предложена Cerny (1985) в контексте задачи коммивояжера. van Laarhoven и Aarts (1987) предоставили первое строгое теоретическое рассмотрение, доказав свойства сходимости при различных графиках охлаждения. С тех пор метод стал одной из наиболее широко изучаемых и применяемых метаэвристик, используемых в проектировании, исследовании операций, компоновке СБИС и настройке гиперпараметров машинного обучения.

Когда применять

Имитация отжига применима к любой задаче, где можно определить структуру соседства в пространстве решений, независимо от того, является ли целевая функция дифференцируемой, выпуклой или даже аналитически выразимой. Она особенно хорошо подходит для комбинаторных задач (составление расписаний, маршрутизация, задачи на графах) и непрерывной оптимизации «черного ящика». Не требуется никаких обучающих данных или предположений о нормальности. График охлаждения и структура соседства должны быть настроены под задачу; выполнение менее чем примерно 1 000 итераций рискует преждевременной сходимостью к локальному оптимуму, в этом случае следует предпочесть более простой детерминированный локальный поиск.

Ограничения и замечания

  • Качество решения чувствительно к графику охлаждения; плохой график может дать результаты не лучше случайного поиска.
  • Структура соседства должна быть разработана для каждого класса задач, что требует экспертных знаний в предметной области.
  • Сходимость к глобальному оптимуму на практике требует чрезвычайно медленного охлаждения, что делает время выполнения долгим для гарантий высокого качества.
  • Не использует информацию о градиенте или структуре, поэтому градиентные методы превосходят его на гладких, дифференцируемых задачах.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Может выходить из локальных оптимумов за счет вероятностного принятия худших решений, в отличие от чистого градиентного подъема.
  • Применима практически к любому типу задач — комбинаторным, непрерывным, смешанным — при условии определения структуры соседства.
  • Не требует информации о градиенте и безразлична к математической структуре целевой функции.
  • Имеет теоретическую гарантию сходимости к глобальному оптимуму при достаточно медленном охлаждении (Hajek 1988).
  • Мало гиперпараметров: начальная температура, скорость охлаждения и структура соседства.

Применение

  • Комбинаторные задачи составления расписаний и графиков, где пространство решений слишком велико для полного перебора.
  • Задачи коммивояжера и маршрутизации транспортных средств в логистике и исследовании операций.
  • Компоновка схем СБИС и планировка чипов в электротехнике.
  • Сворачивание белков и задачи молекулярной конформации в вычислительной биологии.
  • Оптимизация гиперпараметров для моделей машинного обучения при отсутствии информации о градиенте.
  • Задачи распределения ресурсов и назначения в инженерии и науке управления.

Как это работает

Как это работает

1

Алгоритм начинается с начального решения — любой допустимой точки в пространстве поиска — и высокой начальной температуры. Начальное решение может быть случайным или специфичным для задачи; начальная температура обычно устанавливается достаточно высокой, чтобы почти любое соседнее решение принималось в начале.

2

Соседнее решение генерируется путем применения небольшого случайного изменения («шага») к текущему решению. Структура соседства должна быть адаптирована к задаче: для задачи составления расписания шаг может заключаться в обмене двумя задачами; для непрерывной функции он может заключаться в добавлении небольшой случайной пертурбации к текущему вектору параметров.

3

Вычисляется разница в значении целевой функции между новым и текущим решением. Если новое решение лучше, оно всегда принимается. Если оно хуже, оно принимается с вероятностью, которая убывает с увеличением ухудшения и текущей температуры — обычно exp(−ΔE / T). Это вероятностное принятие является основным механизмом, предотвращающим преждевременную сходимость.

4

После каждой итерации (или после фиксированного числа шагов при той же температуре) температура снижается согласно графику охлаждения — обычно геометрическому графику T ← α·T, где α немного меньше 1. Выбор графика охлаждения сильно влияет на качество решения: слишком быстрое охлаждение приводит к застреванию поиска в локальном оптимуме; слишком медленное охлаждение тратит вычислительное время.

5

Алгоритм останавливается, когда температура падает ниже минимального порога, достигается максимальное число итераций или решение не улучшалось в течение заданного числа шагов. Возвращается лучшее решение, найденное за весь прогон — а не только конечное состояние.

Частые ошибки

  • Выполнение слишком малого числа итераций (примерно менее 1 000) не позволяет графику охлаждения функционировать должным образом, и поиск остается в локальном оптимуме — предпочтите табу-поиск или детерминированный локальный поиск, если время выполнения сильно ограничено.
  • Установка слишком низкой начальной температуры означает, что алгоритм немедленно ведет себя как жадный градиентный подъем и теряет способность выходить из локальных оптимумов.
  • Слишком агрессивное снижение температуры (например, α ниже 0.9) вызывает преждевременную сходимость; проверяйте качество конечного решения, перезапуская алгоритм из нескольких начальных решений.
  • Применение шага соседства, разработанного для одного типа задачи, к другой задаче может сделать шаги недопустимыми или бессмысленными — всегда проверяйте, что каждый сгенерированный сосед является допустимым решением.
  • Отчетность только о конечном состоянии, а не о лучшем найденном решении за все время работы, может привести к упущению истинного оптимума, найденного на промежуточном этапе.

Часто задаваемые вопросы

Как выбрать график охлаждения?

Геометрический график T ← α·T с α между 0.90 и 0.99 является наиболее распространенной отправной точкой. Практический подход заключается в установке начальной температуры достаточно высокой, чтобы в начале принималось примерно 80% шагов, затем ее снижение до тех пор, пока не будет приниматься менее 1% шагов вверх. Если качество конечного решения низкое, замедлите скорость охлаждения (увеличьте α); если время выполнения слишком велико, ускорьте его. Всегда запускайте алгоритм несколько раз из разных начальных решений для оценки надежности.

Чем имитация отжига отличается от генетических алгоритмов или оптимизации роем частиц?

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

Гарантирован ли глобальный оптимум?

Теоретически да, при условии, что температура снижается достаточно медленно (логарифмическое охлаждение). На практике такое охлаждение вычислительно неосуществимо, поэтому алгоритм находит почти оптимальное решение. Качество результата улучшается с замедлением охлаждения и увеличением числа итераций, но нет гарантии конечного времени. Многократные перезапуски и сохранение лучшего найденного решения — практический способ повысить уверенность.

Когда следует предпочесть табу-поиск или генетический алгоритм?

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

Похожие методы

Источники

  1. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

    Открыть ссылку DOI
    Скопировано.
  2. van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.

    ISBN: 9789027725431
    Скопировано.