Комментарии 31
Есть примеры отжига и в биологии.
Это ренатурация ДНК.
Это ренатурация ДНК.
На практике этот метод используется в 100 раз чаще генетических алгоритмов. По крайней мере на топкодеровских марафонах еще никто генетикой не выиграл, а отжиг там весьма распространен.
В проекте я сравнивал работу метода отжига и генетического алгоритма, и генетика даже близко не показывала результатов, сравнимых с отжигом. Хотя не исключаю, что я криво его реализовал.
Недостаток simulated annealing'а в том, что в холодном состоянии он становится таким же жадным, как скажем градиентный спуск. Это значит, что он за горячую фазу должен попасть в ту область, где локальный максимум будет решением задачи.
Генетика — не серебряная пуля, она безусловно медленнее, но она не жадная, что позволяет (и требует) использовать ее для задач с большим количеством локальных максимумов в пространстве решений.
За статью большое спасибо.
Генетика — не серебряная пуля, она безусловно медленнее, но она не жадная, что позволяет (и требует) использовать ее для задач с большим количеством локальных максимумов в пространстве решений.
За статью большое спасибо.
Цветовая гамма на скрине не очень понравилась сонным глазам =\
Сонными глазами такой материал лучше не смотреть.
Вам теорию объясни, практику распиши, пример приведи, литературу покажи, а вы еще и на иллюстрации ругаетесь!
Вы же все мотивацию у авторов убиваете!
Или это показательдеградации лени нашей молодежи? Увы и ах.
Не понравилась картинка, предложите свою, может автор заменит, если будет согласен с вашей критикой.
Вам теорию объясни, практику распиши, пример приведи, литературу покажи, а вы еще и на иллюстрации ругаетесь!
Вы же все мотивацию у авторов убиваете!
Или это показатель
Не понравилась картинка, предложите свою, может автор заменит, если будет согласен с вашей критикой.
Это же классика: красный на синем.
Наверное, не я один открыл статью, чтобы найти тут что-то весёлое? :)
Заголовок, безусловно, определил успех поста на Хабре.
Блин, я реально полез под кат, чтобы почитать как генетическими алгоритмами можно имитировать недетский отжиг! :) И даже сразу придумал применение — поставить на форуме бота, чтобы тот там отжигал… ;)
Вы бы указали где-нибудь в начале, что «имитация отжига» = «simulated annealing». Похоже, есть несколько различных переводов этого термина на русский, и до сегодняшнего дня я не был знаком ни с одним.
Хорошая тенденция в последнее время.
Все больше хороших статей об алгоритмах.
Дейкстра, генерация ландшафтов, несколько статей о генетических алгоритмах, отжиг и т.д.
Уже пора говорить что хабр торт?
Все больше хороших статей об алгоритмах.
Дейкстра, генерация ландшафтов, несколько статей о генетических алгоритмах, отжиг и т.д.
Уже пора говорить что хабр торт?
> Кстати, метод отжига по быстроте и точности по крайней мере не проигрывает генетическому алгоритму, а чаще всего опережает его.
может быть потому, что ГА ищет локальный оптимум? ) Одним из главных входных параметров ГА является дельта — минимальная степень изменения функции цели на каждой итерации. Задача считается решенной, если F(n)/F(n-1) < d.
Обычно вначале прогоняют решение задачи какой-то реализацией ГА, а потом подбирают другие параметры реализации алгоритма ГА так, чтобы решение не сползало в минимальное изменение дельты за очень короткое время. Обычно для этого уменьшают шаг изменения некоторых параметров функции цели или повышают вероятность мутации — это аналог повышения температуры в методе отжига.
Но, собственно, узнать по дельте, нашли ли мы глобальный или локальный оптимум, нельзя.
может быть потому, что ГА ищет локальный оптимум? ) Одним из главных входных параметров ГА является дельта — минимальная степень изменения функции цели на каждой итерации. Задача считается решенной, если F(n)/F(n-1) < d.
Обычно вначале прогоняют решение задачи какой-то реализацией ГА, а потом подбирают другие параметры реализации алгоритма ГА так, чтобы решение не сползало в минимальное изменение дельты за очень короткое время. Обычно для этого уменьшают шаг изменения некоторых параметров функции цели или повышают вероятность мутации — это аналог повышения температуры в методе отжига.
Но, собственно, узнать по дельте, нашли ли мы глобальный или локальный оптимум, нельзя.
Гм… мне почему-то очень и очень напоминает Метод Монте Карло? Просто звучит очень и очень похоже.
Интересно было бы посмотреть на реализацию подбора наиболее вездеходного «велосипеда» — аналогично генетическому алгоритму, ссылку на который недавно постили на хабре.
Ну и сравнить, что эффективнее окажется.
Ну и сравнить, что эффективнее окажется.
Мне кажется, что нельзя метод отжига противопоставиставлять генетическому алгоритму. Потому что, мы легко получим отжиг из ГА просто заменив метод селекции. То есть отжиг — это просто одна из возможных оптимизаций эволюционных алгоритмов.
Рекомендую:
Clever Algorithms. Nature-Inspired Programming Recipes
Книга описывающая множество интересных алгоритмов, включая Simulated Annealing и Genetic-семейство. К алгоритмам прилагается псевдокод и код на Ruby.
PDFку можно скачать прямо с сайта бесплатно.
Clever Algorithms. Nature-Inspired Programming Recipes
Книга описывающая множество интересных алгоритмов, включая Simulated Annealing и Genetic-семейство. К алгоритмам прилагается псевдокод и код на Ruby.
PDFку можно скачать прямо с сайта бесплатно.
Картинки сдохли, можно перезалить? Спасибо.
А правильно ли я понимаю, что в формуле
Дельта Е и Т должны быть примерно одного порядка?
Дельта Е и Т должны быть примерно одного порядка?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Метод имитации отжига