|
|
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.
|
|
| |
|
|
Evolutionary Resynthesis of Combinational Circuits
Kocnová, Jitka ; Sekanina, Lukáš (referee) ; Vašíček, Zdeněk (advisor)
This master thesis is concerned about the resynthesis of combinational circuits with the help of evolutional principles. The first part of this text describes logic synthesis and its weak spots, evolutional synthesis and its advantages, and also some of the existing synthesis programs. The second part shows usage of graph algorithms in logic synthesis and their possible usage in an extension for the chosen synthesis program. Suggested design and practical implementation of the extension is also described in this part. In the third part extension testing is mentioned. The fourth part is the last one and concludes gained knowledge and results.
|
|
|
Self-Modifying Programs in Cartesian Genetic Programming
Minařík, Miloš ; Slaný, Karel (referee) ; Sekanina, Lukáš (advisor)
During the last years cartesian genetic programming proved to be a very perspective area of the evolutionary computing. However it has its limitations, which make its use in area of large and generic problems impossible. These limitations can be eliminated using the recent method allowing self-modification of programs in cartesian genetic programming. The purpose of this thesis is to review the development in this area done so far. Next objective is to design own solutions for solving various problems that are hardly solvable using the ordinary cartesian genetic programming. One of the problems to be considered is generating the terms of various Taylor series. Due to the fact that the solution to this problem requires generalisation, the goal is to prove that the self-modifying cartesian genetic programming scores better than classic one for this problem. Another discussed problem is using the self-modifying genetic programming for developing arbitrarily large sorting networks. In this case, the objective is to prove that self-modification brings new features to the cartesian genetic programming allowing the development of arbitrarily sized designs.
|
|
|
Warehouse Simulation and Product Distribution Optimization for Increased Throughput
Kočica, Filip ; Kolář, Martin (referee) ; Kodym, Oldřich (advisor)
This thesis focuses on the storage location assignment problem using modern meta-heuristic techniques combined with realistic simulation. A graphical tool implemented as part of this work is capable of warehouse model creation, generation of synthetic customer orders, optimization of product allocation using state of the art techniques, extensive warehouse simulation, and a pathfinder capable of finding the shortest path for orders going through the system. The work presents the comparison between different approaches based on many parameters to reach the most efficient allocation of products to warehouse slots. The author conducted tests on an experimental warehouse featuring almost twice the throughput -- 57%. The benefit of this work is a possibility to create model of an already built warehouse and its simulation and optimization, driving impact on the throughput of the warehouse, saving the user's resources, or helping him in planning and bottle-neck identification. Furthermore, this thesis introduces a new approach to warehouse optimization and new optimization criteria.
|
|
|
Race Car Suspension, Springing, Damping
Šťastný, Jan ; Zháňal, Lubor (referee) ; Blaťák, Ondřej (advisor)
The main subject of this bachelor project is overview of suspension, springing and damping methods structural design in racing car. Attention is payed especially to automotive races which are under sponsorship of ACR (Autoclub of Czech Republic). Firstly is placed issue which notify main sort and princip of suspension, springing and damping function. In the next chapter is summary of technological restrictions and prescripts for racing car structural design. Next chapter refers about the most used types of structural designs for given competition. The last chapter considers development trend of suspension, springing and damping systems in racing cars.
|
|
|
Hardware Acceleration of Algorithms for Approximate String Matching
Nosek, Ondřej ; Kořenek, Jan (referee) ; Martínek, Tomáš (advisor)
Methods for aproximate string matching of various sequences used in bioinformatics are crucial part of development in this branch. Tasks are of very large time complexity and therefore we want create a hardware platform for acceleration of these computations. Goal of this work is to design a generalized architecture based on FPGA technology, which can work with various types of sequences. Designed acceleration card will use especially dynamic algorithms like Needleman-Wunsch and Smith-Waterman.
|
|
|
Diffusion Evolutionary Algorithm
Žundálek, Zbyněk ; Puš, Viktor (referee) ; Jaroš, Jiří (advisor)
This bachelor thesis deals with a parallelization of cellular evolutionary algorithms using OpenMP. The theoretical part of the thesis contains an introduction to evolutionary and genetic algorithms followed by the description of their parallel implementation on shared memory systems. This part is completed with the OpenMP key features analysis. The practical part of this thesis describes two possible implementations of a diffusion evolutionary algorithm; synchronous and asynchronous. The comparison of achievable performance of these two methods carried out on the N-Queen problem is provided in the experimental part of the thesis. The quality of found solutions is further examined with respect to the neighborhood size, topology and the replacement operator of the diffusion evolutionary algorithm.
|
|
|
Design of Digital Circuits at Transistor Level
Kešner, Filip ; Šimek, Václav (referee) ; Vašíček, Zdeněk (advisor)
This work aims to design process of integrated circuits on the transistor level, specially using evolutionary algorithm. For this purpose it is necessary to choose reasonable level of abstraction during simulation, which is used for evaluation candidate solutions by fitness function. This simulation has to be fast enough to evaluate thousands of candidate solutions within seconds. This work discusses already used techniques for transistor level circuit design and it chooses useful parts for new design of faster and more reliable automated design process, which would be able to design complex logic circuits. The thesis also discusses implementation of this system and used approach with regard to encountered problems in transistor-level circuit design and optimization by evolution.
|
|
|
Detection of positive selection in reproductive genes of songbirds
Cakl, Lukáš ; Reifová, Radka (advisor) ; Těšický, Martin (referee)
Reproductive genes are assumed to play an important role in adaptive evolution and speciation, yet little is known about the patterns of molecular evolution in these genes within avian species. This thesis is focused on identifying reproductive genes under positive selection and analyzing their function in songbirds, the largest and most diverse suborder of modern birds. Using existing bioinformatic approaches and published genomic data of 14 songbird species, we have first constructed 12000 groups of orthologous genes and detected significant traces of recurrent positive selection within 385 of them. Using proteomic data, this genome wide set of genes was then filtered to obtain genes expressed within songbird spermatozoa and fluids from the female reproductive tract. Within spermatozoa 22 out of 940 expressed genes were positively selected, while female fluids were found to be more conserved, as only 6 out of 529 expressed genes have shown traces of positive selection. We have then computed the enrichment of gene ontology terms within the positively selected genes. The enriched terms suggest evolutionary pres- sures acting on spermatozoa cytoskeleton, molecular motors and energetic metabolism, highlighting the importance of sperm morphology and swimming speed. Furthermore, the enrichment results...
|
guest ::
