Genetic Programming

GP is very similar to GA.  The main difference is that GA evolves solutions to a problem directly but GP aims to evolve a "program" to solve the problem.

What is a "program"  that GP try to evolve?

A program is a sequence of step-by-step instructions, such as  a calculation of numbers, the commands to move a mobile robot, a grammar to generate some language etc.   The "meaning" of program depends on the definition of its "instruction set".  To compose a program it requires "function" and "terminal" together becomes an instruction set to solve a problem.  Terminals are the basic (primitive) instructions, such as  +, -, x, y (variable names), move-forward (robot command).  Functions are the connectives that join terminals together such as  if-then, sequence which control the flow of instructions.

The most convenient form of program in GP is a tree (or a graph).  The followings are examples of programs in prefix notation :

        ( *  x x )
a program to computer x^2
        ( if  food-ahead move-forward)
a program for a robot if it senses that food is ahead then it moves forward.
        ( + ( * m x ) c )
a linear regression y = mx + c, fitting a curve to data.  One can consider it as a program that "predict" future data based on existing data.

Programming paradigm

We will look into the development of programming languages to understand the kind of possible programs to be used in GP.  There are many ways to write a program.  Presently there are a number of approaches in programming.   Mathematically, all programs are equivalent in the sense of "Turing machine".  It is a matter of what is more suitable (convenient) for "human" to work with. In GP we need to find languages that is convenient (or efficient) for "computer" to work with.  The main paradigm in programming are :

Procedural

Step-by-step instructions telling a computer "how" to do a job.
 //  Find maximum element in an array of N elements
max = a[1]
for i = 2 to N
  if a[i] > max then max = a[i]

Logic-based (or Declarative)

Declarative programs tell a computer "what" a user want a computer to accomplish but leave the step-by-step detail to be done implicitly by the computer.   The "what" is declared in term of "goal" and "subgoal" and break down to the level of primitives that a  computer can perform.
 //  Deduction about mortality of a man
 mortal(X) :- man( X ).       //  every man is mortal
 man(socrates).
 //  now one can ask "what can we deduce fromt the above axiom?
 ?  mortal(Y).
 answer  Y = socrates.

 //  Deduction about parenthood
 parent(X,Y) :-  father(X,Y).
 parent(X,Y) :-  mother(X,Y).
 parent(X,Y) :-  parent(X,Z), parent(Z,Y).

The first and second clause said a parent X of Y is either father X of Y or mother X of Y.  The third clause said a parent of a parent is also parent (actually a grand-parent).  Now with some given facts we can reason (or deduce some consequences :
  father(Somchai, Kid).
 mother(Tum, Kid).
 father(Prabhas, Som).
 mother(Took, Som).
 father(Charoen, Prabhas).
 //  is Charoen a parent of someone?
 ?  parent(Charoen, X).
 answer  yes, X = Prabhas, X = Som.
the system deduces that Charoen is the parent of Prabhas and also a grand-parent of Som because Prabhas is also a father of Som.

Function-based (Functional programming)

Functional programming is also declarative.  The main intend of functional programming is to achieve "referential transparency".  This can be achieved by writing program only in the composition of functions.  Variables can be totally eliminated such as in FP (Backus, 1972) (wow, a program with no variable).  This will eliminate any side-effect which is the main cause of programming error.  The other alternative to achieve the same effect is "single assignment" as used in ML.

The following is an example of FP for inner product calculation

 //  inner product
 Def IP = (/+) . (@x ) . trans
 //  where  /+  is a distributor function (distribute +)
 //   @x  is an apply all function (apply x)
 //   trans  is a tranposition function
 //   f . g : x  is applying f(g(x))
 //
 //  and now an example of applying IP to two vectors
 IP : < <1,2,3> , <6,5,4> >
 = (/+).(@x). trans : < <1,2,3> , <6,5,4> >
 = (/+).(@x) : ( trans : < <1,2,3> , <6,5,4> > )
 = (/+) : ( (@x) : < <1,6> , <2,5> , <3,4>> )
 = (/+) : < x : <1,6> , x : <2,5> , x : <3,4>>
 = (/+) : < 6,10,12 >
 = + : < 6, + : <10,12 > >
 = 28
There are many other paradigms in programming such as object-based.

Closure and Type

A function takes argument of a certain type.  A "+" may take two integers, two reals or two strings (if "+" is interpret as concatenation).  If a function is typed it must take only a certain type.   A function is "closed" if its result is the same type as its arguments.  When an instruction set is closed, composing arbitrary programs will always produce valid programs (whether it gives correct answer is another matter).  This is very suitable for "programs" in which GP will operate on.