Оптимизация муравьиной колонии для планировщика путей роботов на C++
Метаэвристический алгоритм Оптимизация муравьиной колонии (ACO) был вдохновлен природой (поведением муравьиной колонии). Марко Дориго был пионером алгоритма. Здесь вы можете найти его книгу.
Статья посвящена решению двух задач оптимизации в графе. Я решил самую критическую проблему, относящуюся к планировщику пути робота, найдя кратчайший путь между стартом и целью на графе. Дополнительно я решил задачу, связанную с популярной задачей на графике, которая определяется как Задача коммивояжёра (TSP).
Реализации этих двух задач на C++ вы найдете на моем GitHub.
Оптимизация муравьиной колонии
Алгоритм может быть получен из поведения муравьиной колонии. Муравьи охотятся за едой, отдаляясь от гнезда в поисках пищи, которую можно принести обратно. Феромоны — это крошечные молекулы, которые распространяет каждый отдельный муравей во время своих путешествий. Другие муравьи будут привлечены к феромонам, что увеличивает вероятность того, что они пойдут тем же путем, что и предыдущие муравьи.
Когда муравьи находят пищу, они возвращаются в гнездо. Каждый раз, когда муравей совершает это путешествие, феромоновый след усиливается, что делает его более привлекательным и гарантирует, что дополнительные муравьи присоединятся к деятельности по добыче пищи из источника. Одни муравьи не в состоянии найти дорогу самостоятельно. Однако такое количество феромонов увеличивает вероятность того, что муравей выберет оптимальный (кратчайший) путь. Поскольку муравьиная колония является динамической системой, она включает в себя параметр деградации феромонов — испарение, которое влияет на конденсацию феромонов с течением времени (как и ожидалось, конденсация феромонов со временем уменьшается).
В контексте алгоритма феромон может рассматриваться муравьями как индикатор «блестящего пути к еде».
Наиболее важной переменной в обсуждаемом алгоритме является механизм обновления феромонов (таблица феромонов), когда муравьи перемещаются между узлами графа в поисках пищи (цель). Таблица феромонов — единственный интересный «параметр», который позволяет муравью решить, какой путь кратчайший. Стол общий для колонии (общий для всех муравьев). Таблица в алгоритме обновляется за итерацию после того, как каждый муравей движется к цели.
На следующем рисунке представлена упрощенная идея обсуждаемого алгоритма. Есть два пути к цели (еде) А, Б. Длина В в два раза больше, чем А. Значит, за то же самое время количество муравьев, двигающихся по пути А, в принципе в два раза больше.< br /> Идем дальше, как обсуждалось до того, как муравей оставит феромон на пути, поэтому на пути А будет больше феромонов. Наконец, плотность феромонов повлияет на увеличение вероятности выбора пути.
Математические формулы алгоритма вы найдете в Википедии. Здесь я дам вам интуицию.
Наиболее важным является понимание обновления таблицы ферономонов и того, как муравей выбирает следующий узел в графе.
Спасибо за чтение.
