Název:
Aplikace mravenčích algoritmů v rozsáhlých úlohách TSP
Překlad názvu:
Ant Colony Optimization for Solving Big Instances of TSP
Autoři:
Ramosová, Patrícia ; Jaroš, Jiří (oponent) ; Bidlo, Michal (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2020
Jazyk:
slo
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [slo][eng]
V súčasnej dobe je v rade aplikácií kladený dôraz na nájdenie optimálneho riešenia určitého problému. Pre niektoré úlohy je však typické, že sa ich náročnosť stupňuje exponenciálne v závislosti na veľkosti inštancie. Typickým príkladom takéhoto problému je obchodný cestujúci (angl. Traveling Salesman Problem - TSP). Jednou triedou metód, ktoré sa ukázali byť v riešení TSP veľmi nápomocné, sú mravčie algoritmy. Narazili však na svoj limit - vysoký počet miest v inštancii, kedy sa už stali kvôli časovej a pamäťovej náročnosti takmer nepoužiteľné. Cieľom tejto práce je modifikovať mravčí algoritmus a vytvoriť tak systém schopný rýchlo a efektívne riešiť rozsiahle úlohy TSP bez výraznej straty na kvalite nájdeného riešenia. Optimalizácie budú zamerané na redukciu priestorovej zložitosti a celkovému zníženiu výpočtového času.
Currently, many applications place emphasis on finding the optimal solution to a particular problem. However, it is typical for some tasks that their complexity increases exponentially depending on the size of the instance. A typical example of such a problem is the Traveling Salesman Problem (TSP). One class of methods that have proven to be very helpful in solving TSPs are ant algorithms. Nonetheless, they reached their limit - a high number of cities in the instance and became almost unusable due to time and memory requirements. This bachelor thesis aims to modify the ant algorithm and create a system capable of quickly and efficiently solve large-scale TSPs without significant loss in the quality of the solution found. Optimization will focus on reducing memory complexity and total execution time.
Klíčová slova:
Ant Colony Optimization; large-scale TSP instances; MAX-MIN Ant System; Travelling Salesman Problem
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/191445