System eksperymentowania porównujący rozwiązania problemu komiwojażera, dostarczone przez algorymt genetyczny i algorytm oparty na optymalizacji kolonią mrówek

Abstract

Artykuł zawiera opis systemu eksperymentowania „TSP Solver” umożliwiającego porównanie wydajności dwóch algorytmów, służących do rozwiązywania problemu komiwojażera: algorytmu genetycznego oraz optymalizacji wykorzystującej kolonię mrówek. W pracy opisano także główną ideę oraz najważniejsze szczegóły zaimplementowanych algorytmów. Dodatkowo zamieszczono kilka przykładowych badań oraz przedstawiono tezy, które zostały postawione w wyniku tych badań.
Autor: Michał OLSZEWSKI

1 WPROWADZENIE

Chociaż dzisiejsze komputery to szybkie i potężne maszyny, to nadal istnieje wiele problemów, których nie są one w stanie rozwiązać w czasie, który byłby akceptowalny. Problemy takie nazywa się problemami NP – Zupełnymi, a jednym z nich jest Problem Komiwojażera (TSP – ang. Travelling Salesman Problem: [2], [4]). Zainteresowanie możliwymi rozwiązaniami TSP jest bardzo duże ze względu na częstość występowania tego problemu w wielu dziedzinach (np. wyznaczanie optymalnych tras dla autobusów szkolnych czy ciężarówek, przetwarzanie równoległe w sieciach komputerowych).

Z powodu dużej popularności tego problemu przy jednoczesnej jego złożoności (która uniemożliwia zastosowanie przeglądu zupełnego) powstała duża potrzeba, by znaleźć nowe, efektywniejsze algorytmy. W ciągu ostatnich trzech dekad stworzono wiele algorytmów, z których dwa zostaną omówione: Algorytm Genetyczny (GA – z ang. Genetic Algorithm) oraz algorytm oparty na Optymalizacji Kolonią Mrówek (ACO – z ang. Ant Colony Optimization). Głównym celem tego artykułu jest zbadanie efektywności tych algorytmów – w tym celu powstał system eksperymentowania („TSP Solver”), który umożliwia takie porównanie.

Artykuł został zorganizowany w następujący sposób: ogólny opis TSP znajduje się w Punkcie 2, oba algorytmy (GA i ACO) omówione są w Punkcie 3. Punkt 4 zawiera krótki opis systemu eksperymentowania. W Punkcie 5 zaprezentowano kilka wyników badań wraz z wnioskami z nich wynikających. Pozostałe wnioski i perspektywy rozwoju pojawiają się w Punkcie 6.