Глава 2. Алгоритм отжига

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

Естественная мотивация

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

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

Алгоритм отжига

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


Алгоритм отжига

Начальное решение

Для большинства проблем начальное решение будет случайным. На самом первом шаге оно помещается в текущее решение (Current solution). Другая возможность заключается в том, чтобы загрузить в качестве начального решения уже существующее, возможно, то самое, которое было найдено во время предыдущего поиска. Это предоставляет алгоритму базу, на основании которой выполняется поиск оптимального решения проблемы.

Оценка решения

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

Случайный поиск решения

Поиск решения начинается c копирования текущего решения в рабочее решение (Working solution). Затем мы произвольно модифицируем рабочее решение. Как именно модифицируется рабочее решение, зависит от того, каким образом оно представляется (кодируется). Представьте себе кодировку задачи коммивояжера, в которой каждый элемент представляет собой город. Чтобы выполнить поиск по рабочему решению, мы берем два элемента и переставляем их. Это позволяет сохранить целостность решения, так как при этом не происходит повторения или пропуска города.

После выполнения поиска рабочего решения мы оцениваем решение, как было описано ранее. Поиск нового решения основан на методе Монте-Карло (то есть случайным образом).


Критерий допуска

На этом этапе алгоритма у нас имеется два решения. Первое - это наше оригинальное решение, которое называется текущим решением, а второе - найденное решение, которое именуется рабочим решением. С каждым решением связана определенная энергия, представляющая собой его эффективность (допустим, что чем ниже энергия, тем более эффективно решение).
Затем рабочее решение сравнивается с текущим решением. Если рабочее решение имеет меньшую энергию, чем текущее решение (то есть является более предпочтительным), то мы копируем рабочее решение в текущее решение и переходим к этапу снижения температуры.
Однако если рабочее решение хуже, чем текущее решение, мы определяем критерий допуска, чтобы выяснить, что следует сделать с текущим рабочим решением. Вероятность допуска основывается на уравнении 2.1 (которое, в свою очередь, базируется на законе термодинамики):

P(dE) = exp(-dE/T)
(2.1)
Значение этой формулы визуально показано на рис. 2.2. При высокой температуре (свыше 60°С) плохие решения принимаются чаще, чем отбрасываются. Если энергия меньше, вероятность принятия решения выше.
Вероятность принятия решения
При снижении температуры вероятность принятия худшего решения также снижается. При этом более высокий уровень энергии также способствует уменьшению вероятности принятия худшего решения. При высоких температурах симулированное восстановление позволяет принимать худшие решения для того, чтобы произвести более полный поиск решений. При снижении температуры диапазон поиска также уменьшается, пока не достигается равенство при температуре 0°.

Снижение температуры

После ряда итераций по алгоритму при данной температуре мы ненамного снижаем ее. Существует множество вариантов снижения температуры. В данном примере используется простая геометрическая функция (см. уравнение 2.2):

T(i+1)=aTi                                      (2.2)

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

Повтор

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

Пример итерации

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

Предположим, что температура окружающей среды равна 50°, а энергия теку­щего решения составляет 10. Мы копируем текущее решение в рабочее решение и выполняем поиск. После оценки энергии устанавливаем, что энергия нового рабочего решения равна 20. В этом случае энергия рабочего решения выше, чем энергия начального решения. Поэтому мы используем критерий допуска:

Энергия текущего решения равна 10. Энергия рабочего решения равна 20.

Дельта энергии для этого примера (энергия рабочего решения минус энергия текущего решения) равна 10. Подставив это значение и температуру 50 в уравнение 2.1, получаем вероятность:

Р = ехр(-10/50) = 0,818731.

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

Энергия текущего решения равна 3. Энергия рабочего решения равна 7......................


Задача 8 ферзей