Метод отжига

2 634
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
  • Название: Имитация отжига (алгоритм Метрополиса) = метод отжига (Simulated Annealing — SA);
  • Применение: Поиск глобального экстремума;
  • Уровень: средний;
  • Входные параметры: целевая функция, заданные ограничения;
  • Результат: Эвристический. Глобальный максимум или минимум

Пример из жизни:

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

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

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

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

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

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

Постановка задачи:

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

Лингвистическое описание алгоритма:

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

После синхронизации модели отжига с задачей оптимизации, опишем работу алгоритма.

Шаг 1. Инициализируется начальная температура (tmax — начало отжига) и минимальная температура (tmin — конец отжига).

Шаг 2. Определяется функция нового состояния и задается произвольное начальное состояние системы — So;

Шаг 2. Сравнивается текущее значение целевой функции (энергия системы до перехода в новое состояние — E(S0)) и значение после принятия нового состояния (энергия после перехода в новое состояние — E(Si) — на i — шаге);

Шаг 3. Если вычисленное значение целевой функции после принятия нового состояния оказалось меньше (для задачи поиска глобального минимума), то сохраняем его в качестве текущего значения целевой функции. E(Si) < E(S0) => S0 = Si;

Шаг 4. В противном случае, вычисляется вероятность принятия текущего значения даже если оно больше (не удовлетворяет условиям задачи). Вероятность равна e-ΔE/Ti ,  где  ΔE — разность текущего значения целевой функции до и после принятия нового состояния  E(So)  — E(Si), Ti  текущая температура. Если такая вероятность больше определенного значения (например, 0.5), то сохраняем новое состояние системы S0 = Si;

Шаг 5. Вычисляем новое значение температуры Ti (температура может понижаться в соответствии с определенной закономерностью, например линейной, Ti = Ti-1 * α / i , где i — шаг на определенной итерации и α — настраиваемый коэффициент, обычно принимается за значение в интервале 0.8 <= α <= 0.99 ).

Шаг 6. Если Ti <=Tmin. Алгоритм завершается, в против случае переход на Шаг 2.

Реализация:

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

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

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

Реализуем класс Annealing, в котором будет определен соответствующий функционал. Для начала инициализируем константы: SIZE_CHESSBOARD — размер шахматной доски (10×10), START_TEMPERATURE — начальную температуру т.е. нагреем нашу воображаемую систему до (10 градусов), FINISH_TEMPERATURE — температуру при которой будем считать систему охлажденной (0.00001 градусов), COUNT_ITERATIONS — количество итераций при понижении температуры (1000) и ALPHA — постоянная альфа, которая используется при вычислении новой температуры после охлаждения системы. Так же определим свойство — $cell массив, который будет хранить текущее количество конфликтов в системе (которые надо минимизировать) и полученное решение (расположение ферзей на шахматной доске).

При инициализации задачи расположим ферзей так, чтобы они хотя бы не попадали под горизонтальный удар. При этом сохраним текущее расположение в массиве $arr[‘val’]. Обратите внимание, в массиве кодирование местоположения фигуры на клетке задается следующим образом [0,0] первая ячейка и т.д.

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

Определим метод, который вычисляет количество конфликтов, которые необходимо минимизировать  т.е. текущее состояние системы (энергия — E). Во-первых, происходит заполнение шахматной доски $board[$i][$solution[‘val’][$i]] = «Q», после этого проверяются конфликты по диагоналям, где $step_x = [-1, 1, -1, 1] — обход вверх-влево и $step_y = [-1, 1, 1, -1] — обход вниз-вправо. Следующее перемещение осуществляется до тех пор пока не будет достигнут конец верха или низа доски. Если на этом «пути» попадется ферзь, то увеличиваем счетчик конфликта —$conflicts.

Осталось описать работу самого алгоритма отжига. На 1 шаге производится инициализация системы (2-4 строки): установка начальной температуры отжига и начальная расстановка ферзей. При этом вычисляется «энергия» системы, которая показывает количество конфликтов на начальном этапе. Затем имитируется последовательное «охлаждение» системы с помощью цикла — while, где фигурирует счетчик цикла — $i, который задает темп охлаждения системы. На 2 шаге (10 строка) вычисляется новое состояние системы и его число конфликтов (энергия). После этого (шаг 3) происходит сравнение конфликтов до перехода в новое состояние и после (11 строка). Если число конфликтов оказалось меньше, что, безусловно, удовлетворяет условию задач, то расположение ферзей (состояние при котором этих конфликтов меньше) запоминается — используется в дальнейших расчетах. В противном случае, (шаг 4) вычисляется вероятность принять решение заведомо неудовлетворяющее условиям задачи (17-21 строки). Если это значение больше, чем случайное число из интервала от 0 до 1, то принимается «худшее» решение после чего происходит понижении температуры шаг 5 и проверка условиях выхода из цикла шаг 6. Если температура меньше заданного значения (FINISH_TEMPERATURE) то происходит повторная работа алгоритма.

Осталось описать метод вывода результатов и функции понижения температуры. Как было отмечено выше алгоритм не требует специальных настроек,  за исключением подбора  ALPHA. В данном случае, ALPHA = 0.98.

Выводы:

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

Список источников:

  1. Введение в оптимизацию. Имитация отжига;
  2. Алгоритмы оптимизации, основанные на методе проб и ошибок;
  3. М. Тим Джонс. Программирование искусственного интеллекта в приложениях. Издательство: ДМК Пресс Год: 2011
  4.  Стивен С. Скиена Алгоритмы. Руководство по разработке— 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.

Полезное видео:

Р.В. Шамин. Лекция №1. Метод отжига

Поделиться

Отправить ответ

avatar
wpDiscuz