Original title:
Evoluční algoritmy
Translated title:
Evolutionary algorithms
Authors:
Haupt, Daniel ; Polách, Petr (referee) ; Honzík, Petr (advisor) Document type: Bachelor's theses
Year:
2009
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií Abstract:
[cze][eng]
První část práce je teoretická a zabývá se optimalizací a evolučními algoritmy, které jsou používány k řešení složitých optimalizačních problémů. Konkrétně jsou popsány algoritmy diferenciální evoluce, genetický algoritmus, simulované žíhání a deterministický neevoluční algoritmus zakázané prohledávání. Dále je diskutována problematika testování optimalizačních algoritmů pomocí tzv. galerii testovacích funkcí a testování pomocí srovnání výsledků algoritmů při řešení problému obchodního cestujícího. Ve druhé části práce jsou všechny uvedené algoritmy testovány na 11 testovacích funkcích a na třech modelech rozmístění měst v problému obchodního cestujícího. Nejprve jsou algoritmy srovnávány s možností neomezeného přístupu k účelové funkci a dále s omezenou možností přístupu k účelové funkci. Veškerá data jsou statisticky a graficky zpracována. Jednotlivé algoritmy jsou seřazeny dle úspěšnosti.
The first part of this work deals with the optimization and evolutionary algorithms which are used as a tool to solve complex optimization problems. The discussed algorithms are Differential Evolution, Genetic Algorithm, Simulated Annealing and deterministic non-evolutionary algorithm Taboo Search.. Consequently the discussion is held on the issue of testing the optimization algorithms through the use of the test function gallery and comparison solution all algorithms on Travelling salesman problem. In the second part of this work all above mentioned optimization algorithms are tested on 11 test functions and on three models of placement cities in Travelling salesman problem. Firstly, the experiments are carried out with unlimited number of accesses to the fitness function and secondly with limited number of accesses to the fitness function. All the data are processed statistically and graphically.
Keywords:
comparison of algorithms; crossing; Differential Evolution; edge recombination crossover; ERX; evolution; evolutionary algorithms; fitness function; generation; Genetic Algorithm; mutation; optimization; optimization algorithms; population; relative position indexing; Simulated Annealing; Taboo Search; test function gallery; Travelling salesman problem; TSP; diferenciální evoluce; evoluce; evoluční algoritmy; fitness funkce; galerie testovacích funkcí; generace; genetický algoritmus; křížení; mutace; operátor křížení s rekombinací hran; optimalizace; optimalizační algoritmy; populace; problém obchodního cestujícího; relativní indexování pozic; simulované žíhání; srovnání algoritmů; zakázané prohledávání; účelová funkce
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/11482