next up previous
Next: The Relationship Between Intrinsic Up: Unconstrained Evolution and Hard Previous: The Use of Simulation

SAGA and Fault Tolerance

 

When considering the mutation rate for SAGA (Section 6), we saw that there is an `error catastrophe' mutation rate above which the species disintegrates and loses its local fitness peak. For practical SAGA mutation rates, the population will never completely converge upon the single locally-most-fit sequence, but will converge around it, in an equilibrium of being driven away by mutation and pulled back by selection. Most of the individuals will not have the locally-most-fit genotype, but will be a small number of mutations away in genotype space. This has the effect that selection is not able to hold the population at an isolated `needle in the haystack' peak as well as it can hold it on a `smoother' hillside, where fitness falls away gradually with increasing Hamming distance from the peak. In fact, Thompson [14] adapts one of Eigen & Schuster's experiments [15] to SAGA, illustrating that an initially completely converged population can abandon an isolated peak in favour of a less fit smoother one.

The result is that, under certain conditions, the evolving species tends to move to a high fitness region of the landscape at which mutations have only a gradual effect on fitness on average (if such a region exists). In particular, most single mutations will tend not to decrease fitness dramatically, although a few critical ones might. What does this have to do with fault tolerance? Take an example: say that part of the genotype directly encodes the connectivity between some components of the phenotype circuit, with a 1 indicating a connection and a 0 no connection. The preceding argument predicts that single mutations will tend to have only small effects on fitness, implying that the performance of the circuit will tend not to be drastically degraded by the creation or removal of connections. Therefore the evolved circuits will tend to be tolerant to hardware faults that cause connections to be broken or spuriously created.

This general phenomenon applies whenever the genetic encoding is such that a genetic mutation has the same effect on the phenotype as would a certain type of fault; there will be a tendency for the evolved systems to be less sensitive to that type of fault than equivalent systems produced by non-evolutionary means. Current research aims to characterise the effect using the NK model of fitness landscapes [16] over the full range of possible SAGA parameters and selection schemes: for some settings, evolved individuals have been seen to be 10% less sensitive to single mutations than equivalent individuals found through exhaustive search, on average. Thompson [14] deals with the evolution of fault tolerance in greater detail than here, also suggesting that the use of a co-evolving antagonistic population of emulated faults could force tolerance to a large set of faults in cases where the above technique is inapplicable or insufficient.


next up previous
Next: The Relationship Between Intrinsic Up: Unconstrained Evolution and Hard Previous: The Use of Simulation

Adrian Thompson
Tue Feb 25 21:48:02 GMT 1997