Bottom-up tree evaluation in tree-based genetic programming

Geng Li, Xiao Jun Zeng

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


    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.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.
    PublisherSpringer Nature
    Number of pages9
    ISBN (Print)3642134947, 9783642134944
    Publication statusPublished - 2010
    Event1st International Conference on Advances in Swarm Intelligence, ICSI 2010 - Beijing
    Duration: 1 Jul 2010 → …


    Conference1st International Conference on Advances in Swarm Intelligence, ICSI 2010
    Period1/07/10 → …


    • Bottom-up Evaluation
    • Genetic Programming
    • Top-down Evaluation
    • Tree Evaluation


    Dive into the research topics of 'Bottom-up tree evaluation in tree-based genetic programming'. Together they form a unique fingerprint.

    Cite this