The aim of this thesis is to experimentally evaluate the performance of several distinct representations of transition functions for cellular automata. Cellular automata have many potential applications for simulating various phenomena (e.g. natural processes, physical systems, etc.). Parallel computation of cellular automata is based on local cell interactions. Such computation, however, may prove difficult to program the CA, which is the reason for applying evolutionary techniques for the design of cellular automata in many cases. Evolutionary algorithms, based on Darwin's theory of evolution, have been used to find human-competitive solutions to many problems. In order to perform the evolutionary design of cellular automata, special encodings of the candidate solutions are often necessary. For this purpose the performance testing of various representations of the transition functions will be investigated. In particular, table representation, conditionally matching rules, and genetic programming will be treated. The problem of square calculations in cellular automata will be considered as a case study.

Tato disertační práce se zabývá evolučním návrhem a optimalizací jak běžných, tak polymorfních digitálních obvodů. V práci jsou uvedena a vyhodnocena nová rozšíření kartézského genetického programování (Cartesian Genetic Programming, CGP), která umožňují zkrácení výpočetního času a získávání kompaktnějších obvodů. Další část práce se zaměřuje na nové metody syntézy polymorfních obvodů. Uvedené metody založené na polymorfních binárních rozhodovacích diagramech a polymorfním multiplexovaní rozšiřují běžné reprezentace digitálních obvodů, a to s ohledem na začlenění polymorfních hradel. Z důvodu snížení počtu hradel v obvodech syntetizovaných uvedenými metodami je provedena evoluční optimalizace založená na CGP. Implementované polymorfní obvody, které jsou optimalizovány s využitím CGP, reprezentují nejlepší známá řešení, jestliže je jako cílové kritérium brán počet hradel obvodu.

This master's thesis deals with evolutionary algorithms and how them to use to design of combinational circuits. Genetic programming especially CGP is the most applicable to use for this type of task. Furthermore, it deals with computation on computer cluster and the use of evolutionary algorithms on them. For this computation is the most suited island models with CGP. Then a new way of recombination in CGP is designed to improve them. This design is implemented and tested on the computer cluster.

This work introduces a brief summary of softcomputing and the solutions to NP-hard problems. It especially deals with evolution algorithms and their basic types. The next part involves the study of cartesian genetic programming, which belongs to the field of evolution algorithms, used mainly in the evolution of digital circuits, symbolic regression, etc. A special chapter is devoted to the studies of new technique Age layered population structure, which deals with the problems of premature convergence, which suggests the way of how the population could be divided into subpopulations split up according to the age criteria. Thanks to the maintaining of sufficient diversity, it achieves substantially better solutions in comparison to the classical evolution algorithms. This papier includes the suggestion of two ways of incorporation of the ALPS technique into CGP. In the next part of work there were carried out tests on the classic problems, that would be solved with evolution algorithms. These tests were made with and without using ALPS technique. In the part of work "Experimental results" there was discussed a contribution of using ALPS technique in CGP against the classic CGP.

