Linear genetic programming

Linear genetic programming (LGP) is a particular subset of genetic programming wherein computer programs in a population are represented as a sequence of instructions from imperative programming language or machine language. The graph-based data flow that results from a multiple usage of register contents and the existence of structurally noneffective code (introns) are two main differences of this genetic representation from the more common tree-based genetic programming (TGP) variant.[1][2][3]

"Linear genetic programming" is unrelated to "linear programming".

In genetic programming (GP) a linear tree is a program composed of a variable number of unary functions and a single terminal. Note that linear tree GP differs from bit string genetic algorithms since a population may contain programs of different lengths and there may be more than two types of functions or more than two types of terminals.[4]

Examples of LGP programs

Because LGP programs are basically represented by a linear sequence of instructions, they are simpler to read and to operate on than their tree-based counterparts. For example, a simple program written in the LGP language Slash/A looks like a series of instructions separated by a slash:

input/   # gets an input from user and saves it to register F
0/       # sets register I = 0
save/    # saves content of F into data vector D[I] (i.e. D[0] := F)
input/   # gets another input, saves to F
add/     # adds to F current data pointed to by I (i.e. F := F + D[0])
output/. # outputs result from F

By representing such code in bytecode format, i.e. as an array of bytes each representing a different instruction, one can make mutation operations simply by changing an element of such an array.

See also

Notes

  1. Brameier, M.: "On linear genetic programming Archived 2007-06-29 at the Wayback Machine", Dortmund, 2003
  2. W. Banzhaf, P. Nordin, R. Keller, F. Francone, "Genetic Programming – An Introduction. On the Automatic Evolution of Computer Programs and its Application", Morgan Kaufmann, Heidelberg/San Francisco, 1998
  3. Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4.
  4. Foundations of Genetic Programming.
  • Slash/A A programming language and C++ library specifically designed for linear GP
  • DigitalBiology.NET Vertical search engine for GA/GP resources
  • Discipulus Genetic-Programming Software
  • MicroGP Genetic-Programming Software (open source)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.