МУРАВЬИНЫЙ АЛГОРИТМ НА PYTHON

Аннотация

Данное исследование посвящено анализу и оптимизации муравьиного алгоритма для решения за- дачи коммивояжёра, являющейся классической NP-трудной проблемой комбинаторной оптимизации. Основная цель работы – экспериментальная оценка влияния параметров алгоритма на качество и эф- фективность поиска приближённых решений, а также разработка рекомендаций по их адаптивной настройке. В качестве тестового набора данных использован стандартный граф Berlin52 из библио- теки TSPLIB, содержащий координаты 52 городов с известным оптимальным маршрутом длиной 7542 единицы. Эксперименты проводились в среде Python с использованием библиотеки ACO-Pants, реализующей муравьиный алгоритм. Была выполнена серия из 10 запусков с фиксированными парамет- рами: количество муравьёв (20), число итераций (100), коэффициенты влияния феромонов (α=1.0) и расстояний (β=2.0), а также скорость испарения феромонов (ρ=0.5). Результаты показали среднее отклонение от оптимума в 1.85%, с лучшим найденным решением 7675.23 (отклонение 1.67%). Для повышения эффективности алгоритма исследованы адаптивные механизмы динамической настройки параметров: линейное увеличение α (до 2.0) и уменьшение β (до 3.0), снижение ρ (до 0.3), а также рост числа муравьёв (до 30). Это позволило сократить среднее отклонение до 1.70% и повысить стабиль- ность решений. Особое внимание уделено анализу баланса между исследованием новых маршрутов и эксплуатацией накопленных данных. Установлено, что увеличение количества муравьёв улучшает ка- чество решений, однако после 30 агентов прирост эффективности снижается. Динамическая коррек- тировка параметров предотвращает преждевременную сходимость к локальным минимумам и уско- ряет поиск глобально оптимальных путей. Визуализация динамики сходимости подтвердила быстрое уменьшение длины маршрута на первых 20 итерациях с последующей стабилизацией. Практическая значимость работы заключается в демонстрации гибкости муравьиного алгоритма для задач мар- шрутизации в логистике и сетевом планировании. Результаты показывают, что ACO превосходит универсальные методы (например, генетические алгоритмы) по вычислительной эффективности для TSP. Разработанные рекомендации по настройке параметров могут быть применены для масштаби- рования алгоритма на графы большей размерности. Исследование подчёркивает важность адаптив- ных подходов в метаэвристической оптимизации и открывает перспективы для дальнейшего улучше- ния алгоритма за счёт гибридизации с другими методами.