|
Genetic Improvement of Cartesian Genetic Programming Software
Husa, Jakub ; Jaroš, Jiří (referee) ; Sekanina, Lukáš (advisor)
Genetic programming is a nature-inspired method of programming that allows an automated creation and adaptation of programs. For nearly two decades, this method has been able to provide human-comparable results across many fields. This work gives an introduction to the problems of evolutionary algorithms, genetic programming and the way they can be used to improve already existing software. This work then proposes a program able to use these methods to improve an implementation of cartesian genetic programming (CGP). This program is then tested on a CGP implementation created specifically for this project, and its functionality is then verified on other already existing implementations of CGP.
|
|
Evolutionary Design of Hash Functions
Kidoň, Marek ; Bidlo, Michal (referee) ; Dobai, Roland (advisor)
Hash tables are fast associative array implementations which became part of modern world of information technology and thanks to its simplicity became very popular among computer programmers. The choice of proper hash function is very important. Improperly selected hash function can result in poor hash table performance and its application. Currently there are many exceptional implementations of general hash functions. Such functions are not constrained to a concrete set of inputs, they perform on any input. On the other hand if we know the input domain we can design a specific hash function for desired application thus reaching better levels of performance compare to a general hash function. However hash function design is not trivial. There are no rules, standards, guides nor automated tools that would help us with such a task. In case of manual design the hash function author has to rely on his/her knowledge, experience, inventiveness and intuition. In case of such complicated tasks there is sometimes advantageous to choose a different path and use techniques such as evolution algorithms. Natural computing is an approach of certain problem solutions that are inspired by the process of species reproduction as defined by Charles Darwin. In this thesis we will design hash functions for the domain of IP addresses, that serve as an unique network device interface identifier in internet protocol networks. The chosen subset of natural computing is the genetic programming, a very specific technique that is an adequate approach to our problem thanks to its properties. Evolutionary designed hash functions offer good properties. They outperform state-of-the-art generic, human-created hash functions in terms of speed and collision resistance.
|
| |
|
Decision Tree Design Based on Evolutionary Algorithms
Benda, Ondřej ; Trzos, Michal (referee) ; Karásek, Jan (advisor)
Tato diplomová práce pojednává o dvou algoritmech pro dolování z proudu dat - Very Fast Decision Tree (VFDT) a Concept-adapting Very Fast Decision Tree (CVFDT). Je vysvětlen princip klasifikace rozhodovacím stromem. Je popsána základní myšlenka konstrukce stromu Hoeffding Tree, který je základem pro algoritmy VFDT a CVFDT. Tyto algoritmy jsou poté rozebrány detailněji. Dále se tato práce zabývá návrhem algoritmu Genetického Programování (GP), který je použit pro vytváření klasifikátoru obrazových dat. Vytvořený klasifikátor je použit jako alternativní způsob klasifikace objektů v obraze ve frameworku Viola-Jones. V práci je rozebrána implementace algoritmů, které jsou implementovány v jazyce Java. Algoritmus GP je integrován do knihovny “Image Processing Extension” programu RapidMiner. Algoritmy VFDT a CVFDT jsou testovány na syntetických a reálných textových datech. Algoritmus GP je testován na klasifikaci obrazových dat a následně vytvořený klasifikátor je otestován na detekci obličejů v obraze.
|
|
Scalability of genetic programming model
Kozempel, Lukáš ; Přinosil, Jiří (referee) ; Burget, Radim (advisor)
Theme of this thesis is practical realization of so-called Island model which is one of way of parallel genetic programming. First part is theoretical. This part is describing terms of genetic programming, age-layered population structure and island model. In second part of thesis is described realization of island model in Java language.
|
|
Automated File Editing Using Genetic Programming
Sedláček, Marek ; Vašíček, Zdeněk (referee) ; Sekanina, Lukáš (advisor)
Úprava souborů je nedílnou součástí práce pro mnoho lidí, ale ne každý umí programovat a nebo má dostatečnou znalost editovacích nástrojů, aby byl tento proces efektivní a rychlý. Toto je přesně to, co se snaží program představený v této práci -- Ebe -- vyřešit. Ebe z úryvků úprav provedených uživatelem pomocí genetického programovaní nalezne algoritmus na požadovanou transformaci souboru, který je pak možné použít na celý soubor nebo i více souborů najednou. Ebe se skládá z více částí, které musely být navrhnuty a implementovány ke splnění stanovených cílů. Za tímto účelem byl navrhnut nový programovací jazyk pro editaci souborů a kompatibilitu s genetickým programováním. Dále byl implementován interpreter pro tento jazyk a také překladač, který z poskytnutých ukázek syntetizuje editační algoritmus. Ebe bylo poté otestován a porovnáno s dalšími nástroji pro úpravu souborů. Tyto experimenty byly zaměřeny na celkovou editační dobu a Ebe ve většině experimentů dosáhlo lepších časů než jazyk Python 3 a podobných editačních časů jako jazyk AWK. Tyto experimenty potvrdily, že pro mnoho často prováděných úprav má Ebe potenciál jako alternativní nástroj pro tyto úlohy.
|
|
Regession Methods in Traffic Prediction
Vaňák, Tomáš ; Korček, Pavol (referee) ; Petrlík, Jiří (advisor)
Master thesis deals with possibilities of predicting traffic situation on the macroscopic level using data, that were recorded using traffic sensors. This sensors could be loop detectors, radar detectors or cameras. The main problem discussed in this thesis is the travel time of cars. A method for travel time prediction was designed and implemented as a part of this thesis. Data from real traffic were used to test the designed method. The first objective of this thesis is to become familiar with the prediction methods that will be used. The main objective is to use the acquired knowledge to design and to implement an aplication that will predict required traffic variables.
|
|
Application of SAT Solvers in Circuit Optimization Problem
Minařík, Vojtěch ; Mrázek, Vojtěch (referee) ; Vašíček, Zdeněk (advisor)
This thesis is focused on the task of application of SAT problem and it's modifications in area of evolution logic circuit development. This task is supposed to increase speed of evaluating candidate circuits by fitness function in cases where simulation usage fails. Usage of SAT and #SAT problems make evolution of complex circuits with high input number significantly faster. Implemented solution is based on #SAT problem. Two applications were implemented. They differ by the approach to checking outputs of circuit for wrong values. Time complexity of implemented algorithm depends on logical complexity of circuit, because it uses logical formulas and it's satisfiability to evaluate logic circuits.
|
|
Genetic Programming in Prediction Tasks
Machač, Michal ; Mrázek, Vojtěch (referee) ; Sekanina, Lukáš (advisor)
This thesis introduces various machine learning algorithms which can be used in prediction tasks based on regression. Tree genetic programming and linear genetic programming are explained more thoroughly. Selected machine learning algorithms (linear regression, random forest, multilayer perceptron and tree genetic programming) are compared on publicly available datasets with the use of scikit-learn and gplearn libraries. A core part of this project is a new implementation of linear genetic programming which was developed in C++, tested on common symbolic regression problems and then evaluated on real datasets. Results obtained with the proposed system are compared with the results obtained with gplearn.
|
|
Automated Creation of Portable Stimuli Scenarios Using Evolutionary Algorithms
Tichý, Andrej ; Bardonek, Petr (referee) ; Zachariášová, Marcela (advisor)
This thesis focuses on the automation of scenarios creation for Portable Stimulus standard. The main goal of the work is an automatic generation of tests, which are defined as graphs for the Questa inFact tool from the Mentor company. For the automation I used an evolutionary algorithm with using a grammatical evolution. The generated scenarios are connected to the existing verification environment based on UVM methodology, then the verification of the connected component is started. Based on the achieved functional and structural coverage, the individual's fitness value is calculated and propagated into an evolutionary algorithm. At the end of the work, experiments are performed on the timer component and the contribution of the proposed evolutionary algorithm is evaluated. The proposed evolutionary algorithm is configurable by grammar and user-defined basic transactions, which allows a wide range of uses. The evolutionary algorithm managed to achieve high functional and structural coverage on the verified timer component.
|