The goal of this project is to design a hardware unit that is designed to accelerate evolutionary design of digital circuits on transistor level. The project is divided to two parts. The first one describes design methods of the MOSFET circuits and issues of evolutionary algorithms. It also analyses current results in this domain and provides a new method for the design and optimization. The second part describes proposed unit that accelerates the new method on the circuit Zynq which integrates ARM processor and programmable logic. The new method functionality has been empirically analysed in the task of optimization of few circuits with more inputs. The hardware unit has been tested for designing of gates on transistor level.

This project deals with combinational digital circuits and their optimization. First there are presented main levels of abstraction utilized in the design of combinational digital circuits. Afterwards different methods are surveyed for optimization of combinational digital circuits. The next part of this project is mainly devoted to evolutionary algorithms, their common characteristics and branches: genetic algorithms, evolutionary strategies, evolutionary programming and genetic programming. The variant of genetic programming called Cartesian Genetic Programming (CGP) and the use of CGP in various areas, particularly in the synthesis and optimization of combinational logic circuits are described in detail. The project also discusses some modifications of CGP and the scalability problem of evolutionary circuit design. Consequential part of this thesis describes the method for evolution resynthesis of combinational digital circuits. There is description of design, especially the method of splitting circuits into subcircuits, and implementation details. Finally experiments with these method and their results are described.

The goal of this Master's Thesis is finding a SAT solving heuristic by the application of an evolutionary algorithm. This thesis surveys various approaches used in SAT solving and some variants of evolutionary algorithms that are relevant to this topic. Afterwards the implementation of a linear genetic programming system that searches for a suitable heuristic for SAT problem instances is described, together with the implementation of a custom SAT solver which expoloits the output of the genetic program. Finally, the achieved results are summarized.

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.

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.

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.

[pt] Na área de exploração e produção de petróleo são alocados grandes investimentos para conseguir diminuir os riscos associados à baixos níveis de produção, que podem ser minimizados mediante a acertada caracterização do reservatório de petróleo. Uma valiosa fonte de informação pode ser extraída de dados sísmicos 3D, obtidos do campo em estudo. O custo econômico de aquisição de esta base de dados para o reservatório completo é relativamente baixo, se comparado com uma amostragem direta por meio de perfurações de poços. Embora, a relação entre os dados sísmicos e as propriedades de reservatório seja considerada ambígua, esta deve ser integrada com informação confiável, como aquela obtida mediante perfilagem de poços. Fazendo uso dos abundantes dados sísmicos e das escassas, mas, precisas medições em perfurações existentes, foi desenvolvido neste trabalho um sistema baseado no algoritmo de Programação Genética (PG) para caracterizar geologicamente um reservatório de petróleo. PG é uma técnica de computação evolucionária capaz de estimar relações não lineares entre um conjunto de entrada e de saída, mediante uma expressão simbólica explícita. Para extrair informação adicional nos registros sísmicos são calculados atributos sísmicos, que facilitam a identificação de características estratigráficas ou estruturais do subsolo representadas indiretamente pela sísmica. Adicionalmente, é utilizado o método de inversão sísmica para o cálculo da impedância acústica, que é uma variável auxiliar derivada de sísmica calibrada com perfis de poço. Os atributos sísmicos junto com a impedância acústica servirão para a estimação de propriedades geológicas. Esta metodologia de trabalho foi testada em um reservatório real de grande complexidade geológica. Por meio de PG, foi representada satisfatoriamente a relação entre dados derivados da sísmica e a porosidade do campo, demostrando assim que PG é uma alternativa viável para a caracterização geológica de reservatórios. Posteriormente, foi realizada uma clusterização do campo baseada em características geofísicas que permitiram a construção de estimadores por PG especializados para cada zona. / [en] In the field of oil exploration and production a great deal of investment is allocated in reducing the risks associated to low production levels that can be minimized through an accurate oil reservoir characterization. A valuable source of information can be extracted from 3D seismic data, obtained from the studied reservoir. The economic cost of the acquisition of this data base for the whole reservoir is relatively low, if compared to the direct sampling method of well drilling. Being that the relationship between seismic data and reservoir properties is considered ambiguous, it must be integrated with reliable information, such as that obtained by well logging. Making use of abundant seismic data and scarce, yet accurate, measurements from the existing drillings, it was developed in this study a system based in the algorithm of Genetic Programming (GP), to geologically characterize an oil reservoir. GP is an evolutionary computational technique capable of estimating the non-linear relationships between input and output parameter, through an explicit symbolic expression. In order to extract additional information from seismic records, seismic attributes are calculated, which facilitate tasks of identifying stratigraphic and structural characteristics of the subsurface, represented indirectly by seismic data. Moreover, a seismic inversion method is used to estimate the acoustic impedance, an auxiliary variable derived from seismic data calibrated by well logs. The seismic attributes along with the acoustic impedance will be used to estimate geological properties. This workflow was tested on a real reservoir, thus presenting geological complexity. Through GP, the relationship between seismic derived data and the field porosity was represented satisfactorily, demonstrating that GP is a viable alternative for geologic reservoir characterization. Afterwards, the reservoir was divided in clusters according to geophysical properties, this allowed the construction of GP based estimators for each zone.

In this thesis we address the problem of integrated software pipelining for clustered VLIW architectures. The phases that are integrated and solved as one combined problem are: cluster assignment, instruction selection, scheduling, register allocation and spilling. As a first step we describe two methods for integrated code generation of basic blocks. The first method is optimal and based on integer linear programming. The second method is a heuristic based on genetic algorithms. We then extend the integer linear programming model to modulo scheduling. To the best of our knowledge this is the first time anybody has optimally solved the modulo scheduling problem for clustered architectures with instruction selection and cluster assignment integrated. We also show that optimal spilling is closely related to optimal register allocation when the register files are clustered. In fact, optimal spilling is as simple as adding an additional virtual register file representing the memory and have transfer instructions to and from this register file corresponding to stores and loads. Our algorithm for modulo scheduling iteratively considers schedules with increasing number of schedule slots. A problem with such an iterative method is that if the initiation interval is not equal to the lower bound there is no way to determine whether the found solution is optimal or not. We have proven that for a class of architectures that we call transfer free, we can set an upper bound on the schedule length. I.e., we can prove when a found modulo schedule with initiation interval larger than the lower bound is optimal. Experiments have been conducted to show the usefulness and limitations of our optimal methods. For the basic block case we compare the optimal method to the heuristic based on genetic algorithms. This work has been supported by The Swedish national graduate school in computer science (CUGS) and Vetenskapsrådet (VR).

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.