Component Approach to Evolvable Systems

dissertation

English

In recent years evolutionary algorithms have been successfully applied to hardware design in the field of bioinspired hardware. This PhD thesis deals with evolvable hardware, which refers to evolutionary design of electronic circuits directly at the hardware level. Evolvable hardware also enables to design high performance and adaptive circuits for applications, in which the problem specification is unknown beforehand or can vary in time. While a number of relatively simple circuits were successfully evolved in FPGAs (Field Programmable Gate Arrays), nowadays, FPGAs are not suitable for implementation of real-world applications of evolvable hardware operating in the changing environment. The main reason is that common FPGAs do not provide an effective way of reconfiguration. Furthermore, the current approach to the design of such systems can be characterized as ad hoc design. The primary goal of this thesis is to solve at least some of the problems, which appear when we want to perform a routine design of evolvable hardware based applications using common FPGAs. We present an original idea of component approach to evolvable system, which is based on a system decomposition that enables emergence of so called evolvable components. The evolvable component encapsulates the reconfigurable circuit and the genetic operators, while the fitness function is considered as a (potentially dynamic) environment surrounding the component. We argue that a separation of the fitness function is a crucial idea for efficient design of evolvable systems. Such components are designed for a given class of applications and may be reused, for instance, as IP (Intellectual Property) macros. Evolvable component approach allows a unified view on all evolvable computational systems. Hence it is possible to formally define general evolvable computational machine and investigate its properties. The aim of the proposed formal approach was to clarify what we really do in evolvable hardware from a computational point of view. We showed that the generalized evolvable computational machine operating in a dynamic environment possesses a super-Turing computational power. This means that such a machine cannot be simulated using traditional computational models like Turing machines. From a practical viewpoint this power is limited by No Free Lunch theorems. In order to show an example of the evolvable component, we have designed an evolvable component for image pre-processing. It may be considered as a real-world application of evolvable hardware because the relatively complex circuits of 72 inputs and 8 outputs are evolved. We have extended Cartesian Genetic Programming to functional level to manage scalability problems that are typical for evolutionary design of such large circuits. Using the component we were able to evolve image filters for Gaussian, uniform, and shot noise and an edge detector that exhibit higher quality and sometimes also lower implementation costs in comparison with conventional circuits. Furthermore, we showed that the component is able to autonomously adapt to the changing environment if a sufficient time is provided for evolution. Evolutionary image operator design clearly demonstrates that much time consuming fitness calculation is the most painful problem of evolvable hardware. In order to overcome this problem, we have developed a method that makes us possible building a new reconfigurable platform using a common FPGA and thus speeding up the fitness calculation in hardware. This new reconfigurable circuit, which exactly fits to the requirements of a given application, is designed using resources available in a common FPGA. Regardless problems with implementation costs, we were able to synthesize the circuit into a common Virtex FPGA. Then the evolvable component can adapt to the changing fitness function in sufficient time. We can summarize that the thesis provides a

evolvable hardware, evolvable machines, evolutionary circuit design, evolvable components, virtual reconfigurable circuits

SEKANINA, L.

12. 11. 2002

Brno

132