Results

Throughout the experiment, an oscilloscope was directly attached to the output pin of the FPGA (see Fig. 13), so that the behaviour of the evolving circuits could be visually inspected. Fig. 15 shows photographs of the oscilloscope screen, illustrating the improving behaviour of the best individual in the population at various times over the course of evolution.

Figure 15: Photographs of the oscilloscope screen. Top: The 1kHz and 10kHz input waveforms. Below: The corresponding output of the best individual in the population after the number of generations marked down the side. For these photographs an analogue oscilloscope of 20MHz bandwidth was used.

The individual in the initial random population of 50 that happened to get the highest score produced a constant +5V output at all times, irrespective of the input. It received a fitness of slightly above zero just because of noise. Thus, there was no individual in the initial population that demonstrated any ability whatsoever to perform the task.

For the first few hundred generations, the `best' circuits simply copied the input to the output, combined with various high-frequency oscillatory components. By generation 650, definite progress had been made. For the 1kHz input, the output appeared to stay mostly high; for the 10kHz input, the output resembled the input.

The photographs (Fig. 15) show the behaviour gradually being refined, finally reaching the perfect desired behaviour. In fact, not visible in the final photographs were infrequent unwanted spikes in the output; these were finally eliminated around generation 4100. The GA was run for a further 1000 generations without any observable change in the behaviour of the best individual. The final circuit (arbitrarily taken to be the best individual of generation 5000) appears to be perfect when observed by eye on the oscilloscope. If the input is changed from 1kHz to 10kHz (or vice-versa), then the output changes cleanly between a steady +5V and a steady 0V without any perceptible delay.

It is apparent from the oscilloscope photographs that evolution explored beyond the scope of conventional design. For instance, the waveforms at generation 1400 would seem absurd to an electronics designer of either digital or analogue schools. Not so evident in these photographs is the rich range of dynamical timescales actually present. The components of the nominally digital FPGA were not used according to a binary logic abstraction, because a wider repertoire of behaviours was available in the absence of design constraints.

Graphs of maximum and mean fitness, and of genetic convergence, are given in Fig. 16.

Figure 16: Population statistics. Top: Maximum and mean fitnesses of the population at each generation. Below: Genetic convergence, measured as the mean Hamming distance between the genotypes of pairs of individuals, averaged over all possible pairs.

These graphs suggest interesting population dynamics, especially at around generation 2660. The experiment is analysed in depth from an evolution-theoretic perspective in [58]. Crucial to any attempt to understand the evolutionary process that took place is the observation that the population had formed a genetically converged `species' before fitness began to increase: this is contrary to some conventional GA thinking [43,44]. Evolution was the process of continual adaptation of this relatively converged species, with mutation playing a key role in generating new variants. Neutral networks -- pathways of mutational change having no effect on fitness -- are thought to have been important in allowing continued exploration without becoming stuck at poor local optima [58].

The entire experiment took 2-3 weeks. This time was dominated by the five seconds taken to evaluate each individual, with a small contribution from the process of calculating and saving data to aid later analysis. The times taken for the application of selection, the variation operators, and to configure the FPGA were all negligible in comparison. Current work suggests that the fitness tests could have used much shorter bursts of input tones. If evolution is to be free to exploit all of the components' physical properties, fitness evaluations must take place at the real timescales of the task to be performed, and cannot simply be accelerated, as they could for a discrete-time system by increasing the clock speed. The evolution of circuits in detailed physical simulations is increasingly attractive as computer-power increases, but would be infeasible for circuits of this complexity in the near future. See §V-C for the use of simulations.

The final circuit is shown in Fig. 17; observe the many continuous-time feedback paths. The lack of visible patterns in the circuit structure is not surprising: no preconceived bias towards modular or repeated substructures was applied, nor is it apparent that such patterning would be appropriate for such a small circuit and for this task.

Figure 17: The final evolved circuit. The $10\times 10$ array of cells is shown, along with all connections that eventually connect an output to an input. Connections driven by a cell's function output are represented by arrows originating from the cell boundary. Connections into a cell which are selected as inputs to its function unit have a small square drawn on them. The actual setting of each function unit is not indicated in this diagram.

