Цель - найти кратчайший путь
между начальной и конечной позициями, общий путь
длина выбирается как стоимость или вознаграждение, связанное
с каждым возможным решением.
В симуляции три разных размера сетки
сети, то есть 20X20, 30X30 и
40X40. Предполагается, что один муравей может занимать только одного
узел и перемещается к одному из соседних узлов одновременно
в четырех разных направлениях, то есть вверх, вниз, влево и
право. Все узлы равномерно распределены в
сеть; и расстояние между любыми двумя соседними
узлы нормированы на 1 (или 1 единицу блока). Таким образом
длина пути представлена в виде числа
(блок) блоков.
Симуляция начинается с «чистой» среды;
то есть в исходной сети нет никаких препятствий.
верхний левый угол выбирается в качестве отправной точки и
нижний правый встречный выбран в качестве пункта назначения.
Все феромоны инициализируются как 0,1. Муравей
Затем применяется алгоритм колонии, чтобы найти самый короткий
путь и феромоны откладываются. Вычислительный
Блок-схема показана на рис. 1. Рис. 2 иллюстрирует путь
найдено по алгоритму ACO в сетке 20X20
сходится к своему оптимальному значению, где ось у
представляет длину пути (в количестве блоков / сеток)
и ось X представляет время моделирования (в
секунд). Чтобы моделировать динамическую среду, барьеры (препятствия) добавляются после схождения алгоритма (для справедливого сравнения размеры препятствий пропорциональны размерам сетей). Где две более темные области в сетке 40X40 представляют два произвольных препятствия, добавленных в позиции, которые выбираются случайным образом. Алгоритм ACO должен быть вызван снова, чтобы найти кратчайший путь в этой новой сети с препятствиями. Инициализация феромона играет важную роль в алгоритме ACO. В этом проекте после добавления препятствий феромоны в сети повторно инициализируются. Тестируются две разные схемы реинициализации, а именно: глобальная инициализация и локальная инициализация, и сравниваются их характеристики. При глобальной инициализации все феромоны во всей сети равномерно сбрасываются обратно к исходному уровню феромонов, который равен 0,1. При локальной инициализации «градиент» феромонов инициализируется вокруг объекта. Значение половины самых высоких уровней феромонов в сети применяется непосредственно к точкам, которые находятся рядом с объектом. Уровни феромонов затем уменьшаются на долю (например, на 50%), когда точки движутся наружу в виде «круга» вокруг объекта.