genetic programming

In artificial intelligence, genetic programming (GP) is the automatic creation or modification of programs using genetic algorithms. With the help of this methodology, programs are “grown”, it is getting better and better (in accordance with a certain fitness function for chromosomes) that solve the stated computational problem.

Coding algorithm

The choice of a program coding method in a genetic algorithm is one of the main issues of genetic programming. The program must be encoded in such a way that it is easy to automatically make random changes (mutation operator) and combine the two algorithms into one (the crossing operator).

Encoding methods can be divided into two classes:

• Direct coding - the genetic algorithm works with the program in an explicit form.
• Indirect coding - the genetic algorithm does not work with the program code itself, but with the rules for its construction. That is, the genetic algorithm works with a program that generates the program we need.

Neural networks

Tree

Function represented in tree form

In tree encoding, each node in the tree contains a function, and each leaf contains an operand. An expression represented as a tree can be easily recursively counted. Traditional GP is easier to use for growing programs written in languages that naturally embody a tree structure: Lisp, Haskell, F #, and other functional programming languages.

Non-dream program presentations have also been proposed and successfully implemented, for example, linear genetic programming suitable for traditional imperative languages.

Crossover operator

Crossing operator for tree view programs

In the tree view, the crossing operator is implemented by exchanging two nodes together with their descendants (subtrees) between two trees.

Example:

  individual.Children [randomChildIndex] = otherIndividual.Children [randomChildIndex];

Mutation operator

Unlike a crossing operator, a mutation operator affects only one chromosome. In a tree view, it can be implemented by changing information in a node or adding / removing a node or an entire subtree. At the same time it is necessary to monitor the correctness of the operator’s results

Example:

  individual.Information = randomInformation ();

or

  individual = generateNewIndividual ();

Metagenetic programming

Metagenetic programming is a GP in which not only a given computer program is changed and, thus, “grown”, but also the used crossing and mutation operators themselves.