Time and Individual Duration in Genetic Programming

Abstract

This paper presents a new way of measuring complexity in variable-size-chromosome-based evolutionary algorithms. Dealing with complexity is particularly useful when considering bloat in Genetic Programming. Instead of analyzing size growth, we focus on the time required for individuals' fitness evaluations, which correlates with size. This way, we consider time and space as two sides of a single coin when devising a more natural method for fighting bloat. We thus view the problem from a perspective that departs from traditional methods applied in Genetic Programming. We have analyzed first the behavior of individuals across generations, taking into account their fitness evaluation times, thus providing clues about the general practice of the evolutionary process when modern parallel and distributed computers are used to run the algorithm. This new perspective allows us to understand that new methods for bloat control can be derived. Moreover, we develop from this framework a first proposal to show the usefulness of the idea: to group individuals in classes according to computing time required for evaluation, automatically accomplished by parallel and distributed systems without any change in the underlying algorithm, when they are only allowed to breed within their classes. Experimental data confirms the strength of the approach: using computing time as a measure of individuals' complexity allows control of the natural size growth of genetic programming individuals while preserving the quality of solutions in both the parallel and sequential versions of the algorithm.

Keywords

• Bloat
• computing time
• genetic programming