The Experiment

The task was to evolve a circuit -- a configuration of a $10\times 10$ corner of the XC6216 FPGA -- to discriminate between square waves of 1kHz and 10kHz presented at the input [55]. Ideally, the output should go to +5V as soon as one of the frequencies is present, and to 0V for the other. The task was intended as a first step into the domains of pattern recognition and signal processing, as well as being part of the scientific programme. One could imagine such a circuit being used to demodulate frequency-modulated binary data received over a telephone line.

This task was not facile, because few components were provided and the circuit has no access to a clock, or other off-chip resources such as RC time constants, by which the period of the input could be timed or filtered. Evolution was required to produce a configuration of the 100 cells to discriminate between input periods five orders of magnitude longer than the input $\Rightarrow$ output propagation time of each cell (which is just a few nanoseconds). A continuous-time recurrent arrangement of the 100 cells had to be found that could perform the task entirely on-chip.

Although the results of §III suggested a benefit in providing a clock of evolvable frequency as an optional resource rather than as an imposed constraint, no clock was made available. This was primarily to assess the possibility of evolution of very unusual circuits. There is also an engineering justification: the components needed for an external time reference would be bulky compared to the 1% of the FPGA's silicon area used by the final evolved circuit. The fully integrated solution is preferable in terms of size, mechanical robustness, and the cost of components and manufacturing.

To configure a single cell, there were 18 multiplexer control bits to be set, and these bits were directly encoded onto a linear bit-string genotype. The genotype of length 1800 bits was formed from left to right by taking the cells in the $10\times 10$ corner in a raster fashion, from west to east along each row, and taking the rows from south to north. A basic GA was again used, with a population size of 50, a crossover probability of 0.7, and a per-bit mutation probability such that the expected number of mutations per genotype was 2.7. The mutation rate was derived empirically.

Figure 13: The apparatus for the tone discriminator experiment. The $10\times 10$ corner of cells used is shown to scale with respect to the whole FPGA. The single input to the circuit was applied as the east-going input to a particular cell on the west edge, as shown. The single output was designated to be the north-going output of a particular cell on the north edge.

Figure 14: The circuitry to evolve the tone discriminator. This ISA card plugs directly into the PC, and no extra electronics is needed. Left: The FPGA (beneath a fan-cooled heatsink) and its interface chips. Centre: A micro-controller supervising fitness evaluations. Right: The analogue integrator.

The GA was run on a normal desktop PC interfaced to some simple in-house electronicsas shown in Figs. 13 and 14. 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 $10\times 10$ corner of the FPGA, and the FPGA was enabled. At this stage a genetically specified circuit existed on the chip, behaving in real-time according to semiconductor physics.

The fitness of a physically instantiated circuit was evaluated automatically as follows. A 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. An 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 $i_{t}$ (t=1,2,...10). Let $S_{1}$ be the set of five 1kHz test tones, and $S_{10}$ the set of five 10kHz test tones. Then the individual's fitness was calculated as:

$$\mbox{fitness} = \frac{1}{5}\left\vert \left( k_{1}\sum_{t \... ...ht) - \left( k_{2}\sum_{t \in S_{10}}i_{t} \right) \right\vert$$ (2)

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 $k_{1}$ and $k_{2}$ were determined empirically, such that circuits simply connecting their output directly to the input would receive zero fitness. Otherwise, with $k_{1} = k_{2} = 1.0$, small frequency-sensitive effects in the integration of the square-waves were found to make these useless circuits a troublesome local optimum. This fitness specification is an example of direct behavioural requirements.

It is important that the evaluation method -- here embodied in the analogue integrator and the fitness function (Eqn. 2) -- facilitates an evolutionary pathway of very small incremental improvements. Earlier attempts, where the evaluation method only paid attention to whether the output voltage was above or below the logic threshold, met with failure.