Ant Colony Optimization
Thesis title: | Optimalizace pomocí algoritmů mravenčích kolonií |
---|---|
Author: | Zahálka, Jaroslav |
Thesis type: | Diplomová práce |
Supervisor: | Fábry, Jan |
Opponents: | Zouhar, Jan |
Thesis language: | Česky |
Abstract: | Diplomová práce se zabývá algoritmy mravenčích kolonií a jejich využitím pro řešení okružních a rozvozních úloh. Tyto algoritmy se řadí mezi tzv. metaheuristiky a představují inovativní přístup k řešení NP - obtížných problémů vhodný především pro úlohy většího rozsahu. Práce začíná popisem okružních a rozvozních úloh včetně způsobů jejich řešení. V další kapitole analyzuje metaheuristiku Ant Colony a její možné aplikace na zmíněné problémy. Nejdůležitější součástí práce je praktická část, kterou představuje program Ant Colony Optimization Framework. Jde o rozšiřitelnou aplikaci napsanou v jazyce Java schopnou řešit úlohu obchodního cestujícího a základní rozvozní úlohu. V závěru práce je předvedena analýza řešení těchto problémů na testovacích datech. |
Keywords: | algoritmy mravenčích kolonií; úloha obchodního cestujícího; okružní a rozvozní úlohy |
Thesis title: | Ant Colony Optimization |
---|---|
Author: | Zahálka, Jaroslav |
Thesis type: | Diploma thesis |
Supervisor: | Fábry, Jan |
Opponents: | Zouhar, Jan |
Thesis language: | Česky |
Abstract: | This diploma thesis deals with Ant Colony algorithms and their usage for solving Travelling Salesman Problems and Vehicle Routing Problems. These algorithms are metaheuristics offering new approach to solving NP-hard problems. Work begins with a description of the forementioned tasks including ways to tackle them. Next chapter analyses Ant Colony metaheuristic and its possible usage and variations. The most important part of the thesis is practical and is represented by application Ant Colony Optimization Framework. It is easily extensible application written in Java that is able to solve introduced problems. In conclusion this work presents analysis of solutions on test data. |
Keywords: | travelling salesman problem; vehicle routing problem; ant colony algorithms |
Information about study
Study programme: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
---|---|
Type of study programme: | Magisterský studijní program |
Assigned degree: | Ing. |
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: | 27. 11. 2007 |
---|---|
Date of submission: | 25. 8. 2008 |
Date of defense: | 16. 9. 2008 |
Identifier in the InSIS system: | https://insis.vse.cz/zp/13959/podrobnosti |