Original title:
Aplikace mravenčích algoritmů v rozsáhlých úlohách TSP
Translated title:
Ant Colony Optimization for Solving Big Instances of TSP
Authors:
Ramosová, Patrícia ; Jaroš, Jiří (referee) ; Bidlo, Michal (advisor) Document type: Bachelor's theses
Year:
2020
Language:
slo Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[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.
Keywords:
Ant Colony Optimization; large-scale TSP instances; MAX-MIN Ant System; Travelling Salesman Problem
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/191445