Evolvable Hardware
Computer Architecture and Design Group,IDI, NTNU

                            Abstracts

               Inspired by biological development where from a single cell, a complex organism can evolve, we are interested
               in finding ways in which artificial development may be introduced to genetic algorithms so as to solve our
               genotype challenge. This challeng e may be expressed in terms of shrinking the genotype. We need to move
               away from a one-to-one genotype-phenotype mapping so as to enable evolution to evolve large complex
               electronic circuits. We present a first case study where we have considered th e mathematical formalism
               L-systems and applied their principles to the development of digital circuits. Initial results, based on extrinsic
               evolution, indicate that our representation based on L-systems provides an interesting methodology for further
               investigation. We also present our implementation platform for intrinsic evolution with development, enabling
               on-chip evaluation of grown solutions.

"Untidy Evolution: Evolving Messy Gates for Fault Tolerance"
by Julian F. Miller and Morten Hartmann, 4th International Conference on Evolvable Systems: From Biology to Hardware,  ICES2001, 14-25

               The exploitation of the physical characteristics has already been demonstrated in the intrinsic evolution of
               electronic circuits. This paper is an initial attempt at creating a world in which "physics" can be exploited in
               simulation. As a starting point we investigate a model of gate-like components with added noise. We refer to
               this as a kind of messiness. The principal idea behind these messy gates is that artificial evolution makes a
               virtue of the untidiness. We are ultimately trying to study the question: What kind of components should we
               use in artificial evolution? Several experiments are described that show that the messy circuits have a natural
               robustness to noise, as well as an implicit fault-tolerance. In addition, it was relatively easy for evolution to
               generate novel cir-cuits that were surprisingly efficient.

"From Here to There: Future Robust EHW Technologies for Large Digital Designs"
by Pauline C Haddow and Piet van Remortel, The Third NASA/DoD Workshop on Evolvable Hardware, EH 2001, pp 232-239

               A long term goal of EHW is to evolve large complex de-signs for large devices. Evolving large complex
               designs is beyond our reach due to the resource greedy nature of evo-lutionary techniques. Manufacturers are
               also struggling to develop reliable large devices. In this work we focus on dig-ital circuits and consider their
               demands as well as the de-mands from evolutionary techniques and development tech-niques on the
               underlying technology. In addition, we con-sider the platform reliability problem. We discuss these is-sues in
               the light of today’s EHW technology, FPGAs, and a proposed fault tolerant technology Amorphous
               Computers. We then propose more reliable technologies which meet the demands of evolving large complex
               designs.

"Bridging the Genotype-Phenotype Mapping for Digital FPGAs"
by Pauline C Haddow and Gunnar Tufte, The third NASA/Dod Workshop on Evolvable Hardware, EH'01, pp109-115

               To solve the genome complexity issue and enable evolution of large complex circuits, the need to move away
               from a one-to-one genotype/phenotype mapping is becoming generally accepted. This involves development
               of new forms of representation with feat ures such as growth. Shrinking the size of the genotype in effect
               moves complexity from the genotype representation to the genotype/phenotype mapping. The field of digital
               evolvable hardware is relatively young but already researchers have not on ly had to move through different
               technology platforms i.e. 6200, 4000 and Virtex series, but also evolution friendly features have disappeared.
               A mass produced evolution friendly reconfigurable platform is not likely to be ahead of us and a newer te
               chnology more evolution friendly than traditional reconfigurable platforms is not around the corner. To be able
               to reuse results and lessons learned from today's technology on tomorrow's technology and exploit the power
               of evolution, one solution is to provide a virtual evolution friendly reconfigurable platform which may be
               mapped onto a given technology. We propose a two stage genotype/phenotype mapping using our virtual
               evolvable hardware FPGA as the bridge. The two stages simplify the ge notype/phenotype transition at the
               same time as the virtual evolvable hardware FPGA bridge provides a more evolution friendly platform, further
               reducing the complexity of the genotype representation.

"Evolving messy gates for fault tolerance: some preliminary findings"
by Julian F. Miller and Morten Hartmann, The Third NASA/DoD Workshop on Evolvable Hardware,  EH'01, 116-123

               We investigate a preliminary model of gate-like components with added random noise. We refer to these
               types of components as messy. The principal idea behind messy gates is that evolving circuits using messy
               gates may confer some beneficial properties, one being fault-tolerance. The exploitation of the physical
               characteristics has already been demonstrated in intrinsic evolution of electronic circuits. This provided some
               of the inspiration for the work reported in this paper. Here we are trying to create a simulateable world in
               which "physical characteristics" can be exploited. We are also trying to study the question: What kind of
               components are most useful in an evolutionary design scenario?

"An Evolvable Hardware FPGA for Adaptive Hardware"
by Pauline Haddow and Gunnar Tufte, CEC'00, pp 553-560

Can we realise the opportunities that lie in design by evolution by using traditional technologies or are there better technologies which will allow us to fully realise the potential inherent in evolvable hardware? In this paper we consider the  characteristics of evolvable hardware --- especially for adaptive design, and discuss the demands that these characteristics place on the underlying technology. We suggest a potential alternative to today's FPGA technology. The proposed architecture is particularly focused at reducing the genotype required for a given design by reducing the configuration data required for unused routing resources and allowing partial configuration down to a single CLB. In addition, to support adaptive hardware, self-reconfiguration is enabled.

"Evolving an Adaptive Digital Filter"
by Gunnar Tufte and Pauline Haddow, EH'00, pp 143-150

One important feature of signal processing is coping with noise. In a non-adaptive filter, characteristics of the filter may be refined to remove noise. One method of achieving this is to use evolution to decide the filter characteristics. However, if the noise level is sufficient or the input signal is not of the required type for the output signal required, then a satisfactory output signal may not be achievable. To be able to achieve the required output signal for a wide range of input signals and noise, it is desirable to be able to adjust both the characteristics and the type of the filter. In this way the resulting filter may be said to be an adaptive filter. In this
paper we propose an on-chip solution for an adaptive digital filter using an on-chip evolvable hardware method. We
highlight a challenge within evolvable hardware for adaptive designs and that is to find efficient ways in which sufficient genetic
material will be available to the evolution process. This problem appears when the evolution process is automatically restarted so as to adapt to a change in the environment.

[publications page]

"Evolving a Robot Controller in Hardware"
by Pauline Haddow and Gunnar Tufte, NIK'99, pp 141-150

In this paper, the concept of hardware evolution is presented along with a newer approach to hardware evolution termed Complete Hardware Evolution (CHE). An experimental robot controller design --- GERC (Genetically Evolved Robot Controller), is described which uses CHE in the design process. The robot controller steers the robot around a given area trying to move as straight and as far as possible, exhibiting wall avoidance behaviour. By using CHE the whole evolution process is implemented on the same chip as the evolved circuit --- the robot steering circuitry. No external interaction is thus required to evaluate the robots behaviour during the evolution process.

"Prototyping a GA Pipeline for Complete Hardware Evolution"
by Gunnar Tufte and Pauline Haddow,  EH'99, pp 143-150

In this paper a new approach to evolvable hardware is introduced termed 'Complete Hardware Evolution' (CHE). This method differs from Extrinsic and Intrinsic evolution in that the evolution process itself is implemented in hardware. In addition, the evolution process implementation, referred to herein as the GA Pipeline, is implemented on the same chip as the evolving design. A prototype implementation of the GA Pipeline is presented which uses FPGA technology as the implementation medium.

[publications page]

[EHWmainpage]