Лекция: Модификация рабочего решения.

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

Расчёт энергии рабочего решения.

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

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

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

Расчёт вероятности допуска рабочего решения.

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

Р(sЕ) = ехр(-sЕ/Т)

Значение этой формулы визуально показано на рис. 10.32.

Рисунок 10.32. Графическое изображение формулы для расчёта вероятности допуска.

При высокой температуре (свыше 60С) плохие решения принимаются чаще, чем отбрасываются. Если энергия меньше, вероятность принятия решения выше. При снижении температуры вероятность принятия худшего решения также снижается. При этом более высокий уровень энергии также способствует уменьшению вероятнocти принятия худшего решения.

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