Выпуск №10 (Июнь)

https://doi.org/10.25313/2520-2057-2019-10

XLII Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.06.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.05.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XL Международная научно-практическая конференция «Актуальные проблемы современной науки», 28.03.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

МНПК "Цифровая трансформация и инновации в экономике, праве, государственном управлении, науке и образовательных процессах", 18-21.03.2019

XXXIX Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.02.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XIII Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 31.01.2019 (Совместная конференция с Финансово-экономическим научным советом)

XXXVIII Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.01.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XXXVІI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2018 (Совместная конференция с Международным научным центром)

XXXVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2018 (Совместная конференция с Международным научным центром)

XIII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXXV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.10.2018 (Совместная конференция с Международным научным центром)

XXXIV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2018 (Совместная конференция с Международным научным центром)

ХXXIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.08.2018 (Совместная конференция с Международным научным центром)

ХXXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 31.07.2018 (Совместная конференция с Международным научным центром)

XII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХXXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2018 (Совместная конференция с Международным научным центром)

ХІ Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2018 (Совместная конференция с Международным научным центром)

XXIХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.04.2018 (Совместная конференция с Международным научным центром)

ХХVIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.03.2018 (Совместная конференция с Международным научным центром)

ІІІ МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 19-22.03.2018 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 28.02.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХХVІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2018 (Совместная конференция с Международным научным центром)

ХХVІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2018 (Совместная конференция с Международным научным центром)

XІІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.12.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2017 (Совместная конференция с Международным научным центром)

ХХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2017 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2017 (Совместная конференция с Финансово-экономическим научным советом)

XІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.09.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2017 (Совместная конференция с Международным научным центром)

X Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.07.2017 (Совместная конференция с Международным научным центром)

ХXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2017 (Совместная конференция с Международным научным центром)

"Тенденции развития национальных экономик: экономическое и правовое измерение" 18-19.05.2017 (Совместная конференция с Финансово-экономическим научным советом и ККИБиП)

ХIX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.04.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.03.2017 (Совместная конференция с Международным научным центром)

МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 20–23.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

VIII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.02.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2017 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.01.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2017 (Совместная конференция с Международным научным центром)

ХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2016 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 28.12.2016 (Совместная конференция с Финансово-экономическим научным советом)

VII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.11.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.10.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.10.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конф. «Научный диспут: вопросы экономики и финансов», 30.09.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.09.2016 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.08.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 29.07.2016 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.07.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.06.2016 (Совместная конференция с Финансово-экономическим научным советом)

ІX Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2016 (Совместная конференция с Международным научным центром)

VI Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.05.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 30.05.2016 (Совместная конференция с Международным научным центром)

V Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 29.04.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.04.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 31.03.2016 (Совместная конференция с Международным научным центром)

ІI Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 30.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 21-24.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 26.02.2016 (Совместная конференция с Финансово-экономическим научным советом)

II Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 20.02.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.12.2015 (Совместная конференция с Международным научным центром)

IV Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.12.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.11.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 29.10.2015 (Совместная конференция с Финансово-экономическим научным советом)

Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 28.10.2015 (Совместная конференция с Международным научным центром)

III Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.09.2015 (Совместная конференция с Финансово-экономическим научным советом)

III Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.08.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІІ Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 30.06.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2015 (Совместная конференция с Международным научным центром)

II Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.05.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы экономики и финансов, 29.04.2015 (Совместная конференция с Финансово-экономическим научным советом)

Научный диспут: вопросы экономики и финансов, 31.03.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы современной науки, 27.03.2015 (Совместная конференция с Международным научным центром)

Глобальные проблемы экономики и финансов, 27.02.2015 (Совместная конференция с финансово-экономическим научным советом)



Бойків М. В., Житенко О. В. Аналіз досліджень маршрутизації руху з використанням мурашиних алгоритмів оптимізації // Міжнародний науковий журнал "Інтернаука". — 2019. — №10.


Отрасль науки: Технические науки
Скачать статью (pdf)

Технічні науки

УДК 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]. Подальший розвиток підходу спостерігається у застосуванні бази нечітких правил за аналогією з нечітким управління параметрами генетичних алгоритмів.

Література

  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. 343-349.
  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.