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

Автор(и)

  • V. A. Syzko Дніпровський державний технічний університет, м. Кам’янське, Україна
  • M. V. Babenko Дніпровський державний технічний університет, м. Кам’янське, Україна
  • N. M. Lymar Дніпровський державний технічний університет, м. Кам’янське, Україна
  • I. O. Gosalo Дніпровський державний технічний університет, м. Кам’янське, Україна

DOI:

https://doi.org/10.31319/2519-2884.36.2020.17

Ключові слова:

мурашиний алгоритм, розпаралелювання, задача комівояжера

Анотація

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

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

У розробленому авторами програмному забезпеченні на кожному ядрі комп’ютера розвивається власна незалежна колонія мурашок, яка обмінюється з іншими кращими індивідами через певну кількість поколінь. Топологія їх взаємодії має вигляд «кожен з кожним».

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

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

Посилання

Левитин А.В. Алгоритмы. Введение в разработку и анализ. М.: Вильямс, 2006. 576с.

Dorigo М. & Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1997, 1 (1): 53-66.

Олейник А.А. Сравнительный анализ методов оптимизации на основе методов муравьиных колоний. Комп’ютерне моделювання та інтелектуальні системи: збірник наукових праць. Запоріжжя: ЗНТУ, 2007. С.147-159.

##submission.downloads##

Опубліковано

2020-09-07

Номер

Розділ

Комп'ютерні науки та інформаційні технології