Aplikace algoritmu mravencí kolonie na problém obchodního cestujícího

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.