Coevolution of Fitness Predictors
 Michael D. Schmidt and Hod Lipson, Member, IEEE
 Fitness prediction is a technique to replace fitness evaluation in evolutionary algorithms with a lightweight approximation that adapts with the solution population.
 Cannot approximate the full landscape, but shift focus during evolution.
 Aka local caching.
 Or adversarial techniques.
 Instead use coevolution, with three populations:
 1) solutions to the original problem, evaluated using only fitness predictors;
 2) fitness predictors of the problem; and
 3) fitness trainers, whose exact fitness is used to train predictors.
 Trainers are selected high variance solutions across the predictors, and predictors are trained on this subset.

 Lightweight fitness predictors evolve faster than the solution population, so they cap the computational effort on that at 5% overall effort.
 These fitness predictors are basically an array of integers which index the full training set  very simple and linear. Maybe boring, but the simplest solution that works ...
 They only sample 8 training examples for even complex 30node solution functions (!!).
 I guess, because the information introduced into the solution set is relatively small per generation, it makes little sense to oversample or overspecify this; all that matters is that, on average, it's directionally correct and unbiased.
 Used deterministic crowding selection as the evolutionary algorithm.
 Similar individuals have to compete in tournaments for space.

 Showed that the coevolution algorithm is capable of inferring even highly complex manyterm functions
 And, it uses function evaluations more efficiently than the 'exact' (each solution evaluated exactly) algorithm.
 Coevolution algorithm seems to induce less 'bloat' in the complexity of the solutions.
 See also {842}
