Throughout the experiment, an oscilloscope was directly attached to the output pin of the FPGA (see Fig. 2), so that the behaviour of the evolving circuits could be visually inspected. Fig. 3 shows photographs of the oscilloscope screen,
Figure 3: 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.
illustrating the improving behaviour of the best individual in the population at various times over the course of evolution.
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.
After 220 generations, the best circuit was basically copying the input to the output. However, on what would have been the high part of the square wave, a high frequency component was also present, visible as a blurred thickening of the line in the photograph. This high-frequency component exceeds the maximum rate at which the FPGA can make logic transitions, so the output makes small oscillations about a voltage slightly below the normal logic-high output voltage for the high part of the square wave. After another 100 generations, the behaviour was much the same, with the addition of occasional glitches to 0V when the output would otherwise have been high.
Once 650 generations had elapsed, definite progress had been made. For the 1kHz input, the output stayed high (with a small component of the input wave still present) only occasionally pulsing to a low voltage. For the 10kHz input, the input was still basically being copied to the output. By generation 1100, this behaviour had been refined, so that the output stayed almost perfectly at +5V only when the 1kHz input was present.
By generation 1400, the neat behaviour for the 1kHz input had been abandoned, but now the output was mostly high for the 1kHz input, and mostly low for the 10kHz input...with very strange looking waveforms. This behaviour was then gradually improved. Notice the waveforms at generation 2550 -- they would seem utterly absurd to a digital designer. Even though this is a digital FPGA, and we are evolving a recurrent network of logic gates, the gates are not being used to `do' logic. Logic gates are in fact high-gain arrangements of a few transistors, so that the transistors are usually saturated -- corresponding to logic 0 and 1. Evolution does not `know' that this was the intention of the designers of the FPGA, so just uses whatever behaviour these high-gain groups of transistors happen to exhibit when connected in arbitrary ways (many of which a digital designer must avoid in order to make digital logic a valid model of the system's behaviour). This is not a digital system, but a continuous-time, continuous valued dynamical system made from a recurrent arrangement of high-gain groups of transistors -- hence the unusual waveforms.
By generation 2800, the only defect in the behaviour was rapid glitching present on the output for the 10kHz input. Here, the output polarity has changed over: it is now low for the 1kHz input and high for 10kHz. This change would have no impact on fitness because of the absolute value signs in the fitness function (Eqn. 1); in general it is a good idea to allow evolution to solve the problem in as many ways as possible -- the more solutions there are, the easier they are to find.
In the final photograph at generation 3500, we see the perfect desired behaviour. In fact, there were infrequent unwanted spikes in the output (not visible in the photo); these were finally eliminated at 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 (which I will arbitrarily take 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.
Graphs of maximum and mean fitness, and of genetic convergence, are given in Fig. 4. These graphs suggest that some interesting population dynamics took place, especially at around generation 2660. The experiment is analysed in depth from an evolution-theoretic perspective in a companion paper [5], so I will not dwell on it here. Crucial to any attempt to understand the evolutionary process which took place is the observation that the population had formed a genetically converged `species' before fitness began to increase: this is contrary to conventional GA thinking, but at the heart of Harvey's Species Adaptation Genetic Algorithm (SAGA) [4] conceptual framework.
Figure 4: (a) Maximum and mean fitnesses of the population at each
generation.
(b) Genetic convergence, measured as the mean Hamming distance between the
genotypes of pairs of individuals, averaged over all possible pairs.
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 genetic operators, and to configure the FPGA were all negligible in comparison. It is not known whether the experiment would have succeeded if the individuals had been evaluated for shorter periods of time -- fitness evaluations should be just accurate enough that the small incremental improvements in performance that facilitate evolution are not swamped by noise. An exciting aspect of hardware evolution is that very high-speed tasks can be tackled, for instance in the pattern recognition or signal processing domains, where fitness evaluation -- and hence evolution -- can be very rapid. The recognition of audio tones, as in this experiment, is a long duration task in comparison to many of these, because it is reasonable to expect that the individuals will need to be evaluated for many periods of the (slow) input waveforms, especially in the early stages of evolution. The author was engaged in a different project while the experiment was running, so it consumed no human time.