Бойків М. В., Житенко О. В. Аналіз досліджень маршрутизації руху з використанням мурашиних алгоритмів оптимізації // Міжнародний науковий журнал "Інтернаука". — 2019. — №10.
Технічні науки
УДК 519.863
Бойків Микола Васильович
кандидат технічних наук,
доцент кафедри транспортних технологій
Національний університет “Львівська політехніка”
Бойкив Николай Васильевич
кандидат технических наук,
доцент кафедры транспортных технологий
Национальный университет "Львовская политехника"
Boykiv Mykola
Candidate of Technical Sciences,
Associate Professor of Transport Technologies Department
Lviv Politechnic National University
Житенко Олександр Вікторович
кандидат технічних наук,
доцент кафедри транспортних технологій
Національний університет “Львівська політехніка”
Житенко Александр Викторович
кандидат технических наук,
доцент кафедры транспортных технологий
Национальный университет "Львовская политехника"
Zhytenko Oleksander
Candidate of Technical Sciences,
Associate Professor of Transport Technologies Department
Lviv Politechnic National University
АНАЛІЗ ДОСЛІДЖЕНЬ МАРШРУТИЗАЦІЇ РУХУ З ВИКОРИСТАННЯМ МУРАШИНИХ АЛГОРИТМІВ ОПТИМІЗАЦІЇ
АНАЛИЗ ИССЛЕДОВАНИЙ МАРШРУТИЗАЦИИ ДВИЖЕНИЯ С ИСПОЛЬЗОВАНИЕМ МУРАВЬИНЫХ АЛГОРИТМОВ ОПТИМИЗАЦИИ
ROUTE INVESTIGATIONS ANALYSIS USING ANT COLONY OPTIMIZATION
Анотація. Запропоновано до розгляду аналіз досліджень щодо оптимізації складних систем, де застосовуються природні механізми пошуку найкращих рішень – мурашині алгоритми.
Ключові слова: мурашині алгоритми, задача комівояжера, маршрут.
Аннотация. Предложено к рассмотрению анализ исследований по оптимизации сложных систем, где применяются природные механизмы поиска лучших решений - муравьиные алгоритмы.
Ключевые слова: муравьиные алгоритмы, задача коммивояжера, маршрут.
Summary. It is proposed to consider the analysis of research on optimization of complex systems where natural mechanisms of searching for the best solutions - ant algorithms are used.
Key words: ant algorithms, travelling salesman problem, route.
В науковій періодиці широко представлено точні та евристичні підходи вирішення задач оптимізації [1]. Недоліком першого підходу є потреба в великих обчислювальних ресурсах, другий підхід не гарантує визначення оптимального вирішення проблеми даючи на виході певний локальний оптимум.
Все частіше при оптимізації складних систем науковці застосовують природні механізми прийняття найкращих рішень. Науковий напрямок Natural Computing об'єднує методи з природними засобами прийняття рішень до яких належить алгоритми мурашиних колоній (Ant Colony Optimization). При такому підході відмовляються від спроб відшукати точне рішення і зосереджуються на пошуку наближеного, нехай не оптимального, але хоча б близького до нього. Мурашині алгоритми є одними з найефективніших поліноміальних алгоритмів для знаходження наближених розв'язків задачі комівояжера, а також аналогічних задач пошуку маршрутів на графах.
Мурашині алгоритми оптимізації належать до класу евристичних, що засновані на природній поведінці мурах. Дані алгоритми широко використовуються для вирішення багатьох комбінаторних задач оптимізації, їх різновид продовжує зростати та набувати широкої популярності у різних сферах досліджень.
Перші експерименти з вивчення поведінки реальних мурах було виконано дослідниками Брюсельського вільного університету (Universitе Libre de Bruxelles) у 1989 році [2], які цікавилися питаннями щодо здатності тварин з обмеженою і локальною навігаційною інформацією знаходити найкоротші маршрути до їжі. Спостерігаючи за колонією аргентинських мурах дослідники відзначили їх здатність прокладати найкоротший маршрут виходу з лабіринту взаємодіючи одна з одною залишаючи після себе феромони, тобто біологічно активні речовини, які виділяють тварини. Присутність даної речовини впливає на рішення інших мурах щодо вибору свого маршруту слідування, що пояснюється наявністю позитивного зворотного зв’язку. Тобто мураха з найбільшою вірогідністю буде слідувати маршрутом з найбільшою кількістю феромону опираючись на вже існуючий досвід інших. Проте описати поведінку мурах та розробити стратегію вирішення задач пошуку найкоротших відстаней вдалося лише у 1992 році дослідникові цього ж університету Маркові Доріго [3]. Було визначено послідовність кроків алгоритму, а саме створення мурашок, пошук найкоротшого маршруту, який являє собою вершини графа та оновлення феромону. Ймовірність переходу від однієї вершини графа до іншої було описано наступною формулою:
(1)
де кількість феромону на ребрі (i, j); привабливість ребра (відстань між вершинами i та j); та параметри, що визначають вагу ребра та рівень феромону при виборі шляху слідування; список вже відвіданих вершин графу.
Найпростіший експеримент, який демонструє здатність мурах знаходити оптимальні маршрути руху можна провести якщо на шляху слідування мурах поставити перешкоду. В такому разі постає необхідність визначення нового оптимального маршруту шляхом її обходу з правої, або ж з лівої сторони. Дійшовши до перешкоди мурахи з однаковою вірогідність будуть обходити її з обох сторін. Однак ті мурахи, які випадково виберуть коротший шлях слідування будуть швидше його проходити і за декілька пересувань він буде більше збагачений феромоном. Оскільки вибір мурахи залежить від концентрації феромону, то наступні комахи будуть надавати перевагу саме цьому маршруту продовжуючи збагачувати його ферментом поки цей маршрут з певних причин стане недоступним (рис. 1) [4-6]. Аналогічно оптимальні маршрути будуть знаходитися з більшою кількістю перешкод.
Рис. 1. Поведінка мурашиної колонії [7]
Мурашині алгоритми оптимізації можуть бути застосовані при вирішення проблем маршрутизації, планування, біоінформатики тощо.
Для прикладу розглянемо як можна застосувати ідею мурашиних алгоритмів оптимізації при проектуванні маршрутної мережі громадського транспорту. Завдання проектування маршрутної мережі пасажирського транспорту є узагальненням відомої задачі комівояжера (Travelling Salesman Problem), при якій необхідно побудувати відразу кілька незамкнутих маршрутів. Головна ідея проектування маршрутної мережі громадського транспорту полягає в пошуку оптимальних пар початкових та кінцевих зупинок. Різні пари можуть формувати різні маршрути з різними пасажиропотоками. Якщо розглядати автобуси як колонії мурах, початкові зупинки як гнізда, звідки комахи починають свій шлях, а кінцеві зупинки як джерело їжі, то задача проектування маршрутних мереж громадського транспорту спрощується до процесу пошуку мурашиними колоніями їжі, а маршрути будуть будуватися крок за кроком на основі базової ідеї, що наведена на рис. 1.
На рис. 2 представлено псевдозапис мурашиного алгоритму оптимізації.
Рис. 2. Псевдоазапис мурашиного алгоритму оптимізації [5]
Як видно з рис. 1 на кожній ітерації мурашки будують ряд рішень ConstractAntSolution, які опціонально будуть поліпшуватися через локальний пошук ApplyLocalSearch, та оновлювати феромони UpdatePheromones. Інакше кажучи на рис. 2 показано імітацію поведінки мурашок, які безперервно шукають оптимальне рішення з можливістю адаптації до змін зовнішнього середовища у реальному часі. Реалізацію алгоритму, а також його різновиди та удосконалення на різних мовах програмування можна з легкістю відшукати на веб-сервісах для спільної розробки програмного забезпечення, наприклад GitHub.
Мурашині алгоритми оптимізації також застосовуються при вирішенні задачі комівояжера (Travelling Salesman Problem) [8]. Стандартно в якості вхідних параметрів є набір міст та відстані між ними. Розв’язком тут буде найкоротший шлях, який буде пройдений через усі міста, причому відвідувати кожне місто можна лише один раз. В даному випадку проблема вирішується шляхом імітації штучних мурах, що рухаються по ребрам та вершинам графу. Кожна вершина графу являє собою місто, а ребро – зв'язок між двома містами. Певна кількість мурах розміщується у випадково обраному місті, кожна мураха на своєму шляху вибирає все ще не відвідане місто відповідно до насиченості шляху феромонами. Приймає таке рішення мураха відповідно до свого списку вже відвіданих міст (1). На наступній ітерації відбувається оновлення маршруту де найбільш коротші маршрути отримуються найбільшу кількість феромону і в подальшому будуть вибиратися з більшою ймовірністю. Цикл буде повторюватися до заданої кількості ітерацій.
Пізніше було запропоновано різновиди підходів за способом оновлення шляхів – ребер [9], які дістали назви щільнісний (ant-density), кількісний (ant-quantity) та циклічний (ant-cycle).
У зв’язку з можливістю різного математичного опису поведінки мурах [9] розроблено методи засновані на елітній стратегії, ранжуванні, максі-мінний (MAX-MIN), а також їх модифікації [10, 11]. Подальший розвиток підходу спостерігається у застосуванні бази нечітких правил за аналогією з нечітким управління параметрами генетичних алгоритмів.
Література
