Lecture 10

Evolutionary Computation:
Evolution strategies and genetic programming
Evolution strategies
Genetic programming
Summary

Negnevitsky, Pearson Education, 2002

Evolution Strategies
Another approach to simulating natural
evolution was proposed in Germany in the early
1960s. Unlike genetic algorithms, this approach
called an evolution strategy was designed
to solve technical optimisation problems.

Negnevitsky, Pearson Education, 2002

In 1963 two students of the Technical

University of Berlin, Ingo Rechenberg and
Hans-Paul Schwefel, were working on the
search for the optimal shapes of bodies in a
flow. They decided to try random changes in
the parameters defining the shape following the
example of natural mutation. As a result, the
evolution strategy was born.
Evolution strategies were developed as an
alternative to the engineers intuition.
Unlike GAs, evolution strategies use only a
mutation operator.

Negnevitsky, Pearson Education, 2002

Basic evolution strategies

In its simplest form, termed as a (1+1)-evolution
strategy, one parent generates one offspring per
generation by applying normally distributed
mutation. The (1+1)-evolution strategy can be
implemented as follows:
Step 1: Choose the number of parameters N to
represent the problem, and then determine a feasible
range for each parameter:

{ x1min ,

x1max }, { x2min , x2max }, . . . ,

{ x Nmin ,

x Nmax }

Define a standard deviation for each parameter and

the function to be optimised.
Negnevitsky, Pearson Education, 2002

Step 2: Randomly select an initial value for each

parameter from the respective feasible range. The
set of these parameters will constitute the initial
population of parent parameters:
x1 , x2 , . . . , xN
Step 3: Calculate the solution associated with the
parent parameters:
X = f (x1, x2, . . . , xN)

Negnevitsky, Pearson Education, 2002

Step 4: Create a new (offspring) parameter by

adding a normally distributed random variable a
with mean zero and pre-selected deviation to each
parent parameter:
xi = xi + a (0, )

i = 1, 2, . . . , N

Normally distributed mutations with mean zero

reflect the natural process of evolution (smaller
changes occur more frequently than larger ones).
Step 5: Calculate the solution associated with the
offspring parameters:
X = f (x1 , x2 , . . . , xN )
Negnevitsky, Pearson Education, 2002

Step 6: Compare the solution associated with the

offspring parameters with the one associated with
the parent parameters. If the solution for the
offspring is better than that for the parents, replace
the parent population with the offspring
population. Otherwise, keep the parent
parameters.
Step 7: Go to Step 4, and repeat the process until a
satisfactory solution is reached, or a specified
number of generations is considered.
Negnevitsky, Pearson Education, 2002

An evolution strategy reflects the nature of a

chromosome.
A single gene may simultaneously affect several
characteristics of the living organism.
On the other hand, a single characteristic of an
individual may be determined by the simultaneous
interactions of several genes.
The natural selection acts on a collection of genes,
not on a single gene in isolation.

Negnevitsky, Pearson Education, 2002

Genetic programming
One of the central problems in computer science is
how to make computers solve problems without
being explicitly programmed to do so.
Genetic programming offers a solution through the
evolution of computer programs by methods of
natural selection.
In fact, genetic programming is an extension of the
conventional genetic algorithm, but the goal of
genetic programming is not just to evolve a bitstring representation of some problem but the
computer code that solves the problem.

Negnevitsky, Pearson Education, 2002

Genetic programming is a recent development in

the area of evolutionary computation. It was
greatly stimulated in the 1990s by John Koza.
According to Koza, genetic programming searches
the space of possible computer programs for a
program that is highly fit for solving the problem at
hand.
Any computer program is a sequence of operations
(functions) applied to values (arguments), but
different programming languages may include
different types of statements and operations, and
have different syntactic restrictions.

Negnevitsky, Pearson Education, 2002

10

Since genetic programming manipulates programs

by applying genetic operators, a programming
language should permit a computer program to be
manipulated as data and the newly created data to
be executed as a program. For these reasons,
LISP was chosen as the main language for
genetic programming.

Negnevitsky, Pearson Education, 2002

11

