Semantic Backpropagation for Designing Search Operators in Genetic Programming

Tomasz P. Pawlak, Bartosz Wieloch, Krzysztof Krawiec


In genetic programming, a search algorithm is expected to produce a program that achieves the desired final computation state (desired output). To reach that state, an executing program needs to traverse certain intermediate computation states. An evolutionary search process is expected to autonomously discover such states. This can be difficult for nontrivial tasks that require long programs to be solved. The semantic backpropagation algorithm proposed in this paper heuristically inverts the execution of evolving programs to determine the desired intermediate computation states. Two search operators, Random Desired Operator and Approximately Geometric Semantic Crossover, use the intermediate states determined by semantic backpropagation to define subtasks of the original programming task, which are then solved using an exhaustive search. The operators outperform the standard genetic search operators and other semantic-aware operators when compared on a suite of symbolic regression and Boolean benchmarks. This result and additional analysis conducted in this study indicate that semantic backpropagation helps evolution at identifying the desired intermediate computation states, and makes the search process more efficient. 

Access full text

Preprint or Final full text at IEEExplore.


The appendix for this study, containing a description of efficient implementation of library search is here.


author={Pawlak, T.P. and Wieloch, B. and Krawiec, K.},
journal={Evolutionary Computation, IEEE Transactions on},
title={Semantic Backpropagation for Designing Search Operators in Genetic Programming},
keywords={Boolean algebra;backpropagation;genetic algorithms;geometric programming;mathematical operators;regression analysis;search problems;Boolean benchmarks;evolutionary search process;exhaustive search algorithm;genetic programming;geometric semantic crossover;program synthesis;random desired operator;semantic backpropagation algorithm;semantic-aware operators;standard genetic search operators;symbolic regression;Algorithm design and analysis;Backpropagation;Context;Genetic programming;Programming;Semantics;Vectors;Geometric crossover;mutation;problem decomposition;program synthesis;reversible computing;semantics},

Suplementary material

The Java source code of Semantic Backpropagation, Random Desired Operator, Approximately Geometric Semantic Crossover and other operators presented in the paper, together with the compiled Jar are available under conditions of Academic Free License. Java 1.7+ is required to compile the Jar from source. Instructions how to create configuration files and run the experiment are available in ECJ manual. The classes under interest of this study can be found in the following namespaces:

  •* (problem definitions)
  •* (operators and basic semantic stuff)
  • library.* (semantic library helper classes)