Аналіз досліджень маршрутизації руху з використанням мурашиних алгоритмів оптимізації

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Кафедра транспортних технологій

Національний університет «Львівська політехніка»

Аналіз досліджень маршрутизації руху з використанням мурашиних алгоритмів оптимізації

Анализ исследований маршрутизации движения с использованием муравьиных алгоритмов оптимизации

Route investigations analysis using ant colony optimization

Бойків Микола Васильович

кандидат технічних наук

Житенко Олександр Вікторович

кандидат технічних наук

Анотація

Ключові слова: мурашині алгоритми, задача комівояжера, маршрут.

Аннотация

Ключевые слова: муравьиные алгоритмы, задача коммивояжера, маршрут.

Summary

Key words: ant algorithms, travelling salesman problem, route.

В науковій періодиці широко представлено точні та евристичні підходи вирішення задач оптимізації [1]. Недоліком першого підходу є потреба в великих обчислювальних ресурсах, другий підхід не гарантує визначення оптимального вирішення проблеми даючи на виході певний локальний оптимум.

Все частіше при оптимізації складних систем науковці застосовують природні механізми прийняття найкращих рішень. Науковий напрямок Natural Computing об'єднує методи з природними засобами прийняття рішень до яких належить алгоритми мурашиних колоній (Ant Colony Optimization). При такому підході відмовляються від спроб відшукати точне рішення і зосереджуються на пошуку наближеного, нехай не оптимального, але хоча б близького до нього. Мурашині алгоритми є одними з найефективніших поліноміальних алгоритмів для знаходження наближених розв'язків задачі комівояжера, а також аналогічних задач пошуку маршрутів на графах.

Мурашині алгоритми оптимізації належать до класу евристичних, що засновані на природній поведінці мурах. Дані алгоритми широко використовуються для вирішення багатьох комбінаторних задач оптимізації, їх різновид продовжує зростати та набувати широкої популярності у різних сферах досліджень.

Перші експерименти з вивчення поведінки реальних мурах було виконано дослідниками Брюсель- ського вільного університету (Universito Libre de Bruxelles) у 1989 році [2], які цікавилися питаннями щодо здатності тварин з обмеженою і локальною навігаційною інформацією знаходити найкорот- ші маршрути до їжі. Спостерігаючи за колонією аргентинських мурах дослідники відзначили їх здатність прокладати найкоротший маршрут виходу з лабіринту взаємодіючи одна з одною залишаючи після себе феромони, тобто біологічно активні речовини, які виділяють тварини. Присутність даної речовини впливає на рішення інших мурах щодо вибору свого маршруту слідування, що пояснюється наявністю позитивного зворотного зв'язку. Тобто мураха з найбільшою вірогідністю буде слідувати маршрутом з найбільшою кількістю феромону опираючись на вже існуючий досвід інших. Проте описати поведінку мурах та розробити стратегію вирішення задач пошуку найкоротших відстаней вдалося лише у 1992 році дослідникові цього ж університету Маркові Доріго [3]. Було визначено послідовність кроків алгоритму, а саме створення мурашок, пошук найкоротшого маршруту, який являє собою вершини графа та оновлення феромону. Ймовірність переходу від однієї вершини графа до іншої було описано наступною формулою:

Найпростіший експеримент, який демонструє здатність мурах знаходити оптимальні маршрути руху можна провести якщо на шляху слідування мурах поставити перешкоду. В такому разі постає необхідність визначення нового оптимального маршруту шляхом її обходу з правої, або ж з лівої сторони. Дійшовши до перешкоди мурахи з однаковою вірогідність будуть обходити її з обох сторін. Однак ті мурахи, які випадково виберуть коротший шлях слідування будуть швидше його проходити і за декілька пересувань він буде більше збагачений феромоном. Оскільки вибір мурахи залежить від концентрації феромону, то наступні комахи будуть надавати перевагу саме цьому маршруту продовжуючи збагачувати його ферментом поки цей маршрут з певних причин стане недоступним (рис. 1) [4-6]. Аналогічно оптимальні маршрути будуть знаходитися з більшою кількістю перешкод.

Рис. 1. Поведінка мурашиної колонії [7]

маршрутизація рух мурашиний алгоритм

Мурашині алгоритми оптимізації можуть бути застосовані при вирішення проблем маршрутизації, планування, біоінформатики тощо.

