Порівняння мурашиного алгоритму оптимізації та двох його модифікацій

Анотація

Алгоритм мурашиної оптимізації є одним із ефективних сучасних алгоритмів для пошуку наближених розв’язків задачі комівояжера та подібних задач пошуку маршрутів на графах. Першу версію цього метаевристичного алгоритму оптимізації запропонував Марко Доріго в 1992 році [1]. Через деякий час в літературі було запро-поновано декілька модифікацій цього алгоритму. Метою дослідження є проведення порівняльного аналізу алгоритму оптимізації мурах (Ant Colony Optimization, ASO) [1] та його найбільш вдалих модифікацій: Ant Colony System (ACS) [2] і Max-Min Ant System (MMAS) [3]. Для цього проведено аналіз систем-них особливостей обміну інформацією в колонії мурах під час пошуку їжі. Представ-лено покроковий алгоритм, який моделює природну поведінку мурах-фуражирів у по-шуку найкоротшого шляху доставки їжі до мурашника. Розроблено програмну реалізацію трьох вказаних мурашиних алгоритмів для розв’язання задачі комівояжера. Через вікно інтерфейсу можна ввести кількість міст, кількість мурах, максимальну кількість ітерацій, виконати налаштування кожного алгоритму та вибрати будь-який із трьох алгоритмів. Результатами програми є: візуалізація найкоротшого знайденого маршруту, довжина цього маршруту та най-менша кількість ітерацій, за допомогою яких досягається найкоротший маршрут. Порівняльний аналіз результатів дозволив зробити такі висновки: 1) При вдало вибра-них параметрах налаштування алгоритму ітераційні методи, зазвичай, дають ре-зультат, близький до оптимального, однак, кількість необхідних для цього ітерацій може істотно відрізнятися. 2) Вивчення проблеми комівояжера за допомогою мура-шиних алгоритмів є швидше експериментальним, ніж теоретичним. Результат дуже сильно залежить від параметрів налаштування алгоритму, але теоретичне до-слідження цих залежностей залишається актуальним і невирішеним питанням.