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

Анотація

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

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

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

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

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