This project deals with evolutionary design of electronic circuits with an emphasis on digital circuits. It describes the theoretical basics for the evolutionary design of circuits on computer systems, including the explanation of Genetic Programming and Evolutionary Strategies, possible design levels of electronic circuits, CMOS technology overview, also the overview of the most important evolutionary circuits design methods like development and Cartesian Genetic Programming. Next introduced is a new method of digital circuits design on the transistor level, which is based on CGP. Also a design system using this new method is introduced. Finally, the experiments performed with this system are described and evaluated.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-03T18:47:50Z No. of bitstreams: 1 DissMAA.pdf: 3325891 bytes, checksum: 1b4744d48d74943990bed42753cc4b4c (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T18:27:58Z (GMT) No. of bitstreams: 1 DissMAA.pdf: 3325891 bytes, checksum: 1b4744d48d74943990bed42753cc4b4c (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T18:28:04Z (GMT) No. of bitstreams: 1 DissMAA.pdf: 3325891 bytes, checksum: 1b4744d48d74943990bed42753cc4b4c (MD5) / Made available in DSpace on 2016-10-20T18:28:13Z (GMT). No. of bitstreams: 1 DissMAA.pdf: 3325891 bytes, checksum: 1b4744d48d74943990bed42753cc4b4c (MD5) Previous issue date: 2016-03-04 / Não recebi financiamento / The use of technology based on Field Programmable Gate Arrays (FPGAs), a reconfigurable technology, has become a frequent object of study. This technique is feasible and a promising application in the development of embedded systems, however, the difficulty in finding a flexible and efficient way to perform such an application is their bigger problem. In this work, a virtual and reconfigurable architecture (AVR) in FPGA for hardware applications is presented using a Genetic Programming Software on the development of an optimal reconfiguration for this AVR, in order to build a hardware capable of performing a given task in an embedded system. This proposal is a simple, flexible and efficient way to achieve appropriate applications in embedded systems, when compared to other reconfigurable hardware techniques. The representation of phenotype of the proposed evolutionary system is based on a bi-dimensional network function elements (EF). The GPLAB tool for MATLAB is used in Genetic Programming, and the solution found by this procedure is converted into a memory mapping to represent the best solution, where it is used to reconfigure the hardware. In the tests, GPLAB found results for logic circuits in a few generations, and for image filters containing efficient solutions, where there was little hardware occupation, especially memory, in the cases this has been presented, with a reduced chromosome size, shows a proposal efficiency. / O uso da tecnologia baseada em Field Programmable Gate Arrays (FPGAs), de forma reconfigurável, para a solução de diversos problemas atuais, tem se tornado um frequente objeto de estudo. Essa técnica é de aplicação viável e promissora na elaboração de sistemas embarcados, porém, a dificuldade em encontrar uma forma flexível e eficiente de realizar tal aplicação é o seu maior problema. Neste trabalho, é apresentada uma arquitetura virtual e reconfigurável (AVR) em FPGA para aplicações em hardware, utilizando um software de Programação Genética na elaboração de uma reconfiguração ótima para esta AVR, de forma a construir um hardware capaz de efetuar uma determinada tarefa em um sistema embarcado. Esta proposta é uma forma simples, flexível e eficiente de realizar aplicações adequadas em sistemas embarcados, quando comparada a outras técnicas de hardware reconfigurável. A representação do fenótipo no sistema evolutivo proposto se baseia em uma rede de elementos de função (EF) bidimensional. A ferramenta GPLAB, para MATLAB, é usada na Programação Genética, e a solução encontrada por esta é convertida em um mapeamento de memória com o cromossomo da melhor solução, onde este é usado para reconfigurar o hardware. Nos testes realizados, a GPLAB encontrou resultados para circuitos lógicos em poucas gerações, e para filtros de imagem encontrou soluções eficientes, onde ocorreu pouca ocupação de hardware, principalmente da memória nos casos apresentados, apresentando um cromossomo de tamanho reduzido, o que demonstra uma boa eficiência da proposta.

Spotřeba a energetická efektivita se stává jedním z nejdůležitějších parametrů při návrhu počítačových systémů, zejména kvůli omezené kapacitě napájení u zařízení napájených bateriemi a velmi vysoké spotřebě energie rostoucích datacenter a cloudové infrastruktury. Současně jsou uživatelé ochotni do určité míry tolerovat nepřesné nebo chybné výpočty v roustoucím počtu aplikací díky nedokonalostem lidských smyslů, statistické povaze výpočtů, šumu ve vstupních datech apod. Přibližné počítání, nová oblast výzkumu v počítačovém inženýrství, využívá rozvolnění požadavků na funkčnost za účelem zvýšení efektivity počítačových systémů, pokud jde o spotřebu energie, výpočetní výkon či složitost. Aplikace tolerující chyby mohou být implementovány efektivněji a stále sloužit svému účelu se stejnou nebo mírně sníženou kvalitou. Ačkoli se objevují nové metody pro návrh přibližně počítajících výpočetních systémů, je stále nedostatek automatických návrhových metod, které by nabízely velké množství kompromisních řešení dané úlohy. Konvenční metody navíc často produkují řešení, která jsou daleko od optima. Evoluční algoritmy sice přinášejí inovativní řešení složitých optimalizačních a návrhových problémů, nicméně trpí několika nedostatky, např. nízkou škálovatelností či vysokým počtem generací nutných k dosažení konkurenceschopných výsledků. Pro přibližné počítání je vhodný zejména multikriteriální návrh, což existující metody většinou nepodporují. V této práci je představen nový automatický multikriteriální paralelní evoluční algoritmus pro návrh a aproximaci digitálních obvodů. Metoda je založena na kartézském genetickém programování, pro zvýšení škálovatelnosti byla navržena nová vysoce paralelizovaná implementace. Multikriteriální návrh byl založen na principech algoritmu NSGA-II. Výkonnost implementace byla vyhodnocena na několika různých úlohách, konkrétně při návrhu (přibližně počítajících) aritmetických obvodů, Booleovských funkcích s vysokou nelinearitou či přibližných logických obvodů pro tří-modulovou redundanci. V těchto úlohách bylo dosaženo význammých zlepšení ve srovnání se současnými metodami.

This diploma thesis deals with the use of Cartesian Genetic Programming (CGP) for combinational circuits design. The work addresses the issue of optimizaion of selected logic circuts, arithmetic adders and multipliers, using Cartesian Genetic Programming. The implementation of the CPG is performed in the Python programming language with the aid of NumPy, Numba and Pandas libraries. The method was tested on selected examples and the results were discussed.

The aim of this work is to automatically design a program that is able to detect dyskinetic movement features in the measured patient's movement data. The program will be developed using Cartesian genetic programming equipped with coevolution of fitness predictors. This type of coevolution allows to speed up a design performed by Cartesian genetic programming by evaluating a quality of candidate solutions using only a part of training data. Evolved classifier achieves a performance (in terms of AUC) that is comparable with the existing solution while achieving threefold acceleration of the learning process compared to the variant without the fitness predictors, in average. Experiments with crossover methods for fitness predictors haven't shown a significant difference between investigated methods. However, interesting results were obtained while investigating integer data types that are more suitable for implementation in hardware. Using an unsigned eight-bit data type (uint8_t) we've achieved not only comparable classification performance (for significant dyskinesia AUC = 0.93 the same as for the existing solutions), with improved AUC for walking patient's data (AUC = 0.80, while existing solutions AUC = 0.73), but also nine times speedup of the design process compared to the approach without fitness predictors employing the float data type, in average.

Tato diplomová práce se zabývá  aproximativní implementace aritmetických operací v obrazových filtrech. Zejména tedy využitím aproximativních technik pro úpravu způsobu násobení v netriviálním obrazovém filtru. K tomu je využito několik technik, jako použití převodu násobení s pohyblivou řadovou čárkou na násobení s pevnou řadovou čárkou, či využití evolučních algoritmů zejména kartézkého genetického programování pro vytvoření nových aproximovaných násobiček, které vykazují přijatelnou chybu, ale současně redukují výpočetní náročnost filtrace. Výsledkem jsou evolučně navržené aproximativní násobičky zohledňující distribuci dat v obrazovém filtru a jejich nasazení v obrazovém filtru a porovnání původního filtru s aproximovaným fitrem na sadě barevných obrázků.