LISP structure
LISP has a highly symbol-oriented structure. Its
basic data structures are atoms and lists. An atom
is the smallest indivisible element of the LISP
syntax. The number 21, the symbol X and the string
This is a string are examples of LISP atoms. A
list is an object composed of atoms and/or other
lists. LISP lists are written as an ordered collection
of items inside a pair of parentheses.

Negnevitsky, Pearson Education, 2002

12

LISP structure
For example, the list
( (* A B) C)
calls for the application of the subtraction function
() to two arguments, namely the list (*A B) and
the atom C. First, LISP applies the multiplication
function (*) to the atoms A and B.
Once the list (*A B) is evaluated, LISP applies the
subtraction function () to the two arguments, and
thus evaluates the entire list
( (* A B) C).
Negnevitsky, Pearson Education, 2002

13

Graphical representation of LISP S-expressions

Both atoms and lists are called symbolic
expressions or S-expressions. In LISP, all data
and all programs are S-expressions. This gives
LISP the ability to operate on programs as if they
were data. In other words, LISP programs can
modify themselves or even write other LISP
programs. This remarkable property of LISP
makes it very attractive for genetic programming.
Any LISP S-expression can be depicted as a rooted
point-labelled tree with ordered branches.

Negnevitsky, Pearson Education, 2002

14

LISP S-expression ( (*A B) C)

*
A

Negnevitsky, Pearson Education, 2002

15

How do we apply genetic programming

to a problem?
Before applying genetic programming to a problem,
we must accomplish five preparatory steps:
1. Determine the set of terminals.
2. Select the set of primitive functions.
3. Define the fitness function.
4. Decide on the parameters for controlling the run.
5. Choose the method for designating a result of
the run.
Negnevitsky, Pearson Education, 2002

16

The Pythagorean Theorem helps us to illustrate

these preparatory steps and demonstrate the
potential of genetic programming. The theorem
says that the hypotenuse, c, of a right triangle with
short sides a and b is given by

c = a +b
2

The aim of genetic programming is to discover a

program that matches this function.

Negnevitsky, Pearson Education, 2002

17

To measure the performance of the as-yetundiscovered computer program, we will use a

number of different fitness cases. The fitness
cases for the Pythagorean Theorem are
represented by the samples of right triangles in
Table. These fitness cases are chosen at random
over a range of values of variables a and b.

Side a
3
8
18
32
4

Side b
5
14
2
11
3

Hypotenuse c
5.830952
16.124515
18.110770
33.837849
5.000000

Negnevitsky, Pearson Education, 2002

Side a
12
21
7
16
2

Side b
10
6
4
24
9

Hypotenuse c
15.620499
21.840330
8.062258
28.844410
9.219545
18

Step 1: Determine the set of terminals.

The terminals correspond to the inputs of the
computer program to be discovered. Our
program takes two inputs, a and b.
Step 2: Select the set of primitive functions.
The functions can be presented by standard
arithmetic operations, standard programming
operations, standard mathematical functions,
logical functions or domain-specific functions.
Our program will use four standard arithmetic
operations +, , * and /, and one mathematical
function sqrt.
Negnevitsky, Pearson Education, 2002

19

Step 3: Define the fitness function. A fitness

function evaluates how well a particular computer
program can solve the problem. For our problem,
the fitness of the computer program can be
measured by the error between the actual result
produced by the program and the correct result
given by the fitness case. Typically, the error is
not measured over just one fitness case, but
instead calculated as a sum of the absolute errors
over a number of fitness cases. The closer this
sum is to zero, the better the computer program.
Negnevitsky, Pearson Education, 2002

20

Step 4: Decide on the parameters for controlling

the run. For controlling a run, genetic
programming uses the same primary parameters
as those used for GAs. They include the
population size and the maximum number of
generations to be run.
Step 5: Choose the method for designating a
result of the run. It is common practice in
genetic programming to designate the best-so-far
generated program as the result of a run.
Negnevitsky, Pearson Education, 2002

21

Once these five steps are complete, a run can be

made. The run of genetic programming starts with
a random generation of an initial population of
computer programs. Each program is composed of
functions +, , *, / and sqrt, and terminals a and b.
In the initial population, all computer programs
usually have poor fitness, but some individuals are
more fit than others. Just as a fitter chromosome is
more likely to be selected for reproduction, so a
fitter computer program is more likely to survive by
copying itself into the next generation.
Negnevitsky, Pearson Education, 2002

