|
|
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.
|
|
|
Computational tasks for solving parallel data processing
Rexa, Denis ; Uher, Václav (oponent) ; Mašek, Jan (vedoucí práce)
The goal of this diploma thesis was to create four laboratory exercises for the subject "Parallel Data Processing", where students will try on the options and capabilities of Apache Spark as a parallel computing platform. The work also includes basic setup and use of Apache Kafka technology and NoSQL Apache Cassandra database. The other two lab assignments focus on working with a Travelling Salesman Problem. The first lab was designed to demonstrate the difficulty of a task where the student will face an exponential increase in complexity. The second task consists of an optimization algorithm to solve the problem in cluster. This algorithm is subjected to performance measurements in clusters. The conclusion of the thesis contains recommendations for optimization as well as comparison of running with different number of computing devices.
|
|
|
Optimalizační algoritmy inspirované přírodou
Babjarčiková, Lenka ; Zbořil, František (oponent) ; Zbořil, František (vedoucí práce)
Táto práca sa venuje štyrom optimalizačným algoritmom inšpirovaných prírodou. Popisuje algoritmus mravčej kolónie, algoritmus párenia včiel, algoritmus vlčej svorky a algoritmus simulovaného žíhania. Súčasťou tejto práce bolo aplikovanie daných algoritmov pre tri optimalizačné úlohy. Jednou z úloh bol problém obchodného cestujúceho, ktorý je riešený pomocou algoritmu mravčej kolónie, ďalšou nájdenie extrému funkcie, ktoré je riešené algoritmom vlčej svorky a algoritmom simulovaného žíhania a poslednou úlohou bol problém splniteľnosti logických formúl, ktorý bol v tejto práci riešený algoritmom párenia včiel. Práca obsahuje experimenty s danými algoritmami a vyhodnocuje získané výsledky.
|
|
|
Monge property for interval matrices
Černý, Martin ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Tato práce je prvním průzkumem oblasti intervalových matic s Mongeovou vlastností. Zabývá se charakterizacemi a vlastnostmi dvojice tříd matic - třídy intervalových silně Mongeových matic a třídy intervalových slabě Mongeových matic. V práci je představeno několik metod na rozpoznávání a rekonstrukci těchto matic a následně prozkoumána jejich aplikace v problémech kombina- torické optimalizace a v problému související s výpočetní geometrií.
|
|
|
Genetické algoritmy
Masárová, Mária ; Zbořil, František (oponent) ; Zbořil, František (vedoucí práce)
Táto práca sa zaoberá genetickými algoritmami, ich terminológiou a využitím. Popisuje rôzne problémy, ktoré sa dajú pomocou genetických algoritmov riešiť. V práci sú taktiež predstavené rôzne algoritmy skupinovej inteligencie, pričom algoritmus svetlušiek slúži aj na porovnanie efektivity medzi ním a genetickým algoritmom. Hlavnou úlohou tejto práce je vykonať experimenty s tromi optimalizačnými úlohami, konkrétne sú to, problém obchodného cestujúceho, splniteľnosť logických formúl a hľadanie extrému funkcie.
|
|
|
Vymezení trasy pro běžecký závod modifikací úlohy obchodního cestujícího
Havel, Filip ; Borovička, Adam (vedoucí práce) ; Fábry, Jan (oponent)
Diplomová práce se zabývá nalezením optimální trasy pro běžecký závod. V množině až 251 křižovatek hledá propojení vymezující okruh s předem daným počátečním a současně cílovým místem. Modelově čerpá ze základního tvaru úlohy obchodního cestujícího, jehož primárním úkolem je projít zadanou množinu míst po co nejkratší cestě či v co nejkratším čase a vrátit se zpět do výchozího místa, přičemž každé místo navštíví právě jednou. Trasy hledané touto prací se ovšem v několika aspektech odlišují. Předně není nutné, aby zahrnovaly všechna místa, ty lze navštívit i vícekrát. Výsledná trasa nemá být nejkratší, ale měla by mít určité délkové rozpětí a klíčovým faktorem k optimalizaci jsou získané výškové metry. Řešení exaktními metodami předvede optimalizační software LINGO, pro vyšší výpočetní náročnost však pouze na omezeném rozsahu úlohy, 21 křižovatkách v centru města. Vymezení delší trasy na větší množině křižovatek umožní až odvozené heuristiky s pracovními názvy: nejvzdálenější soused s nejmenším stoupáním a minimální profilová změna. Součástí práce je detailní popis použitého matematického modelu i obecný postup, ukázka a rozbor obou aplikovaných heuristik.
|
|
|
Aplikace rozvozní úlohy pro geocaching
Frolík, Tomáš ; Skočdopolová, Veronika (vedoucí práce) ; Sekničková, Jana (oponent)
Geocaching je celosvětová hra, která využívá Globální polohovací systém (GPS). Většina hráčů se snaží při hledání kešek vytvořit takovou trasu, aby byla co nejkratší. Cílem této bakalářské práce je navrhnout takový model, aby dokázal vytvořit nejkratší trasu mezi jednotlivými kešemi za určitých omezujících podmínek v rámci pěti nezávislých okruhů. V první části práce jsou představeny základní teoretické poznatky nutné k porozumění praktické části. Druhá část je věnována základním termínům geocachingu. Dále je pak v rámci druhé kapitoly představen základní model rozvozní úlohy, jeho jednotlivé pro-měnné, rovnice a vyhodnocení. Ve výsledku takový model ale není zcela správný a je nutné jej rozšířit o třetí index, který nastaví podmínky pro jednotlivé vytvořené okruhy zvlášť.
|
|
|
Metody řešení vybraných dopravních problémů a jejich implementace.
Drobný, Michal ; Grygarová, Libuše (vedoucí práce) ; Zimmermann, Karel (oponent)
S různými typy dopravních problémů se v praxi setkáváme velmi často. Tento problém lze chápat především jako rozvoz zboží od dodavatelů k odběratelům s cílem minimalizace distribučních nákladů. Reálné dopravní problémy se od těch obecných liší především uvažovanými restrikcemi, což mohou být například kapacity vozidel a objednávek, časová okna a různá další speciální distribuční omezení. Problematiku dopravního problému formuloval již F. L. Hitchcock v roce 1941 a od té doby bylo popsáno mnoho stochastických a nedeterministických metod pro řešení dopravního problému, nicméně při zavedení distribučních restrikcí pro řešení reálných problémů jsou tyto metody obtížně aplikovatelné. Tato práce poskytuje kompilaci nejznámějších deterministických metod vhodných pro řešení dopravních problémů, přičemž metody vhodné pro řešení reálných dopravních problémů jsou popsány podrobněji. Postup řešení pro vybrané metody je demonstrován na jednoduchých příkladech a výsledky porovnány s výsledky řešení ostatních metod. Na základě analýzy těchto metod jsou navrženy nové metody pro řešení reálných dopravních problémů, které jsou implementovány a jejich výsledky porovnány s metodami, které poskytuje komerční softwarový produkt.
|
|
|
Využití matematických metod při plánování sítě obchodních zástupců
Mitas, Lukáš ; Fábry, Jan (vedoucí práce) ; Borovička, Adam (oponent)
Podniky z různých produkčních odvětví v dnešní době používají jako prostředek prodeje svého zboží nebo služeb síť obchodních zástupců. Tato diplomová práce se zabývá navrhováním sítě jako takové a dále tvořením plánu cest pro jednotlivé obchodní zástupce s cílem minimalizovat náklady spojené s jejich činností. Pro navrhování sítě je použito úlohy o pokrytí a přiřazovací úlohy. Pro plánování cest obchodního zástupce je využito klasické úlohy obchodního cestujícího, úlohy obchodního cestujícího s více obchodními cestujícími, heuristiky nejbližšího souseda, metody výměn, rozvozní úlohy a vlastního návrhu řešení. Stručně je popsána možnost využití metod vícekriteriálního hodnocení variant při rozhodování spojeném s vybavováním sítě obch. zástupců. Pro demonstraci metod na reálných datech byla využita data poskytnutá firmou Tata Global Beverages (Jemča).
|
|
|
Efektivita evolučních algoritmů
Němec, Jan ; Mlýnek, Petr (oponent) ; Fujdiak, Radek (vedoucí práce)
Tato diplomová práce se zabývá evolučními algoritmy. Jejím úkolem je vybrat vhodný evoluční algoritmus, který bude rešit vhodný problém. V tomto případě se jedná o genetický algoritmus, který bude řešit problém obchodního cestujícího. Výsledkem této diplomové práce bude implementace algoritmu, určení jeho ideálního nastavení a změření výsledků pro různá vstupní data.
|
host ::
RSS.