Skip to main content
main-content

Über dieses Buch

This book covers the basic theory, practical details and advanced research of the implementation of evolutionary methods on physical substrates. Most of the examples are from electronic engineering applications, including transistor-level design and system-level implementation. The authors present an overview of the successes achieved, and the book will act as a point of reference for both academic and industrial researchers.

Inhaltsverzeichnis

Frontmatter

Evolvable Hardware Practice

Frontmatter

Chapter 1. Evolution, Development and Evolvable Hardware

Abstract
Evolution is the change in the inherited characteristics of biological populations over successive generations. Evolutionary processes give rise to diversity at every level of biological organisation, including species, individual organisms and molecules such as DNA and proteins. Biological development involves the mechanisms that control the spatial distribution of different specialised types of cells and which lead to the different types of tissues, organs, organisms and bodily anatomy. We will consider in this book how engineers might use artificial forms of evolution and development in the creation of their artefacts. In this opening chapter we will give some of the basics related to the subject and some definitions related to Evolvable Hardware that will be of use to you for the rest of the book. Before we get to hardware however, it is useful to give a little consideration to biology.
Andy M. Tyrrell, Martin A. Trefzer

Chapter 2. Devices and Architectures for Evolutionary Hardware

Abstract
From the concepts introduced in Chapter 1 it becomes clear that, as the name suggests, evolutionary hardware (EHW) is hardware that offers the capability to change its structure and behaviour in order to automatically optimise its operation for a specific task or environment. Taking inspiration from biological organisms and natural evolution in order to create this kind of hardware system and develop appropriate optimisation methods and algorithms requires not only changes to hardware during manufacture, but frequent and rapid changes. Today’s hardware systems are generally not capable of physically changing, extending or reproducing themselves beyond options that have already been built in at design time, giving rise to the large family of reconfigurable hardware platforms as the most suitable candidates for EHW research and applications.
Martin A. Trefzer, Andy M. Tyrrell

Chapter 3. Representations and Algorithms

Abstract
Since the early days of Evolvable Hardware the field has expanded beyond the use of simple Evolutionary Algorithms on simple electronic devices to encompass many different combinations of Evolutionary and Biologically Inspired Algorithms with various physical devices (or simulations of physical devices). The field of Evolvable Hardware can be split into the two related areas of Evolvable Hardware Design (including optimisation) and Adaptive Hardware (Haddow and Tyrrell, 2011; Yao and Higuchi, 1999).
Evolvable Hardware Design is the use of Evolvable and Biologically Inspired Algorithms for creating physical devices and designs (or their optimisation); examples of fields where Evolvable Hardware Design has had some success include analogue and digital electronics, antennas, MEMS chips and optical systems as well as quantum circuits (Greenwood and Tyrrell, 2006).
Andy M. Tyrrell, Martin A. Trefzer

Chapter 4. Measurement and Fitness Function

Abstract
One of the greatest challenges in Evolvable Hardware—in particular when dealing with intrinsic evolution—is to monitor and assess the performance of an (evolving) circuit or system in order to arrive at a solution that ultimately meets the design specifications. In order to be able to accurately assess performance it is necessary to accurately measure not only input/output characteristics, but also properties such as power consumption, resource consumption and temperature. From these measurements desired performance characteristics can then be calculated; the formula (or algorithm) that achieves this is called the fitness function. Once more borrowing terminology from biology, the fitness of a design under test represents its performance on one or more previously defined objectives. The fitness value is then used by the evolutionary algorithm to rank a population of candidate solutions (individuals), hence to decide which ones shall survive and produce offspring, and which ones shall be discarded. Note that although this chapter is mostly about electronic systems, many of the problems addressed are generic to all evolved physical systems and just the way certain properties manifest themselves changes. For example, in electronic circuits “device variability” occurs as a result of the manufacturing process and the equivalent in biological organisms would be “cell diversity”, which occurs due to how growth takes place.
Martin A. Trefzer, Andy M. Tyrrell

Evolvable Hardware Applications

Frontmatter

