Пользователь
0,0
рейтинг
30 сентября 2010 в 22:20

Разработка → Муравьиные алгоритмы

Предисловие


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

Введение


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

Эти факты, однако, никак не согласуются с успешностью муравьев как вида. Они существуют на планете более 100 миллионов лет, строят огромные жилища, обеспечивают их всем необходимым и даже ведут настоящие войны. В сравнении с полной беспомощностью отдельных особей, достижения муравьев кажутся немыслимыми.

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

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

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

В 1992 году в своей диссертации Марко Дориго (Marco Dorigo) предложил заимствовать описанный природный механизм для решения задач оптимизации [1]. Имитируя поведение колонии муравьев в природе, муравьиные алгоритмы используют многоагентные системы, агенты которых функционируют по крайне простым правилам. Они крайне эффективны при решении сложных комбинаторных задач – таких, например, как задача коммивояжера, первая из решенных с использованием данного типа алгоритмов.

 

Классический муравьиный алгоритм для решения задачи коммивояжера


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

Каждый муравей хранит в памяти список пройденных им узлов. Этот список называют списком запретов (tabu list) или просто памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма – то есть перед тем, как муравей вновь проходит путь – он опустошается.

Кроме списка запретов, при выборе узла для перехода муравей руководствуется «привлекательностью» ребер, которые он может пройти. Она зависит, во-первых, от расстояния между узлами (то есть от веса ребра), а во-вторых, от следов феромонов, оставленных на ребре прошедшими по нему ранее муравьями. Естественно, что в отличие от весов ребер, которые являются константными, следы феромонов обновляются на каждой итерации алгоритма: как и в природе, со временем следы испаряются, а проходящие муравьи, напротив, усиливают их.

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



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

После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный длине пройденного пути:

,

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



 

Обзор модификаций классического алгоритма


Результаты первых экспериментов с применением муравьиного алгоритма для решения задачи коммивояжера были многообещающими, однако далеко не лучшими по сравнению с уже существовавшими методами. Однако простота классического муравьиного алгоритма (названного «муравьиной системой») оставляла возможности для доработок – и именно алгоритмические усовершенствования стали предметом дальнейших исследований Марко Дориго и других специалистов в области комбинаторной оптимизации. В основном, эти усовершенствования связаны с большим использованием истории поиска и более тщательным исследованием областей вокруг уже найденных удачных решений. Ниже рассмотрены наиболее примечательные из модификаций.

Elitist Ant System

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

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

Ant-Q

Лука Гамбарделла (Luca M. Gambardella) и Марко Дориго опубликовали в 1995 году работу, в которой они представили муравьиный алгоритм, получивший свое название по аналогии с методом машинного обучения Q-learning [4]. В основе алгоритма лежит идея о том, что муравьиную систему можно интерпретировать как систему обучения с подкреплением. Ant-Q усиливает эту аналогию, заимствуя многие идеи из Q-обучения.

Алгоритм хранит Q-таблицу, сопоставляющую каждому из ребер величину, определяющую «полезность» перехода по этому ребру. Эта таблица изменяется в процессе работы алгоритма – то есть обучения системы. Значение полезности перехода по ребру вычисляется исходя из значений полезностей перехода по следующим ребрам в результате предварительного определения возможных следующих состояний. После каждой итерации полезности обновляются исходя из длин путей, в состав которых были включены соответствующие ребра.

Ant Colony System

В 1997 году те же исследователи опубликовали работу, посвященную еще одному разработанному ими муравьиному алгоритму [5]. Для повышения эффективности по сравнению с классическим алгоритмом, ими были введены три основных изменения.

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

Max-min Ant System

В том же году Томас Штютцле (Tomas Stützle) и Хольгер Хоос (Holger Hoos) предложили муравьиный алгоритм, в котором повышение концентрации феромонов происходит только на лучших путях из пройденных муравьями [6]. Такое большое внимание к локальным оптимумам компенсируется вводом ограничений на максимальную и минимальную концентрацию феромонов на ребрах, которые крайне эффективно защищают алгоритм от преждевременной сходимости к субоптимальным решениям.

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

ASrank

Бернд Бульнхаймер (Bernd Bullnheimer), Рихард Хартл (Richard F. Hartl) и Кристине Штраусс (Christine Strauß) разработали модификацию классического муравьиного алгоритма, в котором в конце каждой итерации муравьи ранжируются в соответствие с длинами пройденных ими путей [7]. Количество феромонов, оставляемого муравьем на ребрах, таким образом, назначается пропорционально его позиции. Кроме того, для более тщательного исследования окрестностей уже найденных удачных решений, алгоритм использует элитных муравьев.

 

