Introduction to Genetic Programming

Disclaimer: For easy computation, the code given below has a limited number of terminals (Operands) and Operators. The code to a simple Genetic Program has been linked below.

picklehari/GP

What are Evolutionary Algorithms?

Bio-mimicry has been a strategy humans have equipped for generations. We have always derived inspiration from Nature to tackle complex stuff (Ranging from Drones to comic book heroes).

Evolutionary Algorithms are a class of Algorithms that mimics Natural phenomenon (Such as Animal Behaviors to Natural Selection). One of the major sub-classes being Genetic Algorithms.

Genetic Algorithms

Theories of Evolution suggest the importance of genetic variation and random mutation is vital when building a fit being. The same principle comes into play under Genetic Algorithms. Usually, used as an optimization approach, they consider each small independent entity (Varying from problem to problem) as an analogy to alleles.

Basic working of GAs. Fitness function evaluates and the population. The process of selection,crossover and Mutation are together called Reproduction and are an analogy to their biological counterpart processes.

Genetic Programming

Genetic programs are a sub-class of genetic algorithms that produce program codes. Here each allele is presented as a parse tree with terminal values( Variables and constants) as leaf nodes and Operators as non-leaf nodes.

The thick outlined nodes represent leaf nodes. A non-leaf node may have multiple operands depending on the type of operands. Here O(n) represents an operator that takes n arguments. The value of T maybe a variable (like x or y) or a constant (like “cat” or 5 or 5.23).

An example walk-through

Consider a program that generates a LISP code for evaluating a polynomial. In this case, for simplicity, we consider polynomials that have factors belonging to the set {-2,-1,0,1,2}. We also undertake binary arithmetic operations and
We produce LISP code because it is easier to generate from a parse tree.

Step 01: Generating Random Trees

We take an operand and attach subtrees as it’s children. A subtree could be a terminal or another tree. This is done recursively till all leaf nodes are obtained.

Step 02: Selection

Here two or multiple parents (Trees) are selected for mating. There are multiple approaches to selection. Here a tournament-based selection is used. A fixed number of trees are selected from the population at random and are evaluated under the fitness function. The number of trees competing shouldn’t be too big or too small. This ensures diversity among the new population. Two parents are selected.

Step 03: Crossover

Here sub-trees are interchanged at random between the parents. Exchange of genes take place. Thus forming children. These children constitute the next population.

Step 04: Mutation

A small fraction of the newly formed population is induced with a mutation. A very small fraction of sub-trees is replaced at random.

Step 05: Halting?

Here a halting condition is specified. In the above case, the code stops when the fitness value evaluates to 1 or 250 generations are generated. Thus producing the most optimal parse tree as output.

Step 06: Generating LISP code from parse tree

Preorder traversal is performed in the parse trees and is grouped as “(Operator, Operand, Operand)”.

This thus forms a LISP function to evaluate the function.