22

Crossover in genetic programming:

Two parental S-expressions
/

sqrt

sqrt

(/ ( (sqrt (+ (* a a) ( a b))) a) (* a b))

Negnevitsky, Pearson Education, 2002

sqrt

(+ ( (sqrt ( (* b b) a)) b) (sqrt (/ a b)))

23

Crossover in genetic programming:

Two offspring S-expressions
/

sqrt

sqrt

sqrt

(/ ( (sqrt (+ (* a a) ( a b))) a) (sqrt ( (* b b) a)))

Negnevitsky, Pearson Education, 2002

(+ ((* a b) b) (sqrt (/ a b)))

24

Mutation in genetic programming

A mutation operator can randomly change any
function or any terminal in the LISP S-expression.
Under mutation, a function can only be replaced by
a function and a terminal can only be replaced by a
terminal.

Negnevitsky, Pearson Education, 2002

25

Mutation in genetic programming:

Original S-expressions
/

sqrt

sqrt

(/ ( (sqrt (+ (* a a) ( a b))) a) (* a b))

Negnevitsky, Pearson Education, 2002

sqrt

(+ ( (sqrt ( (* b b) a)) b) (sqrt (/ a b)))

26

Mutation in genetic programming:

Mutated S-expressions
/

sqrt

(/ (+ (sqrt (+ (* a a) ( a b))) a) (* a b))

Negnevitsky, Pearson Education, 2002

sqrt

sqrt

(+ ( (sqrt ( (* b b) a)) a) (sqrt (/ a b)))

27

In summary, genetic programming creates computer

programs by executing the following steps:
Step 1: Assign the maximum number of generations
to be run and probabilities for cloning, crossover
and mutation. Note that the sum of the probability
of cloning, the probability of crossover and the
probability of mutation must be equal to one.
Step 2: Generate an initial population of computer
programs of size N by combining randomly
selected functions and terminals.

Negnevitsky, Pearson Education, 2002

28

Step 3: Execute each computer program in the

population and calculate its fitness with an
appropriate fitness function. Designate the bestso-far individual as the result of the run.
Step 4: With the assigned probabilities, select a
genetic operator to perform cloning, crossover or
mutation.

Negnevitsky, Pearson Education, 2002

29

Step 5: If the cloning operator is chosen, select one

computer program from the current population of
programs and copy it into a new population.
If the crossover operator is chosen, select a pair
of computer programs from the current
population, create a pair of offspring programs
and place them into the new population.
If the mutation operator is chosen, select one
computer program from the current population,
perform mutation and place the mutant into the
new population.
Negnevitsky, Pearson Education, 2002

30

Step 6: Repeat Step 4 until the size of the new

population of computer programs becomes equal
to the size of the initial population, N.
Step 7: Replace the current (parent) population
with the new (offspring) population.
Step 8: Go to Step 3 and repeat the process until
the termination criterion is satisfied.

Negnevitsky, Pearson Education, 2002

31

Fitness history of the best S-expression

100

sqrt
F i t n e s s, %

80

60
40

20

a
0

2
3
Gen e ra t i o n s

Negnevitsky, Pearson Education, 2002

4
Best of gene ration

32

What are the main advantages of genetic

programming compared to genetic algorithms?
Genetic programming applies the same
evolutionary approach. However, genetic
programming is no longer breeding bit strings that
represent coded solutions but complete computer
programs that solve a particular problem.
The fundamental difficulty of GAs lies in the
problem representation, that is, in the fixed-length
coding. A poor representation limits the power of
a GA, and even worse, may lead to a false
solution.

Negnevitsky, Pearson Education, 2002

33

A fixed-length coding is rather artificial. As it

cannot provide a dynamic variability in length,
such a coding often causes considerable
redundancy and reduces the efficiency of genetic
search. In contrast, genetic programming uses
high-level building blocks of variable length.
Their size and complexity can change during
breeding.
Genetic programming works well in a large
number of different cases and has many potential
applications.

Negnevitsky, Pearson Education, 2002

34