Я студент, работающий над симулятором колонии муравьев для курсового проекта. Алгоритм для этого (очевидно) алгоритм колонии муравьев. Я знаю, что существуют различные формы алгоритма, но все они были слишком математически детализированы для нас, поэтому мы выбрали подход, в котором мы имеем:
- Муравей рождается в колонии и должен собирать пищу из источника, чтобы поддерживать колонию.
- Все муравьи похожи.
- Область, в которой перемещается муравей, представляет собой сетку 1000x1000, поэтому каждая точка сетки служит допустимой точкой для размещения муравья. Теперь все алгоритмы, с которыми я сталкивался, включают в себя обработку вершин и ребер отдельно, но, поскольку мы ограничиваем движение муравьев только четырьмя направлениями (вверх, вниз, влево, вправо), я думаю, не имеет значения, куда мы помещаем феромон.
- Точки сетки, упомянутые выше, хранят феромон.
- Муравей сбрасывает феромон, только если он несет пищу.
- Для муравья в позиции (i, j) он решает, куда двигаться на следующем шаге, принимая во внимание количество феромонов на его четырех смежных узлах в простой вероятностной формуле, то есть вероятность поездки в узел определяется как (количество феромона в конкретном соседнем узле) / (сумма количеств феромона в 4 смежных узлах).
- Муравей не может вернуться в положение, из которого он только что пришел. Он может сделать это только в том случае, если он находится в месте, где есть еда, или в своей колонии.
Теперь меня беспокоит (и то, что на самом деле происходит в нашей программе), что когда муравей FIRST достигает позиции, в которой есть пища, и поднимает ее, то, как работает наш алгоритм, он может двигаться куда угодно! Это потому, что он оставит только след феромона, как только у него будет пища, а не раньше, и, поскольку это первый муравей, следа не будет.
Если муравей может куда-либо двигаться, муравьи, которые достигают источника пищи после него, также в основном будут следовать за ним… ДАЖЕ ЕСЛИ он не движется обратно к колонии. Это противоречит цели всего алгоритма.
Так что мои вопросы
- Действительна ли вышеуказанная проблема? Если нет, то почему? Если да, то как с этим бороться?
- Нужно ли нам вносить некоторые изменения в наше базовое понимание алгоритма, чтобы он действительно работал?
- Какие еще тонкие, но важные вещи могут пропустить такие новички, как я?
источник
Ответы:
Это не так, как работает ACO. ACO сбрасывает феромоны только после того, как муравьи прошли через все точки сетки. Затем вы что-то оцениваете (возможно, общее время в пути), а затем отбрасываете феромоны для хороших муравьев и повторяете.
Как правило, они не перемещаются в одну и ту же вершину дважды, хотя вы можете настроить это для специфичности реализации.
Феромоны не сбрасываются при каждом движении, они выпадают после того, как они перемещаются повсюду, и что-то оценивается, чтобы определить, какие муравьи лучше. Муравьи, которые лучше, чем выпадающие фереомоны (возможно, лучшие из 25% действующих муравьев).
источник
Реализации, которые я видел от других, и те, которые я написал для себя, всегда заставляли муравьев высвобождать феромоны вдоль пути, по которому они шли, чтобы добраться до еды, как только они достигли еды. То есть муравьи идут от своей колонии к еде после случайной прогулки; пути, по которым следуют муравьи из колонии до еды , затем маркируются с помощью феромонов только после того, как муравьи добились успеха в достижении пищи. Обратное путешествие не моделируется явно. Как правило, несколько муравьев проходят свой курс, прежде чем любые феромоны будут депонированы для текущей итерации. Затем феромоны используются для успешного прохождения пути, и начинается новый раунд.
Обычно шансы муравья зайти в данный узел взвешиваются на количество феромонов, умноженное на меру «благости». Например, мера благости может быть чем-то вроде инверсии расстояния между муравьем и пищей - это будет держать муравьев, пытающихся двигаться к еде, независимо от предыдущих отложений феромона. Качество может быть дополнительно взвешено для учета других факторов, например, через некоторые узлы легче проходить, чем через другие. И, как указывает enderland, как правило, существует какая-то форма «выбора» пути, когда все муравьи успешно прошли свои курсы, где только некоторая часть «лучших» путей выбирается для отложения феромона. Тем не менее, вы все равно должны получить разумные пути даже без выбора,
источник