Заключение


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

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

Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать анализ способа выбора настраиваемых параметров алгоритмов. В последние годы предлагаются различные способы адаптации параметров алгоритмов «на лету» [8]. Поскольку от выбора параметров сильно зависит поведение муравьиных алгоритмов, именно к этой проблеме обращено наибольшее внимание исследователей на данный момент.

 

Литература


[1] M. Dorigo, “Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale (Optimization, Learning, and Natural Algorithms)”, диссертация на соискание ученой степени “Doctorate in Systems and Information Electronic Engineering”, Politecnico di Milano, 1992 г.

[2] A. Colorni, M. Dorigo, V. Maniezzo, “Distributed Optimization by Ant Colonies” // Proceedings of the First European Conference on Artificial Life, Paris, France, Elsevier Publishing, стр. 134-142, 1991 г.

[3] M. Dorigo, V. Maniezzo, A. Colorni, “The Ant System: Optimization by a colony of cooperating agents” // IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 1, стр. 29-41, 1996 г.

[4] L. M. Gambardella, M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem” // Twelfth International Conference on Machine Learning, Morgan Kaufmann, стр. 252-260, 1995 г.

[5] M. Dorigo, L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation Vol. 1, 1, стр. 53-66, 1997 г.

[6] T. Stützle, H. Hoos, “MAX-MIN Ant System and local search for the traveling salesman problem” // IEEE International Conference on Evolutionary Computation, стр. 309-314, 1997 г.

[7] Bernd Bullnheimer, Richard F. Hartl, Christine Strauß, “A new rank based version of the Ant System. A computational study” // Adaptive Information Systems and Modelling in Economics and Management Science, 1, 1997 г.

