Aplication of the ACO algorithms on the travelling salesman problem

Thesis title: Aplikace algoritmu mravencí kolonie na problém obchodního cestujícího
Author: Krahulec, Lukáš
Thesis type: Bakalářská práce
Supervisor: Jablonský, Josef
Opponents: Fábry, Jan
Thesis language: Česky
Abstract:
Práce zkoumá aplikace metod mravenčí kolonie na problém obchodního cestujícího. Za účelem pochopení motivace a výhod heuristických přístupů řešení je nastíněna problematika výpočetní složitosti a kombinatorické optimalizace. Dále je vysvětlen biologický základ metaheuristiky ACO, klíčové vlastnosti metaheuristiky a jejich aplikaci na problém obchodního cestujícího. Zmiňuje specifické aplikace AS, EAS, RAS, MMAS a ACS, včetně jejich chování a parametrizace. V závěru práce porovnáváme výkon exaktních metod řešení a jednotlivých algoritmů ACO na vzorku úloh z TSPLIB95. Algoritmy ACO, zvláště MMAS a ACS, se ukazují být silnými nástroji pro zkoumání úloh větších rozměrů.
Keywords: Kombinatorická optimalizace; Metaheuristiky; Algoritmy mravenčí kolonie; Problém obchodního cestujícího
Thesis title: Aplication of the ACO algorithms on the travelling salesman problem
Author: Krahulec, Lukáš
Thesis type: Bachelor thesis
Supervisor: Jablonský, Josef
Opponents: Fábry, Jan
Thesis language: Česky
Abstract:
Thesis focuses on exploring the use of ACO metaheuristic on the travelling salesman problem. To better explain the appeal and advantages of approximative solution methods, first chapter gives brief overview of computational complexity and heuristics. Second part explores the biological inspiration of the ACO - ant colonies and their observed behaviour. Following that we explain the gradual abstraction that led to the development of ACO metaheuristic and how these principles can be applied to solve combinatorial optimization problems - namely the AS, EAS, RAS, MMAS and ACS algorithms. The last part of the work compares the peformance of exact solution methods and ACO on set of TSP problems drawn from TSPLIB95. It is concluded that ACO algorithms, especially the MMAS and ACS, are competitive on the larger problem instances, where they provide solutions close to the optimum in time that is generally a fraction of that required by exact solver.
Keywords: Travelling salesman problem; Combinatorial optimization; Metaheuristics; Ant colony optimization; Ant algorithms

Information about study

Study programme: Kvantitativní metody v ekonomice/Matematické metody v ekonomii
Type of study programme: Bakalářský studijní program
Assigned degree: Bc.
Institutions assigning academic degree: Vysoká škola ekonomická v Praze
Faculty: Faculty of Informatics and Statistics
Department: Department of Econometrics

Information on submission and defense

Date of assignment: 7. 11. 2012
Date of submission: 15. 5. 2013
Date of defense: 26. 6. 2013
Identifier in the InSIS system: https://insis.vse.cz/zp/40222/podrobnosti

Files for download

    Last update: