Genetic programming
Genetic programming is a subset of genetic algorithms, the only difference between them being the representation of the chromosome. Genetic algorithms deal with optimization problems where the phenotype is based on point or vector, while in genetic programming the phenotype is based on tree. In addition to this, they also can increase or decrease their genotype by adding more terminals and instructions.
As we already know genetics programming is based on trees, it is hugely applied to evolve decision and behavioral tress for game playing.
Sante Fe Ant trail
The Sante Fe Ant trail, is one of the most used examples of genetic programming. It basically is a situation where a trail of food is placed around the map, and we need to maximize the amount of food collected with a limited number of steps taken. We use genetic programming to prepare a set of instructions for the ant to follow to solve this problem.
The above diagram is a representation of the Santa Fe Ant Trail problem.
Setting up the problem.
Irrespective of the algorithm there are two different preliminaries that need to be taken care of in evolutionary computation. They are as follows:
- Creation of initial population
- Fitness function
From our prior knowledge, we know genetic algorithms can create a uniform population randomly from the domain, but it is different for genetic programming. Genetic programming needs to follow a problem-dependent grammar structure. It is done by first defining the BNF grammar for the problem. After that, the depth of the tree is set. The depth is decided according to the number of layers in the tree. We define a min and max depth, that affects the initial population. Therefore, the initial population becomes generation individuals that will be between the min and max generations while other individuals can shrink and grow.
Function elements from grammar are randomly selected to create the tree. They then branch out by randomly choosing the terminals, and similar to the genetic algorithm, we discard individuals with lower values than min or higher values than max and keep on sampling until we get an individual within the min and max range.
The fitness function for genetic programming can have different ways to determine the fitness values, such as it can create test cases and evaluating how well an agent did on the test. It can also use AI for evaluation. Though, we need to reject overly complex models as our requirement is to decrease the model complexity so that it can generalize to new inputs. To avoid the complex models we can assess the bloating of the model. Bloating refers to the addition of more terminal nodes and depth to a tree, while the fitness value is decreased only slightly.
Reference