Optimalizace mravenčí kolonií je metoda řešení kombinatorických optimalizačních problémů založená na chování skutečných mravenců. Jedním z optimalizačních problémů, na které je optimalizace mravenčí kolonií aplikovatelná, je problém obchodního cestujícího.
Práce se zaobírá popisem několika algoritmů inspirovaných chováním skutečných mravenců a jejich aplikací na problém obchodního cestujícího.
Anotace v angličtině
Ant colony optimization is a method of solving combinatorial optimization problems based on behavior of real ants. Travelling salesman problem is one of the optimization problems to which ant colony optimization can be applied.
The thesis concerns with the description of a few algorithms inspired by behavior of real ants and their application to travelling salesman problem.
Klíčová slova
ACO, optimalizace mravenčí kolonií, TSP, problém obchodního cestujícího, ant system, elitist ant system, rank based ant system, Max-Min ant system, ant colony system, AS, EAS, Rank based AS, MMAS, ACS
Klíčová slova v angličtině
ACO, ant colony optimization, TSP, travelling salseman problem, ant system, elitist ant system, rank based ant system, Max-Min ant system, ant colony system, AS, EAS, Rank based AS, MMAS, ACS
Rozsah průvodní práce
45 s. (52 914 znaků)
Jazyk
CZ
Anotace
Optimalizace mravenčí kolonií je metoda řešení kombinatorických optimalizačních problémů založená na chování skutečných mravenců. Jedním z optimalizačních problémů, na které je optimalizace mravenčí kolonií aplikovatelná, je problém obchodního cestujícího.
Práce se zaobírá popisem několika algoritmů inspirovaných chováním skutečných mravenců a jejich aplikací na problém obchodního cestujícího.
Anotace v angličtině
Ant colony optimization is a method of solving combinatorial optimization problems based on behavior of real ants. Travelling salesman problem is one of the optimization problems to which ant colony optimization can be applied.
The thesis concerns with the description of a few algorithms inspired by behavior of real ants and their application to travelling salesman problem.
Klíčová slova
ACO, optimalizace mravenčí kolonií, TSP, problém obchodního cestujícího, ant system, elitist ant system, rank based ant system, Max-Min ant system, ant colony system, AS, EAS, Rank based AS, MMAS, ACS
Klíčová slova v angličtině
ACO, ant colony optimization, TSP, travelling salseman problem, ant system, elitist ant system, rank based ant system, Max-Min ant system, ant colony system, AS, EAS, Rank based AS, MMAS, ACS
Zásady pro vypracování
Problém obchodního cestujícího má za cíl nalezení nejkratší cesty přes množinu zákazníků. K řešení úlohy obchodního cestujícího bylo navrženo mnoho heuristických metod. Jednou z nich je algoritmus, jehož kroky jsou založeny na podobenství s mravenčí kolonií. Iterace směřující k optimu jsou určovány chováním mravenců.
Ti se považují za sociální hmyz a tomu odpovídá jejich chování. Při honbě za potravou je pro ně důležité dostat se k potravě co nejkratší cestou. K tomuto účelu jsou vybaveni schopností vylučovat chemické látky zvané feromony. Ostatní mravenci feromony rozpoznávají a jsou schopni rozeznat i jeho koncentraci. Mravenec, který se vydává na cestu za potravou si s větší pravděpodobností zvolí cestu, na které je výskyt feromon? větší. Algoritmus zahrnuje pravidla pro ukládání a také vyprchávání feromonu na jednotlivých hranách grafu.
Cílem práce je vytvořit funkční aplikaci tohoto algoritmu.
Zásady pro vypracování
Problém obchodního cestujícího má za cíl nalezení nejkratší cesty přes množinu zákazníků. K řešení úlohy obchodního cestujícího bylo navrženo mnoho heuristických metod. Jednou z nich je algoritmus, jehož kroky jsou založeny na podobenství s mravenčí kolonií. Iterace směřující k optimu jsou určovány chováním mravenců.
Ti se považují za sociální hmyz a tomu odpovídá jejich chování. Při honbě za potravou je pro ně důležité dostat se k potravě co nejkratší cestou. K tomuto účelu jsou vybaveni schopností vylučovat chemické látky zvané feromony. Ostatní mravenci feromony rozpoznávají a jsou schopni rozeznat i jeho koncentraci. Mravenec, který se vydává na cestu za potravou si s větší pravděpodobností zvolí cestu, na které je výskyt feromon? větší. Algoritmus zahrnuje pravidla pro ukládání a také vyprchávání feromonu na jednotlivých hranách grafu.
Cílem práce je vytvořit funkční aplikaci tohoto algoritmu.
Seznam doporučené literatury
DORIGO, M.; MANIEZZO, V.; COLONI, A. The Ant System: Optimization by a colony of cooperating agents. In IEEE Transactions on Systems, Man, and Cybernetics - Part B., Vol. 26, No. 1, 1996. s. 13.
MICHALEWICZ, Z.; FOGEL, D.B. How to Solve It : Modern Heuristics. Berlin Heideberg New York : Springer - Verlag, 1998. 554 s. ISBN 9783642061349
Seznam doporučené literatury
DORIGO, M.; MANIEZZO, V.; COLONI, A. The Ant System: Optimization by a colony of cooperating agents. In IEEE Transactions on Systems, Man, and Cybernetics - Part B., Vol. 26, No. 1, 1996. s. 13.
MICHALEWICZ, Z.; FOGEL, D.B. How to Solve It : Modern Heuristics. Berlin Heideberg New York : Springer - Verlag, 1998. 554 s. ISBN 9783642061349
Přílohy volně vložené
1 CD ROM
Přílohy vázané v práci
ilustrace, grafy, tabulky
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
V bakalářské práci byly splněny všechny požadavky zadání, autor popsal a naprogramoval několik verzí algoritmu mraveniště a jejich funkčnost byla ověřena na testovacích úlohách. Bakalářská práce byla zpracována na velmi dobré úrovni. Autor zodpověděl otázky komise a ta ji ohodnotila známkou výborně.
Hodnocení odpovědí na otázky z odborných předmětů odpovídá celkovému výsledku zkoušky výborně.
Komise navrhuje bakalářskou práci na ocenění za vynikající tvůrčí výsledky dle článku 2, odst. 3, písm. b) Stipedijního řádu Univerzity Pardubice.