Evolvable Components

At the beginning of the 1990s research started in how to combine soft comput­ ing with reconfigurable hardware in a quite unique way. One of the methods that was developed has been called evolvable hardware. Thanks to evolution­ ary algorithms researchers have started to evolve electronic circuits routinely. A number of interesting circuits - with features unreachable by means of con­ ventional techniques - have been developed. Evolvable hardware is quite pop­ ular right now; more than fifty research groups are spread out over the world. Evolvable hardware has become a part of the curriculum at some universi­ ties. Evolvable hardware is being commercialized and there are specialized conferences devoted to evolvable hardware. On the other hand, surprisingly, we can feel the lack of a theoretical background and consistent design methodology in the area. Furthermore, it is quite difficult to implement really innovative and practically successful evolvable systems using contemporary digital reconfigurable technology.

Auteur

Lukas Sekanina received MSc degree in Computer Science and Engineering and PhD degree in Information Technology from Brno University of Technology, Czech Republic, in 1999 and 2002 , respectively. He was a visiting lecturer with Pennsylvania State University, USA, and a visiting researcher with Department of Informatics, University of Oslo, Norway, in 2001. He is author or co-author of more than 20 refereed conference papers mainly on evolvable hardware and bio-inspired computing. He was awarded Siemens Awards 1999 and 2000 and The best paper award at IEEE Design and Diagnostics of Electronic Circuits and System workshop 2002. Currently he is an assistant professor with Faculty of Information Technology, Brno University of Technology. His research interests focus on theory, design and implementations of bio-inspired computational systems.

Contenu

