Автор: Mazumder Pinaki
Автор перевода: Нифталиев В.Э.
Источник: Genetic Algorithms: For Vlsi Design, Layout & Test Automation // Pearson Education, 1999 , p. 79-80
Моделирование отжига является хорошо известным, высокопроизводительным методом оптимизации для комбинаторных задач. Алгоритм имитации отжига представлены в Рис.1. Температура устанавливается равной относительно высокому значению, и она постепенно снижается пока "точка замерзания" не будет достигнута. При каждой температуре выбираются компоненты для возможного движения, пока не будет достигнуто равновесие. Если подвижность выбранных компонентов улучшает их размещение, то движение выполняется. В противном случае, движение выполняется с вероятностью, которая экспоненциально уменьшается с ростом температуры. Компоненты обычно выбирается случайным образом для парных обменов.
Рисунок 1 – Алгоритм имитации отжига
Имитации отжига и генетические алгоритмы являются весьма интенсивными вычислениями. Тем не менее, генетический алгоритм имеет некоторые присущие особенности, которые, если использовать должным образом, могут привести к значительной экономии. Одно из различий в том, что имитация отжига работает только с одним решением за один раз, в то время как генетический алгоритм поддерживает большую популяцию решений, которые оптимизированы одновременно. Таким образом, генетический алгоритм использует опыт, накопленный в прошлом опыт для разведки пространства решений, и он может начать интенсивнее искать в области в которой средние затраты будут меньше. В то время как имитация отжига работает только с одним решением, и имеет очень мало истории от прошлых итераций, которую можно использовать в обучении.
Имитация отжига и генетические алгоритмы имеют механизмы для предотвращающие схождение в локальном потимуме. В имитации отжига, это достигается путем отбрасывания лучшего решения, и сохранения худших. Генетический алгоритм также опирается на худших особей и тем самым откладывая возможность нахождения ложного оптимума, но так как в генетических алгоритмах популяция состоит из большого числа особей, то нет необходимости отбрасывать самых лучших особей. Кроме того, в генетическом алгоритме, каждая новая особь построена из двух предыдущих, что означает, что через несколько итераций, все особи в популяции имеют шанс унаследовать лучшие свойства для формирования одной супер-особи. В имитации отжига, каждое новое решение формируется только из одного старого решения, которое означает, что хорошие характеристики радикально различных решений не смешиваются. Решение принимаются или отбрасываются в целом, в зависимости от их общей стоимости.
Имитации отжига является по своей сути последовательным алгоритмом. Мы ищем алгоритм, который можно эффективно распараллелить на распределенных компьютерах, подключенных, например, по Ethernet. Такие сети, в отличие от специализированных параллельных аппаратных средств, очень популярны сегодня. Генетический алгоритма можно распараллелить на таких слабосвязанных распределенных компьютерных сетях со 100% загрузкой процессора [148]. Существенные исследования были проведены для распараллеливания алгоритма имитации отжига [27], [62]. Хотя некоторые модифицированные параллельные реализации алгоритма имитации отжига разработаны для объединения памяти нескольких компьютеров, и они как известно, последовательные алгоритмы, которые не могут быть эффективно распараллелены в распределенной среде сети.