Chapter 5. Overcoming Variability Through Transistor Reconfiguration: Evolvable Hardware on the PAnDA Architecture

Abstract
The speed and function density of field-programmable gate arrays (FPGAs) are increasing as transistor sizes shrink to the nano-scale. As transistors reduce in size and approach the atomic scale, the presence or absence of single doping atoms and structural irregularities are likely to affect the behaviour of the device in a random manner (Papanikolaou et al, 2006). Despite advances in the manufacturing process, the fundamentally granular nature of matter can not be overcome and the impact will increase as the technology continues to shrink further (Asenov, 2007; Nassif et al, 2007; Takeuchi et al, 2007). As intrinsic variability becomes more of a problem, every physical instance of a design will behave differently, which will result in a decrease in fabrication yield.
James A. Walker

Chapter 6. Functional Equivalence Checking for Evolution of Complex Digital Circuits

Abstract
Inspired by a seminal paper (Higuchi et al, 1993), many researchers have started to work on evolutionary design and optimisation of combinational digital circuits. In this method, electronic circuits encoded as strings of symbols are constructed and optimised by the EA in order to obtain a circuit implementation satisfying the specification. In order to evaluate a candidate circuit, a reconfigurable circuit (or its simulator if evolution is performed using a circuit simulator) is reconfigured using a new configuration created on the basis of the chromosome (i.e. configuration string) content. The configured device is then evaluated and its behaviour is compared with the desired behaviour. The fitness score is calculated, which reflects to what extent the candidate circuit satisfies the specification. The main reason why evolutionary circuit design has been studied and developed is its ability to (i) provide novel designs hardly reachable by means of conventional methods; (ii) deliver good solutions for problems where the specification is inherently incomplete and no golden solution exists; and (iii) achieve adaptation/fault tolerance directly at the hardware level. Recent overviews of applications and design methods can be found, for example, in (Sekanina et al, 2011; Haddow and Tyrrell, 2011; Sekanina, 2012).
Lukáš Sekanina, Zdeněk Vašíček

Chapter 7. Fault Tolerant Applications

Abstract
Reducing the failure probability and increasing reliability has been a goal of electronic systems designers ever since the first components were developed (von Neumann, 1956). No matter how much care is taken designing and building an electronic system, sooner or later an individual component or device will fail. For systems operating in remote environments, such as satellite applications, the effect of a single failure could result in a multi-million pound installation being rendered useless. With safety-critical systems such as aircraft, the effects could be even more severe. Reliability needs to be built into these and many other applications. The development of fault tolerance techniques is driven by the need for ultra-high availability, reduced maintenance costs, and long lifespan to ensure systems can continue to function in the presence of faults (Avizienis, 1976).
Andy M. Tyrrell

Chapter 8. Principles and Applications of Polymorphic Circuits

Abstract
A polymorphic gate is an unconventional reconfigurable component which is capable of performing several logic functions. Electronic circuits containing such polymorphic gates can be reconfigured in a non-traditional way, for example by means of the power supply voltage. This possibility opens the door to a new class of applications exploiting the inexpensive reconfiguration mechanisms that are provided by polymorphic gates. The aim of this chapter is to survey the field of polymorphic electronics: available polymorphic components, design methods for polymorphic circuits and potential applications.
Lukáš Sekanina

Chapter 9. A Developmental Image Compression Technique Using Gene Regulatory Networks

Abstract
One of the most fascinating properties of biological development is the fact that large, complex organisms are created using the relatively small amount of information that is encoded in the deoxyribonucleic acid (DNA) of a single cell. Once development is initiated, a complex process of gene activity and regulation takes place that triggers a series of cell actions which, over time, create complex, multicellular organisms (Wolpert et al, 2002). During the organism’s lifetime, the developmental process constantly adapts to changing environments and maintains it in the case of damage. Hence, the crucial factor that allows developmental processes to unfold their power is time. From an engineering and computer science point of view, this means that information is encoded in the time steps of the dynamic system represented by the developmental process. In this respect, the DNA represents compressed information, which is expanded during the developmental process and expressed through the various states of the organism.
Martin A. Trefzer

