Original title: Optimalizace mravenčí kolonií
Translated title: Ant colony optimization
Authors: Kovács, Peter ; Pangrác, Ondřej (advisor) ; Balko, Martin (referee)
Document type: Bachelor's theses
Year: 2018
Language: slo
Abstract: [eng] [cze]
The aim of this work was to compare metaheuristic Ant Colony with other metaheuristics like Simulated Annealing, Tabu Search or Greedy algo- rithms. Metaheuristics were compared on three different NP-hard problems. Specificaly, Traveling Salesman Problem, Graph Coloring Problem and Set Covering Problem. Detailed description of implementation of metaheuristics in particular problems can be found in this work. Metaheuristics were com- pared based on cost function and execution time. However, this work tries to identify instances, in which Ant Colony was the best choice. Ant Colony is reliable metaheuristic on large Traveling Salesman or Set Covering problems. V práci sa venujem porovnávaniu metaheuristiky Ant Colony s inými metaheuristikami ako Simulated Annealing, Tabu Search alebo hladné al- goritmy. Metaheuristiky som porovnával na probléme obchodného cestujú- ceho, pri ofarbovaní grafu a množinovom pokrytí. V práci sú podrobne rozo- braté implementácie metaheuristík na jednotlivé problémy. Pri porovnávaní je braná do úvahy hlavne výsledná cenu riešenia, ale aj čas. V práci je snaha identifikovať, v ktorých prípadoch je vhodné použiť Ant Colony. Ant Colony v prípade množinového pokrytia a problému obchodného cestujúceho funguje spoľahlivo pri veľkých instanciách.
Keywords: Ant Colony; Graph Coloring; heuristics; optimization; Set Covering; Traveling Salesman Problem; heuristiky; množinové pokrytie; mravčia kolónia; ofarbovanie grafu; optimalizácia; problém obchodného cestujúceho

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/100907

Permalink: http://www.nusl.cz/ntk/nusl-386827


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses