Fast Grammar-Based Evolution Using Memoization

Martin Luerssen, David Powers

    Research output: Contribution to conferencePaper

    Abstract

    A streamlined, open-source implementation of Shared Grammar Evolution represents candidate solutions as grammars that can share production rules. It offers competitive search performance, while requiring little user-tuning of parameters. Uniquely, the system natively supports the memoization of return values computed during evaluation, which are stored with each rule and also shared between solutions. Significant improvements in evaluation time, up to 3.9-fold in one case, were observed when solving a set of classic GP problems - and even greater improvements can be expected for computation-intensive tasks. Additionally, the rule-based caching of intermediate representations, specifically of the terminal stack, was explored. It was shown to produce significant, although lesser speedups that were partly negated by computational overhead, but may be useful in dynamic and memory-bound tasks otherwise not amenable to memoization.

    Original languageEnglish
    Pages502-511
    Number of pages10
    DOIs
    Publication statusPublished - 12 Nov 2010
    Event11th International Conference on Parallel Problem Solving From Nature -
    Duration: 11 Sep 2010 → …

    Conference

    Conference11th International Conference on Parallel Problem Solving From Nature
    Period11/09/10 → …

    Keywords

    • Evolutionary algorithms
    • genetic programming
    • grammatical evolution
    • memoization
    • shared grammar evolution

    Fingerprint Dive into the research topics of 'Fast Grammar-Based Evolution Using Memoization'. Together they form a unique fingerprint.

  • Cite this

    Luerssen, M., & Powers, D. (2010). Fast Grammar-Based Evolution Using Memoization. 502-511. Paper presented at 11th International Conference on Parallel Problem Solving From Nature, . https://doi.org/10.1007/978-3-642-15871-1_51