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

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

Такие «шаги назад», когда от текущего состояния переходят к худшим состояниям, в некоторых случаях позволяют, в конечном счете, достичь лучших результатов.

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

Шаг 1. Генерируется некоторое корректное начальное расписание  обработки деталей и для этого расписания вычисляется значение критерия , по которому будет производиться отбор лучшего расписания. Это значение полагается равным рекорду . Кроме того, задаются:

- предельное количество итераций алгоритма ,

- достаточно большое начальное значение температуры ,

- величина , с помощью которой считаются итерации метода, полагается равной нулю ( =0),

- величина , с помощью которой считается количество итераций метода, не приведших к улучшению значения критерия, также полагается равной нулю (),

- величина , определяющая максимальное количество изменений расписания, которые не привели к улучшению значения критерия.

Следует переход к Шагу 2.

Шаг 2. Производится мутация расписания, в результате которой происходит изменение порядка запуска на обработку некоторых деталей. Мутация расписания должна быть произведена таким образом, чтобы было получено новое корректное расписания . Для этого расписания вычисляется значение критерия . Мутация может проводиться по аналогии с тем, как это делается в генетических алгоритмах, описанных в предыдущем пункте. Следует переход к Шагу 3.

Шаг 3. Производится проверка вновь сгенерированного расписания , которое называют временным, на предмет включения в список постоянных расписаний. Временное расписание может стать постоянным с некоторой вероятностью . Таким образом, задаётся переход от одной итерации алгоритма к другой. Для расписания   определён переход к расписанию  через случайное применение операций с вероятностью , где вероятность задаётся формулой:

где  – по существу функция, определяющая величину критерия при обработке деталей по соответствующему расписанию,   – убывающая последовательность значений температуры. Функция  в данной формуле играет такую же роль, как и энергии атомов в кристаллической решётке для имитации процесса отжига. Если вычисленная по приведенной выше формуле величина  оказывается больше заданного значения  (0< <1), то вновь сгенерированное расписание  включается в список постоянных расписаний, величина  полагается равной нулю (). В противном случае  не включается в список постоянных расписаний, величина  полагается равной +1 и следует переход к Шагу 2. Если вычисленная по приведенной выше формуле величина  оказывается равной 1, то производится сравнение значений критериев  и . Если  окажется меньше  (), то производится присвоение . Следует переход к Шагу 4.

Шаг 4. Производится переход на следующую итерацию метода. Если вновь сгенерированное расписание  включается в список постоянных расписаний, то  присваивается значение +1, расписание  включается в список постоянных расписаний, как  и следует переход к Шагу 5.

Шаг 5. Производится проверка завершения вычислений по количеству выполненных итераций или количеству итераций, в которых не произошло улучшения функционала. Если  или , то в качестве решения выбирается расписание с рекордным значением критерия  и вычисления прекращаются. В противном случае следует переход к Шагу 6.

Шаг 6. Производится проверка изменения температуры. Если после предыдущего изменения температуры прошло заданное количество итераций, то температура  меняется по закону, который задает пользователь. Следует переход к Шагу 2.

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

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

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