Bottom-up tree evaluation in tree-based genetic programming

In tree-based genetic programming (GP) performance optimization, the primary optimization target is the process of fitness evaluation. This is because fitness evaluation takes most of execution time in GP. Standard fitness evaluation uses the top-down tree evaluation algorithm. Top-down tree evaluation evaluates program tree from the root to the leaf of the tree. The algorithm reflects the nature of computer program execution and hence it is the most widely used tree evaluation algorithm. In this paper, we identify a scenario in tree evaluation where top-down evaluation is costly and less effective. We then propose a new tree evaluation algorithm called bottom-up tree evaluation explicitly addressing the problem identified. Both theoretical analysis and practical experiments are performed to compare the performance of bottom-up tree evaluation and top-down tree evaluation. It is found that bottom-up tree evaluation algorithm outperforms standard top-down tree evaluation when the program tree depth is small. © 2010 Springer-Verlag.