Abstract
Present work studies different acceptance criteria in the simulated annealing algorithm. Existing (Metropolis, Tsallis, Barker, threshold acceptance) and original criteria are examined. Their efficiency is compared using different optimization problems: synthetic test function, traveling salesman problem, minimal linear arrangement, magic squares construction, graph coloring.
Ключевые слова: симуляция отжига; комбинаторная оптимизация
Keywords: simulated annealing; combinatorial optimization
Введение
Симуляция отжига (СО) — алгоритм оптимизации, предложенный Киркпатриком [5] и независимо Черны [1], являющийся адаптацией алгоритма выборки Метрополиса [6]. СО имитирует процесс отжига в металлургии, при котором металл нагревается до температуры выше температуры кристаллизации и затем медленно охлаждается. Этот процесс устраняет внутреннее напряжение и в результате приводит к кристаллической решётке с малой внутренней энергией. СО находит широкое применение благодаря эффективности и простоте реализации.
Сформулируем проблему оптимизации: найти решение x, максимизирующее или минимизирующее целевую функцию (ЦФ) E(x). Допустим также, что имеется метод генерации случайных ходов, переводящих решение x в соседнее решение x’. На каждом шаге рассмотрению подвергается новое соседнее решение. В отличие от стохастического восхождения (hillclimbing), которое принимает лишь ходы, приводящие к улучшению, СО иногда принимает ходы, ухудшающие значение ЦФ, что позволяет ей выходить из локальных оптимумов. Без ограничения общности допустим, что мы имеем дело с проблемой минимизации. В классическом СО используется критерий Метрополиса: вероятность принятия хода, приводящего к изменению энергии (ЦФ) 
есть
,
где 
— параметр по аналогии с оригинальным процессом называемый температурой и имеющий ту же размерность, что и ЦФ. Все ходы, приводящие к улучшению (
) принимаются, но вероятность принятия ухудшающих ходов (
) зависит от температуры. Лишь ходы с 
порядка T имеют значительный шанс принятия, в то время как ходы с 
скорее всего будут отвергнуты. Изменяя параметр , можно контролировать свойства поиска: при очень высоких температурах принимаются почти все ходы (случайный поиск, жидкое состояние), в то время как при очень низких температурах принимаются лишь хорошие ходы (локальный поиск, кристаллическое состояние). СО работает, постепенно понижая температуру, что позволяет изучить пространство поиска сначала на грубом, а затем на более тонком уровне. Более детальное рассмотрение аналогий между оптимизацией и статистической механикой может быть найдено в оригинальной статье [5].
Обобщённая процедура СО может быть записана следующим образом:
i := 0 Сбросить счётчик итераций
x := Random_Solution Создать начальное решение
Best := x
repeat
x’ := Random_Neighbour(x) Сгенерировать соседнее решение
dE := E(x’) – E(x) Вычислить изменение энергии
T := Schedule(i) Выбрать температуру
if Random < P(dE / T) then Принять или отвергнуть
x := x’ пользуясь критерием принятия
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
if E(x) < E(Best) then Обновить лучшее решение
Best := x
i := i + 1
until Stopping_Condition Проверить критерий остановки
return Best Вернуть лучшее решение
Таким образом, для реализации СО необходимы следующие элементы:
· Формулировка задачи
◦ Пространство решений
◦ Целевая функция 
◦ Функция генерации случайного соседа 
· Параметры алгоритма
◦ Температурный режим 
◦ Функция принятия 
, 
◦ Критерий остановки
Температурным режимам и различным модификациям базового алгоритма посвящено значительное количество работ, однако функции принятия уделяется меньше внимания. Данная работа является попыткой предпринять исследование, направленное на изучение её влияния.
Начальная и конечная температуры
Критерием остановки в данной работе является достижение фиксированного количества итераций 
. В качестве температурного режима используется геометрическое охлаждение:
, 
,
где 
и 
— начальная и конечная температуры соответственно. Оно является самым популярным режимом, так как обеспечивает быстрое охлаждение (и соответственно скорость сходимости) и демонстрирует хорошие результаты на практике. Для исследования работы алгоритма на различных задачах необходим универсальный способ выбора параметров и .
Изначально система должна находиться в жидком состоянии, когда принимаются почти все ходы. В противном случае температурных флуктуаций энергии может быть недостаточно для преодоления высоких потенциальных барьеров и решение застрянет в области, далёкой от оптимума. Возможный способ оценки — произвести начальный поиск при бесконечной температуре (принимая все ходы). Начальная температура должна иметь тот же масштаб, что и изменения энергии соседних решений 
во время этой стадии. В данной работе используется выражение, основанное на средне модуле изменения энергии:
, 
В конце поиска температура должна быть достаточно мала, чтобы почти все ухудшающие ходы отвергались, иначе решение не достигнет локального оптимума. Если минимально значимое изменение ЦФ обозначить 
, то вероятность принятия хода, приводящего к такому изменению в конце поиска 
, а среднее число итераций до принятия 
. В условной «холодной фазе» (последние 
итераций) ни одно минимальное ухудшение не должно быть принято:
, 
Эта оценка является завышенной, так как основана на минимальной температуре, в то время как в начале холодной фазы температура и, следовательно, вероятность принятия ухудшающих ходов может быть значительно выше. Поэтому воспользуемся несколько меньшим значением:
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
, 
, 
И хотя приведённые рассуждения основываются на грубых прикидках, для большинства задач они дают вполне адекватные оценки параметров и 
.
Функция принятия
Стандартная функция принятия, унаследованная от алгоритма Метрополиса
,
но в принципе ничто не мешает использовать какую-либо другую. Популярный альтернативный критерий — пороговое принятие (threshold accepting), являющееся детерминированным:
В отличии от критерия Метрополиса, критерий Баркера может иногда отвергать ухудшающие ходы:
Ещё один критерий основан на обобщённой формулировке статистической механики Цаллиса [9]:
В работе [8] показано, что многие критерии принятия эквивалентны критериям Метрополиса или Баркера после монотонного преобразования температуры. Тем не менее, на практике может быть более удобно работать с фиксированным семейством температурных режимов, но менять функцию принятия — подход, принятый в данной работе. Различные семейства обобщённых функций принятия приведены в таблице 1:
Таблица 1
Семейства критериев принятия
Наиболее важным параметром функции принятия является её асимптотическое поведение при 
. Медленно затухающие, тяжёлые «хвосты» дают высокую вероятность принятия больших ухудшающих изменений. С одной стороны это даёт возможность перепрыгнуть высокие потенциальные барьеры и выбраться из локального минимума. С другой стороны, это может привести к недостаточному изучению около-оптимального региона. Чем тяжелее хвост, тем менее локален поиск.
Результаты тестирования
Для выяснений особенностей функций принятия были использованы различные тестовые задачи:
· Тестовая функция (ТестФ)
◦ Формулировка:
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Мультимодальная тестовая функция, схожая с функцией Растригина [11].
◦ Энергия:
, 
◦ Случайный ход:
, 
, 
— случайное число со стандартным нормальным распределением.
· Задача коммивояжёра (ЗКВ) [7]
◦ Формулировка:
Обойти заданные точки замкнутым маршрутом, имеющим минимальную длину.
◦ Энергия:
Суммарная длина маршрута.
◦ Случайный ход:
2-Opt: разорвать маршрут в двух случайных местах и пересоединить два получившихся пути [7].
· Магический квадрат (МагКв)
◦ Формулировка:
Заполнить массив 
числами от 1 до 
так, чтобы сумма чисел во всех строках, столбцах и диагоналях была одинакова.
◦ Энергия:
Сумма абсолютных отклонений сумм в строках, столбцах и диагоналях от магической константы 
.
◦ Случайный ход:
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Обменять значения в двух случайно выбранных ячейках.
· Минимальное линейное размещение (МинЛР) [3]
◦ Формулировка:
Заполнить массив числами от 1 до так, чтобы минимизировать сумму абсолютной разницы между числами во всех соседних ячейках.
◦ Энергия:
◦ Случайный ход:
Обменять значения в двух случайно выбранных ячейках.
· Раскраска графа (РГ) [2]
◦ Формулировка:
Раскрасить вершины графа фиксированным количеством цветов так, чтобы никакие две соседние вершины не имели одинаковый цвет.
◦ Энергия:
Количество соседних вершин, имеющих одинаковый цвет.
◦ Случайный ход:
Присвоить случайный цвет случайной вершине.
Таблица 2
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Параметры тестовых задач