Chapter 10. Medical Applications of Evolvable Hardware

Abstract
Medicine is an important and challenging area for machine learning and computational intelligence approaches. Evolutionary algorithms, in particular, offer a number of advantages when solving problems in this domain. For instance, unlike decision trees and neural-network-based approaches, they are not tied to particular solution representations. This flexibility is important for problems where the aim is to model specific biological or pathological processes, and it also provides scope for using interpretable models, in which evolved solutions can be mined for information. Another important advantage is the ability of evolutionary algorithms to explore a relatively large space of solutions, without requiring a priori knowledge of the structure of a problem. This means that evolutionary algorithms can often be used as a discovery tool, providing new fundamental knowledge to clinicians. For these reasons and others, over the last decade there has been growing interest in the use of evolutionary algorithms in medicine (Smith and Cagnoni, 2011).
Michael A. Lones, Stephen L. Smith

Chapter 11. Metamorphic Systems: A Schema for Adaptive Autonomous Systems

Abstract
Unmanned vehicles (UVs) are taking on increasing roles in military and space missions. These UVs operate in radically different domains, yet they have several common features: (1) they must survive in harsh domains for extended time periods, (2) they must adapt their behaviour to accommodate changing circumstances and (3) they must operate autonomously, which means they must perform assigned tasks with little or no human intervention. For instance, since August 2012 NASA’s scientific laboratory rover Curiosity has been exploring the Martian surface searching for signs of life (NASA, 2012). Martian surface temperatures average –63°C. As another example, the U.S. Navy is currently developing the Anti-submarine Continuous Trail Unmanned Vessel (ACTUV) to track quiet diesel-electric submarines. The goal is to have a UV that can autonomously interact with an intelligent adversary over ranges spanning thousands of kilometers while enduring harsh ocean environmental conditions for months at a time (DARPA, 2012).
Garrison W. Greenwood, Andy M. Tyrrell

Chapter 12. Hierarchical Networks-on-Chip Architecture for Neuromorphic Hardware

Abstract
The mammalian brain has become one of the most interesting and active research topics, not only for neuroscientists, but also for computer scientists and engineers. However, whilst neuroscientists are interested in biophysical models (Trappenberg, 2009), computer scientists and engineers are more interested in the brain’s powerful signal-processing capability (Paugam-Moisy and Bohte, 2012), which is able to perform extraordinary computational feats such as highly parallel, low-powered, fault tolerant computing in comparison to traditional computer paradigms, i.e. generalpurpose computers, which have a centralised sequential hardware architecture based on the von Neumann computing approach (Patterson et al, 2006).
Snaider Carrillo, Jim Harkin, Liam McDaid

Chapter 13. Evolvable Robot Hardware

Abstract
The theory and practice of evolutionary robotics is well established (Nolfi and Floreano, 2000). However, the overwhelming majority of work in evolutionary robotics has, to date, been concerned with evolving a robot’s control system. The robot’s control system is normally expressed entirely in software: it may be a program, or weights in an artificial neural network (ANN). Then the instantiation of a robot from its genome typically requires only that the control program coded by the genome is uploaded into the fixed robot hardware, ready for fitness evaluation. This is not to belittle the difficult challenges of evolutionary robotics, but to point out that conventional practice has, with a very small number of notable exceptions, avoided the altogether greater challenge of evolving a robot’s physical body.
Alan F. T. Winfield, Jon Timmis

Chapter 14. Developmental Evolvable Hardware

Abstract
Even though human-made designs may be complex and advanced they are not at all as complex as the designs around us created by nature. Inspiration from nature can lead us towards new and unconventional methods or design ideas (Bentley, 1999). Nature has created a vast diversity of creatures and plants with sophisticated behaviour. Properties such as complexity, adaption to the environment, selfreproduction, self-repair and collective behaviour are obvious in nature but very hard to put into human-made designs.
Pauline C. Haddow

Backmatter

Weitere Informationen

Premium Partner