В предыдущем разделе мы заметили, что переход от бинарных нейронов к аналоговым значительно улучшил свойства решения. Аналогичного эффекта можно добиться используя по-прежнему бинарные нейроны, но заменив детерминистскую динамику стохастической, характеризуемой некоторой эффективной температурой
Положительная роль температуры заключается в том, что шум позволяет системе покидать локальные минимумы энергии и двигаться в сторону более глубоких энергетических минимумов. Соответствующий (не нейросетевой) алгоритм оптимизации был предложен в 1953 г. и получил название имитации отжига (Metropolis et al., 1953). Этот термин происходит от названия способа выжигания дефектов в кристаллической решетке. Атомы, занимающие в ней неправильное место, при низкой температуре не могут сместиться в нужное положение - им не хватает кинетической энергии для преодоления потенциального барьера. При этом система в целом находится в состоянии локального энергетического минимума. Для выхода из него металл нагревают до высокой температуре, а затем медленно охлаждают, позволяя атомам занять правильные положения в решетке, соответствующее глобальному минимуму энергии.
Субоптимальное решение некоторой задачи оптимизации, например, задачи коммивояжера, также может рассматриваться как решение в котором имеются дефекты - неправильные части маршрута. Лин и Кернигэн (Lin & Kernigan, 1973) ввели элементарные операции изменения текущего решения, такие как перенос (часть маршрута вырезается и вставляется в другое место) и обращение (выбирается фрагмент маршрута и порядок прохождения городов в нем меняется на обратный). При применении одной из этих операций происходит изменение маршрута с
на