@dimka_kravchuk30 сен 2010 в 18:20

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

8 мин

87K

Алгоритмы *

+77

Комментарии 43

@r00tkit 30 сен 2010 в 19:09

Прочитал и всё же не понял — допустим, что муравьи полагаются только на собратьев (эффект стада), тогда 5 муравей последует за 4, 4 за 3, 3 за 2, 2 за 1, а 1 как? Придется ему все-таки анализировать обстановку? Или куда глаза глядят? Вариант «по феромонам других муравьев» не предлагать, ибо эти феромоны тоже каким-то образом были оставлены первооткрывателями.

@popov 30 сен 2010 в 19:22

У них есть деление по функциям. Ищет муравей-разведчик. «Агенты»-муравьи отличаются примитивными функциями.

НЛО прилетело и опубликовало эту надпись здесь

@xn__p2a 1 окт 2010 в 06:35

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

Насколько мне известно, вытаскивают они яйца не чтобы погреть на солнце (температура внутри муравейника летом и так достаточно высокая), а чтобы наоборот проветрить, чтобы не перегревались и чтобы плесень не образовывалась от влаги.

НЛО прилетело и опубликовало эту надпись здесь

@Nitrych 30 сен 2010 в 19:11

Я так ждал картинок

@Markmaster 30 сен 2010 в 19:12

А тут формулы!!! АААА!!!

@xn__p2a 30 сен 2010 в 19:18

Картинки есть в статье википедии

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

@TheShock 30 сен 2010 в 19:40

Исследователь нашел источник пищи и, чтобы не заблудится, вернулся по своим же ж следам. Где гарантия, что этот путь самый короткий (если другого не нашли). Даже в картинке из википедии путь не самый короткий, но ведь они могли даже такого короткого так и не найти.

@TheShock 30 сен 2010 в 19:41

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

@xn__p2a 30 сен 2010 в 20:32

Такое тоже возможно, но маловероятно. Из-за того, что муравьёв в колонии очень много и они поначалу исследуют местность хаотически, шанс того, что значительно более длинный маршрут «освоят» гораздо раньше, чем более короткий, небольшие.

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

@xn__p2a 30 сен 2010 в 19:54

Сначала доля случайности. Муравьёв много, они расползаются в разные стороны (случайно) и вероятно одну и ту же «добычу» найдут несколько муравьёв по разным маршрутам. И возвращаться они будет тоже по разным маршрутам. Но чем длиннее путь, тем дольше по нему идти, и тем больше испаряются феромоны до очередного прохода муравья. Т.е. короткие маршруты «пахнут» феромонами интенсивнее (там их концентрация больше), а длинные менее интенсивно (там больше успевает испариться).
Поэтому со временем после многократного хождения муравьёв по разным путям маршруты оптимизируются и из множества остаются только самые короткие (а точнее самые быстрые по времени прохождения). Такая естественная селекция.

@TheShock 30 сен 2010 в 20:25

ну это я понял. но допустим, добычу нашел один муравей и путь неоптимален. все? никаких шансов?

@xn__p2a 30 сен 2010 в 20:34

Да, если нашёл один и на большом расстоянии, то шансов мало. Тут работают законы больших чисел.

@vladsharikov 17 апр 2014 в 20:51

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

@GreenAngel 30 сен 2010 в 19:30

В процессе чтения Вербера «муравьи» встречаются мне повсюду.
Пожалуй третью книгу дочитывать не буду…

@xaja 30 сен 2010 в 19:53

когда читаю такие статьи начинаю чувствовать себя как то неуютненько 8)

@digreen 30 сен 2010 в 20:21

Идите в ЖЖ. Там уютненько -))

@jackxxl 30 сен 2010 в 21:03

Хабрахабр — самостоятельно реорганизуемое сообщество.
Мы все муравьи и бегаем по муравьиному алогритму.
Наверное, поэтому на хабре доминирует много обзоров ноутов, apple…
Хабрачеловеки! Мы все стали предсказуемы! ААА! :-)
Печально…

@Iforgot 30 сен 2010 в 20:32

Ага, а во как сбоят муравьиные алгоритмы. Знаменитый муравьиный круг смерти.

@Iforgot 30 сен 2010 в 20:35

Я в смысле, что на хабре об этом уже писали

@ilyak 1 окт 2010 в 19:48

Как же я хочу увидеть такое в живую!

@TreyLav 30 сен 2010 в 20:46