Для прикладу розглянемо як можна застосувати ідею мурашиних алгоритмів оптимізації при проектуванні маршрутної мережі громадського транспорту. Завдання проектування маршрутної мережі пасажирського транспорту є узагальненням відомої задачі комівояжера (Travelling Salesman Problem), при якій необхідно побудувати відразу кілька незамкнутих маршрутів. Головна ідея проектування маршрутної мережі громадського транспорту полягає в пошуку оптимальних пар початкових та кінцевих зупинок. Різні пари можуть формувати різні маршрути з різними пасажиропотоками. Якщо розглядати автобуси як колонії мурах, початкові зупинки як гнізда, звідки комахи починають свій шлях, а кінцеві зупинки як джерело їжі, то задача проектування маршрутних мереж громадського транспорту спрощується до процесу пошуку мурашиними колоніями їжі, а маршрути будуть будуватися крок за кроком на основі базової ідеї, що наведена на рис. 1.

На рис. 2 представлено псевдозапис мурашиного алгоритму оптимізації.

Рис. 2. Псевдоазапис мурашиного алгоритму оптимізації [5]

Як видно з рис. 1 на кожній ітерації мурашки будують ряд рішень ConstractAntSolution, які опці- онально будуть поліпшуватися через локальний пошук ApplyLocalSearch, та оновлювати феромони UpdatePheromones. Інакше кажучи на рис. 2 показано імітацію поведінки мурашок, які безперервно шукають оптимальне рішення з можливістю адаптації до змін зовнішнього середовища у реальному часі. Реалізацію алгоритму, а також його різновиди та удосконалення на різних мовах програмування можна з легкістю відшукати на веб-сервісах для спільної розробки програмного забезпечення, наприклад GitHub.

Мурашині алгоритми оптимізації також застосовуються при вирішенні задачі комівояжера (Travelling Salesman Problem) [8]. Стандартно в якості вхідних параметрів є набір міст та відстані між ними. Розв'язком тут буде найкоротший шлях, який буде пройдений через усі міста, причому відвідувати кожне місто можна лише один раз. В даному випадку проблема вирішується шляхом імітації штучних мурах, що рухаються по ребрам та вершинам графу. Кожна вершина графу являє собою місто, а ребро -- зв'язок між двома містами. Певна кількість мурах розміщується у випадково обраному місті, кожна мураха на своєму шляху вибирає все ще не відвідане місто відповідно до насиченості шляху феромонами. Приймає таке рішення мураха відповідно до свого списку вже відвіданих міст tabu_k (1). На наступній ітерації відбувається оновлення маршруту де найбільш коротші маршрути отримуються найбільшу кількість феромону і в подальшому будуть вибиратися з більшою ймовірністю. Цикл буде повторюватися до заданої кількості ітерацій.

Пізніше було запропоновано різновиди підходів за способом оновлення шляхів -- ребер [9], які дістали назви щільнісний (ant-density), кількісний (ant-quantity) та циклічний (ant-cycle).

У зв'язку з можливістю різного математичного опису поведінки мурах [9] розроблено методи засновані на елітній стратегії, ранжуванні, максі- мінний (MAX-MIN), а також їх модифікації [10, 11]. Подальший розвиток підходу спостерігається у застосуванні бази нечітких правил за аналогією з нечітким управління параметрами генетичних алгоритмів.

Література

1. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 2003. Vol. 35(3), PP. 268-308.

2. Goss S., Aron J., Deneubourg J. Self-organized shortcuts in the argentine ant, Naturwissenschaften, 1989. Vol. 76. PP.579-581.

3. Dorigo M., Optimization, Learning and Natural Algorithms, Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, 1992 (in Italian).

4. Er. Manpreet Kaur, Er. Gurpreet Singh A review on Neural Network and Ant Colony Optimization for Vehicle Traffic Analysis and Routing, International Journal of Engineering and Computer Science, 2017. Vol. 6, Issue 5. PP. 343349.

5. Dorigo M., Birattari M., Stutzle T. Ant colony optimization, Computational Intelligence Magazine IEEE, 2006. Vol. 1. PP. 28-39.

6. Sharma R., Kumari A. A Review on Traffic Route Optimizing by Using Different Swarm Intelligence Algorithm International Journal of Computer Science and Mobile Computing, 2015. Vol. 4. Issue 5. PP. 271-277.

7. Koushal M., Verma V. A Review on ANT Colony Optimization Technique to Solve Scheduling Problem, International Journal of Scientific Research Engineering & Technology, 2017. -- Vol. 6, Issue 3, pp. 212-215.

8. Dorigo M., Gambardella L. Ant colony system: A cooperative learning approach to the traveling salesman problem, Transactions on Evolutionary Computation, 1997. Vol. 1 PP. 53-66.

9. Bullnheimer B. A new rank-based versio of the ant system: A computation study, Central Europian Journal for Operations Research and Economics, 1999. Vol. 7 (1). PP. 25-38.

10. H. B. Duan Development on ant colony algorithm theory and its application, Control and Decision, 2004. Vol. 19. PP. 1321-1326.

11. K. Sochaand Ant colony optimization for continuous domains, European Journal of Operational Research. 2008. Vol. 185. № 3. PP. 1155-1173.

Размещено на Allbest.ru