Solving the combinatorial optimization problems with the Ant Colony Optimization metaheuristic method

Metoda optimalizace pomocí mravenčí kolonie (Ant Colony Optimization - ACO) patří mezi metaheuristické metody a byla vyvinuta v poměrně nedávné době. Doposud vykázala poměrně dobrou schopnost překonat v kvalite řešení jiné metaheuristické metody. Tato práce analyzuje možnosti aplikací této metody na klasické optimalizační kombinatorické problémy - úloha obchodního cestujícího, úloha okružních jízd, úloha o batohu, zevšeobecněný přiřazovací problém a problém hledání maximální kliky. Taky prezentuje praktické experimenty s aplikací na některé optimalizační problémy a analýzu časové a paměťové složitosti takovýchto algoritmů. Poslední část práce je věnovaná možnosti paralelizace algoritmu, který byl výsledkem aplikace metody ACO na úlohu obchodního cestujícího. Přináší analýzu kritických operací a problémů synchronizace údajů, a taky i praktický příklad a demonstraci paralelizované verze algoritmu.

The Ant Colony Optimization belongs into the metaheuristic methods category and it has been developing quite recently. So far it has shown its capabalities to over-perform other metaheuristic methods in quality of the solutions. This work brings analysis of the possible applications of the method on the classical optimization combinatorial problems -- traveling salesman problem, vehicle routing problem, knapsack problem, generalized assignment problem and maximal clique problem. It also deals with the practical experiments with application on several optimization problems and analysis of the time and memory complexity of such algorithms. The last part of the work is dedicated to the possibility of parallelization of the algorithm, which was result of the application of the ACO method on the traveling salesman problem. It brings analysis of the crucial operations and data synchronization issues, as well as practical example and demonstration of the parallelized version of the algorithm.