[8] T. Stützle, M. López-Ibáñez, P. Pellegrini, M. Maur, M. de Oca, M. Birattari, Michael Maur, M. Dorigo, “Parameter Adaptation in Ant Colony Optimization” // Technical Report, IRIDIA, Université Libre de Bruxelles, 2010 г.
Дмитрий @dimka_kravchuk
карма
94,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

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

  • 0
    Прочитал и всё же не понял — допустим, что муравьи полагаются только на собратьев (эффект стада), тогда 5 муравей последует за 4, 4 за 3, 3 за 2, 2 за 1, а 1 как? Придется ему все-таки анализировать обстановку? Или куда глаза глядят? Вариант «по феромонам других муравьев» не предлагать, ибо эти феромоны тоже каким-то образом были оставлены первооткрывателями.
    • +1
      У них есть деление по функциям. Ищет муравей-разведчик. «Агенты»-муравьи отличаются примитивными функциями.
      • НЛО прилетело и опубликовало эту надпись здесь
    • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        как укрытие для яиц и для их обогрева под солнцем. Обычно муравьи постоянно вытаскивают яйца на солнышко, при этом подвергают их большому риску.
        Насколько мне известно, вытаскивают они яйца не чтобы погреть на солнце (температура внутри муравейника летом и так достаточно высокая), а чтобы наоборот проветрить, чтобы не перегревались и чтобы плесень не образовывалась от влаги.
        • НЛО прилетело и опубликовало эту надпись здесь
  • +5
    Я так ждал картинок
    • +15
      А тут формулы!!! АААА!!!
    • +4
      Картинки есть в статье википедии

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

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

            Тем более, что исследования местности не прекращаются даже тогда, когда мощная тропа протоптана. Если позже будет найден ощутимо более оптимальный маршрут, то он постепенно будет переманивать к себе больше муравьёв и со временем станет основным маршрутом.
        • +2
          Сначала доля случайности. Муравьёв много, они расползаются в разные стороны (случайно) и вероятно одну и ту же «добычу» найдут несколько муравьёв по разным маршрутам. И возвращаться они будет тоже по разным маршрутам. Но чем длиннее путь, тем дольше по нему идти, и тем больше испаряются феромоны до очередного прохода муравья. Т.е. короткие маршруты «пахнут» феромонами интенсивнее (там их концентрация больше), а длинные менее интенсивно (там больше успевает испариться).
          Поэтому со временем после многократного хождения муравьёв по разным путям маршруты оптимизируются и из множества остаются только самые короткие (а точнее самые быстрые по времени прохождения). Такая естественная селекция.
          • 0
            ну это я понял. но допустим, добычу нашел один муравей и путь неоптимален. все? никаких шансов?
            • +1
              Да, если нашёл один и на большом расстоянии, то шансов мало. Тут работают законы больших чисел.
            • 0
              Если его нашел один муравей, то он отложит некоторый уровень феромона на пути, а значит на следующем цикле больше муравьев обратят внимание на этот путь. Они в свою очередь отложат свой феромон и феромон на пути станет еще сильнее. Таким образом муравьи, которые будут ходить по не оптимальному пути постепенно станут пользоваться оптимальным.
  • –2
    В процессе чтения Вербера «муравьи» встречаются мне повсюду.
    Пожалуй третью книгу дочитывать не буду…
  • +1
    когда читаю такие статьи начинаю чувствовать себя как то неуютненько 8)
    • +8
      Идите в ЖЖ. Там уютненько -))
    • +1
      Хабрахабр — самостоятельно реорганизуемое сообщество.
      Мы все муравьи и бегаем по муравьиному алогритму.
      Наверное, поэтому на хабре доминирует много обзоров ноутов, apple…
      Хабрачеловеки! Мы все стали предсказуемы! ААА! :-)
      Печально…
  • 0
    Ага, а во как сбоят муравьиные алгоритмы. Знаменитый муравьиный круг смерти.
    • +1
      Я в смысле, что на хабре об этом уже писали
    • 0
      Как же я хочу увидеть такое в живую!
  • 0
    Занимательно. Лично мне сразу вспомнился «Непобедимый» Станислава Лема.
  • 0
    Если бы вашу заметку прочитал Дж.Оруэлл, кто знает, возможно его книга называлась бы не «Скотный двор» а както иначе)
  • 0
    Был выпуск передачи Гордон в полночь на тему организации муравьев.

    Вот тут можно посмотреть. Помню, интересно слушать было.
  • +1
    Алгоритм пчел, муравьев. Ждем алгоритм стада слонов :)
    • +8
      алгоритм проще простого. стаду слонов не нужно искать кратчайший путь — оно его прокладывает :)
  • 0
    Думаю что проблема муравьиных алгоритмов в необходимости иметь широкий охват путей, что бы быть универсальными и не сваливаться в субоптимальные решения. А следовательно они будут не очень эффективными. Возможно когда-нить будет широкое распараллеливание будет нормой и тогда, на этих системах они будут эффективнее, но на централизованных скорее всего нет.
    • 0
      Я не совсем Вас понял. Что значит «широкий охват путей»?

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

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

        Помня о том, что локальный оптимум — это путь до еды, и то, что еда в той точке у муравьев обычно быстро заканчивается, то приходим к выводу, что эта неэффективность быстро исчезает, т.к. заканчивается еда.
        • 0
          Это в жизни еда кончается, в задачах оптимизации оптимум никуда не исчезает.
          • 0
            Поэтому предлагаю оптимизацию поиска оптимумов =)

            При нахождении экстремумма запоминать его и постепенно изменять его в сторону среднего результата, таким образом стимулируя агентов к поиску новых результатов.
  • 0
    Кстати, а подобные алгоритмы могут быть очень даже эффективными в применении к задачам Code game Challenge
  • 0
    Мне подумалось, что это можно использовать для расчета рейтинга блогов на хабре )
  • 0
    Насколько мне известно, проводились опыты, которые доказали что муравьи достаточно сообразительны что бы передавать друг-другу информацию не только в виде феромонового следа. В опыте, после того как разведчики находили еду, лабиринт менялся на аналогичный, но чистый, без запахов. Но рабочие муравьи заготовители всё равно находили пищу. Скорее всего информация передавалась в виде жестов усиками, наподобие пчелиного танца.
    • 0
      Естественно, муравьи используют и непосредственный обмен информацией, а не только стигмергию. Усиками они «обнюхивают» друг друга, насчет жестов — не знаю.
      • 0
        Я вам даже больше скажу — они считать умеют
        Не в том арифметическом понимании, как мы себе представляем, но он в состоянии считать особые характерности пути, по которому он бежал, и передавать эту информацию муравьям-фуражорам. Независимо от химических следов
  • 0
    Реализовываю данный алгоритм. Написал эту часть для одного муравья (обернуть циклом, считающим муравьев, позже не проблема): муравей выбрал рандомно путь, опираясь на уровень феромона и на расстояние, перешел на следующую вершину. Это мне нужно обернуть в некий цикл. Каким он должен быть? Никак не врублюсь.

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

    image

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

    Вот каким должно быть условие, которое определило бы для данного муравья, что он пришел в конец или он заблудился = идти больше некуда, все посещенные вокруг.
    • 0
      Идти больше некуда — это значит проход выполнил. Следующий.

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

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

    wiki описывает эти параметры как Alpha — величина, определяющая «жадность» алгоритма,
    Beta — величина, определяющая «стадность» алгоритма.
    Alpha + Beta = 1.

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.