Pull to refresh

Муравьиные алгоритмы

Reading time 8 min
Views 76K
Algorithms *

Предисловие


Совсем недавно в этом блоге была опубликована статья, посвященная алгоритму поведения роя пчел. Данная статья рассказывает о другом алгоритме роевого интеллекта, называемом муравьиным алгоритмом. Она состоит из введения, вкратце рассказывающего о заимствованном природном механизме, описания оригинального алгоритма Марко Дориго, обзора других муравьиных алгоритмов и заключения, в котором указываются области применения муравьиных алгоритмов и перспективные направления в их исследованиях.

Введение


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

Эти факты, однако, никак не согласуются с успешностью муравьев как вида. Они существуют на планете более 100 миллионов лет, строят огромные жилища, обеспечивают их всем необходимым и даже ведут настоящие войны. В сравнении с полной беспомощностью отдельных особей, достижения муравьев кажутся немыслимыми.
Читать дальше →
Total votes 83: ↑80 and ↓3 +77
Comments 43

Поиск в социальных сетях на основе поведения муравьёв

Reading time 3 min
Views 1.3K
Algorithms *


Исследователи из Мадридского университета имени Карлоса III (Universidad Carlos III de Madrid, UC3M) разработали алгоритм, основанный на поведении муравьёв при поиске еды. Данный алгоритм, как утверждают авторы, ускоряет поиск связей между элементами социальных сетей.
Ползти дальше
Total votes 21: ↑13 and ↓8 +5
Comments 5

Муравьиный алгоритм MMAS

Reading time 2 min
Views 13K
High performance *Programming *Algorithms *
Sandbox
Приветствую всех читателей. Сегодня попробую продолжить серию достаточно редких статей, посвящённым естественным алгоритмам. В частности, эта статья будет посвящена модификации муравьиного алгоритма, известной как Max-Min Ant System (MMAS). Я расскажу об отличиях от классического муравьиного алгоритма и о причинах внесения таких модификаций. Подробности под катом.
Читать дальше →
Total votes 11: ↑9 and ↓2 +7
Comments 2

Оптимизация на примере. Имитационный отжиг против муравьиного алгоритма. Часть 1

Reading time 11 min
Views 27K
Algorithms *
Sandbox
Всем доброго времени суток. Недавно прочитал статью про имитационный отжиг на примере задачи коммивояжера. Картинка до и после оптимизации вызвала интерес. Чем-то подобные вещи заманивают.Также в комментариях заметил, что людям было бы интересно посмотреть на сравнение с другими видами оптимизации.


Читать дальше →
Total votes 44: ↑44 and ↓0 +44
Comments 15

96 вычислительных ядер и оптимизация кода муравьиного алгоритма поиска маршрутов

Reading time 10 min
Views 17K
Intel corporate blog High performance *Algorithms *
Translation
Сегодня поговорим об оптимизации кода, который реализует муравьиный алгоритм нахождения оптимальных путей на графах. Узкие места в программе будем искать с помощью Intel VTune Amplifier XE 2016 Update 2, а оптимизировать с использованием MPI, OpenMP и библиотеки Intel Threading Building Blocks.



Наша цель заключается в том, чтобы добиться эффективной работы программы на компьютере с четырьмя процессорами Intel Xeon E7-8890 v4. Система оснащена 512 Гб оперативной памяти, на ней установлена Linux 3.10.0-327.el7.x86_64, код компилировался с помощью Intel Parallel Studio XE 2016 U2.
Читать дальше →
Total votes 50: ↑49 and ↓1 +48
Comments 11

Оптимизация на примере. Муравьиный алгоритм (ACS) против Метода отжига. Часть 2

Reading time 12 min
Views 19K
Algorithms *Matlab *
Продолжаю цикл статей «Оптимизация на примере». В данной статье сравниваются два эвристических алгоритма на избитой симметричной задаче коммивояжера. Сегодня чуть углубимся в данную тему и разберем определенную модификацию муравьиного алгоритма.


Читать дальше →
Total votes 23: ↑22 and ↓1 +21
Comments 7

Рисуем муравьями: процедурные изображения при помощи алгоритмов оптимизации муравьиной колонии

Reading time 7 min
Views 9.6K
Game development *Algorithms *Image processing *
Translation

Почему мне захотелось рисовать муравьями


Я хотела создать произведение искусства, исследующее сложность проектирования программного обеспечения. Когда я представляю огромную кодовую базу, то думаю о её самостоятельно возникающей сложности и о её переплетённых, взаимосвязанных частях. Её общая форма, если так можно выразиться, возникает из действий множества отдельных личностей.

