ВИКОРИСТАННЯ МУРАШИНОГО АЛГОРИТМУ ДЛЯ ПОШУКУ БЛИЗЬКОГО ДО ОПТИМАЛЬНОГО МАРШРУТУ - Наукові конференції
Головна
UA RU EN

Вас вітає Інтернет конференція!

Вітаємо на нашому сайті

Рік заснування видання - 2011

ВИКОРИСТАННЯ МУРАШИНОГО АЛГОРИТМУ ДЛЯ ПОШУКУ БЛИЗЬКОГО ДО ОПТИМАЛЬНОГО МАРШРУТУ

11.05.2022 18:59

[1. Інформаційні системи і технології]

Автор: Штогрин Павло Петрович, студент магістратури, кафедра СПіСКС, Національний технічний університет України "Київський політехнічний інститут імені Ігоря Сікорського", м.Київ


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

Штучні «мурахи» переміщаються у просторі параметрів, що представляє всі можливі рішення, знаходячи оптимальні рішення. У справжньому світі мурахи відкладають феромони, чим направляють один одного до ресурсів, досліджують своє середовище. «Мурахи», які були змодельовані так само записують свої позиції та якість своїх рішень, таким чином в пізніших ітераціях моделювання більше мурах знаходить кращі рішення.[2]

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

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

- Кожне місто потрібно відвідати рівно один раз.

- Віддалене місто має менше шансів бути обраним (видимість).

- Чим інтенсивніший феромонний слід, прокладений на межі між двома містами, тим більша ймовірність того, що цей шлях буде обраний.

- Після завершення своєї подорожі, мураха відкладає більшу кількість феромонів на всі пройдені шляхи, якщо подорож коротка.

- Після кожної ітерації сліди феромонів випаровуються.

Наочно це можна побачити на рисунку 1.





Рисунок 1 – Робота мурашиного алгоритму по визначенню найкоротшого шляху



Не гарантується, що рішення алгоритму будуть оптимальними щодо локальних змін, і, отже, можуть бути вдосконалені за допомогою методів локального пошуку. Виходячи з цього спостереження, найкраща продуктивність досягається за допомогою гібридних алгоритмів, що поєднують імовірнісну побудову рішення колонією мурах із локальними алгоритмами пошуку, такими як 2–3 opt, tabu-search тощо.[3] Tabu-search також може допомогти із проблемою зациклювання, оскільки він забороняє маршрути, які дозволяють повертатись до попередніх рішень і зациклювати роботу.[4]



У таких гібридних алгоритмах мурах можна розглядати як керуючих локальним пошуком шляхом побудови перспективних початкових рішень, оскільки мурахи переважно використовують компоненти рішення, які раніше під час пошуку містилися в хороших локально оптимальних рішеннях.[3]



Також реалізувати локальне пошукове рішення за допомогою стратегії розподілу вихідних мурах та динамічного евристичного оновлення параметрів на основі ентропії. Це може допомогти уникнути застійної поведінки та передчасної конвергенції.[5]



Література



1. Monmarché Nicolas, Guinand Frédéric and Siarry Patrick (2010). Artificial Ants. Wiley-ISTE. ISBN 978-1-84821-194-0.



2. Ant Colony Optimization by Marco Dorigo and Thomas Stützle. MIT Press, 2004. ISBN 0-262-04219-3



3. Camelia-M. Pintea, Petrică C. Pop & Camelia Chira. The generalized traveling salesman problem solved with ant algorithms. Complex Adaptive Systems Modeling volume 5, Article number: 8 (2017).



4. Blazewicz J., Hawryluk P., Walkowiak R.. Using a tabu search approach for solving the two-dimensional irregular cutting problem.  Annals of OR, 41(1-4), pp.313-325, 1993.



5. Krishna H. Hingrajiya. An Approach for Solving Multiple Travelling Salesman Problem using Ant Colony Optimization. Computer Engineering and Intelligent Systems ISSN 2222-1719. 



__________________



Науковий керівник: Боярінова Юлія Євгенівна, к.т.н, доцент кафедри СПіСКС, с.н.с., Національний технічний університет України "Київський політехнічний інститут імені Ігоря Сікорського"






Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Інші наукові праці даної секції

Конференції

Конференції 2024

Конференції 2023

Конференції 2022

Конференції 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення