🔴 Сложный ⏱️ 50 минут

Simulated Annealing

📋 Содержание урока

Simulated Annealing 🔥

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

Simulated Annealing, метод имитации отжига, — это алгоритм оптимизации, который буквально симулирует этот физический процесс на компьютере, только вместо атомов металла у него кандидаты-решения оптимизационной задачи, а вместо тепловой энергии кристаллической решётки — значение целевой функции, которое нужно минимизировать. Как и остывающий металл, алгоритм начинает работу «горячим»: на старте он готов принимать почти любые ходы, включая те, что временно ухудшают решение, — это позволяет ему широко исследовать пространство поиска и не увязнуть в первой попавшейся ложбине. По мере хода оптимизации управляющий параметр — температура $T$ — постепенно снижается, и алгоритм становится всё разборчивее: под конец он, как и остывший металл, принимает почти исключительно улучшающие ходы, аккуратно доводя решение до устойчивого состояния.

Здесь стоит сразу провести параллель, которая пригодится тебе не только в оптимизации, но и в повседневной работе с языковыми моделями. Когда ты генерируешь текст с помощью GPT-подобной модели и выставляешь параметр temperature в запросе к API, ты управляешь буквально тем же самым принципом. Softmax-распределение вероятностей следующего токена при высокой температуре становится более «плоским» и случайным — модель охотнее выбирает не самый вероятный токен, а один из многих правдоподобных, генерация получается разнообразнее и «креативнее». При низкой температуре softmax становится «острым»: модель почти всегда выбирает наиболее вероятный токен, генерация — предсказуемая и консервативная. Это не поверхностное сходство названий: и там, и там температура буквально управляет тем, насколько система готова отклониться от «жадного», наиболее очевидного выбора ради более широкого исследования пространства возможностей. В методе отжига высокая температура означает готовность принять частично «плохой» ход ради шанса найти лучшее решение дальше; в сэмплировании языковой модели высокая температура означает готовность выбрать не самый вероятный токен ради более разнообразного текста. Ты увидишь эту параллель ещё раз чуть позже, когда разберёшь формулу критерия принятия Метрополиса — она структурно очень похожа на формулу softmax.

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

История

Идея метода имитации отжига родилась на стыке статистической физики и вычислительной оптимизации, и у неё было предвестие за тридцать лет до её формального появления. В 1953 году группа физиков — Николас Метрополис, Ариана Розенблют, Маршалл Розенблют, Августа Теллер и Эдвард Теллер — опубликовала статью «Equation of State Calculations by Fast Computing Machines», в которой описала алгоритм для моделирования поведения систем частиц при заданной температуре методом Монте-Карло. Ключевая идея этой статьи — правило, по которому симуляция решает, принять ли новое, случайно предложенное состояние системы частиц: если новое состояние обладает более низкой энергией — принять его безоговорочно, если более высокой — принять его лишь с некоторой вероятностью, зависящей от того, насколько сильно выросла энергия, и от температуры системы. Это правило вошло в историю как критерий Метрополиса, и именно оно почти три десятилетия спустя стало математическим сердцем метода имитации отжига.

В 1983 году трое исследователей из исследовательского подразделения IBM — Скотт Киркпатрик (Scott Kirkpatrick), Даниэль Гелатт (C. Daniel Gelatt) и Марио Веччи (Mario P. Vecchi) — опубликовали в журнале Science статью «Optimization by Simulated Annealing». Киркпатрик, физик по образованию, работал над задачами проектирования компьютерных схем — в частности, над размещением элементов на кристалле так, чтобы минимизировать общую длину соединяющих их проводников. Эта задача комбинаторной оптимизации по своей структуре была пугающе похожа на модели статистической физики, с которыми Киркпатрик уже был знаком: огромное дискретное пространство состояний, целевая функция с множеством локальных минимумов, и никакого разумного способа перебрать все варианты. Авторы предложили прямую аналогию: пусть целевая функция оптимизационной задачи играет роль энергии физической системы, пусть решения-кандидаты играют роль конфигураций этой системы, и пусть алгоритм оптимизации исследует пространство решений точно так же, как критерий Метрополиса заставляет физическую систему исследовать пространство состояний при заданной температуре, — с постепенным понижением температуры по определённому расписанию, имитирующему отжиг металла.

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

Аналогия с отжигом металла и роль температуры

Интуиция

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

В оптимизационной задаче это переводится буквально. У алгоритма есть текущее решение $x$, целевая функция $E(x)$ (традиционно её называют «энергией», следуя физической метафоре, даже если задача не имеет ничего общего с физикой), и управляющий параметр $T$ — температура. На каждом шаге алгоритм генерирует «соседнее» решение-кандидата $x'$ — например, слегка изменённую версию текущего решения — и решает, принять его или остаться на месте, руководствуясь значением $\Delta E = E(x') - E(x)$ и текущей температурой $T$. Пока $T$ велико, алгоритм ведёт себя почти как случайное блуждание по пространству решений, готовое принять даже заметные ухудшения. Когда $T$ приближается к нулю, поведение алгоритма стягивается к обычному жадному локальному поиску: принимаются практически только улучшающие ходы.

Формальное определение

Общая схема Simulated Annealing. Дана целевая функция $E(x)$, которую нужно минимизировать, начальное решение $x_0$, начальная температура $T_0$ и расписание охлаждения $T(t)$, убывающее с номером итерации $t$. На каждой итерации:

  1. Сгенерировать случайного соседа $x'$ текущего решения $x$ (например, небольшим случайным возмущением).
  2. Вычислить $\Delta E = E(x') - E(x)$.
  3. Принять $x'$ как новое текущее решение с вероятностью, определяемой критерием Метрополиса (см. следующий раздел), иначе остаться в $x$.
  4. Понизить температуру согласно расписанию охлаждения и перейти к следующей итерации.
  5. Всё время отдельно запоминать лучшее из всех когда-либо посещённых решений — алгоритм может временно уйти в худшую область, но не должен «забывать» лучший результат.
def simulated_annealing(x0, energy, neighbor, T0, cooling_schedule, iterations):
    x = x0
    best_x, best_energy = x0, energy(x0)
    T = T0
    for t in range(iterations):
        x_candidate = neighbor(x)
        delta_e = energy(x_candidate) - energy(x)
        if delta_e < 0 or random.random() < math.exp(-delta_e / T):
            x = x_candidate
            if energy(x) < best_energy:
                best_x, best_energy = x, energy(x)
        T = cooling_schedule(T0, t, iterations)
    return best_x, best_energy

Обрати внимание: алгоритм оперирует текущим решением $x$, которое может временно быть хуже уже найденного лучшего решения best_x — именно поэтому его нужно отслеживать отдельной переменной. Без этого алгоритм рисковал бы «забыть» лучший результат, случайно уйдя из него на высокой температуре и не успев вернуться.

Примеры

Пример 1: горячий старт против холодного старта. Пусть целевая функция имеет два локальных минимума — мелкий при $E=10$ и глубокий, глобальный, при $E=2$, разделённые барьером с энергией $E=15$ где-то посередине пространства решений. Алгоритм локального поиска (эквивалент отжига при $T=0$ на каждом шаге), стартовавший рядом с мелким минимумом, никогда не пересечёт барьер — любой ход в сторону барьера ухудшает $E$, а при нулевой температуре ухудшающие ходы запрещены категорически. Алгоритм имитации отжига со стартовой температурой $T_0 = 20$ на ранних итерациях способен принять ход с $\Delta E$ до барьера порядка $5$–$10$ с ощутимой вероятностью (это будет видно из расчёта критерия Метрополиса в следующем разделе) — и таким образом имеет реальный шанс перевалить через барьер и «скатиться» в глубокий глобальный минимум ещё до того, как температура упадёт настолько, что подобные ухудшения станут практически недостижимы.

Пример 2: качественное поведение траектории во времени. На первых итерациях при высокой температуре траектория $x_t$ выглядит почти как случайное блуждание — значение $E(x_t)$ то растёт, то падает, довольно хаотично мечась по широкому диапазону значений. По мере остывания траектория постепенно «успокаивается»: размах колебаний $E(x_t)$ сокращается, а сама траектория всё чаще движется вниз. На финальных, самых холодных итерациях поведение становится почти монотонным — алгоритм фактически превращается в жадный локальный поиск, точечно доводящий уже найденную хорошую область до локального минимума.

Пример 3: температура как единственный переключатель режима. Возьми один и тот же алгоритм с одной и той же функцией neighbor и целевой функцией $E$, но зафиксируй температуру константой вместо расписания охлаждения. При $T \to 0$ (константа, близкая к нулю) алгоритм ведёт себя как чистый жадный локальный поиск (hill climbing) — принимает практически только улучшения. При очень большой константной $T$ (скажем, $T=10^6$ при типичных значениях $\Delta E$ порядка единиц) алгоритм принимает почти любой ход независимо от его качества и превращается в почти случайное блуждание по пространству решений, почти не сходясь к оптимуму вообще. Именно поэтому температура должна не оставаться константой, а именно убывать по расписанию — только переход от одного крайнего режима к другому в течение оптимизации даёт методу отжига его характерное поведение: широкий поиск в начале, точная доводка в конце.

Почему это важно

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

Критерий принятия Метрополиса

Интуиция

Представь, что ты стоишь у подножия холмистого ландшафта, где высота в каждой точке — это значение целевой функции $E(x)$, а твоя цель — найти самую глубокую впадину. Простейшая стратегия — жадный локальный поиск: делать шаг только туда, где ниже, чем сейчас, и никогда не подниматься вверх. Проблема очевидна — если ты оказался в мелкой ямке, ты в ней и останешься, даже если в двух шагах отсюда есть пропасть куда глубже. Критерий Метрополиса — это правило, которое время от времени разрешает тебе подняться вверх, причём не наугад с фиксированной вероятностью, а разумно: чем меньше подъём, тем охотнее ты на него соглашаешься, а чем сильнее ты «разогрет» — тем больше подъёмов ты готов стерпеть.

Формально критерий Метрополиса даёт правило принятия любого хода — и улучшающего, и ухудшающего, — в терминах разницы энергий $\Delta E$ между кандидатом и текущим решением, а также текущей температуры $T$.

Формальное определение

Критерий принятия Метрополиса. Пусть $\Delta E = E(x') - E(x)$ — изменение целевой функции при переходе от текущего решения $x$ к кандидату $x'$. Вероятность принятия кандидата $x'$ равна

$$P(\text{принять}) = \begin{cases} 1, & \Delta E \le 0 \\[4pt] \exp\!\left(-\dfrac{\Delta E}{T}\right), & \Delta E > 0 \end{cases}$$

Если $\Delta E \le 0$ (кандидат не хуже текущего решения), он принимается безусловно. Если $\Delta E > 0$ (кандидат хуже), он принимается с вероятностью $\exp(-\Delta E / T)$, а иначе алгоритм остаётся в текущей точке $x$ на этой итерации.

Обе ветви можно объединить в одну универсальную формулу $P(\text{принять}) = \min\bigl(1,\ \exp(-\Delta E / T)\bigr)$, потому что при $\Delta E \le 0$ показатель степени неотрицателен, а значит $\exp(-\Delta E/T) \ge 1$, и минимум с единицей корректно даёт безусловное принятие.

Стоит проговорить прямую алгебраическую параллель с softmax, о которой шла речь во вступлении. Softmax-вероятность выбора токена с логитом $z_i$ при температуре $T$ записывается как $P(i) = \dfrac{\exp(z_i/T)}{\sum_j \exp(z_j/T)}$ — то есть тоже экспонента от величины, делённой на температуру, с той же качественной ролью $T$: при $T \to 0$ распределение вырождается в выбор одного максимального значения (аналог жадного локального поиска), при $T \to \infty$ распределение становится равномерным (аналог полностью случайного блуждания). Критерий Метрополиса — это, по сути, несимметричная, «однонаправленная» версия того же самого принципа: не полное распределение по всем возможным ходам, а бинарное решение «принять/отклонить» один конкретный предложенный ход.

Примеры

Пример 1: явный численный расчёт при небольшом ухудшении и высокой температуре. Пусть $\Delta E = 2$ (кандидат хуже текущего решения на 2 единицы энергии), а температура $T = 10$ (алгоритм ещё «горячий», в начале оптимизации). Тогда

$$P(\text{принять}) = \exp\left(-\frac{2}{10}\right) = \exp(-0{,}2) \approx 0{,}819$$

Вероятность принятия — около 82%. При высокой температуре и небольшом ухудшении алгоритм почти наверняка согласится на такой ход, продолжая широко исследовать пространство решений.

Пример 2: тот же $\Delta E$, но низкая температура. Возьмём то же ухудшение $\Delta E = 2$, но теперь температура опустилась до $T = 0{,}5$ (поздняя стадия оптимизации). Тогда

$$P(\text{принять}) = \exp\left(-\frac{2}{0{,}5}\right) = \exp(-4) \approx 0{,}0183$$

Вероятность принятия упала до 1,8%. Один и тот же по величине ухудшающий ход, который на высокой температуре почти наверняка был бы принят, на низкой температуре практически заблокирован — это и есть механизм, за счёт которого алгоритм со временем «остывает» и всё больше напоминает жадный локальный поиск.

Пример 3: сравнение сильного и слабого ухудшения при одной и той же температуре. Зафиксируем температуру $T=5$ и сравним два кандидата: один с небольшим ухудшением $\Delta E_1 = 1$, другой с сильным ухудшением $\Delta E_2 = 8$. Для первого: $P_1 = \exp(-1/5) = \exp(-0{,}2) \approx 0{,}819$. Для второго: $P_2 = \exp(-8/5) = \exp(-1{,}6) \approx 0{,}202$. При одной и той же температуре слабое ухудшение принимается в четыре раза охотнее, чем сильное, — критерий Метрополиса не просто «иногда разрешает ухудшение», а делает это пропорционально тому, насколько велика цена ошибки: мелкие шероховатости прощаются легко, серьёзные откаты — редко, даже когда система ещё довольно «горячая».

Почему это важно

Критерий Метрополиса — это математическое ядро всего метода, и именно от него зависит, работает ли алгоритм вообще так, как задумано. Если заменить экспоненциальную формулу на что-то более грубое — скажем, на фиксированную вероятность принятия любого ухудшения независимо от его величины, — алгоритм либо будет слишком часто соглашаться на катастрофические откаты назад, либо, наоборот, слишком консервативно откажется от полезных исследовательских шагов. Экспоненциальная зависимость от $\Delta E/T$ обеспечивает ровно нужный баланс: небольшие шероховатости рельефа целевой функции преодолеваются легко почти на любой температуре, а крупные провалы требуют по-настоящему высокой температуры, чтобы через них решиться перепрыгнуть, — и именно поэтому расписание охлаждения, определяющее, как долго алгоритм остаётся достаточно «горячим», критически влияет на итоговое качество результата.

Расписания охлаждения температуры

Интуиция

Раз температура — это тот самый переключатель между широким исследованием и точной доводкой, то то, как быстро она понижается со временем, определяет весь компромисс между качеством найденного решения и временем работы алгоритма. Слишком быстрое охлаждение — алгоритм «замерзает» преждевременно, застряв в случайной, необязательно хорошей области, точь-в-точь как резко закалённый металл получает хрупкую структуру с дефектами. Слишком медленное охлаждение — алгоритм действительно находит очень качественное решение, но ценой огромного количества итераций, многие из которых тратятся впустую на почти бесполезные блуждания при всё ещё высокой температуре. Расписание охлаждения (cooling schedule) — это явная функция, которая задаёт значение температуры $T$ как функцию номера итерации или доли пройденного времени.

Формальное определение

Линейное расписание охлаждения.

$$T(t) = T_0 - \alpha \cdot t$$

где $\alpha$ — константа скорости охлаждения, $t$ — номер итерации. Температура убывает равными шагами и должна быть остановлена (или заменена малым положительным значением) при приближении к нулю, чтобы избежать деления на ноль в критерии Метрополиса.

Геометрическое (экспоненциальное) расписание охлаждения.

$$T(t) = T_0 \cdot \alpha^t, \qquad 0 < \alpha < 1$$

где $\alpha$ — коэффициент охлаждения за одну итерацию (обычно $\alpha$ близко к единице, например $0{,}95$–$0{,}99$, чтобы охлаждение было постепенным). Это самое распространённое расписание на практике: температура убывает пропорционально своему текущему значению, а не фиксированными абсолютными шагами.

Логарифмическое расписание (теоретическая гарантия сходимости).

$$T(t) = \frac{T_0}{\ln(1+t)}$$

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

Примеры

Пример 1: числовой расчёт геометрического расписания. Пусть $T_0 = 100$, $\alpha = 0{,}95$. Через 10 итераций: $T(10) = 100 \cdot 0{,}95^{10} \approx 100 \cdot 0{,}599 \approx 59{,}9$. Через 50 итераций: $T(50) = 100 \cdot 0{,}95^{50} \approx 100 \cdot 0{,}0769 \approx 7{,}7$. Через 200 итераций: $T(200) = 100 \cdot 0{,}95^{200} \approx 100 \cdot 0{,}0000350 \approx 0{,}0035$. Видно, что температура убывает не равномерно, а стремительно замедляясь в абсолютных числах: первые 50 итераций «сжигают» больше 92% начальной температуры, а дальнейшее охлаждение проходит уже во всё более узком, низкотемпературном диапазоне.

Пример 2: сравнение линейного и геометрического расписаний на одном и том же числе итераций. Пусть нужно пройти от $T_0=100$ до около $T\approx1$ за 100 итераций. Линейное расписание с $\alpha = (100-1)/100 = 0{,}99$ даёт $T(50) = 100 - 0{,}99\cdot50 = 50{,}5$ — ровно половину пути на полпути по итерациям. Геометрическое расписание с коэффициентом, подобранным так, чтобы тоже дойти от 100 до 1 за 100 шагов ($\alpha = (1/100)^{1/100} \approx 0{,}955$), даёт $T(50) = 100\cdot0{,}955^{50}\approx 100\cdot0{,}0977\approx9{,}77$ — то есть уже на середине пути по итерациям температура упала почти до 10, а не до 50. Геометрическое расписание тратит относительно больше времени «горячим» в начале (где исследование особенно ценно) и быстрее «дожимает» финальную доводку — этим и объясняется его популярность на практике по сравнению с линейным.

Пример 3: эффект слишком быстрого охлаждения на конкретной задаче. Пусть у целевой функции есть барьер высотой $\Delta E_{\text{барьер}} = 6$, который нужно перепрыгнуть, чтобы попасть в глобальный минимум, а типичное время, необходимое алгоритму, чтобы «нащупать» подходящий ход в сторону барьера, — порядка 30 итераций. Если расписание охлаждения выбрано так агрессивно, что уже к 30-й итерации $T$ упало до $0{,}3$, то вероятность принятия хода через барьер составит $\exp(-6/0{,}3) = \exp(-20) \approx 2\times10^{-9}$ — практически нулевой шанс. Тот же барьер при более щадящем расписании, где к 30-й итерации $T$ всё ещё около $4$, даёт $\exp(-6/4) = \exp(-1{,}5) \approx 0{,}223$ — вполне реальный шанс на успех за разумное число попыток. Разница между «слишком быстро остыл» и «остыл достаточно медленно» здесь буквально решает, найдёт ли алгоритм глобальный оптимум или навсегда застрянет по одну сторону барьера.

Почему это важно

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

Выход из локальных минимумов и задача коммивояжёра

Интуиция

Собери воедино всё, что ты уже разобрал: критерий Метрополиса даёт вероятностный, а не категорический запрет на ухудшающие ходы, а высокая температура делает эту вероятность существенной даже для заметных ухудшений. Это ровно то свойство, которого категорически лишён чисто жадный локальный поиск (hill climbing): он принимает решение «застрять» в первом же локальном минимуме мгновенно и безвозвратно, потому что по определению никогда не делает шаг, ухудшающий целевую функцию. Метод имитации отжига на высокой температуре способен «перепрыгнуть» через энергетический барьер, отделяющий текущий локальный минимум от более глубокого — потенциально глобального — минимума где-то ещё в пространстве решений, именно потому, что временное ухудшение ему не запрещено, а лишь статистически менее вероятно, чем улучшение.

Формальное определение

Почему жадный локальный поиск гарантированно застревает. Пусть $x^*$ — локальный минимум целевой функции $E$: для любого соседа $x'$ из окрестности $x^*$ выполняется $E(x') \ge E(x^*)$. Жадный локальный поиск по определению принимает только ходы с $E(x') < E(x)$, значит, оказавшись в $x^*$, он не может покинуть эту точку никогда — вероятность выхода равна нулю тождественно.

Почему Simulated Annealing может выйти из локального минимума. При $T > 0$ для любого соседа $x'$ с $\Delta E = E(x') - E(x^*) > 0$ вероятность принятия $\exp(-\Delta E/T)$ строго больше нуля. Значит, вероятность оставаться в $x^*$ бесконечно долго строго меньше единицы — с ненулевой вероятностью алгоритм рано или поздно сделает ход наружу из локального минимума, и чем выше температура (или чем меньше барьер $\Delta E$), тем эта вероятность выше и тем быстрее это произойдёт в среднем.

Классическая иллюстрация: задача коммивояжёра

Задача коммивояжёра (traveling salesman problem, TSP) — классический полигон для демонстрации метода имитации отжига, и не случайно: у неё огромное, комбинаторно растущее пространство решений (для $n$ городов существует $(n-1)!/2$ различных маршрутов при неориентированном цикле), простая целевая функция (суммарная длина маршрута, которую нужно минимизировать) и естественное определение «соседа» текущего решения.

Представление решения. Решение — это перестановка городов, задающая порядок посещения, например маршрут через 6 городов: $[1, 4, 2, 6, 3, 5]$ (и обратно в город 1, замыкая цикл).

Целевая функция. $E(\text{маршрут}) = \sum_{i} \text{расстояние}(\text{город}_i, \text{город}_{i+1})$ — суммарная длина маршрута, включая возврат в исходную точку.

Генерация соседа. Самый распространённый оператор — 2-opt: выбрать два случайных ребра маршрута и «развернуть» участок пути между ними. Например, из маршрута $[1,4,2,6,3,5]$, выбрав разворот участка между позициями 2 и 4, получаем $[1,4,6,2,3,5]$ — локальное, небольшое изменение маршрута, которое обычно меняет суммарную длину лишь незначительно.

Примеры

Пример 1: конкретный шаг 2-opt и его энергия. Пусть текущий маршрут $[A, B, C, D, E]$ имеет суммарную длину $E(x) = 42$. Разворот участка $[B,C,D]$ даёт кандидата $[A, D, C, B, E]$ с пересчитанной длиной $E(x') = 45$. Тогда $\Delta E = 3$. При температуре $T = 6$ вероятность принятия — $\exp(-3/6) = \exp(-0{,}5) \approx 0{,}607$ — алгоритм примет этот чуть более длинный маршрут почти в двух случаях из трёх, продолжая исследовать соседние конфигурации, вместо того чтобы намертво зациклиться на маршруте длины 42, если тот на самом деле не был оптимальным.

Пример 2: почему локальный поиск на TSP легко застревает. Возьмём маршрут, в котором любой единичный 2-opt-разворот увеличивает суммарную длину — то есть маршрут является локальным оптимумом относительно оператора 2-opt. Известно, что таких локальных оптимумов у типичной задачи TSP на 50 и более городах может быть очень много, и лишь ничтожная их доля совпадает с истинным глобальным минимумом. Жадный локальный поиск, стартовавший из случайной точки, с высокой вероятностью сойдётся к одному из многочисленных «посредственных» локальных оптимумов и никогда его не покинет. Имитация отжига с ненулевой температурой сохраняет шанс продолжить блуждание даже из такого локального оптимума, постепенно исследуя соседние конфигурации в поисках более глубокого минимума.

Пример 3: типичная динамика на практике. На реалистичной задаче TSP из нескольких сотен городов с геометрическим расписанием охлаждения и разумно подобранной стартовой температурой метод имитации отжига типично проходит три фазы: на раннем, «горячем» этапе суммарная длина маршрута колеблется довольно широко, временами заметно ухудшаясь; на среднем этапе колебания сужаются, а общий тренд длины маршрута устойчиво идёт вниз; на позднем, «холодном» этапе алгоритм лишь изредка принимает крошечные ухудшения и в целом ведёт себя как локальный поиск, аккуратно дотачивающий уже почти готовое решение. Итоговые маршруты, полученные имитацией отжига, на практике типично на 5–15% короче тех, что даёт чисто жадный локальный поиск из той же стартовой точки — именно за счёт способности перепрыгивать барьеры на ранней, «горячей» стадии.

Почему это важно

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

ML-применения: гиперпараметры, кластерные расписания и температура softmax

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

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

Комбинаторные задачи в ML-инфраструктуре. Размещение вычислительных задач обучения моделей на кластере GPU — классическая комбинаторная задача: нужно распределить множество задач по ограниченному числу узлов так, чтобы минимизировать суммарное время выполнения или простой ресурсов, учитывая зависимости между задачами и неоднородность узлов по вычислительной мощности. Пространство возможных распределений огромно и дискретно, целевая функция (общее время выполнения) легко вычисляется для конкретного распределения, но не дифференцируема по своей природе — ровно тот случай, где имитация отжига (наряду с генетическими алгоритмами из урока 296) оказывается практичным инструментом, тогда как градиентные методы неприменимы в принципе.

Температура softmax при генерации текста. Эта параллель заслуживает того, чтобы вернуться к ней ещё раз, уже вооружившись полным пониманием критерия Метрополиса. Когда языковая модель сэмплирует следующий токен, она делит логиты на температуру $T$ перед применением softmax: $P(i) \propto \exp(z_i/T)$. При $T=1$ используется исходное распределение модели. При $T<1$ распределение заостряется — модель ведёт себя более «жадно» и предсказуемо, почти всегда выбирая наиболее вероятный токен, что соответствует низкотемпературному режиму имитации отжига, где почти всегда выбираются только «улучшающие» (наиболее вероятные) ходы. При $T>1$ распределение выравнивается — модель чаще выбирает менее вероятные токены, генерация становится разнообразнее и «рискованнее», что напрямую соответствует высокотемпературному режиму отжига, где система охотно исследует менее очевидные варианты. Это не метафора «для красоты» — это буквально одна и та же математическая конструкция (экспонента от величины, делённой на температуру), применённая в двух разных контекстах: в одном случае она управляет вероятностью принятия конкретного предложенного хода оптимизации, в другом — распределением вероятностей по следующему токену последовательности.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Вычисли вероятность принятия хода по критерию Метрополиса при $\Delta E = 4$ и $T = 8$.

Задание 2: Вычисли вероятность принятия хода при $\Delta E = -3$ (то есть решение улучшилось) и $T = 2$.

Задание 3: При $T_0 = 50$ и геометрическом коэффициенте охлаждения $\alpha = 0{,}9$ вычисли температуру после 5 итераций.

Задание 4: При линейном расписании $T(t) = 100 - 2t$ найди, на какой итерации температура впервые станет неположительной.

Задание 5: Сравни вероятности принятия хода с $\Delta E = 5$ при $T=1$ и при $T=100$, не вычисляя точные значения — только качественно объясни разницу.

Задание 6: Что произойдёт с алгоритмом Simulated Annealing, если зафиксировать температуру константой, равной очень большому числу, и никогда её не понижать?

Задание 7: Что произойдёт, если стартовать сразу с $T_0 \approx 0$?

Задание 8: Дан маршрут TSP длиной 60. После 2-opt-разворота получен кандидат длиной 63. Вычисли $\Delta E$.

Задание 9: Используя $\Delta E$ из задания 8 и температуру $T=4$, вычисли вероятность принятия этого хода.

Задание 10: Объясни своими словами, почему в алгоритме отдельно хранят переменную best_x, а не просто возвращают финальное текущее решение после последней итерации.

Продвинутые задания (11–20)

Задание 11: При $\Delta E = 2$ найди температуру $T$, при которой вероятность принятия хода равна ровно $0{,}5$.

Задание 12: Два кандидата имеют $\Delta E_1 = 1$ и $\Delta E_2 = 10$ при одной и той же температуре $T=5$. Вычисли отношение вероятностей их принятия $P_1/P_2$.

Задание 13: Геометрическое расписание $T(t) = T_0 \alpha^t$ должно уменьшить температуру со $100$ до $1$ ровно за $t=50$ итераций. Найди $\alpha$.

Задание 14: Объясни, почему линейное расписание охлаждения $T(t) = T_0 - \alpha t$ рискованно использовать без дополнительной проверки на последних итерациях.

Задание 15: На задаче TSP из 8 городов оцени порядок числа различных маршрутов (перестановок с точностью до направления обхода и стартовой точки), используя формулу $(n-1)!/2$.

Задание 16: Докажи (используя критерий Метрополиса), что вероятность остаться в локальном минимуме навсегда строго меньше единицы при любой температуре $T>0$, если у него есть хотя бы один сосед с конечным $\Delta E$.

Задание 17: Объясни, почему при $T \to 0$ формула $P = \min(1, \exp(-\Delta E/T))$ превращает Simulated Annealing в обычный жадный локальный поиск (hill climbing).

Задание 18: В softmax-сэмплировании языковой модели при $T \to 0$ распределение вырождается в выбор единственного токена с максимальным логитом. Проведи аналогию с поведением Simulated Annealing при $T \to 0$.

Задание 19: Почему для задачи коммивояжёра оператор 2-opt (разворот участка маршрута) — удачный выбор функции генерации соседа для Simulated Annealing, а, скажем, полностью случайная перестановка всех городов — плохой выбор?

Задание 20: Дан маршрут TSP с суммарной длиной $E=80$. За 2-opt-разворот получен кандидат $E'=77$. Что произойдёт в алгоритме независимо от текущей температуры?

Задания-челленджи (21–30)

Задание 21: Объясни, почему логарифмическое расписание охлаждения $T(t) = T_0/\ln(1+t)$, дающее теоретическую гарантию сходимости к глобальному оптимуму, почти никогда не используется на практике.

Задание 22: Придумай и опиши схему адаптивного расписания охлаждения, где скорость понижения температуры зависит от того, как часто алгоритм в последнее время принимает ухудшающие ходы, а не от фиксированной формулы времени.

Задание 23: Оптимизация гиперпараметров модели через Simulated Annealing: опиши, что здесь будет играть роль «соседнего решения» и почему вычисление $\Delta E$ для одного шага здесь заметно дороже, чем в задаче TSP.

Задание 24: Сравни концептуально Simulated Annealing и генетические алгоритмы (урок 296) с точки зрения того, как каждый из них справляется с локальными минимумами.

Задание 25: Размещение задач обучения моделей на кластере GPU через Simulated Annealing: предложи целевую функцию $E$ и опиши, что будет являться «соседним» распределением задач.

Задание 26: Объясни, почему при $\Delta E$, выраженном в существенно разных единицах измерения (например, если целевая функция — не длина маршрута в километрах, а сумма штрафов в условных единицах порядка миллионов), нельзя использовать одно и то же значение стартовой температуры $T_0$ без адаптации к масштабу задачи.

Задание 27: Докажи, что при фиксированной температуре $T$ отношение вероятностей принятия двух кандидатов с ухудшениями $\Delta E_1$ и $\Delta E_2$ равно $\exp\bigl((\Delta E_2 - \Delta E_1)/T\bigr)$, и объясни, как из этой формулы следует, что при $T \to \infty$ все ухудшения становятся «примерно равновероятными» для принятия.

Задание 28: Языковая модель генерирует текст с температурой $T=0{,}2$ (низкая) для юридического документа и с температурой $T=1{,}3$ (высокая) для черновика художественного рассказа. Объясни этот выбор в терминах компромисса «исследование против использования», знакомого тебе из метода имитации отжига.

Задание 29: Обобщая пройденный блок метаэвристик (эволюционные алгоритмы, генетические алгоритмы, PSO, Simulated Annealing), сформулируй общий признак, объединяющий все методы этого семейства, и одно ключевое отличие Simulated Annealing от остальных трёх.

Задание 30: Спроектируй гибридную схему: сначала запустить генетический алгоритм (урок 296) для грубого глобального поиска перспективной области, а затем Simulated Annealing с невысокой стартовой температурой для точной доводки лучшего найденного решения. Объясни, почему такая последовательность имеет смысл.

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

Ошибка 1. Считают, что Simulated Annealing гарантированно находит глобальный оптимум на любой практической задаче.

Как выглядит: «раз метод умеет выходить из локальных минимумов, он рано или поздно точно найдёт лучшее решение».

Почему возникает: теоретическая гарантия сходимости к глобальному оптимуму действительно существует, но только при очень медленном (логарифмическом) расписании охлаждения, которое практически никогда не используется.

Как правильно: на практике, с реалистичными геометрическими или линейными расписаниями, метод даёт хорошее, но не гарантированно оптимальное решение — это метаэвристика, а не точный алгоритм с доказанными границами качества за разумное время.

Ошибка 2. Путают роль критерия Метрополиса, считая, что он принимает любые ходы с заданной фиксированной вероятностью, а не в зависимости от величины ухудшения.

Как выглядит: «вероятность принятия ухудшающего хода на этой итерации — 30%, и всё».

Почему возникает: упрощённое понимание метода как «иногда соглашаться на ухудшение» без внимания к тому, что вероятность экспоненциально зависит от $\Delta E$ и $T$.

Как правильно: вероятность принятия конкретного хода всегда вычисляется по формуле $\exp(-\Delta E/T)$ индивидуально для каждого кандидата — небольшие ухудшения принимаются охотно, крупные значительно реже, при одной и той же температуре.

Ошибка 3. Выбирают стартовую температуру $T_0$ «на глаз», без учёта реального масштаба значений $\Delta E$ в конкретной задаче.

Как выглядит: копирование значения $T_0$ из чужого примера кода без пересчёта под свою целевую функцию.

Почему возникает: кажется, что температура — универсальный параметр, тогда как на самом деле она имеет смысл только относительно масштаба $\Delta E$ данной задачи.

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

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

Как выглядит: возврат текущего $x$ после цикла оптимизации вместо отдельно отслеживаемого best_x.

Почему возникает: в детерминированных методах локального поиска текущее решение и лучшее решение всегда совпадают, и по инерции это же предположение переносят на Simulated Annealing.

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

Ошибка 5. Используют слишком агрессивное расписание охлаждения, чтобы «сэкономить время», а затем считают, что метод просто не работает на их задаче.

Как выглядит: температура падает почти до нуля уже за первые несколько десятков итераций из тысяч запланированных.

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

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

Главное запомнить

  • Simulated Annealing (метод имитации отжига) — метаэвристика, вдохновлённая металлургическим отжигом: медленное остывание позволяет системе найти энергетически выгодную конфигурацию, тогда как быстрое охлаждение «замораживает» дефекты.

  • Температура $T$ — единственный управляющий параметр алгоритма: высокая температура означает готовность принимать даже заметно ухудшающие ходы, низкая — почти исключительно улучшающие, приближая поведение к жадному локальному поиску.

  • Критерий принятия Метрополиса: если кандидат не хуже текущего решения ($\Delta E \le 0$) — принять безусловно; если хуже — принять с вероятностью $\exp(-\Delta E/T)$.

  • Формула критерия Метрополиса структурно совпадает с формулой softmax при температурном сэмплировании языковых моделей — в обоих случаях температура управляет балансом между «жадным» и «разнообразным» выбором через экспоненту от величины, делённой на $T$.

  • Расписание охлаждения задаёт, как $T$ убывает со временем: линейное ($T_0 - \alpha t$), геометрическое ($T_0 \alpha^t$, самое распространённое на практике) и логарифмическое ($T_0/\ln(1+t)$, единственное с теоретической гарантией сходимости, но непрактично медленное).

  • Метод способен выпрыгивать из локальных минимумов именно потому, что при $T>0$ вероятность принятия любого ухудшающего хода строго положительна — в отличие от чисто жадного локального поиска, который категорически не может покинуть локальный минимум.

  • Классическая иллюстрация метода — задача коммивояжёра (TSP): соседние решения генерируются оператором 2-opt (разворот участка маршрута), а целевая функция — суммарная длина маршрута.

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

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

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

Связь с темами курса

Что нужно было знать до этого урока

Этот урок продолжает блок метаэвристических методов оптимизации, начатый уроком 294 (методы нулевого порядка) и уроком 295 (эволюционные алгоритмы как общая идея). Уроки 296 (генетические алгоритмы) и 297 (Particle Swarm Optimization) показали два способа организовать поиск через популяцию решений — скрещивание и мутацию генов в одном случае, коллективную память роя частиц в другом. Simulated Annealing подходит к той же самой проблеме — оптимизации без градиента в пространстве с множеством локальных минимумов — совершенно другим путём: не популяцией параллельных решений, а единственной траекторией, управляемой убывающим параметром температуры.

Итог блока метаэвристик (294–298)

Пройденный блок уроков образует цельную картину методов оптимизации «чёрного ящика», не полагающихся на градиент целевой функции. Методы нулевого порядка (294) познакомили тебя с самой общей идеей — оценивать направление улучшения без аналитической производной. Эволюционные и генетические алгоритмы (295–296) показали, как популяция решений, скрещивание и мутация имитируют естественный отбор для поиска в сложных пространствах. Particle Swarm Optimization (297) предложил другую метафору коллективного поиска — рой частиц, обменивающихся информацией о лучших найденных позициях. Simulated Annealing (298) завершает блок методом, который вместо популяции использует единственную траекторию и единственный, зато исключительно интерпретируемый управляющий параметр — температуру, — да ещё и связывает этот параметр напрямую с температурой softmax, с которой ты уже наверняка сталкивался при работе с языковыми моделями и ещё не раз встретишь при их дообучении и сэмплировании. У всех этих методов общая природа: они жертвуют теоретическими гарантиями точного градиентного метода ради способности работать там, где градиента попросту нет или он бесполезен, — на дискретных, комбинаторных, шумных или чёрно-ящичных задачах, которые в реальной инженерной практике встречаются ничуть не реже, чем гладкие дифференцируемые функции потерь.

Что изучить дальше

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

Где это нужно в жизни

🔧 Проектирование микросхем. Исторически первое и до сих пор актуальное применение — размещение и трассировка элементов на кристалле, минимизирующие суммарную длину соединений и электромагнитные помехи.

🤖 Подбор гиперпараметров моделей. Simulated Annealing применяется как один из методов оптимизации «чёрного ящика» для дискретных и смешанных пространств гиперпараметров, где целевая функция (качество на валидации) не даёт градиента и дорого вычисляется.

☁️ ML-инфраструктура и планирование задач. Размещение вычислительных задач обучения на узлах кластера, балансировка нагрузки, составление расписаний — классические комбинаторные задачи, где метод отжига конкурирует с генетическими алгоритмами как практичное решение.

🚚 Логистика и маршрутизация. Задача коммивояжёра и её многочисленные практические варианты — маршрутизация транспорта, доставка, объезд точек обслуживания — остаются учебным и практическим полигоном для метода отжига по сей день.

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

  • Критерий Метрополиса, лежащий в основе метода отжига, был впервые описан в 1953 году для совершенно другой цели — моделирования статистической физики методом Монте-Карло, а не для оптимизации. Понадобилось тридцать лет, прежде чем Киркпатрик, Гелатт и Веччи разглядели в этом физическом правиле универсальный алгоритм оптимизации.

  • Среди пяти авторов статьи 1953 года о критерии Метрополиса был Эдвард Теллер — физик, которого чаще вспоминают в связи с разработкой термоядерного оружия, а не с алгоритмами оптимизации, которыми сегодня пользуются специалисты по машинному обучению.

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

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

Лайфхаки

  • Перед тем как выбирать стартовую температуру $T_0$, сделай короткий «пристрелочный» прогон: сгенерируй десяток-другой случайных соседних решений от начальной точки, посмотри на типичный разброс $\Delta E$ между ними, и выбери $T_0$ так, чтобы средний $\Delta E$ делился на неё в диапазоне примерно от 0,5 до 2 — тогда на старте алгоритм будет принимать заметную, но не абсолютно любую долю ухудшающих ходов.

  • Начинай с геометрического расписания охлаждения ($T(t) = T_0 \alpha^t$ с $\alpha$ в диапазоне $0{,}9$–$0{,}99$) как с разумного значения по умолчанию — оно почти всегда работает лучше линейного на практике и не требует отдельно продумывать момент остановки, в отличие от линейного расписания, которое рискует уйти в отрицательные температуры.

  • Если после нескольких прогонов алгоритм стабильно сходится к одному и тому же не очень удачному решению, в первую очередь заподозри слишком быстрое охлаждение, а не саму задачу или реализацию — увеличь число итераций или замедли коэффициент $\alpha$, прежде чем менять что-то ещё.

  • Для задач с дорогим вычислением целевой функции (например, подбор гиперпараметров, где каждая оценка $\Delta E$ требует полного переобучения модели) рассмотри гибридную схему: сначала более дешёвый и широкий поиск (случайный поиск или генетический алгоритм) для нахождения перспективной области, а затем Simulated Annealing с невысокой стартовой температурой для точной локальной доводки — это экономит бюджет дорогих вычислений там, где он важнее всего.

  • Логируй не только текущее и лучшее значение целевой функции, но и долю принятых ухудшающих ходов на скользящем окне итераций — резкое падение этой доли раньше, чем ты ожидал по расписанию охлаждения, обычно сигнализирует об ошибке в реализации критерия Метрополиса или о неудачно подобранном масштабе температуры относительно $\Delta E$ твоей конкретной задачи.

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

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!