Genetic Programming

Genetic Algorithms

Subject: Evolutive Computation

Author: Edwin Camilo Cubides Garz

on, Ph.D.(c)
eccubidesg@unal.edu.co

Advisor: Jonatan G
omez Perdomo, Ph.D.
jgomezpe@unal.edu.co
Grupo de investigaci
on en vida artificial Research Group on Artificial Life (Alife)
Departamento de Ingeniera de Sistemas e Industrial
Facultad de Ingeniera
Universidad Nacional de Colombia
2nd Semester 2014

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

1 / 30

Outline

Contextualization

Evolutionary Algorithm

Genetic Programming
Representation of programs
Generation of initial populations
Selection strategy
Generation of offspring
Replacement strategy
Advantages and disadvantages

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

2 / 30

Contextualization

Outline

Contextualization

Evolutionary Algorithm

Genetic Programming
Representation of programs
Generation of initial populations
Selection strategy
Generation of offspring
Replacement strategy
Advantages and disadvantages

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

3 / 30

Contextualization

Soft Computing

SP = ANN + FL + EC
Soft

Artificial

Fuzzy

Evolutionary

Computing

Neural

Logic

Computation

Networks

Hard computing = imprecision, uncertainty, accuracy, partial truths

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

4 / 30

Evolutionary Algorithm

Outline

Contextualization

Evolutionary Algorithm

Genetic Programming
Representation of programs
Generation of initial populations
Selection strategy
Generation of offspring
Replacement strategy
Advantages and disadvantages

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

5 / 30

Evolutionary Algorithm

General Algorithm to Evolve Individuals

Algorithm 1 Evolutionary Algorithm(f , terminationCondition, )
1. t = 0
2. P0 = InitPopulation()
3. evaluate(P0 , f )


4. while terminationCondition(t, Pt , f ) = false do


5.
newIndividuals = Generate Pt , f , Select Function
6.
Pt+1 = offspring = Replacement(Pt , newIndividuals, f )
7.
evaluate(Pt+1 , f )
8.
t =t +1
9. end while
10. return Pt
The parameter Select Function is a function used for selecting
the parents to generate new individuals using the genetic operators.

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

6 / 30

Evolutionary Algorithm

Evolutionary Computation

EC = GA + ES + EP
Evolutionary

Genetic

Computation

Evolutionary

Evolutionary

Algorithms

Strategies

Programming

(Holland, 75)

(Rechenberger, 73)

(Fogel, Owens,
Walsh, 66)

GP
Genetic
Programming
(Jhon Koza, 1989)

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

7 / 30

Genetic Programming

Outline

Contextualization

Evolutionary Algorithm

Genetic Programming
Representation of programs
Generation of initial populations
Selection strategy
Generation of offspring
Replacement strategy
Advantages and disadvantages

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

8 / 30

Genetic Programming

Definition I

Definition
Genetic Programming (GP) is a branch of Genetic Algorithms, in which
individuals (chromosomes) of population are computer programs
(Koza, 92, Koza, 94, Koza, 99, Koza, 03) [1, 2, 3, 4].

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

9 / 30

Genetic Programming

John Koza

John R. Koza is a computer scientist and a former consulting professor at

Stanford University, most notable for his work in pioneering the use of
Genetic Programming for the optimization of complex problems.

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

10 / 30

Genetic Programming

Differences between GP and GA

Differences
The main difference between GP and traditional GA is the representation
of the solution. GP creates computer programs in some particular
programming language to represent a solution, whereas genetic algorithms
create a string of numbers that represent the solution
Example
GA: 1001101100111000



GP: + (1, b),

(b, b), ((4, a), c) , (2, a)

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

11 / 30

Genetic Programming

Goal and Fitness of GP

Goal
The goal of the GP is to find a program that solves a problem such that
its analytic solution is very complicated to find.

Fitness
The fitness of a valid individual is generally obtained by the performance
and the behavior of it over a training data sets.

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

12 / 30

Genetic Programming

Functions and Terminals in GP

Functions and Terminals

The set of terminals and functions is the most important component of
the GP. The set of terminals and functions is the alphabet of the programs
that are build over the language programming. The variables and
constants of the programs belong to set of terminals.
Example
Functions: +, , , ,

, ....

Terminals: a, b, c, . . . , 2, 1, 4, . . . .

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

13 / 30

Genetic Programming

Representation of programs

Representation of GP I

Representation
As any program can be represented as a tree or a set of trees (genotype),
the programs (chromosomes) usually are represented as data structures
(trees), these trees are obtained doing parsing over sentences (strings) of a
program (phenotype), from where GP is applied over a particular domain
(programming language).

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

14 / 30

Genetic Programming

Representation of programs

Representation of GP II
Phenotype and Genotype

Phenotype

Genotype

a+bc
2a

E. C. Cubides & J. G
omez (UN)

+
a

Doctorate in Computer Engineering

2nd Semester 2014

15 / 30

Genetic Programming

Representation of programs

Representation of GP III
Phenotype and Genotype

b +


 




b 2 4ac
(b, b), ((4, a), c)
, (2, a)
= + (1, b),
2a

b
4

E. C. Cubides & J. G
omez (UN)

c
a

Doctorate in Computer Engineering

2nd Semester 2014

16 / 30

