РОЗРОБКА ПАРАЛЕЛЬНОГО МУРАШИНОГО АЛГОРИТМУ НА ПРИКЛАДІ ЗАДАЧІ КОМІВОЯЖЕРА

Autor: Syzko, V. A., Babenko, M. V., Lymar, N. M., Gosalo, I. O.
Jazyk: ukrajinština
Rok vydání: 2020
Předmět:
Zdroj: Збірник наукових праць Дніпровського державного технічного університету (технічні науки); Том 1, № 36 (2020): collection; 105-108
Collection of scholarly papers of Dniprovsk State Technical University (Technical Sciences); Том 1, № 36 (2020): collection; 105-108
ISSN: 2519-2884
2617-8389
Popis: The purpose of this study is to develop software to conduct research on the effectiveness of the parallel ant colony optimization algorithm applied to the shortest-path search. The algorithm is based on the behavior principles of an ant colony as well as individual ants, who search the shortest path to the food source. In order to study the effectiveness of the ant colony optimization algorithm one of the most common optimization problems was applied, specifically – a travelling salesman problem.The algorithm shows its efficiency and stability only on the sufficient amount of resources. Its resource usage and therefore the working time grows rapidly together with the growth of the size of the task. In order to solve this problem the parallelism is applied. It is also вused to reduce the premature convergence to the local optimum, as well as to stimulate diversity and search of the alternative solutions of the same problem.In the proposed software each independent ant colony is developed on the separate computer core. Each colony exchanges the best individuals with other colonies in a certain number of generations. The topology of this interaction has the form of «each with each».According to the calculations, we can conclude, that the efficiency of the ant colony optimization algorithm does not change with the increase in the number of kernels (individual populations). However, there is a slight change of the reliability of the particular settings. But at the same time we can observe the substantial increase in operation speed. Thus, the parallelization of the ant colony optimization algorithm can significantly reduce the execution time of a software application without compromising reliability.The ant algorithm is used to solve complex optimization problems. Typical areas of the algorithm application include scheduling, resource and job allocation, transport routing, etc. For this reason, the problem of increasing the efficiency of the algorithm calculations is quite topical.
Целью данной работы является разработка программного обеспечения для исследования эффективности параллельного муравьиного алгоритма при поиске самой короткой длины маршрута. Суть алгоритма основывается на принципах поведения муравьиной колонии и муравьев, ищущих кратчайший путь до еды. Для исследования эффективности муравьиного алгоритма была использована оптимизационная задача, которая часто возникает на практике, а именно задача коммивояжера.Алгоритм показывает свою хорошую работоспособность и надежность только при достаточном количестве ресурсов. Его ресурсоемкость и, соответственно, время работы быстро растут с увеличением размерности задачи. Для решения этой проблемы используется распараллеливание алгоритма. Также оно применяется для снижения преждевременной сходимости к локальному оптимуму, стимуляции разнообразия и поиска альтернативных решений той же проблемы.В разработанном авторами программном обеспечении на каждом ядре компьютера развивается собственная независимая колония муравьев, которая обменивается с другими лучшими индивидами через определенное количество поколений. Топология их взаимодействия имеет вид «каждый с каждым».По результатам расчетов можно сделать вывод, что при увеличении количества ядер, то есть отдельных популяций, качественно работа муравьиного алгоритма не меняется, хотя и наблюдается некоторое изменение надежности для отдельных настроек. В то же время, существенно повышается скорость работы. То есть распараллеливание муравьиного алгоритма позволяет существенно снизить время выполнения программного приложения, не ухудшая надежности.Муравьиный алгоритм применяется для решения сложных комплексных задач оптимизации, а типичными сферами, где можно применить этот алгоритм, являются задача календарного планирования, распределение ресурсов и работ, задача маршрутизации транспорта и т.д., поэтому повышение эффективности расчетов по этому алгоритму достаточно актуального.
Метою даної роботи є розробка програмного забезпечення для дослідження ефективності паралельного мурашиного алгоритму для пошуку найкоротшої відстані маршруту. Суть алгоритму ґрунтується на принципах поведінки мурашиної колонії та мурах, що шукають найкоротший шлях до їжі. Для дослідження ефективності мурашиного алгоритму була використана оптимізаційна задача, яка часто виникає на практиці, а саме задача комівояжера.Алгоритм показує свою працездатність і хорошу надійність при достатній кількості ресурсів. Але необхідна кількість ресурсів та, відповідно, час роботи швидко зростають зі збільшенням розмірності задачі. Для вирішення цієї проблеми використовується розпаралелювання алгоритму. Також воно застосовується для зниження передчасної збіжності до локального оптимуму, стимуляції різноманітності і пошуку альтернативних рішень тієї ж проблеми.У розробленому авторами програмному забезпеченні на кожному ядрі комп’ютера розвивається власна незалежна колонія мурашок, яка обмінюється з іншими кращими індивідами через певну кількість поколінь. Топологія їх взаємодії має вигляд «кожен з кожним».За результатами розрахунків можна зробити висновок, що при збільшенні кількості ядер, тобто окремих популяцій, якісно робота мурашиного алгоритму не змінюється, хоча і спостерігається деяка зміна надійності для окремих налаштувань. В той же час, істотно підвищується швидкість роботи. Тобто розпаралелювання мурашиного алгоритму дозволяє істотно знизити час виконання програмного додатку, не погіршуючи надійності.Мурашиний алгоритм застосовується для вирішення складних комплексних задач оптимізації, а типовими сферами, де можна застосувати цей алгоритм, є задача календарного планування, розподіл ресурсів та робіт, задача маршрутизації транспорту і таке інше, тому підвищення ефективності розрахунків за цим алгоритмом є досить актуальним.
Databáze: OpenAIRE
Externí odkaz: