Hardware Evolution (HE, also known as Evolvable Hardware, Evolutionary Electronics, E-Hard) refers to the automation of electronic circuit design through artificial evolution, and is currently enjoying increasing interest both as a research domain and as an engineering methodology. Already the field has shown its applicability to some real-world problems in engineering [13], and has potential applications in areas currently difficult for conventional methodologies, such as design under difficult constraints of size/power consumption/component type, and even fault tolerance [16]. As a research domain, electronic circuitry is an excellent medium in which to examine new evolutionary algorithms and theories (eg.[3]). The semi-conducting silicon used to make transistors abounds in diverse physical properties whose interactions can give rise to a vast repertoire of behaviours from a small quantity of components. Indeed, evolution is capable of exploiting these interactions and their dynamics more effectively than human designers, who are constrained by top-down ‘divide and conquer’ techniques which limit the amount of continuous-time dynamics present in a circuit to the subset of those which are understandable and analysable [17]. Analysis of some evolved circuits is revealing a new perspective on how certain tasks may be achieved by exploiting parasitic effects such as stray capacitance rather than trying to minimise them, as the conventional approach does [18].

Artificial evolution is applied to circuit design as follows: One or more candidate circuit designs is described by an array of bits in computer memory - its genotype - which may specify component types, values, and interconnections. Each individual genotype is evaluated according to how the circuit it represents achieves some behavioural specification, or ‘fitness’ measure. Less fit individuals are rejected whilst fitter ones enter a variation phase, using a variety of genetic operators depending on the particular evolutionary algorithm employed. Commencing with randomly generated designs, results of previous evolutionary runs, or an initial hand designed attempt, the circle of evaluation-variation continues until fitness scores equating to the solution of the task are obtained.

Translating a candidate genotype into a circuit for fitness evaluation can be achieved entirely in software by using a proprietary circuit simulation package such as SMASH or PSpice. Alternatively, the circuit can be instantiated in physical hardware using some re-configurable device, such as a Field Programmable Gate Array (FPGA). Fitness evaluations in simulation and in physical hardware have come to be termed respectively extrinsic and intrinsic modes of hardware evolution. The literature is rife with comments on the relative merits of both, but much of these are largely speculation since no comparative study has yet been carried out. Certainly, at the present time, the researcher desirous of carrying out intrinsic hardware evolution is constrained by availability and product support for the FPGA he or she is using. The recent withdrawal from the market of two FPGAs used extensively in the field, the Xilinx 6200 digital series, and the Motorola MPAA020 Field Programmable Analogue Array (FPAA) has highlighted this problem. The Xilinx chip in particular is the active element in several evolvable machines (eg.[7],[15]), whose development required considerable investment and whose future is now uncertain. After a brief discussion on the suitability of FPGAs for HE (Section 2), this paper suggests ways in which the dependence of HE research on FPGAs can be reduced. In particular, the question of intrinsic versus extrinsic evolution is revisited; some recent alternative approaches reported in the literature are surveyed (Section 3); and a general configurable evolutionary testbed constructed from readily available components is presented (Section 4). Results from evolutionary runs for three different tasks show how the tesbed can be used to address issues current in HE research, as well as how some objective comparison of intrinsic and extrinsic hardware evolution can be made using a ‘virtual’ version (Section 5).

FPGAs are the preferred device for many groups because they can be re-configured virtually instantaneously to produce a physical circuit, which can be evaluated in real time. Figure 1 is a simplified diagram showing the architecture of the Xilinx XC6216 FPGA. The magnified view at the bottom of the diagram is of the basic configurable element or cell. Each cell can be connected to any of its adjacent neighbours with further hierarchical interconnections possible. This particular device uses 64 x 64 cells totalling 4096. Despite this large number of configurable elements and interconnections, FPGAs are far from ideal for hardware evolution for a number of reasons. Firstly, there is very little choice over the type of element employed in commercial devices - the XC6200 series uses simple boolean functions, while other FPGAs employ higher level configurable logic blocks (CLBs) such as adders and multipliers [12]. This is particularly restrictive if analogue applications are sought. With the demise of the Motorola device there is at present only one analogue FPGA commercially available - the Zetex TRAC020 chip - which uses configurable operational amplifiers as basic elements, and for which evolved circuits have been reported [1], [11]. However, we do not yet know exactly what the most appropriate basic element for hardware evolution might be. Depending on the task it could be extremely basic, such as a transistor; some higher level functional unit; or combinations of different components including passive resistors or capacitors. Secondly, the interconnection highways between circuit elements in FPGAs are designed with the conventional, modular circuit design methodology in mind. Evolution may be able to exploit a different interconnection architecture more effectively, but once again not enough is known at this stage to specify exactly what that system might be.

Figure 1. Internal architecture of the Xilinx XC6216 FPGA [17]

Finally, circuits which have evolved on an FPGA to produce some desired behaviour - especially where synchronous constraints were not imposed - may be extremely difficult to analyse, since it is not possible to access individual circuit elements with test equipment, and computer simulations cannot practically reproduce all of the physical properties of silicon that may be being exploited [18]. For further details of what can and cannot be achieved by intrinsic artificial evolution using FPGAs, the reader is referred to [9],[13].

Before proposing hardware alternatives to FPGAs, It is worth examining the relative merits of extrinsic HE. The consensus of the literature is as follows [1],[5],[9],[19]:

At face value, there seem to be important advantages to the intrinsic approach, especially if detailed understanding of the circuit’s operation is not important. However, the points mentioned do not necessarily reflect the whole truth. I now re-address them:

1. Extrinsic HE is slower than Intrinsic HE…

In some cases, the reverse may be true. Firstly, consider evolving a 0.1Hz square wave oscillator from discrete components. Evaluating candidate circuits for this task would require taking measurements over at least one cycle of oscillation, a period of 10 seconds. In simulation this might only take 1 second of real time. Secondly, when evolving from scratch, a significant number of candidate solutions must be evaluated before the first stable prototype solution for a task - one that gives better fitness scores than say constant output - appears. For extrinsic HE, this prototype need only give fractionally better scores, but for intrinsic HE the scores must also exceed those produced by noisy circuits if it is to survive further rounds of modification/evaluation. Of course, intrinsic evaluations may be made more thorough to counter the effect of noise, but these may last longer than simulated evaluations. Section 6 includes one real case where noise-free extrinsic HE is consistently faster than intrinsic HE.

2. Circuits evolved extrinsically may not work in reality...

This is effectively true for intrinsic HE too. The only ‘real’ example of the circuit is the test platform on which it has evolved. The constraints required to ensure that a circuit evolved intrinsically will work if instantiated in different hardware are identical to those required to ensure that extrinsically evolved circuits will work in reality (for example, constraining the circuit to be synchronous; not allowing exploitation of parameters whose value cannot be precisely specified).

While simulations cannot precisely emulate every physical property pertaining to a circuit, they are capable of reproducing continuous-time dynamics which evolution can exploit where conventional design struggles [17].

4. Extrinsically evolved circuits are easier to analyse…

It is undoubtedly easier to take voltage and current measurements for simulated circuits than for example FPGAs, where the majority of the circuit nodes may not be accessible to measuring equipment. However it is important to note that this does not guarantee complete understanding of the circuit’s operation since evolved circuits may not have a clear functional decomposition [18].

5. Extrinsic evolution affords the researcher more freedom…

There is certainly more choice in the types of component available in commercial simulation packages than in current FPGAs. However, the extent to which the models are accurate reflections of the real component varies. Discrete components such as transistors, inductors, capacitors and so on, are well understood and comprehensively modelled, but models of more complex devices such as operational amplifiers reflect only the more standard configurations of their physical counterparts.

In light of this re-assessment of the generally accepted pros and cons of extrinsic versus intrinsic hardware evolution, some of the apparent advantages of the intrinsic approach vanish. For many experiments and applications, extrinsic hardware evolution may offer a realistic alternative - indeed may be the preferred choice - to intrinsic evolution with FPGAs.

In order to carry out intrinsic HE without using commercial FPGA devices, some evolvable platform is necessary. Examples of such machines reported in the literature range from relatively simple machines built entirely from discrete or Small Scale Integration (SSI) components to custom-designed Very Large Scale Integration (VLSI) devices with on-chip evolutionary algorithm processors.

One of the first examples of intrinsic evolution was reported by Thompson, who used a simple evolvable platform built from off-the-shelf components (an 8-bit RAM chip, a configurable clock, and a few flip-flops) to control a wall-avoiding robot [17]. This architecture was based on a finite state machine, but allowed genetic control to determine whether or not feedback loops from the robot’s sonars and motors were synchronized with a global clock (whose frequency was also under genetic control). The machine, which Thompson called a Dynamic State Machine (DSM) was instrumental in showing how evolution can produce asynchronous digital designs, and also exhibited some degree of fault tolerance. It is surprising therefore, that since this experiment, no-one has applied the DSM for other evolutionary tasks.

Several groups are working on evolvable machines implemented in VLSI. Examples include Hamilton’s Palmo device, a mixed-signal VLSI which can process analogue signals specified as pulse streams [2]; Moreno et al’s FIPSOC device, which comprises a programmable analogue section, a programmable digital section, and a microcontroller on a single chip [10]; ETL’s Gate-Level EHW chip, which includes a Genetic Algorithm (GA) unit on-chip, has already produced practical applications including image compression and synthesis of control circuits for myoelectric artificial hands[6]. While not originally intended for hardware evolution, JPL’s NN-64 analogue neural network chips have been successfully used by Stoica to intrinsically evolve a Gaussian function to a linear input and a visuo-motor tracking behaviour for a mobile robot [14].

Producing custom VLSIs requires considerable investment, and it is to be hoped that some of the above devices will eventually be made available to other groups. However there is still much to learn about hardware evolution from both a design viewpoint - what is the most suitable EA for a particular task; what is the most appropriate architecture and so on - and an implementation viewpoint - what can we learn from the types of circuit produced by artificial evolution; how do they differ from conventional ones; what engineering advantages does this offer. Exploration of these issues need not require large-scale configurable hardware, and havs been investigated intrinsically using simpler discrete platforms such as Hayworth’s context switchable analogue computer, consisting of boards of discrete op-amp chips [4], or my Evolvable Motherboard [8], a discrete general evolutionary platform, to which the remainder of this paper is devoted.

The Evolvable Motherboard (EM), first reported in [9], is a general evolvable platform designed originally to aid research of intrinsic hardware evolution. Recently, a virtual version has been completed allowing a direct comparison between extrinsic/intrinsic approaches to be conducted. The primary objectives of the EM were to provide the researcher with a much larger range of basic configurable elements than are available in FPGAs; to allow virtually any combination of interconnection between these elements; and to allow access to individual elements by test equipment for analysis. Figure 2 is a simplified diagram. It is essentially a diagonal matrix of analogue switches, connected to up to 6 plug-in daughterboards, which contain the desired basic elements for evolution. The diagram shows transistors and operational amplifiers, but the daughterboards could contain any type of electronic component from resistors to microprocessors.

Figure 2. A simplified representation of the Evolvable Motherboard

Each daughterboard takes up to eight lines on the switch matrix, plus a further eight connections to allow for various power lines and I/O, which may be required by components such as operational amplifiers or digital potentiometers. The matrix is designed to provide the minimum number of switches necessary so that every combination of interconnection between basic elements can be configured. In total there are approximately 1500 switches, giving a search space of 10⁴²⁰ possible circuits. Most of these circuits will be useless, since with this configuration of switches, there are many combinations that result in every wire effectively connected to every other wire. However the software interface together with the switch arrangement allows different interconnection architectures (for example the local and global hierarchy system used commonly by FPGAs) to be investigated. Also, via software, the board can be subdivided (for example into 2 matrices each containing three plug-in boards) to allow for mapping individuals genotypes to two sets of components thereby allowing the impact of manufacturing tolerance to be assessed. The motherboard incorporates additional connectors so that several can be daisy-chained together, should the need arise. Programming is achieved via an interface card plugged into a host PC’s ISA bus. The switches can therefore be configured by direct writes to PC’s internal I/O ports, meaning that genotypes can be instantiated in hardware in a very short time (<1ms).

The analogue switches making up the matrix are Harris CD22M3494 programmable crosspoint switch arrays. These devices were chosen because they have separate ground connections for the analogue elements and for the digital programming interface; very high resistance when ‘off’, and low resistance when ‘on’. They are available off-the-shelf, and each switch can withstand relatively high current. Note however that they are not totally transparent. Evolution has been shown in the past to exploit any physical property available in the medium [8],[17]. In this case, it is likely to be the ‘on’ resistance of around 50 ohms for each switch.

It is important to note that the evolvable motherboard is not designed to produce large scale ‘showcase’ applications. It is a research tool for investigating different evolvable architectures, algorithms, and the circuits they produce on a small scale.

This section presents evolutionary runs using the Evolvable Motherboard for three different tasks – a NOT gate, an amplifier, and an oscillator. The particular tasks were chosen as test cases for ongoing research into fault tolerance and population dynamics. Since this type of research requires many runs the test cases must be simple enough to evolve repeatedly within a limited time scale, but fundamentally different from each other, and non-trivial. These tasks were made non-trivial by imposing the (potentially useful) constraint of denying evolution the use of components that would normally be considered essential were they to be designed conventionally, in this case resistors and capacitors. Only 10 bipolar transistors were made available as basic elements. A rank based, generational genetic algorithm with elitism was used for all the runs, with population size 50. Genetic operators were mutation and single-point crossover, with mutation probability set at 0.01 per bit.

The genotype is mapped to the motherboard switches so as to limit the quantity of switches on per row, so that the pins of active components are not too highly inter-connected. This is consistent with many conventional circuits where each component pin is usually only connected to two or three other pins. In the encoding, each column is assigned a corresponding row. The genotype represents the switches a row at a time. For each row, one bit specifies connection to the corresponding column, followed by column address and connection bits for up to n additional switches. For all runs, n was set to 3, and 48 rows/columns were used giving a genotype length of 1056.

Figure 3(a) shows a typical example of an evolved NOT Gate. The boxes in the diagram represent ‘closed’ analogue switches. The circuit was evaluated by using a series of 10 test inputs containing 5 ‘1s’ and 5 ‘0s’ (logical Highs and Lows, respectively) applied sequentially to the input in alternating order. For each test input, the output voltage was measured twice and summed. Fitness f was scored according to equation 1:

where t signifies the test input number, S_L and S_H the set of Low and High test inputs respectively, and v_t (t = 1,2,..10) the summed output voltage corresponding to test number t.

A simple evolved amplifier is shown in figure 3(b). The amplifier was evaluated by applying a 1kHz sine wave of 2mV peak to peak amplitude with a d.c. offset of half the supply voltage. Both input and output were monitored using an A/D converter, and 500 samples of each taken at 10us intervals. Fitness f was the average error between the input and amplified output:

(2)

where a is the desired amplification factor, Vin_i and Vout_i are the ith input and output voltage measurements respectively, and Oin and Oout are the d.c. offsets of input and output respectively. Amplification a was set to –500. Figure 3 (bottom) shows the circuit diagram for an evolved oscillator. The circuit was evaluated as follows: A set of 1000 voltage measurements were made for each candidate circuit at intervals of 3.33 microseconds (a sample frequency of 300,000 kHz). Fitness f was scored according to equation (3), where V_i is the voltage at the ith interval.

This equation sums separately the difference between adjacent measurements where the difference, and therefore the gradient at that point, is negative and positive respectively.

(3)

The fitness is then the normalized minimum of these two sums. Taking two separate sums prevents monotonic transients from giving high fitness scores. The maximum value of equation 3 will be realized for an oscillator whose peak to peak amplitude is equal to the supply voltage (+2.8V for all tasks), and whose frequency is 150kHz plus a positive multiple of the sample frequency, that is 150kHz, 450kHz, 750kHz and so on. The circuit of figure 3 oscillates at just under 400kHz, with a peak to peak amplitude of 1.0V.

