Integrating a Nonbehavioural Requirement of Fault Tolerance

In Section II-C we described the worth of integrating nonbehavioural requirements into the objectives during evolutionary design. Some nonbehavioural characteristics, such as size or power consumption, are usually easily measurable to become factors in the selection process [14]. Others can be impractical to measure directly, but sometimes the evaluation procedure can be contrived so that they exert an implicit influence on fitness. As an example, we consider introducing a fault tolerance requirement for the DSM robot controller. Evolutionary techniques for fault-tolerant electronics are largely unexplored, but the engineering benefits on offer are significant [48,49,6].

The requirement is for the controller to be tolerant to any adverse single-stuck-at (SSA) fault in the memory array of the RAM chip, causing a bit to read the opposite of the value written to it. These faults are easily emulated by inverting one of the bits specified by evolution as it is written to the chip. Altering the configuration is a generally applicable way to emulate some classes of faults in reconfigurable hardware; if the circuits are being evaluated in software simulations there is even more flexibility.

Ideally, for each fitness evaluation an individual would be given a trial in the presence of every possible fault in turn, and the resulting fitness score would be some measure of performance in the face of any fault. However, there are usually many possible faults, making exhaustive testing prohibitively time consuming (but not always [50]). Even for the DSM robot controller, testing each individual in the presence of the 32 emulated adverse SSA faults would take too long.

If the goal is to optimise worst-case performance (i.e. minimise the effects of the most serious fault), there is a potential shortcut. In this case the fitness measure will be based on performance in the presence of only the single most serious fault. If some way of predicting which fault is the most serious can be found, then only this single fault needs to be introduced during the fitness evaluation. A similar situation arises if only a relatively small subset of the possible faults seriously degrades the system: only this subset need be considered.

However, which faults are the most serious might be different for each individual in the population. If the only way to identify the worst faults for each individual is to test them with each fault in turn, there can be no shortcut. In practice, though, after the first few generations the individuals are mostly similar and the population as a whole changes gradually over time. These facts can be used in predicting which faults are the most serious without having to test every individual with every fault.

We now apply these ideas to the robot controller. First, the wall-avoider was evolved as before, but this time using a population size of 50. After 85 generations the GA had stabilised at a good solution. Then the consensus sequence was generated: the genotype formed by, for each locus, taking whichever of the values {0, 1} was most common in the population at that position. The robot controller coded for by this consensus sequence was then tested in the presence of each of the 32 possible adverse SSA faults in turn. The fault that caused the consensus individual to behave the most poorly (lowest fitness score) was nominated as the `current fault.' Another generation of evolution was then performed, but with the current fault being present during all of the fitness evaluations. After this generation the new consensus individual was constructed, tested, and a possibly new current fault nominated for the next generation. The process continued in this way, with a single fault being present throughout all evaluations within a generation -- this fault being the one that caused the worst performance in the consensus individual of the previous generation.

Fig. 9 shows that the maximum and mean fitnesses dropped sharply at generation 85 when faults were first introduced, but over the course of the next 150 generations returned to high values. Fig. 10 shows that when the faults were first applied the controller was already tolerant to most SSA faults, but that a few were critical. At various stages afterwards, this tolerance to most SSA faults is lost in the GA's attempts to improve performance on the single most serious current fault. Some serious faults are seen to persist over long periods. Eventually, consensus individuals arose that give satisfactory performance when any of the SSA faults is present. Fig. 11 compares the fault tolerance of the conventionally-evolved consensus individual at generation 85 with that of the first completely-tolerant consensus which arises at generation 204. The criterion for `satisfactory performance' was for the real robot to display what would reasonably be called wall-avoiding behaviour, and corresponds to a fitness score of $\geq 1.0$.

Figure 9: Maximum and mean fitness in the population over time. The first 85 generations were in the absence of faults, thereafter all fitness evaluations were in the presence of the `current fault'.

Figure 10: The evolution of fault tolerance: results of the exhaustive test over all possible adverse SSA faults made on the consensus individual of each generation. The darker a spot, the more serious the fault. Pure white represents satisfactory performance (fitness $\geq 1.0$), and pure black the worst possible performance. At the generations marked with arrows, the consensus individual is satisfactory in the presence of any SSA fault.

Figure 11: Fault tolerance of the consensus at generation 85, and then after 119 generations of evolution in the presence of faults. In each case, the faults have been sorted from left to right in order of severity.

This crude approach has exploited the similarity between individuals in the population by predicting that a single fault will be the most serious one for all individuals at a particular generation. This fault was identified by exhaustively testing a single `average' individual -- the consensus. Though this fault-prediction strategy is not exact, it had the desired effect of catalysing the evolution of a completely fault-tolerant individual.

Many other strategies could be used to decide which faults an individual should encounter during its evaluation: the example above is merely a simple illustration. If there were many possible faults, exhaustive testing of even just the single consensus individual per generation could take too long. One suggestion is to co-evolve [51] a population of faults that concentrates on the weak spots of the target population and tracks them over time [49,6]. Another potential method is the use of repeated re-evaluations of the more successful individuals to build up gradually an accurate picture of their performance in the presence of a set of faults [52].

Whatever method is used, it seems that if some way of targeting the most serious weak spots of individuals can be found, then subjecting the individuals to these faults during their fitness evaluations can cause the evolution of systems tolerant to all of the possible faults. It may be possible to use an adaptive process such as co-evolution to target the weak spots, or search using application-specific heuristics may prove more appropriate.