Optimalizace včelí kolonií

• Název práce v češtině: Optimalizace včelí kolonií
• Název v anglickém jazyce: Artificial Bee Colony
• Klíčová slova: minimální vrcholové pokrytí, kombinatorická optimalizace, heuristiky, evoluční algoritmy, optimalizace hejnem částic, optimalizace včelí kolonií
• Klíčová slova anglicky: vertex cover problem, combinatorial optimization, heuristics, evolutionary algorithms, particle swarm optimization, artificial bee colony
• Akademický rok vypsání: 2018/2019
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: RNDr. Ondřej Pangrác, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 22.02.2019
• Datum zadání: 28.02.2019
• Datum potvrzení stud. oddělením: 05.03.2019
• Datum a čas obhajoby: 27.06.2019 09:00
• Datum odevzdání elektronické podoby: 14.05.2019
• Datum odevzdání tištěné podoby: 17.05.2019
• Datum proběhlé obhajoby: 27.06.2019
• Oponenti: RNDr. Radek Hušek, Ph.D.

Zásady pro vypracování

Tato práce je pokračováním ročníkového projektu. Úkolem studenta je nastudovat a implementovat algoritmy pro řešení problému vrcholového pokrytí grafu. Následně analyzovat a srovnat výsledky běhů algoritmů pro různé grafy.
Protože se jedná o NP-těžkou úlohu a často nelze efektivně najít optimální řešení, budou v práci použity různé heuristické přístupy. Hlavní důraz by měl být kladen na relativně nový přístup optimalizace včelí kolonií (Artificial bee colony) a dále na genetické algoritmy, kde bude nutné vyladit parametry algoritmu.

Seznam odborné literatury

Demel: Grafy a jejich aplikace (Academia 2002)
Goldgerg: Genetic Algorithms (2006)
Weise: Global Optimization Algorithms
Mitchell, M.: Introduction to genetic algorithms. MIT Press, 1996.
Dervis Karaboga (2010) Artificial bee colony algorithm. Scholarpedia (https://abc.erciyes.edu.tr/index.htm)
Rodrigo Cuesta, Broderick Crawford, Ricardo Soto and Fernando Paredes, An Artificial Bee Colony Algorithm for the Set Covering Problem