Раз в год мы пишем сложную статью, в которой объясняем сложные вещи максимально просто и подробно. Сегодня как раз такая статья.
Когда вы придёте в биг-дату и будете писать алгоритмы для обучения нейросетей, то, скорее всего, одним из таких алгоритмов будет алгоритм имитации отжига. Ещё этот алгоритм применяется для быстрого поиска относительно точных решений — например при построении маршрутов на карте.
Это теоретическая статья, где много примеров из физики и математики. Она может показаться сложной, но такова суть алгоритмов. Заниматься программированием можно и без отжига, но иногда это самое эффективное решение. Если хотите что-то более практичное про алгоритмы — почитайте, как смоделировать игру в рулетку на Python.
Главное кратко
- Существуют математические задачи, которые очень сложно решить со стопроцентной точностью. А раз они математические, то они и программистские тоже.
- Существует физический процесс, когда атомы вещества очень сильно нагревают, чтобы встряхнуть их и навести в них порядок. Это и есть отжиг.
- Математики берут этот физический процесс и переносят на свою задачу.
- Суть метода в том, чтобы начать решать нерешаемую задачу не точно, а приближенно. Но решить нужно много раз. Это называется имитацией отжига.
- С каждым новым решением нужно немного повышать степень точности. За точность отвечает специальная формула.
- В зависимости от того, сколько у нас времени и какой у нас компьютер, мы можем сделать больше или меньше подходов к решению задачи. Чем больше подходов — тем выше точность решения.
Имитацию отжига можно сравнить вот с чем. Представьте, что вы на уроке математики решаете уравнение, но забыли формулу. Вы решаете «взломать» уравнение грубой силой. Вы подставляете какие-то числа в переменные, получаете какой-то результат. Видите, что результат не совпадает. Пробуете снова. Потом ещё и ещё. И с каждым разом вы приближаетесь к нужному результату. Вот это и есть имитация отжига.
Что такое отжиг
Сейчас будет сложновато, но если разобраться в этом — дальше будет всё просто. Заодно узнаете, какая магия случается в физике.
Процесс отжига в физике — это когда металл сначала сильно нагревают, а потом медленно снижают его температуру. Идея в том, чтобы выстроить атомы в кристаллическую решётку и сформировать как можно больше таких устойчивых решёток в металле. Если всё сделать правильно, у металла снижается твёрдость, убираются внутренние напряжения и металл становится более однородным — так его легче обрабатывать.
Вот что происходит внутри металла в это время:
- Во время нагревания атомы начинают двигаться быстрее, энергия движения увеличиваются, и атомы начинают двигаться и могут перескакивать на соседние решётки.
- Когда начинается остывание, атомы успокаиваются и начинают занимать свои места в узлах решётки. При этом пока температура не упадёт до стабильной, атомы могут менять своё место в решётке.
- Постепенно температура снижается, и самые медленные атомы окончательно остаются на своих местах, а остальные ещё могут перескакивать между узлами.
- Это приводит к тому, что со временем почти все узлы в решётках будут заняты атомами — у них просто не останется других вариантов при остывании, как занять свободные места.
- В итоге мы получаем металл с устойчивыми решётками, который можно брать дальше в работу.
Общее правило при отжиге звучит так:
Чем ниже температура, тем меньше вероятность, что атом перескочит на другой узел
При этом атом может перескочить и при низкой температуре, просто вероятность этого будет совсем невысокая. Получается, что, постепенно снижая температуру, мы получим металл с нужными нам итоговыми параметрами.
Запомним эту мысль и вернёмся в ИТ.
Как это применяется в ИТ
Если выписать из процесса отжига ключевые мысли и точки, то получим интересное:
- есть система, которая находится не в нужном для нас состоянии;
- есть процессы, которые могут протекать в этой системе;
- есть параметр (температура), благодаря которому система сама может отрегулировать себя и прийти в нужное состояние;
- и есть конечное значение (температуры), по достижении которого система считается максимально близкой к нужному состоянию.
Получается, что если мы сможем описать формулой состояние системы или зададим их в виде функции, то сможем точно так же привести её к нужному состоянию. Магия в том, что нам достаточно определить формулу и прописать условия снижения виртуальной температуры, а алгоритм дальше всё сделает сам.
Поясним на примере: допустим, мы хотим решить задачу коммивояжёра. Смысл задачи в том, что у нас сколько-то точек, которые нужно соединить между собой оптимальным способом. Например, найти оптимальный путь, чтобы объехать несколько городов или найти лучший маршрут по городу через нужное количество перекрёстков.
Существуют обычные алгоритмы решения задачи коммивояжёра с помощью перебора. Современные компьютеры могут быстро решить эту задачу для 5–10 точек. Если у нас очень много времени, можно загрузить компьютер на неделю, и он найдёт решение задачи для 13 точек. Теоретический максимум для современной кибернетики — 67 точек. Если добавить в задачу 68-ю точку, мы превысим даже теоретические возможности современных вычислительных систем. Но всё это — если нам нужен результат со стопроцентной точностью.
На практике нас устроит погрешность в несколько процентов — если мы строим маршрут в навигаторе, это будет некритично. Тогда мы можем задать нужную погрешность и применить алгоритм имитации отжига. По мере снижения виртуальной температуры он сам найдёт нужный порядок городов.
Если это визуализировать, то вот что может получиться (энергия на видео — это расстояние между городами в текущей ситуации):
Алгоритм имитации отжига
У нас уже достаточно теории, чтобы разложить всё по полочкам. Начнём с температуры — она в алгоритме может быть любой, главное — задать начальное и конечное состояние. Позовём на помощь синтаксис Python:
initial_temp = 90
final_temp = 0.1
Чем шире будет разброс, тем дольше будет работать алгоритм и тем точнее может быть результат (а может и не быть).
Следующее, что нужно — это шаг температуры, с какой скоростью будет остывать наш процесс. Чем меньше шаг — тем дольше будет запекаться результат.
alpha = 0.01
На старте текущая температура равна начальной — считается, что мы уже всё прогрели, можно остужать:
current_temp = initial_temp
Теперь поговорим о состоянии системы. На старте у нас может быть что угодно с данными, полный хаос или отсортировано по порядку — главное, что эти данные уже приняли какую-то форму решения. Например, в случае с коммивояжёром и городами это будет массив с городами — в каком порядке надо ехать. Наверняка это будет неверное решение, но нам нужна какая-то стартовая точка (initial_state). Она же будет и решением на старте:
current_state = initial_state
Главное во всём этом — чтобы мы в процессе умели всё просчитать и понять, какое состояние лучше, а какое хуже. В примере с коммивояжёром этим параметром будет общее расстояние между городами — если расстояние в одном состоянии короче, чем в другом, то лучше там, где короче.
Теперь начинаем остужать. Для этого постоянно сравниваем текущую температуру с минимальной, и, пока они не сравнялись, — всё остальное делаем внутри этого цикла:
while current_temp > final_temp
Чтобы температура упала на одно деление (alpha), нам нужно случайно выбрать новое состояние системы. Например, можно поменять местами пару маршрутов между городами, поменять пять маршрутов или выбрать случайный город и поменять у него маршрут в другой город тоже на случайный. Тут нет единственно верного пути — разработчик сам выбирает логику выбора нового состояния. Она повлияет на скорость работы, но решение будет в любом случае.
Допустим, мы выбрали какой-то алгоритм случайного выбора нового состояния — кладём это состояние в переменную new_state:
new_state = random.choice(выбираем по какому-то алгоритму)
Теперь нам надо выяснить: это состояние лучше старого или нет. Для этого считаем разницу — если она больше нуля, то выбираем новое состояние как решение и меняем текущее состояние:
// находим разницу
cost_diff = current_state.count - new_state.count
// если новое лучше старого — делаем новое текущим
current_state = new_state
А вот теперь — самое необычное: даже если новое состояние не лучше текущего, то всё равно есть шанс, что оно займёт его место. Причём чем выше температура, тем выше этот шанс, всё как в физическом процессе. Это делается для того, чтобы избежать бесконечного цикла поиска наилучшего решения из текущей ситуации — вдруг его просто нет и нужно просто перейти в другое состояние, чтобы оно появилось.
В математике используется специальная формула, которая определяет, будет переход в новое состояние даже при неоптимальном значении или нет. Если переписать её на Python, то она будет выглядеть так:
if random.uniform(0, 1) < math.exp(-1 * cost_diff / current_temp):
current_state = new_stateПереводя на русский, это звучит так: если число e в степени «разница между состояниями делить на текущую температуру, умноженное на минус один» будет больше какого-то случайного в этот момент числа — мы переходим на новое состояние и делаем его текущим. Чем выше температура, тем меньше значение дроби в степени. Но у нас отрицательная степень, поэтому, чем выше температура — тем выше вероятность, что значение степени будет больше случайного числа.
Всё, дальше просто: мы просто понижаем температуру на одно деление и возвращаемся в начало цикла.
current_temp -= alpha
В итоге, мы раз за разом прогоняем цикл с понижением температуры, а система сама в это время подбирает такие значения, чтобы приблизиться к нужному нам значению. Когда температура упадёт до минимальной — всё, процесс завершён, и наше текущее состояние в этот момент и будет решением. Оно может быть неидеальным, но при этом достаточно хорошим, чтобы им пользоваться в жизни.
Где используется имитация отжига
Кроме моделирования физических процессов, алгоритм имитации отжига используется:
- в экономике — для поиска оптимальных торговых стратегий;
- в программировании — для быстрого поиска достаточно хороших решений;
- а главное — для обучения нейросетей.
Идея с обучением нейронок в том, что там вместо городов — узлы, а вместо расстояний — значения весов в этих узлах. Если мы знаем, к какому состоянию нейросети мы хотим прийти, то мы можем методом имитации отжига заранее распределить веса так, чтобы при обучении нейросеть сразу показывала высокие результаты.
Что дальше
Теперь, когда мы знаем всё про алгоритм имитации отжига, используем его для чего-нибудь полезного: решим какую-нибудь сложную задачку и посмотрим, как с этим справится наш алгоритм.