At least 10 evolutionary runs were conducted for each of the above tasks. In most cases, the amplifier and oscillator circuits were dependent on the particular transistors with which they evolved. If one or more of the transistors was substituted with a nominally identical one, fitness was generally lower when the circuit’s performance was re-assessed and in some cases, the circuit ceased to work altogether. This reliance on parameters whose value cannot be precisely specified at manufacture is well known in HE and is no surprise in this case. If evolution was continued after the substitution, in nearly all cases relatively few generations (compared with the quantity taken to evolve from scratch) were required to return to the circuit’s original fitness scores.

The transistors used for the evolutionary tasks (BC109 and BC179) are included in the libraries of most circuit simulation packages. By substituting the analogue switches with resistors of 50 ohms, the same tasks can be evolved extrinsically using a ‘virtual motherboard’. Having remarked on the lack of direct comparisons between intrinsic and extrinsic evolution earlier in this paper, I now discuss the results of evolving the same tasks extrinsically, with identical fitness functions and GA parameters to those evolved intrinsically. Note that the direct comparison of these three tasks cannot be considered a thorough investigation of the relative merits of both approaches – it is merely intended to be a step in the right direction. The amplifier and NOT Gates were both successfully evolved extrinsically to the same levels of fitness as their intrinsically evolved counterparts. An oscillator was also evolved extrinsically, but its amplitude was infinitesimal (around 20 femtoVolts, peak to peak).

For 10 runs of NOT Gate evolution, fitness values reached 90% of the maximum possible value in most cases in around 1000 generations for intrinsic evolution and 150 generations for extrinsic evolution. The time required to evaluate the candidate circuits was limited mainly by the speed of the digital I/O card used to supply the test input, and by the processor speed for the intrinsic and extrinsic methods respectively. Extrinsic evolution was carried out using a 266MHz Pentium P.C., resulting in NOT gate evolution taking an average of around 3 hours extrinsically, compared to 6 hours intrinsically. The real time advantage is not necessarily significant here, since the two approaches had different factors limiting the speed, either of which could make a profound difference if adjusted. However, that extrinsic evolution took an order of magnitude fewer generations to achieve good fitness scores is certainly significant.

Figure 4 shows typical fitness plots of the best individual for both methods. In both cases, initial fitness is zero, given by constant output circuits. However, such circuits in reality are noisy and have produced fitness scores of above 50 on many occasions. During this random search stage, circuits which genuinely performed better than constant output did not remain in future generations until the performance was significantly above the noise level. This was not a problem for the extrinsic approach, which found a circuit giving fitness of 0.2 at generation 0. Since there was no noise, evolution was able to develop this circuit despite it being only marginally better than constant output. The same effect was also observed for the amplifier circuits, although for reasons which are not clear at present, intrinsic evolution took fewer generations on average than extrinsic evolution to produce circuits approaching maximum possible fitness, once a stable prototype had been found.

The final experiment deals with the issue of whether extrinsic evolution is less reliable than intrinsic evolution at producing circuits that work in reality. Recall from section 3.1 that intrinsically evolved circuits may only work well for the components with which they were evolved. This was observed with the amplifier and oscillator circuits in this section, and that if evolution was allowed to continue after different but nominally identical components were substituted, in most cases relatively few generations were required to re-acquire good fitness. Hence, rather than instantiating extrinsically evolved circuits into physical hardware and evaluating them once, a better comparison with intrinsically evolved circuits for operation in reality is re-evolve intrinsically starting with the final (extrinsic) population upon instantiation in hardware. This test was carried out for 5 extrinsically evolved amplifiers. Results were very similar to those obtained by re-evolving the intrinsic amplifiers in 4 cases. Figure 5 is a typical plot showing the best individual’s fitness over the course of evolution. At generation 6000, intrinsic evaluation commenced. Less than 200 generations were necessary to reach 90% of the best performance prior to re-evolving.

Fitness of the best individual for intrinsically (upper) and extrinsically (lower) evolved NOT gates.

Figure 5.

Using the 6000^th generation of extrinsically evolved amplifiers as a seed for further intrinsic evolution.