Original title: Aplikace mravenčích algoritmů
Authors: Olszar, Patrik ; Sedlák, David (referee) ; Bidlo, Michal (advisor)
Document type: Bachelor's theses
Year: 2024
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato bakalářská práce se věnuje implementaci a optimalizaci mravenčích algoritmů v jazyce C++ pro řešení problému obchodního cestujícího (TSP) s desítkami až statisíci měst. Vzhledem k vysokým nárokům na paměť, které tradiční metody v mravenčích algoritmech přinášejí kvůli exponenciálnímu rozšiřování matice feromonů, byla implementována omezená feromonová matice. Tato technika efektivně omezuje velikost paměti potřebnou pro feromonovou matici a zvyšuje tak škálovatelnost algoritmu. Dále práce využívá techniky jako MAX–MIN, paralelizace mravenců, dynamické upravování parametrů alpha a beta, seznam nejbližších sousedů a VCSS. Podařilo se dosáhnout výsledné cesty, která je do 3.5-5% od nejlepšího řešení. This bachelor’s thesis focuses on the implementation and optimization of the ant colony algorithm in C++ for solving the traveling salesman problem (TSP) involving tens of thousands to hundreds of thousands of cities. Due to the high memory demands of traditional ant colony algorithms, which have a exponential expansion of the pheromone matrix, a restricted pheromone matrix was implemented. This technique effectively limits the memory size needed for the pheromone matrix and thus enhances the scalability of the algorithm. Additionally, the work uses techniques such as MAX–MIN, ant parallelization, dynamic adjustment of alpha and beta parameters, a nearest neighbor list, and VCSS. The results achieved a final path that is within 3.5-5% of the optimal solution.
Keywords: ACO; ACS; ant algorithms; C++; MAX–MIN; parallelization; restricted pheromone matrix; TSP; VCSS; ACO; ACS; C++; MAX–MIN; mravenčí algoritmy; omezená feromonová matice; paralelizace; TSP; VCSS

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: https://hdl.handle.net/11012/246558

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


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