Full metadata record
DC poleHodnotaJazyk
dc.contributor.advisorRadová Vlasta, Doc. Dr. Ing.
dc.contributor.authorKučera, Martin
dc.contributor.refereeBulín Martin, Ing. M.Sc.
dc.date.accepted2022-6-22
dc.date.accessioned2022-07-25T22:30:55Z-
dc.date.available2021-10-1
dc.date.available2022-07-25T22:30:55Z-
dc.date.issued2022
dc.date.submitted2022-5-23
dc.identifier89618
dc.identifier.urihttp://hdl.handle.net/11025/49348-
dc.description.abstractHlavním zaměřením této práce jsou genetické algoritmy. Jedná se o typ náhodného prohledávání podpořený heuristikou ve formě fitness funkce imitující přírodní proces evoluce. V této práci budeme analyzovat jejich průběh na úloze obchodního cestujícího, obtížně řešitelném kombinatorickém problému ze skupiny NP-úplných úloh. Nejprve si představíme jednotlivé pojmy jako je chromozom, populace nebo křížení a zavedeme požadavky na jednotlivé procesy algoritmu, aby byl aplikovatelný na úlohu obchodního cestujícího. V dalších kapitolách prozkoumáme vliv velikosti populace N, míry elitismu E_R a míry mutace M_R na schopnost algoritmu konvergovat k optimálnímu řešení úlohy obchodního cestujícího. Různá nastavení algoritmu vyzkoušíme na více grafech včetně úloh att48, eil101 nebo tsp225 z TSPLIB a pokusíme se určit optimální hodnoty pro tyto parametry. V další kapitole si představíme různé operátory mutace a rekombinační operátory. Pokusíme se experimentálně ověřit jejich působení na chod algoritmu a určit takové operátory, které mají nejlepší vliv na schopnost algoritmu konvergovat k optimu.cs
dc.format56
dc.language.isocs
dc.publisherZápadočeská univerzita v Plzni
dc.rightsPlný text práce je přístupný bez omezení
dc.subjectgenetický algoritmuscs
dc.subjectúloha obchodního cestujícíhocs
dc.subjectvelikost populacecs
dc.subjectelitismuscs
dc.subjectmíra mutacecs
dc.subjectoperátory kříženícs
dc.subjectoperátory mutacecs
dc.titleGenetické algoritmy v úloze obchodního cestujícíhocs
dc.title.alternativeGenetic algorithms in travelling salesman problemen
dc.typediplomová práce
dc.thesis.degree-nameIng.
dc.thesis.degree-levelNavazující
dc.thesis.degree-grantorZápadočeská univerzita v Plzni. Fakulta aplikovaných věd
dc.thesis.degree-programAplikované vědy a informatika
dc.description.resultObhájeno
dc.description.abstract-translatedThe subject of this diploma thesis is genetic algorithms. Genetic algorithms are a type of random search supported by a heuristic in the form of a fitness function that imitates the natural process of evolution. We will analyze their performance in the travelling salesman problem, a complex combinatorial problem belonging to the NP-complete class. Firstly, we will introduce concepts such as chromosome, population or crossover. We will then implement requirements for individual processes of the algorithm to apply to the travelling salesman problem. The effect of population size N, elitism rate E_R and mutation rate M_R on the ability of the genetic algorithm to converge to the optimal solution will be discussed in the following chapters. Multiple algorithm settings will be tested and evaluated on the att48, eil101 and tsp225 graphs from the TSPLIB. We will then try to determine the optimal values for the parameters above. In the next chapter, we will introduce various mutation and crossover operators. Experiments will be conducted to determine operators with the best effect on the performance of the genetic algorithm.en
dc.subject.translatedgenetic algorithmen
dc.subject.translatedtravelling salesman problemen
dc.subject.translatedpopulation sizeen
dc.subject.translatedelitismen
dc.subject.translatedmutation rateen
dc.subject.translatedcrossover operatorsen
dc.subject.translatedmutation operatorsen
Vyskytuje se v kolekcích:Diplomové práce / Theses (KKY)

Soubory připojené k záznamu:
Soubor Popis VelikostFormát 
DP.pdfPlný text práce2,55 MBAdobe PDFZobrazit/otevřít
Kucera_V.pdfPosudek vedoucího práce441,56 kBAdobe PDFZobrazit/otevřít
Kucera_O.pdfPosudek oponenta práce477,38 kBAdobe PDFZobrazit/otevřít
Kucera_P.pdfPrůběh obhajoby práce203,25 kBAdobe PDFZobrazit/otevřít
Zobrazit minimální záznam Zobrazit statistiky


Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/49348

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.

hledání
navigace
  1. DSpace at University of West Bohemia
  2. Vysokoškolské kvalifikační práce / Theses
  3. Fakulta aplikovaných věd / Faculty of Applied Sciences
  4. Katedra kybernetiky / Department of Cybernetics
  5. Diplomové práce / Theses (KKY)