Improved Directed Acyclic Graph Evaluation and the Combine Operator in Genetic Programming
Herman H. Ehrenburg · The MIT Press eBooks · 1996
The use of a directed acyclic graph (DAG) to represent a population in genetic programming offers several advantages, only one of which is the efficient use of space. We improve on existing methods to evaluate a DAG and offer two new ways of evaluating a population. The first method uses a linked list and a negligible amount of space. In the second method, each node is evaluated only once on all fitness cases and the results are cached. We also introduce two genetic operators in connection to the use of a DAG. The first is a simpler alternative to crossover. The second is a contextpreserving genetic operator based on the building block hypothesis, which accurately combines two similar trees. 1 Introduction Natural evolution can be viewed as a process that preserves genetic information. In order to preserve information, DNA is constantly copied resulting in many identical pieces of genetic information. Methods like genetic programming Koza (1992) imitate the process of evolution by mu...