Занимательно. Лично мне сразу вспомнился «Непобедимый» Станислава Лема.

@squint 30 сен 2010 в 21:55

Если бы вашу заметку прочитал Дж.Оруэлл, кто знает, возможно его книга называлась бы не «Скотный двор» а както иначе)

@ilyaster 1 окт 2010 в 05:06

Был выпуск передачи Гордон в полночь на тему организации муравьев.

Вот тут можно посмотреть. Помню, интересно слушать было.

@Jenyay 1 окт 2010 в 05:41

Алгоритм пчел, муравьев. Ждем алгоритм стада слонов :)

@grimskin 1 окт 2010 в 06:58

алгоритм проще простого. стаду слонов не нужно искать кратчайший путь — оно его прокладывает :)

@Wott 1 окт 2010 в 06:38

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

@dimka_kravchuk 1 окт 2010 в 06:47

Я не совсем Вас понял. Что значит «широкий охват путей»?

Муравьиные алгоритмы и так не сваливаются в субоптимальные решения. Тому, как увеличить при этом эффективность, посвящена третья часть статьи.

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

@build_your_web 1 окт 2010 в 12:45

С муравьями локальные оптимумы не работают.

Помня о том, что локальный оптимум — это путь до еды, и то, что еда в той точке у муравьев обычно быстро заканчивается, то приходим к выводу, что эта неэффективность быстро исчезает, т.к. заканчивается еда.

@dimka_kravchuk 1 окт 2010 в 14:18

Это в жизни еда кончается, в задачах оптимизации оптимум никуда не исчезает.

@build_your_web 2 окт 2010 в 06:02

Поэтому предлагаю оптимизацию поиска оптимумов =)

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

@Colwin 1 окт 2010 в 07:21

Кстати, а подобные алгоритмы могут быть очень даже эффективными в применении к задачам Code game Challenge

@joint 1 окт 2010 в 09:31

Мне подумалось, что это можно использовать для расчета рейтинга блогов на хабре )

@alexfg 1 окт 2010 в 10:19

Насколько мне известно, проводились опыты, которые доказали что муравьи достаточно сообразительны что бы передавать друг-другу информацию не только в виде феромонового следа. В опыте, после того как разведчики находили еду, лабиринт менялся на аналогичный, но чистый, без запахов. Но рабочие муравьи заготовители всё равно находили пищу. Скорее всего информация передавалась в виде жестов усиками, наподобие пчелиного танца.

@dimka_kravchuk 1 окт 2010 в 14:16

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

@gionet 2 окт 2010 в 17:42

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

@vladsharikov 6 апр 2014 в 21:51

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

Допустим следующая ситуация:

Есть данный граф. Зеленая вершина начальная, красная целевая. Скорее всего муравей пойдет в пятую вершину. Нашли пятую вершину, перешли в нее. Посчитали вероятности, деваться некуда. Идем в 6. Перешли в 6. Можем пойти в 1, но она уже посещенная. Больше идти некуда.

Вот каким должно быть условие, которое определило бы для данного муравья, что он пришел в конец или он заблудился = идти больше некуда, все посещенные вокруг.

@r3code 2 сен 2014 в 06:26

Идти больше некуда — это значит проход выполнил. Следующий.

Посмотрите про реализацию алгоритма тут works.doklad.ru/view/BsaT-3tALgc/3.html наглядно написаны правила выбора направления.
Следующего муравья запускаете из этой же точки — он не пойдет туда где ближе, посомневается.

@r3code 2 сен 2014 в 06:33

Еще очень интересно, как муравьи определают размеры помещений.
Заходит один разведчик и бежит примерно по кгругу, виляя и иногда уприраясь в стены. Набегает несколько кругов, а так как он бегает по разному, то крывые неизбежно пересекаются. Если пересечений много — значит места мало, но если пересечения редки — помещение большое.
После разведчик приводит с собой еще одного муравья и процедура повторяется. Но рабочие все равно не пойдут за двумя муравьями, даже если помещение действительное большое — их надо убедить.
Эти двое приводят еще двух — процедура ииследования повторяется, затем уже четверо идут рассказать другам. Как только достаточно большая масса муравьев уже исследовала помещение — колония одобрила его прием. С этого момента оно заселяется и используется.

@akazakou 6 апр 2015 в 13:52

Мне кажется у этого алгоритма есть несколько багов.

НЛО прилетело и опубликовало эту надпись здесь

Зарегистрируйтесь на Хабре, чтобы оставить комментарий