Inherent Qualities of Circuits Designed by Artificial Evolution:
A Preliminary Study of Populational Fault Tolerance
Paul Layzell
Centre for Computational Neuroscience and Robotics
COGS, University of Sussex, Brighton BN1 9QH, UK
paulla@sussex.ac.uk
Abstract
An investigation of the likelihood of evolved circuit populations to contain an individual robust to a fault which renders the previously best individual useless.
Introduction
In principle, the abstraction and analysis techniques of conventional electronic circuit design can produce circuits which conform perfectly to a given set of behavioural specifications the first time they are implemented in hardware or simulation. By comparison, circuit design by artificial evolution, which requires the implementation of every candidate design for evaluation, can be deemed an incremental process. Even where in practice, conventional design incorporates a phase of trial-and-error, any modifications are made with an expectation, based on knowledge or analysis, of their effect on the circuit’s behaviour. Hence, the modifications applied are constrained to the subset of those that can be analysed or understood. By contrast, modifications by evolutionary operators are not made with any a priori expectations of their consequences. Evolution does not need to analyse its modifications – it only needs to observe the consequent circuit behaviour, and unless constrained to do otherwise, is free to exploit architectures and components in unusual ways.
The fundamentally different nature of these two design processes is reflected in the kinds of circuit they produce. Both exhibit qualities which are inherent, that is, not explicitly required by the design specifications. For example, conventional circuits generally have a clear functional decomposition, whereas evolved ones may not [3]. These qualities may be undesirable if for example, evolution exploits parasitic properties which make it difficult to reproduce a circuit on different hardware.
This paper outlines ongoing research that attempts to isolate qualities inherent in circuits designed by artificial evolution. In particular I focus on one quality of great potential value, if its existence can be affirmed. Hereafter referred to as ‘Populational Fault Tolerance’ (PFT), it is the potential for a population of evolved circuits to contain an individual which adequately performs a task in the presence of a fault that renders the previously best individual useless. If the fault is persistent, the new ‘best’ individual may be used to seed further evolution, possibly attaining performance equal to that before the fault occurred, in a fraction of the time it took to evolve the circuit from scratch. This work is motivated by observations of such effects in previously evolved circuits and in other fields, for example [1]. Two questions are posed: (1) Can PFT be expected in all evolved circuits of some generic class? (2) If so, is this truly an inherent quality of circuits designed by artificial evolution?
A framework for studying PFT
The following study comprises two elements. The first, an empirical study consisting of many evolutionary runs of several different tasks. On completing the runs, hardware faults are effected, and data pertaining to the subsequent performance of individuals in the final population taken. The second, an analysis of the evolved circuits to determine the relative importance of their constituent components, thus providing an indication of the severity of a given fault. The tasks presently used in the study are digital inverters, simple amplifiers, and oscillators. They were evolved intrinsically on an Evolvable Motherboard [2], a configurable platform on which plug-in components can be interconnected using programmable analogue switches. Only bipolar transistors (and the analogue switches in a static state) were provided as constituent components, five each of PNP and NPN. There were no constraints placed on how these components could be exploited or configured. The tasks were evolved using a rank-based genetic algorithm (GA) with elitism, and a population size of 50. Operational parameters and mapping were identical for each of the tasks, full details of which can be found in [2]. The oscillators were evaluated using hardware to measure frequency and amplitude, to prevent aliasing errors. It was thus possible to attain the target frequency of around 25kHz to within 1%.
Multiple runs were conducted until each task had been successfully evolved ten times. At the end of each run, the population had reached a high degree of genetic convergence. Faults were effected by removing transistors used by the elite individual, one at a time. The removal of a transistor is equivalent to a fault common with blown bipolar transistors - both pn junctions becoming open-circuit. The transistors were then classified by analysing their role in the evolved circuits. Transistors wired such that their collector-emitter current was clearly modulated by base voltage are hereafter termed active, the rest passive. While faults in both types may be equally severe in terms of their effect on the performance of a single individual, a faulty active transistor is expected to affect most individuals in the population since many generations may be required to set up its operating conditions.
The extent to which reduced performance of a circuit in the presence of a fault can be considered adequate is dependent on the task. Here, the minimum adequate performance is defined as corresponding to a fitness score significantly above that obtained by a trivial circuit giving constant output. Such a circuit would be an appropriate seed for further evolution, even if it were no longer suitable for the intended task in its existing state.
Initial results are encouraging. When removed, 15 from a total of 30 passive transistors (inverter), and 14 from 19 (amplifier), resulted in useless performance from the elite individual. However, adequate performance was achieved by another member of the population in all 15 cases for the inverter, and in over half the cases for the amplifier. Even where the elite individual did perform adequately, another member of the population performed significantly better in nearly every case. The removal of active transistors was far more damaging. While the elite individual was rendered useless in every case, four of the inverter runs, and just one of the amplifier runs contained individuals which gave adequate performance. The study has not yet been completed for the oscillator circuits.
From these results, there are indications (and nothing more) that PFT occurs for particular kinds of fault, at least for the GA used and the tasks studied. We can now pose the following question: Is this due in some way to evolution’s incremental design process; or the fact that a converged population still contained diverse solutions; or merely that the passive transistors were not really ‘used’, but just acted as wires, and bypassing them by mutation made little difference to performance? Comparisons of the elite individuals’ schematics with those that performed better in the presence of a fault suggest that the last option is rarely the case. One approach to determine whether the effect is due to the nature of the design process could be to instantiate on an evolvable platform a number of conventionally designed circuits, make a population of mutants, and perform the same study. However, this approach is fraught with danger. Apart from the difficulty of hand-designing enough different circuits using only transistors and motherboard switches to provide statistical data, care would have to be taken for example, to extend the redundancy which evolution was afforded to the conventionally designed equivalents (the evolved circuits used on average only about four of the ten transistors available). Therefore, in place of conventional circuits, the above procedure was applied to circuits designed by a hill-climbing algorithm, using identical mutation rates and mapping to those used for the GA. The use of a hill-climber (essentially an elitist GA with a population of two, and no crossover) helps determine the contribution to PFT of population diversity and crossover, even if it does not provide comparative data pertaining to conventionally designed circuits.
As for the GA, ten successful runs of each task were completed. Results were surprisingly similar to those obtained with the GA for both the inverter and amplifier. All mutated populations contained individuals that performed adequately no matter which passive transistor was removed, although there were fewer cases which resulted in the elite individual (the unmutated hill-climber) performing inadequately. The implication is that the key to any PFT observed here is neither crossover, nor any more diversity than one set of mutants of a single individual.
Discussion and future work
While the results presented in this preliminary study are not in themselves sufficiently conclusive to answer the two questions posed in the introduction, they do provide justification for further research into the phenomenon of PFT. Future work includes completing the study for oscillators and additional tasks, conducting a significantly greater quantity of runs for each task, automating the creation of faults, reducing the redundancy available to evolution, and tackling the direct comparison with conventionally designed circuits.
Acknowledgements
This work was funded by British Telecommunications.
Reference