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.