Název: Optimalizace včelí kolonií
Překlad názvu: Artificial Bee Colony
Autoři: Jukl, Jan ; Pangrác, Ondřej (vedoucí práce) ; Hušek, Radek (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2019
Jazyk: cze
Abstrakt: [cze] [eng]
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. 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.
Klíčová slova: evoluční algoritmy; heuristiky; kombinatorická optimalizace; minimální vrcholové pokrytí; optimalizace hejnem částic; optimalizace včelí kolonií; artificial bee colony; combinatorial optimization; evolutionary algorithms; heuristics; particle swarm optimization; vertex cover problem

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/108352

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


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce