Thesis Details

Aplikace mravenčích algoritmů v rozsáhlých úlohách TSP

Bachelor's Thesis Student: Ramosová Patrícia Academic Year: 2019/2020 Supervisor: Bidlo Michal, doc. Ing., Ph.D.
Language
Slovak
Abstract

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, Travelling Salesman Problem, large-scale TSP instances, MAX-MIN Ant System

Department
Department of Computer Systems FIT BUT
Degree Programme
Information Technology
Files
Status
defended, grade B
Date
8 July 2020
Reviewer
Jaroš Jiří, doc. Ing., Ph.D.
Committee
Kořenek Jan, doc. Ing., Ph.D. (DCSY FIT BUT), předseda
Drahanský Martin, prof. Ing., Dipl.-Ing., Ph.D. (DITS FIT BUT), člen
Grézl František, Ing., Ph.D. (DCGM FIT BUT), člen
Hrubý Martin, Ing., Ph.D. (DITS FIT BUT), člen
Polčák Libor, Ing., Ph.D. (DIFS FIT BUT), člen
Citation
RAMOSOVÁ, Patrícia. Aplikace mravenčích algoritmů v rozsáhlých úlohách TSP. Brno, 2020. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2020-07-08. Supervised by Bidlo Michal. Available from: https://www.fit.vut.cz/study/thesis/22589/
BibTeX 
@bachelorsthesis{FITBT22589,
    author = "Patr\'{i}cia Ramosov\'{a}",
    type = "Bachelor's thesis",
    title = "Aplikace mraven\v{c}\'{i}ch algoritm\r{u} v rozs\'{a}hl\'{y}ch \'{u}loh\'{a}ch TSP",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2020,
    location = "Brno, CZ",
    language = "slovak",
    url = "https://www.fit.vut.cz/study/thesis/22589/"
}

Theses

Back to top