Моделирование колонии муравьев - оптимизация пути

Question

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

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

Текущее моделирование работает довольно хорошо, но найденный путь не является оптимальным. У меня есть 2 проблемы, которые я не знаю, как решить:

1. Как мне смоделировать тот факт, что диагональный ход длиннее недиагонального (вверх, вниз, влево или вправо)?

1. Как мне симулировать диффузию феромона? Прямо сейчас, феромон испаряется со временем, но диффузия отсутствует. Я пытался перенести некоторое количество феромона из каждой клетки, каждый тик симуляции в 8 соседних клеток, но в результате получился полный беспорядок - вся среда была заполнена феромоном - я думаю, что это из-за механизма муравьи используют для регулировки уровня феромонов.

Answer 1

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

Поэтому вместо квадратной сетки вы можете рассмотреть сетку или сеть узлов с одинаковым расстоянием, то есть шестиугольную сетку. Это также изменит количество соседних ячеек, но в этом весь смысл.

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