Název: Pokročilá evoluční optimalizace úloh typu TSP
Překlad názvu: Advanced Evolutionary Optimisation of TSP-Based Problems
Autoři: Hladyuk, Vadym ; Vašíček, Zdeněk (oponent) ; Bidlo, Michal (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2023
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
Práce řeší problém obchodního cestujícího pomocí evolučního algoritmu, konktrétně pomocí genetického algoritmu. Jedná se o hybrid genetického algoritmu s využitím lokálního prohledávacího algoritmu a dalších vylepšení, které nám pomohou vylepšit výsledky. Problémy obchodního cestujícího budou řešeny od 20 měst až po 25 tisíc měst. V kapitole s experimenty jsem zjistil nejvhodnější nastavení všech parametrů v programu a řádně otestoval jejich přínos. V další části kapitoly s experimenty jsem zjistil jakých výsledků dosahují genetické algoritmy. V poslední části jsem porovnal vývoj hodnoty fitness různých variant genetických algoritmů a různých variant operátorů křížení, také jsem porovnal časovou náročnost. Navrhnul jsem další možná vylepšení ať už lokálních prohledávacích algoritmů či jiného přístupu k řešení TSP. This paper solves the traveling salesman problem using an evolutionary algorithm, specifically a genetic algorithm. It is a hybrid of the genetic algorithm, using a local search algorithm and other enhancements that further improve the results obtained. The traveling salesman problem will be solved from 20 cities to 25,000 cities. In the experiments chapter, I have determined the best settings for all the parameters in the program and properly tested their appropriateness. In the next part of the experiments chapter, I found out the performance of the full version of the genetic algorithm and its variants. In the last section, I compared the evolution of fitness values of different variants of genetic algorithms and different variants of crossover operators, I also compared the time consumption. I suggested further possible improvements either to the local search algorithm or to another approach to solve the TSP.
Klíčová slova: 2-opt; 3-opt; experimenty optimalizačního problému; genetický algoritmus; hybrid genetického problému; operátory křížení; optimalizační algoritmus; problém obchodního cestujícího; selekce; TSP; turnajový výběr; voluční algoritmy; 2-opt; 3-opt; crossover operators; evolutionary algorithms; genetic algorithm; hybrid genetic problem; optimization algorithm; optimization problem experiments; selection; tournament selection; traveling salesman problem; TSP

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: http://hdl.handle.net/11012/213190

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


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 > Diplomové práce