On the use of a directed acyclic graph to represent a population of computer programs

Abstract

This paper demonstrates a technique that reduces the time and space requirements of genetic programming. The population of parse trees is stored as a directed acyclic graph (DAG), rather than as a forest of trees. This saves space by not duplicating structurally identical subtrees. Also, the value computed by each subtree for each fitness case is cached, which saves computation both by not recomputing subtrees that appear more than once in a generation and by not recomputing subtrees that are copied from one generation to the next. I have implemented this technique for a number of problems and have seen a 15- to 28-fold reduction in the number of nodes extant per generation and an 11- to 30-fold reduction in the number of nodes evaluated per run (for populations of size 500).