Parts of the circuit that could not possibly affect the output can be pruned away. This was done by tracing all possible paths through the circuit that eventually connect to the output. A `path' not only includes routing, but also passing from an input to the output of a cell's function unit. It was assumed that all of a function unit's inputs could affect the function unit output, even when the nominal logic function indicated that this should not be so. This assumption was made because it was not known exactly how function units that were connected in continuous-time feedback loops actually would behave. In Fig. 18, cells and wires are only drawn if there is a connected path by which they could possibly affect the output, which leaves only about half of them.

Figure 18: The pruned circuit diagram: cells and wires are only drawn if there is a connected path through which they could possibly affect the output.

The pruned diagram shows components that could be functional, but does not guarantee that they all are. To find which parts were actually contributing to the behaviour, a search was conducted to find the largest set of cells that could have their function unit outputs simultaneously clamped to constant values ( 0 or 1) without affecting the behaviour. To clamp a cell, the configuration was altered so that the function output of that cell was sourced by the flip-flop inside its function unit (a feature of the chip not mentioned until now, and which was not used during evolution): the contents of these flip-flops can be written by the PC and can be protected against any further changes. A program was written to select a cell at random, clamp it to a random value, perform a fitness evaluation, and to return the cell to its unclamped configuration if performance was degraded, otherwise to leave the clamp in place. This procedure was iterated, gradually building up a maximal set of cells that can be clamped without altering fitness. The order of clamping attempts, and the clamping values chosen, could affect the result; hence the whole exercise was repeated until a clear consensus emerged as to what the largest clamping set was.

In the above automatic search procedure, the fitness evaluations were more rigorous (longer) than those carried out during evolution, so that very small deteriorations in fitness would be detected (made difficult by the noise present during all evaluations). Clamping some of the cells in the extreme north-west corner produced so tiny a fitness decrement that even the extended evaluations did not detect it, yet by the time all of these cells of small influence had been clamped, the combined effect on fitness was quite noticeable. In these cases manual intervention was used (informed by several runs of the automatic method), with evaluations happening by watching the oscilloscope screen for several minutes to check for any infrequent spikes that might have been caused by the newly introduced clamp.

Figure 19: The functional part of the circuit. Cells not drawn here can be clamped to constant values without affecting the circuit's behaviour.

Fig. 19 shows the functional part of the circuit that remains when the largest possible set of cells has been clamped without affecting the behaviour. The cells shaded gray cannot be clamped without degrading performance, even though there is no connected path by which they could influence the output -- they were not present on the pruned diagram of Fig. 18. Clamping one of the gray cells in the north-west corner has only a small impact on behaviour, introducing either unwanted pulses into the output, or a small time delay before the output changes state when the input frequency is changed. However, clamping the function unit of the most south-eastern gray cell, which also has two active connections routed through it, degrades operation severely -- even though that function output is not used as an input to any other cells. The gray cells must be influencing the rest of the circuit by some means other than the normal inter-cell routing; this enigma will be revisited in the analysis to follow.

This circuit is discriminating between inputs of period 1ms and 0.1ms using only 32 cells, each with a propagation delay of less than 5ns, and with no off-chip components whatsoever: a surprising feat. Evolution has been free to explore the full repertoire of behaviours available from the silicon resources provided, even being able to exploit the subtle interactions between adjacent components that are not connected directly. The input/output behaviour of the circuit is digital, because that is what maximising the fitness function required, but the complex analogue waveforms seen at the output during the intermediate stages of evolution betray the rich continuous-time continuous-value dynamics that are likely to be present internally.

Only a core of 32 out of the 100 cells is involved in generating the behaviour, even though there was no explicit encouragement of small solutions. This may be chance, or it may be a natural way to solve the problem. It may be that the mutation rate was sufficiently high that any larger functional circuit could not be maintained by selection (the error threshold [59]). Finally, the implicit search biases mentioned in Section §I-A might have been at play.

Figure 20: The frequency and thermal response of the final circuit. F1 and F2 are the two frequencies that the circuit was evolved to discriminate. For ease of implementation, their exact periods were actually 0.096ms (10.416kHz) and 0.960ms (1.042kHz) respectively.

The circuit's behaviour is not brittle. Fig. 20 shows the average output voltage (measured using the analogue integrator over a period of 5 seconds) for input frequencies from 31.25kHz to 0.625kHz. For input frequencies $\geq$ 4.5kHz the output stays at a steady +5V, and for frequencies $\leq$ 1.6kHz at a steady 0V. Thus, the test frequencies (marked F1 and F2 in the figure) are correctly discriminated with a considerable margin for error. As the frequency is reduced from 4.5kHz, the output begins to rapidly pulse low for a small fraction of the time; as the frequency is reduced further the output spends more time at 0V and less time at +5V, until finally resting at a steady 0V as the frequency reaches 1.6kHz. Beyond this range, the output stays at steady 0V for inputs down to 0Hz (dc), and at steady +5V for inputs up to several MHz. These properties might be called `generalisation and extrapolation,' but are fortuitous: no steps were taken to encourage them. It may be that this is a natural response for a dynamical system of this class, but not enough data is yet available to be sure.

Fig. 20 also shows the circuit's behaviour at temperatures outside the range experienced during the evolutionary experiment. The high temperature was achieved by placing a 60W light bulb near the chip, the low temperature by opening all of the laboratory windows on a cool breezy evening. Varying the temperature moves the frequency response curve to the left or right, so once the margin for error is exhausted the circuit no longer behaves perfectly to discriminate between F1 and F2.

In the examples given here, at $43.0^{\circ}$C the output is not steady at +5V for F1, but is pulsing to 0V for a small fraction of the time. Conversely, at $23.5^{\circ}$C the output is not a steady 0V for F2, but is pulsing to +5V for a small fraction of the time. However, the circuit operates perfectly over the $\pm5^{\circ}$C range of temperatures to which the population was exposed during evolution, despite its only available time reference being the the natural dynamical behaviours of the components, which are temperature dependent.