Алгоритм колонии муравьев

13

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

  • Муравей рождается в колонии и должен собирать пищу из источника, чтобы поддерживать колонию.
  • Все муравьи похожи.
  • Область, в которой перемещается муравей, представляет собой сетку 1000x1000, поэтому каждая точка сетки служит допустимой точкой для размещения муравья. Теперь все алгоритмы, с которыми я сталкивался, включают в себя обработку вершин и ребер отдельно, но, поскольку мы ограничиваем движение муравьев только четырьмя направлениями (вверх, вниз, влево, вправо), я думаю, не имеет значения, куда мы помещаем феромон.
  • Точки сетки, упомянутые выше, хранят феромон.
  • Муравей сбрасывает феромон, только если он несет пищу.
  • Для муравья в позиции (i, j) он решает, куда двигаться на следующем шаге, принимая во внимание количество феромонов на его четырех смежных узлах в простой вероятностной формуле, то есть вероятность поездки в узел определяется как (количество феромона в конкретном соседнем узле) / (сумма количеств феромона в 4 смежных узлах).
  • Муравей не может вернуться в положение, из которого он только что пришел. Он может сделать это только в том случае, если он находится в месте, где есть еда, или в своей колонии.

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

Если муравей может куда-либо двигаться, муравьи, которые достигают источника пищи после него, также в основном будут следовать за ним… ДАЖЕ ЕСЛИ он не движется обратно к колонии. Это противоречит цели всего алгоритма.

Так что мои вопросы

  • Действительна ли вышеуказанная проблема? Если нет, то почему? Если да, то как с этим бороться?
  • Нужно ли нам вносить некоторые изменения в наше базовое понимание алгоритма, чтобы он действительно работал?
  • Какие еще тонкие, но важные вещи могут пропустить такие новички, как я?
транзистор
источник
1
Если бы я строил колонию муравьев, у меня было бы два типа меток феромонов: «обычный», всегда оставленный там, где путешествует муравей, и «еда», оставленная только муравьем, несущим пищу. Муравей движется к большей концентрации «обычного» феромона, если он несет пищу, в противном случае к «пищевым» меткам. Также я бы сделал муравьев "голодными" и "насыщенными"; голодный муравей движется к отметкам «еда», но от «обычных» отметок, чтобы искать новые источники пищи. (Я бы также сделал сетку шестиугольной, но это не главное.)
9000
Хотя существует множество вариантов, я думаю, что большинство алгоритмов колонии муравьев предполагают, что муравей может вспомнить дорогу домой. IOW, он знает уже посещенные узлы. Феромон вступает в игру для случайно перемещающихся муравьев.
Данк
Ты когда-нибудь играл в симант ?
«Я знаю, что существуют различные формы алгоритма, но все они были слишком математически детализированы для нас, поэтому мы выбрали подход, при котором у нас есть ...» Вы уверены, что действительно выполняете задание, которое вам дали, если вы не могли не понимаю алгоритмы?
Доваль
@ Доваль: Мы просто должны сделать проект по нашему выбору. Мы никоим образом не были связаны с полем. Курс является вводным в C ++. Наши инструкторы просто хотят, чтобы у нас был опыт разработки программного обеспечения.
транзистор

Ответы:

6

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

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

Феромоны не сбрасываются при каждом движении, они выпадают после того, как они перемещаются повсюду, и что-то оценивается, чтобы определить, какие муравьи лучше. Муравьи, которые лучше, чем выпадающие фереомоны (возможно, лучшие из 25% действующих муравьев).

enderland
источник
Я не согласен - ACO может работать, отбрасывая феремон каждый шаг, особенно когда целью является симуляция колонии муравьев (алгоритмы ACO для решения проблем, отличных от «это то, что делает колония муравьев», предпринимают шаги, чтобы сделать алгоритм более эффективным, но не обязательно, как настоящие муравьи).
Логан Пикап
1

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

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

Эрик Гринвуд
источник