Поиск кратчайшего пути на основе алгоритма Дейкстры с гибридным генетическо-муравьиным алгоритмом для транспортно-технологических циклов БПЛА

Abstract

Выбор маршрута является одним из ключевых компонентов формирования полетного задания для беспилотных летательных аппаратов (БПЛА), применяемых в точном сельском хозяйстве. В статье представлена компактная формализация маршрутизационного подхода, в котором алгоритм Дейкстры используется как детерминированный эталон поиска кратчайшего пути во взвешенной сети, а гибридная процедура на основе генетического алгоритма (Genetic Algorithm, GA) и алгоритма муравьиной колонии (Ant Colony Optimization, ACO) выполняет популяционный поиск допустимых маршрутов. Граф представлен в виде неориентированной взвешенной сети, веса ребер которой характеризуют стоимость перехода. Компонент ACO формирует альтернативные допустимые пути без циклов, усиливает феромоны на ребрах, входящих в более качественные маршруты, и реализует испарение феромонов; компонент GA ранжирует пути по суммарной стоимости и применяет селекцию, кроссовер и мутацию. В экспериментальной конфигурации исходного исследования использовались 18 узлов и 100 поколений, вероятность мутации составляла 0,30, а начальное значение феромона - 1,0. Лучшее решение было найдено на 20-й итерации, а визуализация маршрутов выполнялась средствами NetworkX. Для исследованной сети комбинированный метод характеризовался более быстрой сходимостью и меньшей стоимостью путей по сравнению с отдельным применением GA или ACO. Полученная схема может использоваться как модуль маршрутизации транспортно-технологических циклов БПЛА в системах точного земледелия, где детерминированная проверка кратчайшего пути и стохастический глобально-локальный поиск применяются совместно.