|
|
Multiobjective shortest path problem with interval costs
Březina, Jiří ; Hladík, Milan (advisor) ; Fink, Jiří (referee)
The multiobjective shortest path problem with interval costs is a gener- alization of the single-pair shortest path problem. In this problem, the edge weights are represented as tuples of intervals. The aim is to find the path that minimizes the maximum regret. We present theorems regarding the compu- tation of the regret and the efficiency of a feasible solution to the problem. The main result of the thesis is an algorithm seeking for the solution with the least regret in the interval multiobjective shortest path problem. 1
|
|
|
Artificial Intelligence for the Unstable Unicorns Game
Kodad, Michal ; Pilát, Martin (advisor) ; Fink, Jiří (referee)
This work explores artificial intelligence for the game Unstable Unicorns. This game started on Kickstarter and over the years, the game creators re- leased several expansions. This work aims to implement a game simulator for this game, analyze the game, and design the artificial intelligence for this game. First, we will analyze the game rules, game mechanics, and artificial intelligence in similar games. We implemented the game simulator as close as possible to the original rules. Afterward, we developed three different artificial intelligence algorithms. These are rule-based agents, Monte Carlo agents and evolutionary agents. Finally, we ran the experiments and com- parison tests with the implemented agents. The best-performing agent is the evolutionary agent. It is quick with the best win rate.
|
|
|
Optimization of the Placement of Electric Vehicle Charging Stations
Beinhauer, David ; Pilát, Martin (advisor) ; Fink, Jiří (referee)
As the number of electric vehicles grows, so does the need to create a suitable network of charging stations. A solution of this problem can be significantly improved by the usage of suitable optimization techniques. We implement a simplified traffic simulator serving as a suitable tool for their analysis. We also analyze optimization techniques using the so-called greedy algorithm, genetic algorithm and k-means algorithm. Based on the exper- iments, the optimizations using the genetic algorithm and the greedy algo- rithm showed noticeably better results. The k-means method did not show signs of results better than a random approach.
|
|
|
Travel Times Visualization Based on Public Transport Timetable
Fürst, Jan ; Pilát, Martin (advisor) ; Fink, Jiří (referee)
People often use public transport to travel to places they visit on regular basis. For these people, it would be very useful if they could live in a place, from which they could get faster to all the places they visit. The problem is how to find such a place. This problem is what we are trying to solve in our web application. By generalizing the standard public transport search we make it possible to calculate the travel times from user-defined places to all other reachable places. We visualize calculated travel times in an interactive map to simplify the search for the suitable place with the lowest travel times. Our web application uses our internal library which contains the functionality required for travel time calculations. This library could be used independently on the web application to solve other problems that require evaluation of travel times by public transport. 1
|
|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (advisor) ; Koubek, Václav (referee) ; Sereni, Jean-Sébastein (referee)
One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...
|
|
|
Anomaly Detection Using Generative Adversarial Networks
Měkota, Ondřej ; Fink, Jiří (advisor) ; Pilát, Martin (referee)
Generative adversarial networks (GANs) are able to capture distribution of its inputs. They are thus used to learn the distribution of normal data and then to detect anoma- lies, even if they are very rare; e.g. Schlegl et al. (2017) proposed an anomaly detection method called AnoGAN. However, a major disadvantage of GANs is instability during training. Therefore, Arjovsky et al. (2017) proposed a new version, called Wasserstein GAN (WGAN). The goal of this work is to propose a model, utilizing WGANs, to detect fraudulent credit card transactions. We develop a new method called AnoWGAN+e, partially based on AnoGAN, and compare it with One Class Support Vector Machines (OC-SVM) (Schöl- kopf et al. (2001)), k-Means ensemble (Porwal et al. (2018)) and other methods. Perfor- mance of studied methods is measured by area under precision-recall curve (AUPRC), and precision at different recall levels on credit card fraud dataset (Pozzolo (2015)). AnoW- GAN+e achieved the highest AUPRC and it is 12% better than the next best method OC-SVM. Furthermore, our model has 20% precision at 80% recall, compared to 8% precision of OC-SVM, and 89% precision at 10% recall as opposed to 79% of k-Means ensemble. 1
|
|
| |
|
|
Evolutionary Algorithms for the Design of Luminaire Optics
Drázdová, Zuzana ; Pilát, Martin (advisor) ; Fink, Jiří (referee)
The goal of this thesis was to explore the possibilities of using evolutionary algorithms to design components with specific purpose. We examined the process of designing an optimal shape of reflector from a highly reflective metal sheet. The main goal of this reflector is to evenly distribute light from a light emitting diode. We created a simplified model of the environment, where our component should be used. Then we used the evolutionary approach to find a suitable reflector shape for an existing device. One selected solution was manufactured and its properties measured. We also used the developed program to search for a design of an optical part for a completely new device proposal. Both tasks were accompanied by a number of problems that originated in an inaccurate task specification and general disparity between the fields of evolutionary computation and industrial components development. We provided an analysis of issues we encountered and presented solutions that can be applied to other similar tasks.
|
|
|
Optimization and Statistics
Fink, Jiří ; Loebl, Martin (advisor)
CONTENTS Nazev prace: Autor: Katedra (ustav-): Vedouci diplomove prace: E-mail vedouciho: Kh'cova slova; Abstrakt: Optimization and Statistics Jifi Fink Katedra aplikovane matematiky Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff, cuni.cz Edwards-Anderson Ising model, Teorie grafu, T-join, Gaussovska distribuce Jedni'm ze zakladnich problemu moderni statisticke fyzikj' je'snada porozumet frus- traci a chaosu. Zakladnfm modelem je konecne dimenzionalni Edwards-Anderson Ising model. V optimalizaci to odpovida zkoumam minimalni'ch T-joinu v konecnych mnzkach s nahodnymi vahami na hranach. V teto praci studujeme "random join", coz je nahodna cesta mezi dvema pevne danj^mi \Tcholy. Puvodni definice je pfilis slozita; a tak jsme ukazali jednodussi. Tato defmice je pouzita k pfesnernu vypoctu "random join" na kruznici. Take jsme ukazali specialm algoritmus, ktery hleda cestu v mrfzce s danymi hranami. Tento algoritmus muze byt pouzit k experimentalnimu studovani "random join". Title: Author: Department: Supervisor: Supervisor's e-mail address: Keywords: Abstract: Optimization and Statistics Jin Fink Department of Applied Mathematics Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff.cuni.cz Edwards-Anderson Ising model, Graph theory, T-join, the Gaussian distribution One of the basic streams of modern statistics physics is...
|
|
|
Searching Image Collections Using Deep Representations of Local Regions
Bátoryová, Jana ; Lokoč, Jakub (advisor) ; Fink, Jiří (referee)
In a known-item search task (KIS), the goal is to find a previously seen image in a multimedia collection. In this thesis, we discuss two different approaches based on the visual description of the image. In the first one, the user creates a collage of images (using images from an external search engine), based on which we provide the most similar results from the dataset. Our results show that preprocessing the images in the dataset by splitting them into several parts is a better way to work with the spatial information contained in the user input. We compared the approach to a baseline, which does not utilize this spatial information and an approach that alters a layer in a deep neural network. We also present an alternative approach to the KIS task, search by faces. In this approach, we work with the faces extracted from the images. We investigate face representation for the ability to sort the faces based on their similarity. Then we present a structure that allows easy exploration of the set of faces. We provide a demo, implementing all presented techniques.
|
guest ::