Я думала о том, как представить это графически, и одной из нашедших во мне отклик картинок стало изображение муравьиной колонии. Муравьи — прекрасный пример возникающей (эмерджентной) сложности. Ни один отдельный муравей не является архитектором, но вместе они строят великолепные сложные структуры.
Читать дальше →
Total votes 42: ↑42 and ↓0 +42
Comments 5

Беги, муравей. Беги

Reading time 16 min
Views 11K
Entertaining tasks Programming *Java *Algorithms *Mathematics *
Tutorial
В данной статье рассматривается процесс создания имитационной модели поведения муравьиной колонии (можно почитать в википедии ) в среде имитационного моделирования «AnyLogic». Данная статья носит практический характер. В ней будет рассмотрен вопрос применения муравьиного алгоритма для решения задачи о коммивояжёре (Почитать можно тут).



Кратко о сути


Суть задачи коммивояжере заключается в том, что коммивояжер (продавец) должен посетить N городов побывав в каждом из них только один раз по наикратчайшему маршруту. Так как данная задача является NP-сложной и количество вариантов всех возможных маршрутов между N городами вычисляется как «N!», то время поиска кратчайшего маршрута будет увеличиваться по экспоненциальному закону с увеличением значения N. Соответственно время поиска кратчайшего маршрута(решения) с использованием алгоритма «полного перебора» (который дает точное решение) при количестве городов N>16 резко увеличивается (носит экспоненциальный характер). Поэтому мы будем искать не самый короткий по протяженности маршрут, а близкий к нему (рациональный) за конечное время с помощью «муравьиного алгоритма».
Читать дальше →
Total votes 17: ↑17 and ↓0 +17
Comments 3

Как муравьи решают проблемы коммивояжёров

Reading time 9 min
Views 14K
Algorithms *Mathematics *Reading room Popular science Biology

В математике и программировании порой используются необычные названия явлений, объектов и алгоритмов. Но почти всегда такие названия позволяют быстро понять суть описываемых сущностей. Возьмём, к примеру, широко известную задачу о коммивояжёре — найти кратчайший путь между заданными точками. И действительно, сразу представляется себе коммивояжёр, которому нужно обойти все дома в небольшом городке, но при этом затратить минимум усилий и времени. Для решения этой задачи используются разные алгоритмы, один из них называется «муравьиным». Для того, чтобы разобраться с этим алгоритмом, нам для начала нужно присмотреться к поведению муравьёв в их необычном организованном мире.

Читать далее
Total votes 41: ↑41 and ↓0 +41
Comments 4

Как создавать уникальные лабиринты

Reading time 11 min
Views 9.5K
RUVDS.com corporate blog Game development *Algorithms *C# *Mathematics *

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

А что если мы хотим тоже сделать свой интересный и уникальный лабиринт? Очевидно, нужно создать эти самые правила. Далее я постараюсь кратко, понятно и без лишних непонятных букв рассказать о разработке своего подхода к генерации различного рода лабиринтов. Объясню, почему я этим занялся, с чего начинал и как всё развилось до вполне приличного алгоритма на основе подхода и почему каждый из вас может взять этот подход за основу и адаптировать его под свои желания.
Погрузиться в мир лабиринтов
Total votes 45: ↑45 and ↓0 +45
Comments 14

Беги муравей, беги! Ремейк 2022

Reading time 22 min
Views 3.4K
System Analysis and Design *Mathematics *Matlab *Visual programming *
Tutorial

На написание этой статьи меня сподвигла одноименная статья на хабре: "Беги, муравей. Беги". В ней рассматривается решение задачи коммивояжёра  в среде AnyLogic.

О самой задаче можно почитать здесь:  Задача коммивояжёра.  

Если кратко, то задача сводится к нахождению самого короткого пути обхода набора точек (городов) на карте. Решение методом перебора не является эффективным, поскольку количество вычислений огромно. Например, для 15 точек существует 43 миллиарда маршрутов, а для 18 точек (городов) уже 117 триллионов!!!

AnyLogic – среда, предназначенная для решения логистических задач с использованием моделей агентов. Мне показалось интересным, что несмотря на «заточенность» среды на агентное моделирование, при создании модели приходится писать достаточно много кода. Поэтому возникла идея: попробовать реализовать подобную модель, используя среду структурного моделирования, в виде графических функционально-блочных диаграмм. Я уже приводил примеры, как можно реализовать принципы объектно-ориентированного программирования (ООП) в графическом языке программирования.  См. "Объектное ориентированное программирование в графических языках". Здесь же мы попробуем реализовать агентное моделирование средствами системной динамики. 

Дальше будем много хардкороного программежа. Поэтому слабонервным, беременным, девушкам обоего пола, кормящим матерям лучше не читать, во избежание родимчика, свинки и чумки!

Читать далее
Total votes 4: ↑4 and ↓0 +4
Comments 4