Source:
Genetic Programming 1997: Proceedings of the Second Annual Conference, Morgan Kaufmann, Stanford University, CA, USA, p.321--328 (1997)
URL:
http://www.cs.cmu.edu/afs/cs/usr/astro/public/papers/GR.ps
Keywords:
genetic algorithms;
genetic programming
Abstract:
For many problems to which genetic programming has
been applied, choosing the number of fitness cases with
which to evaluate the individuals is a crucial
decision. If too few fitness cases are used,
overfitting may occur, and the measured fitness of an
individual may not be representative of its true
fitness. On the other hand, if too many fitness cases
are used, a great deal of computer time can be wasted.
This paper presents a method for the Rational
Allocation of Trials (RAT) that dynamically allocates a
boundedly optimal number of fitness cases for each
individual. RAT allocates individuals to tournaments
prior to their evaluation, and then, borrowing from
previous work in model selection, allocates trials
(fitness cases) only to those individuals for whom the
cost of evaluating another fitness case is outweighed
by the expected utility that the new information will
provide. For most evolutionary computation approaches,
including genetic programming, and for most problems,
the RAT algorithm will provide significant time savings
at minimal additional system complexity.