Original title: Pokročilá evoluční optimalizace úloh typu TSP
Translated title: Advanced Evolutionary Optimisation of TSP-Based Problems
Authors: Hladyuk, Vadym ; Vašíček, Zdeněk (referee) ; Bidlo, Michal (advisor)
Document type: Master’s theses
Year: 2023
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: 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; 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

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

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


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