1 Introduction.- 1.1 Natural Computing.- 1.1.1 Soft Computing.- 1.1.2 Quantum Computing.- 1.1.3 DNA Computing.- 1.1.4 Membrane Computing.- 1.2 Bioinspired Hardware.- 1.3 Motivation for Research.- 2 Reconfigurable Hardware.- 2.1 Digital Cicuits.- 2.2 Digital Circuit Design.- 2.3 Field Programmable Gate arrays.- 2.3.1 Architecture of FPGAs.- 2.3.2 The XC4000 Family.- 2.3.3 ThE Virtex Family.- 2.3.4 The XC6200 Family.- 2.3.5 Atmel FPGAs.- 2.3.6 Features of FPGAs.- 2.4 Hardware Reused as Software.- 2.5 Reconfigurable Computing.- 2.6 Nanotechnology.- 2.7 Cell Matrix.- 2.8 Summary.- 3 Evolutionary Algorithms.- 3.1 Introduction.- 3.2 Variant of Evolutionary Algorithms.- 3.2.1 Genetic Algorithms.- 3.2.2 Genetic Programming.- 3.2.3 Evolutionary Strategies.- 3.2.4 Evolutionary Programming.- 3.3 Some Other Features of Evolutionary Algorithms.- 3.3.1 Parallel Implementations.- 3.3.2 Dynamic Fitness Function.- 3.4 Evolutionary Design and Optimization.- 3.5 The Evolutionary Algorithm Design.- 3.5.1 Missing Theories.- 3.5.2 The Design Strategies.- 3.6 Formal Approach.- 3.7 Summary.- 4 Evolvable Hardware.- 4.1 Basic Concept.- 4.2 Cartesian Genetic Programming.- 4.3 Features of Cartesian Genetic Programming.- 4.3.1 Redundancy and Neutrality.- 4.3.2 Fitness Landscape Analysis.- 4.3.3 Implementation Issues.- 4.4 From Chromosome to Fitness Value.- 4.4.1 Representation.- 4.4.2 Platforms for Circuit Evolution.- 4.4.3 Circuit Evaluation.- 4.5 Fitness Function.- 4.5.1 Fitness Function and Circuit Behavior.- 4.5.2 Evolutionary Circuit Design: Static Fitness Function.- 4.5.3 Evolvable Hardware: Dynamic Fitness Function.- 4.5.4 Discussion.- 4.6 Applications and Degree of Hardware Implementation.- 4.7 Promising Results.- 4.8 Major Current Problems and Potential Solutions.- 4.8.1 Scalability of Representaion.- 4.8.2 SCalability of Fitnes Evaluation.- 4.8.3 Robustness of the Evolved Circuits.- 4.8.4 Applications in Dynamic Environments.- 4.9 Summary.- 5 Towards Evolvable Components.- 5.1 Component Approach to Problem Solving.- 5.2 Evolvable Components.- 5.2.1 System Decomposition.- 5.2.2 Interface.- 5.3 Hardware Implementation.- 5.3.1 Evolvable Componenets.- 5.3.2 Environment.- 5.3.3 Communication Betweem Evolvable Component and Environment.- 5.4 Extension of Evolvable Components.- 5.5 Summary.- 6 Evolvable Computational Machines.- 6.1 Computational Machines and Evolutionary Design.- 6.2 Cellular Automata.- 6.2.1 Basic Model.- 6.2.2 Evolvable Non-Uniform CEllular Automaton.- 6.2.3 An example: Evolvable Non-Uniform Cellular Automaton as a Sequence Generator.- 6.3 General Evolvable Computational Machine.- 6.4 Dynamic Environment.- 6.5 Evolvable Computational System.- 6.5.1 Formal Definition.- 6.5.2 An example: Formal Description of a Simple Image Compression.- 6.6 Properties of Evolvable Machines.- 6.6.1 On the Computation of Evolvable Machines.- 6.6.2 Mappings g and f.- 6.6.3 Changing Fitness Fuction.- 6.7 The Computational Power.- 6.7.1 The Turing Machine and the Church Turing Thesis.- 6.7.2 Beyond the Turing Machines.- 6.7.3 A New Paradigm.- 6.7.4 Site Machine.- 6.7.5 the Power of an Evolvable System.- 6.7.6 Discussion.- 6.8 Summary.- 7 An Evolvable Component for Image Pre-processing.- 7.1 Motivation and Problem Specification.- 7.2 The Image Filter Design.- 7.2.1 Types of Noise Considered for Testing.- 7.2.2 Convnetional Approaches.- 7.2.3 Implementation of FPGAs.- 7.2.4 A Brief Survey of Evolutionary Approaches.- 7.3 Analysis of Reconfigurability and Size of the Search Space.- 7.3.1 Elementary Measures.- 7.3.2 Cartesian Genetic Programming in Hardware.- 7.3.3 Cartesian Genetic Programming at the Fuctional Level.- 7.4 Evolutionary Design: Experimental Framework.- 7.4.1 Reconfigurable Circuit.- 7.4.2 Evolutionary Algorithms.- 7.4.3 Fitness Function.- 7.5 Filters for Smoothing.- 7.5.1 The Results.- 7.5.2 Discussion.- 7.6 Other Image Operators.- 7.6.1 "Salt and Pepper" Noise Filters.- 7.6.2 Random Shot-Noise Filters.- 7.6.3 Edge Detectors.- 7.7 Dynamics Environment.- 7.7.1 Experimental Setup.- 7.7.2 The Results in Tables 7.9 and 7.10.- 7.7.3 Discussion.- 7.8 A Note on a Single Filter Design.- 7.9 Summary.- Virtual Reconfigurable Devices.- 8.1 Chip on Top of a Chip.- 8.2 Architecture of Virtual Reconfigurable Circuits.- 8.2.1 Overview.- 8.2.2 Routing Logic and Configuration Memory.- 8.2.3 Configuration Options.- 8.3 Implementation Costs.- 8.4 Speeding up the Evolutionary Design.- 8.5 Genetic Unit.- 8.6 Physical Realization.- 8.7 Discussion.- 8.8 Summary.- 9 Concluding Statements.- 9.1 The Approach.- 9.2 The Obtained Results.- 9.3 Future Work.- References.