Что такое имитация отжига?

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

Существует два критических фактора, которые должен указать пользователь программы имитации отжига: начальная температура или процент худших решений, которые можно изучить; и скорость охлаждения, которая является скоростью, с которой этот процент уменьшается. Низкая начальная температура часто заканчивается результатом, далеким от оптимального. Запуск с очень высокой температуры может привести к тому, что поиск займет гораздо больше времени, чем необходимо. Аналогично, слишком высокая скорость охлаждения приведет к плохим результатам, а очень низкая скорость охлаждения приведет к тому, что программа будет работать очень долго.

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

Насколько далеко может зайти программа, зависит от процента худших решений, которые программа может изучить. С течением времени все более и более лучшие решения находят, и риск глубокого разрыва уменьшается, поэтому процент худших решений, которые может исследовать компьютер, уменьшается. Уменьшение этой фракции называется «охлаждением». Когда температура достигает заданной доли - которая не должна быть равна 0 - поиск заканчивается.

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