Experiment

The circuit to be evolved has one input and one output. As the input is stimulated with a square wave of either 1kHz or 10kHz, the output is to give a steady high voltage for one input frequency, and a steady low for the other. This frequency discrimination task was used in the earlier experiments, and was chosen to be as simple as possible while raising the issues of interest. In particular, some sort of stable dynamics is needed within the circuit. The tone discrimination task can also lead the way to more sophisticated cases of pattern recognition over time, such as word recognition [11]. We seek to explore new means to generate robust behaviour, which does not necessarily imply that the behaviour could not be achieved in some other way using conventional methods.

The circuit was evolved to be a configuration of the now-obsolete Xilinx XC6216 field-programmable gate array (FPGA). Each candidate design (evolutionary variant) was tested by configuring four XC6216 chips having the conditions shown in Table 1. Evaluations at the target task were then performed on all four chips simultaneously and independently. The evolutionary fitness of the candidate was taken to be the worst of the four measurements. This multi-FPGA, multi-condition apparatus, called `The Evolvatron', was fully described in [12].

Table 1: Conditions of the chips used for fitness evaluation. `Temperature' is that of the surface of the chip package. See [14] for the thermal properties of each package. Power supply units (PSUs) were either switched-mode (s.m.) or linear regulated (lin.). `Position' gives the (row, column) location of the north-west corner of the 10x10 circuit within the 64x64 array, with (63,0) being the extreme north-west corner of the array.

Chip	Fabrication	Package	Interface	Temperature	PSU	Output load	Position
1	Seiko	PQFP	parallel	in PC	PC's 5V s.m.	-	(37,30)
2	Yamaha	PLCC	serial	ambient	5V lin.	$1$k$\Omega$	(32,0)
3	Yamaha	PGA	serial	$60^{\circ}$C	4.75V s.m.	-	(63,0)
4	Seiko	PGA	serial	$-27^{\circ}$C	5.25V s.m.	-	(37,54)

Only the configuration of a 10x10 region of the 64x64 array of cells on the FPGA was subject to evolution. For each chip of Table 1, the 10x10 region was translated in position by a different but constant amount, as shown. Only nearest-neighbour interconnections between cells were enabled. With reference to the datasheet [15], this leaves 10 multiplexers (`muxes') to be configured in each of the 100 cells: four 4:1 neighbour muxes, three 4:1 `X' muxes to select the inputs to the cell's function unit; and within the function unit, two 4:1 muxes (Y1 and Y2), and the single 2:1 CS mux selecting either a combinatorial or a sequential output. The RP (register protect) mux, which can be set to prevent the cell function unit's flip-flop from ever changing, was always set to OFF.

In contrast to the earlier experiments, a clock signal was supplied to all of the FPGAs, and was the clock input to the rising-edge triggered D-type flip-flop inside every cell's function unit. The clock source was a single external crystal oscillator, nominally 6MHz. Under evolutionary control, via the Y1, Y2 and CS muxes, each cell's function unit could be synchronous to the clock (function output taken from the flip-flop), asynchronous to the clock (flip-flop output not selected), or mixed (function output is a combinatorial function of the possibly-asynchronous inputs as well as of the flip-flop's output). Hence, there is no constraint that evolution must produce a synchronous digital design: the clock is a stable dynamical resource to be used or ignored as selection deems fit, rather than being an enforced synchronisation signal [10]. No design rules were imposed.

The evolutionary algorithm was a (1+1) Evolution Strategy (ES) [7,8]. A mutation operator was defined to select one of the 100 cells at random, then one of that cell's 10 muxes at random, and then to randomly reconfigure that mux to select a different input. In the ES, each new variant was produced by applying the mutation operator three times to the parent.

With a new variant configured to the FPGAs, the inputs were stimulated with a sequence of 100ms bursts of 1kHz and 10kHz tones. The tones were shuffled into a random order for each trial, such that there were an equal number of each frequency. The single source of the tones was a 1.000000MHz crystal oscillator module, followed by hardware dividing the frequency by either 100 or 1000.

Separate analogue circuits integrated the output of each chip over each 100ms tone, giving a value proportional to the average output voltage during that time. Let the integrator reading of FPGA chip$c$ at the end of test tone number $t$ be $i^{c}_{t}$ (t=1,2,...T). Let $S_{1}$ be the set of 1kHz test tones, and$S_{10}$ the set of 10kHz test tones. Then the evaluation of the performance of the configuration on chip $c$ was calculated as:

 

$$E^{c} = \frac{1}{2T}\left\vert \sum_{t \in S_{1}}i^{c}_{t} - \sum_{t\in S_{10}}i^{c}_{t} \right\vert - P^{c}$$ (1)

and the fitness $F$ was $\mbox{MIN}^{4}_{c=1}(E^{c})$. The term$P^{c}$ was used towards the end of the run to penalise solutions having spikes or glitches in their output. For each FPGA, a separate resetable counter made from 74LS devices counted the number of low$\Rightarrow$high logic transitions on that FPGA's output during each test tone. If the number of low$\Rightarrow$high transitions during tone t was $N^{c}(t)$, then a counter would return the value $R^{c}(t) = \mbox{MIN}( \;N^{c}(t), \; 255 \;)$. Then $P^{c}$ was defined as

 

$$P^{c} = w \times \frac{1}{2T} \sum_{t=1}^{T} \mbox{MAX}( \;R^{c}(t)-1, \; 0 \; )$$ (2)

where $w$ is a weighting factor, initially zero.

The ES algorithm proceeded as follows, where $L$ is an integer initially 1 but later increased to lengthen the trials:

$\bullet$ Download the initial parent configuration to the FPGAs.
$\bullet$ Measure $F_{parent}$ over $50 \times L$ tones.
REPEAT

$\bullet$ Generate three mutations (the variation operator) and partially reconfigure each FPGA with all three.

$\bullet$$\dagger$Measure $F_{offspring}$ over a total of $24 \times L$test tones, aborting after $8 \times L$or $16 \times L$ tones if $F_{offspring} < F_{parent}$. Before the final group of $8 \times L$ testtones (if reached), all FPGAs are hardware-reset and completely reconfigured from scratch with the new variant.

$\bullet$ IF ($F_{offspring} \geq F_{parent}$)

The offspring becomes the new parent.
All three mutations are left in place.

ELSE

The parent is left unchanged: partially reconfigure the FPGAs to undo the three mutations.

END IF

$\bullet$ IF (15 offspring have been generated without any replacing the parent)

Hardware reset the FPGAs & reconfig. from scratch with the parent.
Extend the parent's evaluation by a further $10 \times L$test tones.
Wait a further 15 offspring before doing this again.

END IF

END REPEAT

 

The initial parent was found through random search for a starting point giving better than trivial performance. Partial reconfiguration is used above because some of the FPGAs are reconfigured via a relatively slow serial interface. The simple variable-length evaluation scheme copes with measurement noise and the stochastic behaviours of some candidate configurations. Termination was by a human observer. The algorithm relies on the existence of pathways of change that make no immediate difference to the fitness, but that alter the opportunities for later improvement. See [4] for a discussion of such `neutral networks' in the context of evolutionary electronics design. One reason for choosing such a simple algorithm was to simplify the study of the role of neutrality, to be reported elsewhere.

The initial parent configuration ($F$=0.43 with $w$=0) was found after testing 75679 randomly generated individuals, using only the fitness measuring step marked $\dagger$ above (with $L$=1), and with a hardware reset and complete reconfiguration of the FPGAs between individuals. In the main phase of evolution ($L$=1, $w$=0), 25000 triple-mutations were accepted out of 861348 attempted (although most evaluations would be aborted early) resulting in a circuit with fitness $F$=6.17. Then $w$ was increased to 1.4/255 and a further 10 triple-mutations were accepted out of 265 trials. Then with $L$=2, $w$=1.0, a further 870 out of 32338 triple-mutations were accepted. Finally, with$L$=5, $w$=5.0, a further 3000 out of 131005 mutants were accepted. Each of these latter phases resulted in a reduction in the number of unwanted spikes in the output, eventually eliminating them entirely.

2000-02-03