If an evolutionary algorithm is implemented in hardware, one expects a substantial speed up. However, for problems where the computation of the fitness function is a large part of the execution, this may not be the case. This paper describes a method to reduce the amount of fitness computation that an evolutionary algorithm does. The idea is to approximate the fitness of an offspring based on the fitness of its parents. If this method is to work, however, it is necessary to track the reliability of this approximation. The authors offer two methods for doing this: one maintains an estimate of the accuracy, and forces a proper computation when this accuracy falls below a predetermined threshold; the other works by explicitly recomputing the fitness for some random proportion of the population. The basic algorithms can be further enhanced by using the presence of true and estimated fitnesses to derive an error compensation to modify the estimated fitnesses.
The paper presents the results of a number of experiments with various algorithms, showing that these fast evolutionary algorithms can improve performance for hardware implementations. In particular, for image compression applications, the fitness estimating algorithm is capable of finding five to 43 percent better compression ratios using 44 to 72 percent of the number of evaluations required by the unmodified algorithm.
The paper is clearly written, and sufficiently self-contained. It can be read by anyone with an understanding of the basic structure of evolutionary algorithms.