Применение метода моделируемого отжига к задаче составления школьного расписания

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

Если измененное решение имеет меньшую энергию, то оно принимается за текущее. Если же измененное решение имеет большую  энергию, то оно принимается с  вероятностью P = exp(-δE/T), где:

• P — вероятность принять измененное решение,
• δE — модуль разности между энергией оптимального решения и энергий измененного решения,
• T — текущая температура.

Уменьшение  температуры

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

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

Выбор начальной и пороговой температуры

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

Области применения:

1. Создание пути
2. Реконструкция изображения
3. Назначение задач и планирование
4. Размещение сети
5. Глобальная маршрутизация
6. Обнаружение и распознавание визуальных объектов
7. Разработка специальных цифровых фильтров

     При помощи моделирования такого процесса ищется такая точка или множество  точек, на котором достигается минимум  некоторой числовой функции  , где . Вводится последовательность точек пространства X. Алгоритм последовательно находит следующую точку по предыдущей, начиная с точки , которая является начальным приближением. Алгоритм останавливается по достижении точки .

     Точка по алгоритму получается на основе текущей точки следующим образом. К точке применяется оператор Α, который случайным образом модифицирует соответствующую точку, в результате чего получается новая точка . Точка становится точкой с вероятностью , которая вычисляется в соответствии с распределением Гиббса:

     Здесь Qi > 0 — элементы произвольной убывающей, сходящейся к нулю положительной последовательности, которая задаёт аналог падающей температуры в кристалле. Скорость убывания и закон убывания могут быть заданы по желанию создателя алгоритма.

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

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

     Эвристика

     Эвристика (др. греч ευρίσκω «отыскиваю», «открываю») — наука, изучающая творческую деятельность, методы, используемые при открытии новых концептов, идей и взаимосвязей между объектами и совокупностями объектов, а также методики процесса обучения. Эвристические методы (другое название эвристики) позволяют ускорить процесс решения задачи.

     Эвристикой, в зависимости от контекста, называют

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

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

     Основным  назначением эвристики является построение моделей процессов решения какой-либо новой задачи. Существуют следующие типы таких моделей:

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

     Целевая функция

     Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в  задаче оптимизации.

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

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

     Транзакция

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

     Различают последовательные (обычные), параллельные и распределённые транзакции. Распределённые транзакции подразумевают использование больше чем одной транзакционной системы и требуют намного более сложной логики (например, two-phase commit — двухфазный протокол фиксации транзакции). Также, в некоторых системах реализованы автономные транзакции, или под-транзакции, которые являются автономной частью родительской транзакции.

   Пример: Необходимо перевести с банковского  счёта номер 5 на счёт номер 7 сумму  в 10 денежных единиц. Этого можно  достичь, к примеру, приведённой  последовательностью действий:

• Начать транзакцию

прочесть  баланс на счету номер 5

уменьшить баланс на 10 денежных единиц

сохранить новый баланс счёта номер 5

прочесть  баланс на счету номер 7

увеличить баланс на 10 денежных единиц

сохранить новый баланс счёта номер 7

• Окончить транзакцию

   Эти действия представляют собой логическую единицу работы «перевод суммы между  счетами», и таким образом, являются транзакцией. Если прервать данную транзакцию, к примеру, в середине, и не аннулировать все изменения, легко оставить владельца счёта номер 5 без 10 единиц, тогда как владелец счета номер 7 их не получит.

   В идеале транзакции разных пользователей  должны выполняться так, чтобы создавалась  иллюзия, что пользователь текущей  транзакции — единственный. Однако в реальности, по соображениям производительности и для выполнения некоторых специальных  задач, СУБД предоставляют различные  уровни изоляции транзакций. Уровни описаны  в порядке увеличения изоляции транзакций и надёжности работы с данными

• 0 — Неподтверждённое чтение (Read Uncommited, Dirty Read, грязное чтение) — чтение незафиксированных изменений своей транзакции и конкурирующих транзакций, возможны нечистые, неповторяемые чтения и фантомы
• 1 — Подтверждённое чтение (Read Commited) — чтение всех изменений своей транзакции и зафиксированных изменений конкурирующих транзакций, нечистые чтения невозможны, возможны неповторяемые чтения и фантомы
• 2 — Повторяемое чтение (Repeatable Read ,Snapshot) — чтение всех изменений своей транзакции, любые изменения, внесённые конкурирующими транзакциями после начала своей недоступны, нечистые и неповторяемые чтения невозможны, возможны фантомы
• 3 — Упорядоченный — (Serializable, сериализуемый) — упорядоченные (сериализуемые) транзакции. Идентичен ситуации при которой транзакции выполняются строго последовательно одна после другой. То есть транзакции, результат действия которых не зависит от порядка выполнения шагов транзакции (запрещено чтение всех данных изменённых с начала транзакции, в том числе и своей транзакцией). Фантомы невозможны.

   Чем выше уровень изоляции, тем больше требуется ресурсов, чтобы их поддерживать.

   В СУБД уровень изоляции транзакций можно  выбрать как для всех транзакций сразу, так и для одной конкретной транзакции. По умолчанию в большинстве  баз данных используется уровень 1 (Read Commited). Уровень 0 используется в основном для отслеживания изменений длительных транзакций или для чтения редкоизменяемых  данных. Уровни 2 и 3 используются при  повышенных требованиях к изолированности  транзакций.

   Полноценная реализация уровней изоляции и свойств ACID представляет собой нетривиальную  задачу. Обработка поступающих данных приводит к большому количеству маленьких  изменений, включая обновление как  самих таблиц, так и индексов. Эти изменения потенциально могут  потерпеть неудачу: закончилось  место на диске, операция занимает слишком  много времени (timeout) и т. д. Система  должна в случае неудачи корректно  вернуть базу данных в состояние  до транзакции.

   Первые  коммерческие СУБД (к примеру, IBM DB2), пользовались исключительно блокировкой доступа к данным для обеспечения свойств ACID. Но большое количество блокировок приводит к существенному уменьшению производительности. Есть два популярных семейства решений этой проблемы, которые снижают количество блокировок: Журнализация изменений (write ahead logging, WAL) и механизм теневых страниц (shadow paging)^[2]. В обоих случаях, блокировки должны быть расставлены на всю информацию, которая обновляется. В зависимости от уровня изоляции и имплементации, блокировки записи также расставляются на информацию, которая была прочитана транзакцией.

   При упреждающей журнализации, используемой в Sybase и MS SQL Server до версии 2005, все изменения записываются в журнал, и только после успешного завершения — в базу данных. Это позволяет СУБД вернуться в рабочее состояние после неожиданного падения системы. Теневые страницы содержат копии тех страниц базы данных на начало транзакции, в которых происходят изменения. Эти копии активизируются после успешного завершения. Хотя теневые страницы легче реализуются, упреждающая журнализация более эффективна.

   Дальнейшее  развитие технологий управления базами данных привело к появлению безблокировочных технологий. Идея контроля за параллельным доступом с помощью временных  меток (timestamp-based concurrency control) была развита  и привела к появлению многоверсионной  архитектуры MVCC. Эти технологии не нуждаются ни в журнализации изменений, ни в теневых страницах. Архитектура, реализованная в Oracle 7.х и выше, записывает старые версии страниц в специальный сегмент отката, но они все ещё доступны для чтения. Если транзакция при чтении попадает на страницу, временная метка которой новее начала чтения, данные берутся из сегмента отката (то есть используется «старая» версия). Для поддержки такой работы ведётся журнал транзакций, но в отличие от «упреждающей журнализации», он не содержит данных. Работа с ним состоит из трёх логических шагов: