In stack-based genetic programming, the programs in the evolving population are expressed in a stack-based programming language. The specific languages vary among systems, but most are similar to FORTH insofar as programs are composed of instructions that take arguments from data stacks and push results back on those data stacks. In the Push family of languages, which were designed specifically for genetic programming, a separate stack is provided for each data type, and program code itself can be manipulated on data stacks and subsequently executed.
Depending on the specific language and genetic operators used, stack-based genetic programming can have a variety of advantages over tree-based genetic programming. These may include improvements or simplifications to the handling of multiple data types, bloat-free mutation and recombination operators, execution tracing, programs with loops that provide valid outputs even when terminated prematurely, parallelism, evolution of arbitrary control structures, and automatic simplification of evolved programs.
Some references to stacked-based GP at the GP Bibliography are as follows:
Stack-Based Genetic Programming
Proceedings of the 1994 IEEE World Congress on Computational Intelligence, Vol. 1, pp. 148-153, IEEE Press, 27-29 June 1994.
Kilian Stoffel and Lee Spector
High-Performance, Parallel, Stack-Based Genetic Programming
Genetic Programming 1996: Proceedings of the First Annual Conference, pp. 224-229, MIT Press, 28-31 July 1996.
Wilker Shane Bruce
The Lawnmower Problem Revisited: Stack-Based Genetic Programming and Automatically Defined Functions
Genetic Programming 1997: Proceedings of the Second Annual Conference, pp. 52-57, Morgan Kaufmann, 13-16 July 1997.
Stack-Correct Crossover Methods in Genetic Programming
Late Breaking Papers at the Genetic and Evolutionary Computation Conference (GECCO-2002), pp. 443-449, AAAI, July 2002.
Lee Spector and Alan Robinson
Genetic Programming and Autoconstructive Evolution with the Push Programming Language
Genetic Programming and Evolvable Machines, 3(1), pp. 7-40, March 2002.
Lee Spector and Jon Klein and Maarten Keijzer
The Push3 execution stack and the evolution of control
GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, Vol. 2, pp. 1689-1696, ACM Press, 25-29 June 2005.
Kenneth Holladay and Kay Robbins and Jeffery von Ronne
FIFTH: A Stack Based GP Language for Vector Processing
Proceedings of the 10th European Conference on Genetic Programming, Lecture Notes in Computer Science, Vol. 4445, pp. 102-113, Springer, 11-13 April 2007.
Thomas Helmuth and Lee Spector
General Program Synthesis Benchmark Suite
GECCO ’15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1039-1046, ACM, 11-15 July 2015.