velikost textu

Optimalizace včelí kolonií

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Optimalizace včelí kolonií
Název v angličtině:
Artificial Bee Colony
Typ:
Bakalářská práce
Autor:
Bc. Jan Jukl
Vedoucí:
RNDr. Ondřej Pangrác, Ph.D.
Oponent:
Radek Hušek
Id práce:
211137
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Informatický ústav Univerzity Karlovy (32-IUUK)
Program studia:
Informatika (B1801)
Obor studia:
Softwarové a datové inženýrství (ISDI)
Přidělovaný titul:
Bc.
Datum obhajoby:
27. 6. 2019
Výsledek obhajoby:
Velmi dobře
Jazyk práce:
Čeština
Klíčová slova:
minimální vrcholové pokrytí, kombinatorická optimalizace, heuristiky, evoluční algoritmy, optimalizace hejnem částic, optimalizace včelí kolonií
Klíčová slova v angličtině:
vertex cover problem, combinatorial optimization, heuristics, evolutionary algorithms, particle swarm optimization, artificial bee colony
Abstrakt:
Abstrakt Problém minimálního vrcholového pokrytí je dobře známý NP-těžký pro- blém. Tato práce prezentuje Artificial Bee Colony (ABC) algoritmus a dva přístupy založené na genetických algoritmech pro řešení tohoto problému. Al- goritmus ABC je optimalizační algoritmus založený na kolektivní inteligenci včelího roje. ABC byl nejdříve navržen pro spojitou optimalizaci a ukázalo se, že na tomto druhu problémů dosahuje mimořádně kvalitních výsledků. V této práci byl algoritmus ABC přizpůsoben pro řešení problému minimálního vrcholového pokrytí a otestován na benchmarcích DIMACS a BHOSLIB. Naměřené výsledky algoritmu ABC, genetického algoritmu založeného na binárním rozhodovacím di- agramu a informovaného genetického algoritmu jsou v práci vzájemně porovná- vány.
Abstract v angličtině:
Abstract The minimum vertex cover (MVC) problem is a well-known NP-hard prob- lem. This thesis presents the Artificial Bee Colony (ABC) algorithm and two genetic algorithm approaches to solve this problem. The ABC algorithm is an optimization algorithm based on the intelligent behaviour of a honey bee swarm. It was first proposed for unconstrained optimization problems and showed that it is superior in performance on these kinds of problems. In this thesis, the ABC algorithm has been extended to solving the minimum vertex cover problem and applied to DIMACS and BHOSLIB benchmarks. The results produced by the ABC, the binary decision diagram based genetic algorithm and the MVC-aware genetic algorithm have been compared.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Jan Jukl 4.19 MB
Stáhnout Příloha k práci Bc. Jan Jukl 39.53 MB
Stáhnout Abstrakt v českém jazyce Bc. Jan Jukl 39 kB
Stáhnout Abstrakt anglicky Bc. Jan Jukl 39 kB
Stáhnout Posudek vedoucího RNDr. Ondřej Pangrác, Ph.D. 237 kB
Stáhnout Posudek oponenta Radek Hušek 121 kB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. Pavel Valtr, Dr. 152 kB