Имитация отжига

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

История

Метод имитации отжига был независимо предложен несколькими исследователями в 1980-х годах. Первая формальная публикация, связывающая алгоритм с термодинамической аналогией, принадлежит Скотту Киркпатрику, Даниэлю Геллату и Марио Векки (1983 год) в статье «Optimization by Simulated Annealing» в журнале Science. Однако аналогичные идеи ранее высказывались в работах В. Черновского и Н. Метрополиса (1953 год), а также в исследованиях по статистической физике.

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

Физическая аналогия

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

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

Алгоритм

Общая схема

1. Инициализация: выбирается начальное решение \( x_0 \) и начальная температура \( T_0 \). Обычно \( T_0 \) выбирается достаточно высокой, чтобы вероятность принятия плохих решений была велика (например, 0.8–0.9).
2. Цикл по температуре:

• Для каждого значения температуры выполняется \( L \) итераций (длина марковской цепи).
• На каждой итерации генерируется новое решение \( x_{\text{new}} \) путём случайного возмущения текущего решения \( x_{\text{current}} \).
• Вычисляется изменение целевой функции \( \Delta E = f(x_{\text{new}}) - f(x_{\text{current}}) \).
• Если \( \Delta E < 0 \) (новое решение лучше), оно принимается.
• Если \( \Delta E \ge 0 \) (новое решение хуже), оно принимается с вероятностью \( P = \exp(-\Delta E / T) \) (правило Метрополиса).

1. Охлаждение: температура уменьшается по заданному закону (например, \( T_{k+1} = \alpha \cdot T_k \), где \( \alpha \) — коэффициент охлаждения, обычно 0.8–0.99).
2. Критерий остановки: алгоритм завершается, когда температура становится ниже порогового значения \( T_{\min} \) или когда за несколько итераций не происходит улучшения.

Правило Метрополиса

Вероятность принятия худшего решения определяется распределением Больцмана: \[ P(\Delta E, T) = \begin{cases} 1, & \Delta E < 0 \\ \exp\left(-\frac{\Delta E}{T}\right), & \Delta E \ge 0 \end{cases} \] При высокой температуре \( T \) вероятность принятия плохих решений близка к 1, что позволяет алгоритму «исследовать» пространство поиска. При низкой температуре вероятность стремится к нулю, и алгоритм «эксплуатирует» лучшие решения.

Параметры алгоритма

Эффективность имитации отжига существенно зависит от выбора параметров:

• Начальная температура \( T_0 \). Слишком низкая температура приводит к преждевременной сходимости к локальному минимуму; слишком высокая — к неоправданно долгому времени работы. Часто \( T_0 \) подбирается эмпирически или вычисляется на основе среднего изменения целевой функции на первых итерациях.
• Скорость охлаждения (коэффициент \( \alpha \)). Медленное охлаждение (высокое \( \alpha \)) увеличивает точность, но требует больше времени. Быстрое охлаждение (низкое \( \alpha \)) ускоряет работу, но может ухудшить качество решения.
• Длина марковской цепи \( L \). Определяет количество итераций при каждой температуре. Чем больше \( L \), тем лучше исследуется пространство, но выше вычислительные затраты.
• Критерий остановки. Обычно — достижение температуры \( T_{\min} \) или стагнация целевой функции на протяжении заданного числа итераций.

Модификации

Существует несколько вариантов и улучшений базового алгоритма:

• Адаптивное охлаждение. Температура изменяется не по фиксированному закону, а в зависимости от поведения целевой функции (например, ускорение при стагнации).
• Параллельная имитация отжига. Запуск нескольких цепочек алгоритма на разных процессорах с обменом лучшими решениями.
• Имитация отжига с отжигом по времени. Вместо температуры используется количество оставшихся итераций.
• Квантовая имитация отжига — гибридный метод, использующий квантовые туннельные эффекты для преодоления энергетических барьеров.
• Метод «быстрого отжига» — использует распределение Коши вместо распределения Больцмана для генерации новых решений, что позволяет быстрее исследовать пространство.

Применение

Имитация отжига применяется в широком спектре задач, где требуется найти приближённое решение в условиях большой размерности или нелинейности:

• Комбинаторная оптимизация: задача коммивояжёра, задача о назначениях, задача о рюкзаке, раскраска графа, разбиение графа.
• Проектирование интегральных схем: размещение элементов, трассировка соединений, минимизация площади.
• Машинное обучение: настройка гиперпараметров нейронных сетей, обучение моделей с большим числом параметров, выбор признаков.
• Обработка изображений: сегментация, реконструкция, восстановление изображений.
• Биоинформатика: выравнивание последовательностей, предсказание структуры белков.
• Экономика и финансы: оптимизация портфеля инвестиций, маршрутизация транспорта.
• Физика и химия: моделирование молекулярных структур, расчёт конформаций.

Преимущества и недостатки

Преимущества

• Способность избегать локальных минимумов за счёт вероятностного принятия худших решений.
• Простота реализации и отсутствие требований к дифференцируемости целевой функции.
• Универсальность: применим как для дискретных, так и для непрерывных задач.
• Гарантированная сходимость к глобальному оптимуму при бесконечном времени работы (теоретически).

Недостатки

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

Сравнение с другими методами

Имитация отжига часто сравнивается с другими метаэвристиками:

• Генетические алгоритмы (ГА): оба метода основаны на случайности, но ГА используют популяцию решений и операции скрещивания и мутации. Имитация отжига проще в настройке, но может быть медленнее на задачах с большим числом локальных минимумов.
• Метод роя частиц (PSO): PSO быстрее сходится в некоторых задачах, но склонен к преждевременной сходимости. Имитация отжига более устойчива к локальным минимумам.
• Табу-поиск: использует память для предотвращения повторения решений, что может быть эффективнее для комбинаторных задач, но требует больше памяти.
• Метод имитации отжига с отжигом по времени — более простой вариант, где температура заменяется на количество оставшихся итераций.

Интересные факты

• В 1983 году статья Киркпатрика была отклонена несколькими журналами из-за «недостаточной математической строгости», но позже стала одной из самых цитируемых в области оптимизации.
• Алгоритм имитации отжига используется в некоторых современных процессорах для автоматической разводки транзисторов.
• В 2010-х годах квантовая имитация отжига была реализована в коммерческих квантовых компьютерах компании D-Wave.

Источники

• Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671–680.
• Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21(6), 1087–1092.
• Aarts, E., Korst, J. (1989). Simulated Annealing and Boltzmann Machines. John Wiley & Sons.
• Ingber, L. (1989). Very fast simulated re-annealing. Mathematical and Computer Modelling, 12(8), 967–973.
• Романов, В. Н. (2005). Методы оптимизации: учебное пособие. Издательство СПбГУ.