Název: Aplikace mravenčích algoritmů
Autoři: Olszar, Patrik ; Sedlák, David (oponent) ; Bidlo, Michal (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2024
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [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.
Klíčová slova: ACO; ACS; C++; MAX–MIN; mravenčí algoritmy; omezená feromonová matice; paralelizace; TSP; VCSS; ACO; ACS; ant algorithms; C++; MAX–MIN; parallelization; restricted pheromone matrix; TSP; VCSS

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: https://hdl.handle.net/11012/246558

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-617628


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Bakalářské práce