The task was to evolve a circuit -- a configuration of the 
corner of the FPGA -- to discriminate between square waves of 1kHz and 10kHz
presented at the input. Ideally, the output should go to +5V as soon as
one of the frequencies is present, and 0V for the other one. The task was
intended as a first step into the domains of pattern recognition and signal
processing, rather than being an application in itself. One could
imagine, however, such a circuit being used to demodulate frequency-modulated
binary data received over a telephone line.
It might be thought that this task is trivially easy. So it would be, if the
circuit had access to a clock or external resources such as RC time-constants
by which the period of the input could be timed or filtered. It had not.
Evolution was required to produce a configuration of the array of 100 logic
cells to discriminate between input periods five orders of magnitude
longer than the input 
output propagation time of each cell
(which is just a few nanoseconds). No clock, and no off-chip components could
be used: a continuous-time recurrent arrangement of the 100 cells had to be
found which could perform the task entirely on-chip. Many people thought this
would not be possible.
The evolutionary algorithm was basically a conventional generational Genetic Algorithm (GA) [3]. The population of size 50 was initialised by generating fifty random strings of 1800 bits each. After evaluation of each individual on the real FPGA, the next generation was formed by first copying over the single fittest individual unchanged (elitism); the remaining 49 members were derived from parents chosen through linear rank-based selection, in which the fittest individual of the current generation had an expectation of twice as many offspring as the median-ranked individual. The probability of single-point crossover was 0.7, and the per-bit mutation probability was set such that the expected number of mutations per genotype was 2.7. This mutation rate was arrived at in accordance with the Species Adaptation Genetic Algorithm (SAGA) theory of Harvey [4], along with a little experimentation.
The GA was run on a normal desktop PC interfaced to some simple in-house
electronics
as shown in Fig. 2.
Figure 2: The experimental arrangement.
To evaluate the fitness of
an individual, the hardware-reset signal of the FPGA was first momentarily
asserted to make certain that any internal conditions arising from previous
evaluations were removed. Then the 1800 bits of the genotype were used to
configure the corner of the FPGA as described in the previous
section, and the FPGA was enabled. At this stage, there now exists on the chip
a genetically specified circuit behaving in real-time according to
semiconductor physics.
The fitness of this physically instantiated circuit was then automatically
evaluated as follows. The tone generator drove the circuit's input with five
500ms bursts of the 1kHz square-wave, and five of the 10kHz wave. These ten
test tones were shuffled into a random order, which was changed every time.
There was no gap between the test tones. The analogue integrator was reset to
zero at the beginning of each test tone, and then it integrated the voltage of
the circuit's output pin over the 500ms duration of the tone. Let the
integrator reading at the end of test tone number t be denoted 
(t=1,2,...10). Let 
be the set of five 1kHz test tones, and 
the set of five 10kHz test tones. Then the individual's fitness was calculated
as:
This fitness function demands the maximising of the difference between the
average output voltage when a 1kHz input is present and the average output
voltage when the 10kHz input is present. The calibration constants 
and
were empirically determined, such that circuits simply connecting
their output directly to the input would receive zero fitness.
Otherwise, with 
, small frequency-sensitive effects in
the integration of the square-waves were found to make these useless circuits
an inescapable local optimum.
It is important that the evaluation method -- here embodied in the analogue integrator and the fitness function Eqn. 1 -- facilitates an evolutionary pathway of very small incremental improvements. Earlier experiments, where the evaluation method only paid attention to whether the output voltage was above or below the logic threshold, met with failure. It should be recognised that to evolve non-trivial behaviours, the development of an appropriate evaluation technique can also be a non-trivial task.