Genetic Programming

Generation of initial populations

Initial population I

Methods
As the mutation is almost always lethal, it is very restricted, then, the
diversity in the generations is obtained only into the initial population.
The main methods are:
Full
Grow
Ramped (half-and-half)

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

17 / 30

Genetic Programming

Generation of initial populations

Initial population II
Full: Length of all branches equal to l > 0.
Example (Depth l = 2)

+
c a

+
b

(c b) + a

(a c) (a + b)

c a

(b c) (a c)
E. C. Cubides & J. G
omez (UN)

b
b+b

c (a b)
Doctorate in Computer Engineering

+
b a

(a b) (a + c)
2nd Semester 2014

18 / 30

Genetic Programming

Generation of initial populations

Initial population III

Grow: Length of all branches of depth less than or equal to l > 0.
Example (Depth 0 < l 2)

c
a

c + (a 2)

ac

a
a

E. C. Cubides & J. G
omez (UN)

aa
Doctorate in Computer Engineering

+
b a

(a b) (a + c)
2nd Semester 2014

19 / 30

Genetic Programming

Generation of initial populations

Initial population II
 
Ramped (half-and-half): if is the cardinal of the population, then l
trees of depth 1, 2, 3, . . . , l are created with the full
 or grow
methods (the root has depth equal to 0). Thus, l trees
are generated, but as
jk

l
j lk

l l
l
j l k
l
l
 
 
 
then l l > 0. If l l > 0 then l l trees of
depth 1 or 2 or or l are generated to complete the
population.

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

20 / 30

Genetic Programming

Generation of initial populations

Initial population IV
Example (For = 6 and depth l = 4, b/lc = 1, b/lcl = 2 )
l1 = 1

l3 = 3

l4 = 4

ac
l2 = 2

a
+

(c b) +

b
a

c ((a + a) b)

+
a

a
b

l5 = 3

l6 = 1

(a (c b)) (a + c)

E. C. Cubides & J. G
omez (UN)

p
b + (c + (a 2))

Doctorate in Computer Engineering

2nd Semester 2014

21 / 30

Genetic Programming

Selection strategy

Selection

Selection: is similar to the selection into genetic algorithms, normally

the selection is done over a sorted set.
Elitism selection
Uniform selection
Tournament selection
Roulette-wheel selection
Rank selection
Stochastic selection

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

22 / 30

Genetic Programming

Selection strategy

Operators I
Crossover: given a couple of programs, a subtree of each program is
randomly selected and these subtrees are swapped.
Example

E. C. Cubides & J. G
omez (UN)

+
c

b
b

b
c

b
b

c
Doctorate in Computer Engineering

2nd Semester 2014

23 / 30

Genetic Programming

Generation of offspring

Operators II
Mutation: given a program, a subtree of this program is randomly
selected and it is replaced by a new randomly generated tree.
Example
+
1

b
c

b
+

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

24 / 30

Genetic Programming

Generation of offspring

Operators II
Swap: given a function, a subfunction f is randomly selected, if this
subfunction has arity n 2, then two different parameters ai ,
aj (i 6= j) are randomly selected and these are swapping, thus
f (a1 , . . . , ai , . . . , aj , . . . , an ) f (a1 , . . . , aj , . . . , ai , . . . , an )
Example
+
1

E. C. Cubides & J. G
omez (UN)

+
a

Doctorate in Computer Engineering

+
b

2nd Semester 2014

25 / 30

Genetic Programming

Replacement strategy

Replacement strategy

Replacement: is similar to the replacement into genetic algorithms.

Generational replacement
Steady state replacement
Replace
Replace
Replace
Replace
Replace
Replace

E. C. Cubides & J. G
omez (UN)

worst
best
parent
random
most similar (crowding)
oldest

Doctorate in Computer Engineering

2nd Semester 2014

26 / 30

Genetic Programming

Advantages and disadvantages

Advantages

It is not necessary background knowledge.

It is possible work with several posible solutions.
They are easy to parallelize.
They can use probabilistic operators.
It is more natural represent the solution with a program instead of a
real number or a binary string.
The solution has implicit the algorithm.
The chromosomes do not have a fixed length.

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

27 / 30

Genetic Programming

Advantages and disadvantages

Disadvantages

The syntax is very restricted.

The mutation is restricted to particular places into the program.
Generally are obtained local optimums.
They can converge prematurely.

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

28 / 30

Genetic Programming

Advantages and disadvantages

References I

John R. Koza, Genetic programming: On the programming of

computers by means of natural selection, Cambridge, MA: MIT Press,
1992.
, Genetic programming ii: Automatic discovery of reusable
programs, MIT Press, 1994.
John R. Koza, F. H. Bennett, D. Andre, and M. A. Keane, Genetic
programming iii: Darwinian invention and problem solving, Morgan
Kaufmann, 1999.
John R. Koza, M. A. Keane, M. J. Streeter, W. Mydlowec, J. Yu, and
G. Lanza, Genetic programming iv: Routine human-competitive
machine intelligence, Kluwer Academic Publishers, 2003.

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

29 / 30

Genetic Programming

Advantages and disadvantages

Thank you
Questions?

E. C. Cubides & J. G
omez (UN)

Doctorate in Computer Engineering

2nd Semester 2014

30 / 30