|
Optimalizace návrhu celulárních automatů
Jílek, Tomáš ; Drábek, Vladimír (oponent) ; Bidlo, Michal (vedoucí práce)
Tato diplomová práce je zaměřena na evoluční návrh celulárních automatů a jeho optimalizaci. Nejprve jsou popsány evoluční algoritmy, celulární automaty, a poté je rozebrán jeden z možných nových postupů pro reprezentaci a evoluční návrh přechodové funkce automatu - podmínková pravidla. Následuje popis experimentů s podrobnými výsledky. V závěru je prezentováno úspěšné dosažení optimalizace evolučního návrhu celulárních automatů za pomocí podmínkových pravidel pro vybrané problémy.
|
|
Celulární automat v evolučním procesu
Hejč, Michal ; Herrman, Tomáš (oponent) ; Bidlo, Michal (vedoucí práce)
Tato diplomová práce pojednává o využití evolučních algoritmů společně s technikou developmentu v celulárních automatech. Popisuje základní principy jednotlivých nástrojů a následně se zaměřuje na jednu specifickou oblast - návrh kombinačních logických obvodů. Pomocí genetického algoritmu je hledán neuniformní celulární automat, který slouží jako generátor výsledného obvodu. Jsou provedeny experimenty se základními typy kombinačních logických obvodů a se speciální třídou nazývanou polymorfní obvody. Na závěr jsou představeny dosažené výsledky a provedeno porovnání s uniformními celulárními automaty.
|
|
Evoluční aproximace obrazových filtrů
Foukal, Tomáš ; Bidlo, Michal (oponent) ; Sekanina, Lukáš (vedoucí práce)
Tato diplomová práce popisuje problematiku aproximativního počítání, filtrování obrazu v hardwaru a evolučních algoritmů. Představuje řešení problému evoluční aproximace mediánových filtrů, kdy je cílem snížit výpočetní a implementační náročnost filtrace a současně minimalizovat chybu výpočtu. Na základě získaných poznatků a návrhů byly vytvořeny implementace nutných programů. Experimentální vyhodnocení ukazuje, že navržená metoda může pro mediánový filtr poskytovat dobrý kompromis mezi kvalitou filtrování a implementační cenou.
|
|
Evoluční návrh simulátoru založeného na celulárních automatech
Brigant, Vladimír ; Šperka, Svatopluk (oponent) ; Mrnuštík, Michal (vedoucí práce)
Tato práce popisuje návrh simulátoru založeného na celulárních automatech, který je schopen předpovědet chování komplexního prostorového systému. Tato predikce je založena na dostupních datech a přechodové funkci získané pomocí regresní analýzy ve spolupráci s evolučními algoritmy. Dvě metody regresné analýzy (lineární a logistická regrese) jsou navrhnuty, implementovány a porovnány na predikci rastu urbanizace města Brno.
|
|
Acceleration Methods for Evolutionary Design of Digital Circuits
Vašíček, Zdeněk ; Miller, Julian (oponent) ; Zelinka,, Ivan (oponent) ; Sekanina, Lukáš (vedoucí práce)
Although many examples showing the merits of evolutionary design over conventional design techniques utilized in the field of digital circuits design have been published, the evolutionary approaches are usually hardly applicable in practice due to the various so-called scalability problems. The scalability problem represents a general problem that refers to a situation in which the evolutionary algorithm is able to provide a solution to a small problem instances only. For example, the scalability of evaluation of a candidate digital circuit represents a serious issue because the time needed to evaluate a candidate solution grows exponentially with the increasing number of primary inputs. In this thesis, the scalability problem of evaluation of a candidate digital circuit is addressed. Three different approaches to overcoming this problem are proposed. Our goal is to demonstrate that the evolutionary design approach can produce interesting and human competitive solutions when the problem of scalability is reduced and thus a sufficient number of generations can be utilized. In order to increase the performance of the evolutionary design of image filters, a domain specific FPGA-based accelerator has been designed. The evolutionary design of image filters is a kind of regression problem which requires to evaluate a large number of training vectors as well as generations in order to find a satisfactory solution. By means of the proposed FPGA accelerator, very efficient nonlinear image filters have been discovered. One of the discovered implementations of an impulse noise filter consisting of four evolutionary designed filters is protected by the Czech utility model. A different approach has been introduced in the area of logic synthesis. A method combining formal verification techniques with evolutionary design that allows a significant acceleration of the fitness evaluation procedure was proposed. The proposed system can produce complex and simultaneously innovative designs, overcoming thus the major bottleneck of the evolutionary synthesis at gate level. The proposed method has been evaluated using a set of benchmark circuits and compared with conventional academia as well as commercial synthesis tools. In comparison with the conventional synthesis tools, the average improvement in terms of the number of gates provided by our system is approximately 25%. Finally, the problem of the multiple constant multiplier design, which belongs to the class of problems where a candidate solution can be perfectly evaluated in a short time, has been investigated. We have demonstrated that there exists a class of circuits that can be evaluated efficiently if a domain knowledge is utilized (in this case the linearity of components).
|
|
Evoluční návrh kolektivních komunikací akcelerovaný pomocí GPU
Tyrala, Radek ; Dvořák, Václav (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce provádí analýzu existující aplikace implementující evoluční algoritmus pro plánování kolektivních komunikací a navrhuje možnosti její akcelerace s využitím obecných výpočtů na grafických čipech (GPU). V práci je obsažen teoretický úvod do problematiky systémů na čipu, plánování kolektivních komunikací a podrobnější popis evolučních algoritmů. Práce dále zkoumá architektury GPU a paměťovou hierarchii grafických karet z pohledu OpenCL. Na základě analýzy zaměřené na časovou náročnost jednotlivých částí aplikace je proveden návrh paralelního zpracování hodnotící funkce fitness a odhad dosažitelného zrychlení. Stěžejní část práce popisuje implementaci navrženého řešení se zaměřením na využité optimalizace. Práce přináší srovnání původního řešení na CPU a paralelního provedení na GPU. V práci je popsána implementace distribuce výpočtu mezi různá zařízení podporovaná standardem OpenCL a jsou diskutovány výhody, omezení a další možnosti akcelerace výpočtu na základě jeho distribuce na heterogenních výpočetních systémech.
|
|
Polymorfní obrazové filtry
Salajka, Vojtěch ; Vašíček, Zdeněk (oponent) ; Sekanina, Lukáš (vedoucí práce)
Tato práce se zabývá evolučním návrhem polymorfních obrazových filtrů. Studie zahrnuje polymorfní obvody, jejich teoretický základ a praktické oblasti nasazení. Dále se zabývá kartézským genetickým programováním, které je použitelné pro evoluční návrh některých typů obrazových filtrů. V dalších částech je specifikován evoluční algoritmus pro návrh polymorfních obrazových filtrů. Je popsána implementace tohoto algoritmu ve dvou verzích -- neakcelerovaná běžící pouze na CPU a akcelerovaná využívající pro svůj běh také GPU. Pomocí algoritmu je navrženo několik polymorfních obrazových filtrů.
|
|
Evoluční návrh neuronových sítí
Beluský, Tomáš ; Vašíček, Zdeněk (oponent) ; Minařík, Miloš (vedoucí práce)
Práce se zabývá vytvořením genetického algoritmu pro návrh struktury a učení neuronových sítí. Fitness funkce zahrnuje i počet skrytých neuronů a tím získáváme nejoptimálnější možné struktury. Představí se vlastní verze operátorů, které řídí celý proces evoluce. Výsledkem práce je knihovna pro evoluční návrh neuronových sítí a kromě ní bylo vytvořeno i grafické rozhraní pro nastavování parametrů a zobrazování výsledků. V experimentální části je návrh porovnán s jinými systémy a algoritmy. Na závěr jsou zhodnoceny výsledky a naznačen postup pro následující vývoj systému.
|
|
Pokročilá evoluční filtrace obrazu
Saranová, Ivana ; Drábek, Vladimír (oponent) ; Bidlo, Michal (vedoucí práce)
Tato práce se zaměřuje na použití celulárních automatů s přechodovou funkcí složenou z podmínkových přechodových pravidel navržených evoluční strategií pro odstranění šumů různých typů a intenzit z digitálního obrazu. Navržená metoda vylepšuje původní koncept podmínkových přechodových pravidel úpravou pravé strany pravidla a rozšiřuje ji z jedné hodnoty na výběr výpočetních funkcí. Dále byla zkoumána různá nastavení evoluční strategie, trénování na různých typech šumů, trénování na částečně poškozených obrazech, a další nastavení, což vedlo k získání kvalitních filtrů pro každý model šumu. Porovnání těchto filtrů se stávajícími metodami ukazuje velké zlepšení oproti původnímu přístupu a schopnost evolučně navrhovat filtry, které se řadí mezi ty kvalitnější mezi porovnávanými metodami.
|
|
Concurrent evolutionary design of hardware and software
Minařík, Miloš ; Sekaj, Ivan (oponent) ; Squillero, Giovanni (oponent) ; Sekanina, Lukáš (vedoucí práce)
Genetic programming (GP) can, to some extent, automatically generate desired programs without asking the user to specify how to do it. It has been used to solve a wide range of practical problems and produce a number of human-competitive results in different fields. An interesting and practically untouched question is whether for a given problem, GP can generate a highly optimized programmable computational model (platform) together with a program running on the platform, solving the problem and satisfying all constrains such as on the area on a chip and speed. In a multi-objective scenario, the user would obtain a set of non-dominated solutions showing various tradeoffs between resources (the area, power consumption) and performance (the speed of execution). This problem can be seen as a concurrent development of hardware and software, simply, HW/SW codesign. This thesis explores the ways how to evolve hardware platforms together with programs in the case that the specification is given in terms of a set of input-output vectors. The initial model of the architecture was created and the evolutionary framework capable of maintaining and evolving the population of such architectures was implemented. Candidate microprogrammed architectures were evolved together with programs using extended linear genetic programming. Several simple experiments were carried out and the framework proved competitive with state-of-the-art methods. The framework was subsequently extended addressing the weak points identified during the initial experiments. The extended framework was validated by means of more complex experiments. One of them focused on an effective implementation of sigmoid function approximation. Various implementations of sigmoid approximation were evolved (sequentional as well as purely combinational). The proposed framework provided several well-known solutions and even optimized some of them for the particular input domain chosen for the experiment. The next set of experiments was supposed to evolve an image filter reducing salt-and-pepper impulse noise. The framework was able to evolve the concept of switching-based filter and even the variation of a switching-based median filter comparable to the filters commonly used. This thesis proved that small-size HW/SW systems can be designed and optimized by means of genetic programming. Moving to an automated evolutionary design of more complex HW/SW systems is an open research problem waiting for a future research.
|