Где я могу узнать больше об оптимизации «муравьиной колонии»?

Question

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

Answer 1

Если вы не знаете немецкий язык (да, извините & # 8230;), мы с другом написали введение в код на эту тему, которое я нахожу вполне сносным. В тексте и коде используется пример TSP, чтобы представить концепцию.

Даже , если вы не знаете немецкий язык, взгляните на код и формулы в тексте, это все равно может помочь.

Answer 2

ссылка на Википедию фактически дала мне начало. Я прочитал статью и занялся кодированием. Я решал злую вариацию проблемы коммивояжера. Это удивительная метаэвристика. В принципе, любой тип поисковой задачи, которую можно поместить в граф (узлы и ребра, симметричные или нет), можно решить с помощью ACO.

Обратите внимание на разницу между глобальными и локальными трассами с феромонами. Местные феромоны препятствуют муравьям одного поколения пересекать один и тот же путь. Они не дают модели сходиться. Глобальные феромоны являются аттракторами и должны захватывать как минимум одного муравья на поколение. Они поощряют оптимальные пути в течение нескольких поколений.

Лучшее предложение, которое я имею, - просто поиграть с алгоритмом. Установите базовый решатель TSP и некоторые основные визуализации колоний. Тогда повеселись. Концептуально работать с муравьями - это круто. Вы программируете их базовое поведение, а затем освобождаете их. Я даже полюбил их. :)

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

Надо просто поиграть с этим, чтобы действительно понять это. Книги & amp; исследовательские работы дают только общее небесное понимание. Как велосипед, ты просто должен начать кататься. :)

ACO, безусловно, моя любимая абстракция для задач с графами.

Answer 3

National Geographic написал интересную статью некоторое время назад, рассказывая о некоторых из теорий.

Answer 4

Лучшим ресурсом по этим темам является Google Scholar.Я некоторое время работал над алгоритмами оптимизации колоний муравьев, вот несколько хороших статей:

• Оптимизация муравьиной колонии — новая метаэвристика
• Оптимизация муравьиной колонии — искусственные муравьи как метод вычислительного интеллекта

Только найдите «Колонию муравьев» в Google Scholar.

Также найдите статьи, опубликованные Марко Дориго.

Answer 5

Я удивлен, что никто не упомянул Библию ACO:

Marco Dorigo & amp; Thomas St & tzle: Оптимизация колоний муравьев

Эта книга написана автором ACO и хорошо читается. Вы можете взять его на пляж и повеселиться, читая его. Но это также самый полный ресурс из всех, отличный как справочник при реализации вещи.

Вы можете прочитать некоторые выдержки в Google Книгах

Еще один замечательный источник мудрости - домашняя страница ACO

Answer 6

См., например, эту статью об ученой учебе.

Здесь также обсуждается Как наиболее эффективно найти путь по графу маленького мира? вопрос.

Answer 7

На первый взгляд, это, похоже, тесно связано (или, возможно, является частным случаем) Алгоритм Метрополис . Так что это еще одно возможное направление для поиска.

Добавление: Этот файл PDF включает ссылку на оригинальную статью Метрополис 1953 года.

Answer 8

Ну, я нашел Домашняя страница Эрика Роллинза и его различные реализации (Haskell, Scala, Erlang,...) алгоритма ACO оказались полезными.А также Книга Энрике Альбы под названием «Параллельная метаэвристика:Новый класс алгоритмов», где вы можете найти целую главу с объяснением алгоритмов ACO и их различных применений.

Хт