ОДИН ІЗ СПОСОБІВ РЕЛІЗАЦІЇ МУРАШИНОГО АЛГОРИТМУ НА ПРИКЛАДІ РОЗВ’ЯЗКУ ЗАДАЧІ КОМІВОЯЖЕРА

Анотація

У сучасному світі оптимізаційні задачі мають ключове значення в логістиці, енергетиці, промисловості, фінансах, медицині, машинному навчанні тощо. Задача оптимізації – це математична задача пошуку найкращого рішення з-поміж усіх можливих, за певним критерієм (мінімізація витрат, часу, максимізація прибутку). Існують точні методи, що дають оптимальний результат (метод повного перебору, динамічне програмування), проте вони неефективні для задач великого масштабу. Евристичні та метаевристичні методи (жадібні, генетичні, мурашині алгоритми) дають наближені, але практично ефективні рішення. Однією із задач оптимізації є задача комівояжера, метою якої є пошук найкоротшого маршруту, що проходить через усі міста один раз.  Мурашиний алгоритм є одним із ефективних алгоритмів для знаходження наближених розв'язків задачі комівояжера, а також аналогічних завдань пошуку маршрутів на графах. Під час пошуку їжі мурахи залишають феромони на шляху. Агенти (мурахи) обирають шляхи за ймовірністю, що залежить від інтенсивності феромонів та довжини маршруту. Кожна мураха поступово будує маршрут, феромони оновлюються після ітерацій з урахуванням якості рішень. Параметри алгоритму (α, β, ρ) впливають на вибір маршруту, здатність до адаптації та уникнення застарілих рішень. В статті наведений процес проєктування та розробки програмного продукту, який забезпечує  генерацію графа та реалізує на ньому пошук найкоротшого маршруту з допомогою мурашиного алгоритму. Програмна реалізація алгоритму оптимізації мурашиної колонії виконана з використанням HTML, CSS і JavaScript. Однією з важливих особливостей програми є візуалізація графа та роботи алгоритму. Графічне представлення здійснюється за допомогою елемента Canvas, що дозволяє відображати вершини у вигляді кольорових кіл, а ребра – у вигляді ліній із товщиною та прозорістю, які відповідають інтенсивності феромонів.