Application of ant optimization algorithms in the solution of the routing problem

Item ID: 6231
1 Media file
2020/04/02
Набір елементів
Навчально-науковий інститут інформаційних технологій та робототехніки » Кафедра комп'ютерних та інформаційних технологій і систем
Скакаліна_6(58)_2019
Властивості
Тип
Українська
Наукові статті
Українська
Article
Назва
Англійська
Application of ant optimization algorithms in the solution of the routing problem
Українська
Застосування мурашиних алгоритмів в рiшенні задачі маршрутизації
Автор
Українська
Скакаліна, О.В.
Опис
Англійська
The article discusses current issues of using evolutionary algorithms to solve the routing problem. Ant algorithms (MA), like most types of evolutionary algorithms, are based on the use of a population of potential solutions and are designed to solve combinatorial optimization problems, first of all, search for various paths on graphs. The cooperation between individuals (artificial ants) is implemented on the basis of stigmetry modeling. In addition, each agent, called artificial ant, is looking for a solution to the problem. Artificial ants consistently build a solution to the problem, moving around the graph, lay the pheromone and, when choosing a further section of the path, take into account the concentration of this enzyme. The higher the concentration of pheromone in the subsequent section, the greater the likelihood of its choice. Since MA is based on the movement of ants along some paths, MAs are effective, first of all, in solving problems that can be interpreted in the form of a graph. Computer experiments showed that the efficiency of MA increases with increasing dimension of the problem and for tasks on high-dimensional graphs they work faster than other evolutionary algorithms. Good results were also noted in solving non-stationary problems on graphs with a changing environment. In connection with this, the implementation of the meta - heuristic method is proposed as a modification of ant optimization algorithms. The scheme of the system is presented. A software product specification is also provided.
Українська
Дослідження показують, що 85-95% загальної тривалості логістичного ланцюга виробничого циклу товарного руху становить очікування на обробку, транспортування та інші операції, включаючи зберігання. Мета логістики - побудувати процес доставки «від дверей до дверей» з мінімальними втратами на місцях з'єднання, з мінімальними накопичувальними витратами та часом для сприяння інтегрованому логістичному потоку.У статті розглядаються актуальні питання використання еволюційних алгоритмів для вирішення задачі маршрутизації. Мурашині алгоритми, як і більшість видів еволюційних алгоритмів, засновані на використанні популяції потенційних рішень і розроблені для вирішення завдань комбінаторної оптимізації, перш за все, пошуку різних шляхів на графах. Кооперація між особинами (штучними мурашками) тут реалізується на основі моделювання стігметріі. При цьому кожен агент, званий штучним мурахою, шукає рішення поставленого завдання. Штучні мурашки послідовно будують рішення завдання, пересуваю-чись по графу, відкладають феромон і при виборі подальшого ділянки шляху враховують концентрацію цього ферменту. Чим більше концентрація феромону в подальшому ділянці, тим більша ймовірність його вибору. Оскільки в основі му-рашиного алгоритма лежить пересування мурах за деякими шляхах, то мурашині алгоритми ефективні, перш за все, при вирішенні завдань, які допускаю інтерпретацію у вигляді графа. Проведені комп'ютерні експерименти показали, що ефективність мурашиного алгоритма зростає при збільшенні розмірності задачі і для задач на графах високої розмірності вони працюють швидше, ніж інші еволюційні алгоритми. Відзначено також хороші результати при вирішенні нестаціонарних задач на графах зі змінною середовищем. В святи з цим пропонується реалізація мета -евристичного методу, як модифікації мурашиних алгоритмів оптимізації. Представлена схема роботи системи. Також представлена специфікація програмного продукту.Результатом дослідження стала розробка системи оптимізації перевезень, яка відповідає сучас-ним вимогам до програмного забезпечення. Програмне забезпечення адаптується до платформи Android.
Мова
English
Дата випуску
2019
Тематика
Англійська
evolutionary algorithms
Англійська
routing problem
Англійська
ant optimization algorithms
Українська
еволюційні алгоритми
Українська
задача маршрутизації
Українська
мурашині алгоритми оптимізації
Видавництво
Українська
Національний університет "Полтавська політехніка імені Юрія Кондратюка"
Бібліографічний опис
Українська
Skakalina O.V. Application of ant optimization algorithms in the solution of the routing problem / O.V. Skakalina // Системи управління, навігації та зв'язку. – 2019. – № 6 (58). – С. 84-91. – doi: 10.26906/SUNZ.2019.6.075
УДК
004.023:65.012
Набори елементів 1
Кафедра комп'ютерних та інформаційних технологій і систем
18 1345 items
Медіа
Скакаліна_6(58)_2019
Скакаліна_6(58)_2019
Metadata Information
Створено
2020-4-2 18:55
Last Modified
2020-4-2 18:55
Date Issued (DC)
2019
Item ID
#6231
Resource Template
Наукова стаття