Метод имитации отжига

[@braintorch]

Самый ожидаемый комментарий в топике.

[@odiszapc]

Да имитирует он.

[@IGlukhov]

Есть примеры отжига и в биологии.
Это ренатурация ДНК.

[@mIK_LH]

bash.org.ru/quote/146034

[@halyavin]

На практике этот метод используется в 100 раз чаще генетических алгоритмов. По крайней мере на топкодеровских марафонах еще никто генетикой не выиграл, а отжиг там весьма распространен.

[@Curious_Vik]

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

[@Unlogic]

Недостаток simulated annealing'а в том, что в холодном состоянии он становится таким же жадным, как скажем градиентный спуск. Это значит, что он за горячую фазу должен попасть в ту область, где локальный максимум будет решением задачи.
Генетика — не серебряная пуля, она безусловно медленнее, но она не жадная, что позволяет (и требует) использовать ее для задач с большим количеством локальных максимумов в пространстве решений.
За статью большое спасибо.

[@Curious_Vik]

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

[@Tranz]

Цветовая гамма на скрине не очень понравилась сонным глазам =\

[@toxicdream]

Сонными глазами такой материал лучше не смотреть.

Вам теорию объясни, практику распиши, пример приведи, литературу покажи, а вы еще и на иллюстрации ругаетесь!
Вы же все мотивацию у авторов убиваете!
Или это показатель деградации лени нашей молодежи? Увы и ах.

Не понравилась картинка, предложите свою, может автор заменит, если будет согласен с вашей критикой.

[@toxicdream]

Вот, банально конечно, но ваши сонные глазки может и не обидятся :)

[@pxx]

Это же классика: красный на синем.

[@r3s3t]

Наверное, не я один открыл статью, чтобы найти тут что-то весёлое? :)

[@track]

Заголовок, безусловно, определил успех поста на Хабре.

[@MATPOCKuH]

Блин, я реально полез под кат, чтобы почитать как генетическими алгоритмами можно имитировать недетский отжиг! :) И даже сразу придумал применение — поставить на форуме бота, чтобы тот там отжигал… ;)

[@Qnan]

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

[@Curious_Vik]

Добавил в тэги.

[@i4niac]

Хорошая тенденция в последнее время.
Все больше хороших статей об алгоритмах.
Дейкстра, генерация ландшафтов, несколько статей о генетических алгоритмах, отжиг и т.д.
Уже пора говорить что хабр торт?

[@Blurayman]

> Кстати, метод отжига по быстроте и точности по крайней мере не проигрывает генетическому алгоритму, а чаще всего опережает его.

может быть потому, что ГА ищет локальный оптимум? ) Одним из главных входных параметров ГА является дельта — минимальная степень изменения функции цели на каждой итерации. Задача считается решенной, если F(n)/F(n-1) < d.

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

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

[@AlexTikhonov]

Гм… мне почему-то очень и очень напоминает Метод Монте Карло? Просто звучит очень и очень похоже.

[@Curious_Vik]

Всё верно. Это вариация (или развитие) метода Монте Карло.

[@deNULL]

Интересно было бы посмотреть на реализацию подбора наиболее вездеходного «велосипеда» — аналогично генетическому алгоритму, ссылку на который недавно постили на хабре.

Ну и сравнить, что эффективнее окажется.

[@Iskin]

Мне кажется, что нельзя метод отжига противопоставиставлять генетическому алгоритму. Потому что, мы легко получим отжиг из ГА просто заменив метод селекции. То есть отжиг — это просто одна из возможных оптимизаций эволюционных алгоритмов.

[@megalol]

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

[@SaveTheRbtz]

Рекомендую:
Clever Algorithms. Nature-Inspired Programming Recipes

Книга описывающая множество интересных алгоритмов, включая Simulated Annealing и Genetic-семейство. К алгоритмам прилагается псевдокод и код на Ruby.

PDFку можно скачать прямо с сайта бесплатно.

[@EvilFox]

Картинки сдохли, можно перезалить? Спасибо.

[@Curious_Vik]

Сделал

[@EvilFox]

Спасибо ещё раз. Ссылка на pdf'ку кстати тоже сдохла, но её не сложно нагуглить.

[@argz]

А правильно ли я понимаю, что в формуле

Дельта Е и Т должны быть примерно одного порядка?