Original title: Optimalizace včelí kolonií
Translated title: Artificial Bee Colony
Authors: Jukl, Jan ; Pangrác, Ondřej (advisor) ; Hušek, Radek (referee)
Document type: Bachelor's theses
Year: 2019
Language: cze
Abstract: [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.
Keywords: artificial bee colony; combinatorial optimization; evolutionary algorithms; heuristics; particle swarm optimization; vertex cover problem; evoluční algoritmy; heuristiky; kombinatorická optimalizace; minimální vrcholové pokrytí; optimalizace hejnem částic; optimalizace včelí kolonií

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/108352

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


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses