×

Evolvable components. From theory to hardware implementations. (English) Zbl 1056.68001

Natural Computing Series. Berlin: Springer (ISBN 3-540-40377-9/hbk). xvi, 194 p. (2004).
This monograph gathers in one volume methods for evolvable hardware design with underlying and supporting fields and theories like soft computing, evolutionary biology and generalizations of computational machines. Evolvable hardware is a reconfigurable electronic circuit, which can be changed by an adaptive process such as a genetic algorithm. The component approach, based on permanent interactions of a number of components, dominating as a concept in contemporary information technology, is also used here. The book consists of 9 chapters. The first four chapters include introductory information. After a short review of bioinspired hardware and motivation for research, chapter 2 surveys the reconfigurable hardware. The solutions offered by the industry (first of all by Xilinx and Atmel) are based on FPGA (Field Programmable Gate Array) blocks. They are briefly reviewed. The second, rather future trend is nanotechnology – a multidisciplinary field drawing from chemistry, biology, computer science and mechanical engineering, aiming at building the logical devices at the physical atomic level.
The book discusses the computational possibilities of a matrix of cells consisting of enormous capacities. Chapter 3 is devoted to evolutionary algorithms. They are the stochastic search algorithms inspired by the theory of evolution. Four types of evolutionary algorithms: genetic algorithms, genetic programming, evolutionary strategies and evolutionary programming are discussed. Formal definitions are formulated. Chapter 4 explains the applications of genetic programming to real hardware. The key concept is representation of the circuit in a chromosome and the computation of the fitness function. Chapter 5 describes the basic concept of evolvable component which combines the evolutionary algorithm with a reconfigurable circuit. The evolvable component differs from the fixed circuit, having only inputs and outputs, by adding a configuration structure consisting of a genetic unit (with fitness input) and a controller (with external control signals). The component interacts with the environment, which determines the quality (fitness) of the circuit. The evolvable component is described precisely by a Moore automaton. The approach is based on a system decomposition that allows for the emergence of optimized evolvable components.
In chapter 6 evolvable computational machines are defined formally and their properties are investigated. The importance of two computational processes is shown: the computation of the evolutionary algorithm and the computation of a a given evolving computational machine. The computational power of evolvable computational machines and the computational power of their physical implementations are investigated. The basic computational model is that of a cellular automaton. A cellular automaton is a multidimensional grid of finite automata (known as cells) (uniform if all the cells are identical, non-uniform otherwise) that operate according to their local transition functions. The formal definition of an evolvable non-uniform cellullar automaton is illustrated by a sequence generator example. The evolvable cellular automaton is generalized to a general evolvable computational machine. The increase of computational power in Turing machines subject to evolutionary generalizations is discussed.
The aim of the studies is to contribute to a uniform view of the component approach. The two final chapters present the results of experiments with practical evolutionary design of digital circuits. In the 7th chapter, image recognition circuit is developed using a software simulator. The simulation results have been utilized for hardware structure. This problem is strongly motivated by real needs of image recognition systems working in a changing environment like the recognition of damaged components in assembly line production. The idea is that a suitable reconfigurable circuit and a genetic unit will remain fixed, but the fitness function will be changed. The goal is to design an evolvable component for image preprocessing. At first, types of noise are discussed, and a conventional approach to filter design is presented. The filters are synthesized into an FPGA. Since the approach based on software simulation is time-consuming, the 8th chapter is oriented towards hardware implementation of the evolvable component. It is shown that a prototype of the evolvable component for image preprocessing can be placed on a common FPGA. This approach is known as virtual reconfigurable devices or chips on top of FPGAs and has been studied by several researchers. Architecture of the virtual reconfigurable circuit is presented with routing circuits built from multiplexers controlled by configuration memory. In order to speed up the evolutionary design, pipelining is used. Genetic unit organization is sketched. The proposed evolvable component is not physically implemented yet in hardware, however some FPGA-based platforms seem very promising for this purpose. The book may serve very well as handbook for courses on evolvable systems.

MSC:

68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q45 Formal languages and automata
68T05 Learning and adaptive systems in artificial intelligence
68Q80 Cellular automata (computational aspects)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
92D15 Problems related to evolution
PDFBibTeX XMLCite