|
Nové aplikace mravenčích algoritmů
Korgo, Jakub ; Drábek, Vladimír (oponent) ; Bidlo, Michal (vedoucí práce)
Mravenčí algoritmy byly použity na rozličné kombinatorické optimalizační úlohy. Jedna z těchto úloh, která však mravenčími algoritmy řešena nebyla, je návrh přechodových pravidel pro celulární automaty (CA). Což je i úloha, na kterou se zaměřuje tato diplomová práce. Tato práce začíná úvodem do mravenčích algoritmů a přehledem jejich aplikací, po kterém následuje úvod do CA. V další části autor navrhuje způsob, jak zakódovat pravidla CA do grafu, který je použit v mravenčích algoritmech. Poslední část této práce obsahuje aplikaci tohoto kódování pravidel do algoritmů elitist ant system a MAX-MIN ant system. Ta je následována experimentálními výsledky pokusů těchto algoritmů o vytvoření přechodových pravidel pro úlohy CA.
|
|
Experimenty s rojovou inteligencí (swarm intelligence)
Hula, Tomáš ; Zbořil, František (oponent) ; Grulich, Lukáš (vedoucí práce)
Práce se zabývá rojovou inteligencí jako podoborem umělé inteligence. Stručně popisuje biologické pozadí problematiky a zabývá se také principy hledání cest v mravenčích koloniích. Představena je i oblast kombinatorické optimalizace a detailně jsou definovány úlohy Travelling Salesman Problem a Quadratic Assignment Problem. Hlavní část práce sestává z popisu metod rojové inteligence pro řešení uvedených problémů a zhodnocení experimentů, které byly na těchto metodách provedeny. Konkrétně jde o algoritmy Ant System, Ant Colony System, Hybrid Ant System a Max-Min Ant System. V rámci práce byla také navržena a otestována vlastní metoda Genetic Ant System, která obohacuje základní Ant System mimo jiné o vývoj parametrů jednotek na základě genetických principů. V rámci obou řešených úloh jsou porovnány výsledky popisovaných metod společně s výsledky metod klasické umělé inteligence.
|
|
Ant Colony Optimization for Solving Big Instances of TSP
Ramosová, Patrícia ; Jaroš, Jiří (oponent) ; Bidlo, Michal (vedoucí práce)
Currently, many applications place emphasis on finding the optimal solution to a particular problem. However, it is typical for some tasks that their complexity increases exponentially depending on the size of the instance. A typical example of such a problem is the Traveling Salesman Problem (TSP). One class of methods that have proven to be very helpful in solving TSPs are ant algorithms. Nonetheless, they reached their limit - a high number of cities in the instance and became almost unusable due to time and memory requirements. This bachelor thesis aims to modify the ant algorithm and create a system capable of quickly and efficiently solve large-scale TSPs without significant loss in the quality of the solution found. Optimization will focus on reducing memory complexity and total execution time.
|
|
Ant Colony Optimization for Solving Big Instances of TSP
Ramosová, Patrícia ; Jaroš, Jiří (oponent) ; Bidlo, Michal (vedoucí práce)
Currently, many applications place emphasis on finding the optimal solution to a particular problem. However, it is typical for some tasks that their complexity increases exponentially depending on the size of the instance. A typical example of such a problem is the Traveling Salesman Problem (TSP). One class of methods that have proven to be very helpful in solving TSPs are ant algorithms. Nonetheless, they reached their limit - a high number of cities in the instance and became almost unusable due to time and memory requirements. This bachelor thesis aims to modify the ant algorithm and create a system capable of quickly and efficiently solve large-scale TSPs without significant loss in the quality of the solution found. Optimization will focus on reducing memory complexity and total execution time.
|
|
Nové aplikace mravenčích algoritmů
Korgo, Jakub ; Drábek, Vladimír (oponent) ; Bidlo, Michal (vedoucí práce)
Mravenčí algoritmy byly použity na rozličné kombinatorické optimalizační úlohy. Jedna z těchto úloh, která však mravenčími algoritmy řešena nebyla, je návrh přechodových pravidel pro celulární automaty (CA). Což je i úloha, na kterou se zaměřuje tato diplomová práce. Tato práce začíná úvodem do mravenčích algoritmů a přehledem jejich aplikací, po kterém následuje úvod do CA. V další části autor navrhuje způsob, jak zakódovat pravidla CA do grafu, který je použit v mravenčích algoritmech. Poslední část této práce obsahuje aplikaci tohoto kódování pravidel do algoritmů elitist ant system a MAX-MIN ant system. Ta je následována experimentálními výsledky pokusů těchto algoritmů o vytvoření přechodových pravidel pro úlohy CA.
|
|
Experimenty s rojovou inteligencí (swarm intelligence)
Hula, Tomáš ; Zbořil, František (oponent) ; Grulich, Lukáš (vedoucí práce)
Práce se zabývá rojovou inteligencí jako podoborem umělé inteligence. Stručně popisuje biologické pozadí problematiky a zabývá se také principy hledání cest v mravenčích koloniích. Představena je i oblast kombinatorické optimalizace a detailně jsou definovány úlohy Travelling Salesman Problem a Quadratic Assignment Problem. Hlavní část práce sestává z popisu metod rojové inteligence pro řešení uvedených problémů a zhodnocení experimentů, které byly na těchto metodách provedeny. Konkrétně jde o algoritmy Ant System, Ant Colony System, Hybrid Ant System a Max-Min Ant System. V rámci práce byla také navržena a otestována vlastní metoda Genetic Ant System, která obohacuje základní Ant System mimo jiné o vývoj parametrů jednotek na základě genetických principů. V rámci obou řešených úloh jsou porovnány výsledky popisovaných metod společně s výsledky metod klasické umělé inteligence.
|