now let's talk about a slightly
different approach to genetic

algorithms called genetic programming
which was developed by John

in the 1990s genetic programming

instead of using strings of numbers

as we did for Robbie the Robot uses
programs represented as

what are called syntactic trees.
I explain that in a moment

here's a picture of Jon Koza lecturing
on Genetic Programming

He's written one two three books on this
subject to become a very

big sub area at the field of genetic
algorithms.

So here's the idea let's consider the
problem of Robbie the robot again

involving a control strategy for him

Here instead of representing his
control strategy as

string of numbers which represent
actions

in every possible situation, here we
would represent

a control strategy as a sort of tree.

This is up but what in computer science
is called a tree where we

have the elements to the program
represented

in terms of these nodes and these
branches

So this particular program isn't if

then else statement here at the book and
it says

if this is the clause to consider

if there's a can in the east and

the north is empty then

the robot should move east otherwise

the robot should move south.That's what
this tree represents and you can look at

it as

a regular kind of program: if east == can
and north equals empty the move east

out of himself.

now suppose Robbie

is in this situation and this is his
strategy, here's what he would do

he would look at the if clause here you
would say

is there's can in my East and is the North

of me empty others can to the east and the
north is empty so

he would follow this first branch, he
would move east

here we go.

And now he's in a new situation so he 
follows this strategy again he says

is there a can to the east of me in the
North empty

no that I follow the second branch

himelf and does it again

not there's not a can in the east and
north of me so move south

so this isn't a very good strategy but
this is what it is for him to follow it

it's a different kind of representation
then what we saw before.

Obviously this tree is way too simple
to be a good strategy because it doesn't

involves picking up any cans

Consider this more complicated strategy
which is represented as a

longer tree. Well this is getting
harder to make sense a

but here we can have Robbie follow this
strategy. Okay here he is

he says if north is empty and there's a
can to my East

well that's true so follow this first
branch

but now this first branch has another
if statement so he looks at this

if it's both true that there's not a can
to my West

there's no can to the west and there is
a can to the east

then well this is true so if all the
first branch is this

move East yes.

now he's in a new situation so start up
here

say is there is the North empty

and there's a can in east, no over here
to the final branch

there was a if there's can in the current
site

there is. pick up the camp

he does it okay will now he's in a
situation where

this first this if clause fails it's not
true

so we go over here there's not a current
can in his sight

so he has to move south. I hope you get
the idea that this is just a different way

to express

a strategy. it's hard to find a tree

that is a good strategy but that's going
to be the job the genetic algorithm

the only difference from what we did
before is that the genetic algorithms

going to evolve these trees

instead of strings
so here's how that works

the initial population instead have said
i've random strings is just a set of

random trees

with some what we call syntactic
constraints

for example we need if else at the root
of the tree

and some other constraints I'm not going
to talk about the details that here

I just want you to get the general idea

to calculate fitness well it's the same
procedure we have Robbie tryout each

strategy in a variety of environments

computer each strategies average score
and then we have the

fitter individuals get to create more
offspring nonetheless fit individuals

that implements selection to do cross
over to produce children

incentive exchange in parts of strings
we exchange subtrees

so here's an example here's to possible
parents

to trees and we might create a child

by taking this subtree from

the second parent and putting it here

instead of this move east note here we
would

put this subtree there to create a child

who looks like this so here this is
exactly the same as this

first parent except for that move east
block

is replaced by this if else block

it's still a syntactically correct treat
it's still a strategy

and this is how the genetic algorithm is
able to take part serve

fit parents and we combine them

mutations started replacing a randomly
chosen value by another random value

we replace a subtree by randomly
generated subtree

to might do this we might take this
subtree here

and replace it by some randomly
generated subtree

I didn't implemented genetic programming
version A Robbie

that's something that the more advanced
programmers among you might be

interested in doing

but I do wanna tell you about a real
genetic programming project

actually to them that are quite
interesting

the first one is applying genetic
programming to computer graphics

this has been done by a lot of people
the most famous example was done by Karl

Sims

curious in the 1990s he's a computer
graphics artist

and decided to you evolve programs to
produce computer graphics that are

aesthetically pleasing. So here's how
that works

the individuals in the population are
trees just like I showed you acceptance

into representing strategies for

virtual robot they represent equations

that generate a collar for each pixel in
an image

okay so this is just some examples and

these are some programs so I'm not
going to explain to you how it works

you can read Carl Sims paper if you're
interested

but just come away with with the idea
that you can represent

these programs as trees

and each program generates a color for
every pixel in the image

okay so you could imagine generating a
bunch of random programs

that randomly color the pixels in the
image

the question is how do you define a
fitness function that is how you define

the fitness of a particular

pixel. well this is something that

right now is beyond computers

to do well so Karl Sims had humans
in the loop

what he did was have humans himself as
an example

look at pictures that the computer
created random pictures

and pick the one that he liked the best

than that one would be used as a parent
and be a crossover

with other random programs and mutation
it would produce new programs

that would produce new images that are
related to the one that he chose

You repeat this over and over again and
the genetic algorithm came up with some

very beautiful results

so here's an example, here's a picture

and here's a program that created it

so this was a collaboration in some
sense between

the genetic algorithm and human

where the human is not actually writing
the program but just saying

what here she likes and then the genetic
algorithm

goes and evolves that program further

here's another example

and another one

here's a particularly beautiful one very
reminiscent of some Japanese paintings I

think

Another one and

it goes on and on. Here 2

KRL's you couldn't go to the first is to
Carl Sims website reaches all these

pictures and talks about a lot of his
different projects

the second one is a applet which

gives you the opportunity to evolve the
sky kinds of pictures yourself

when really interesting thing that
Karl Sims did

in addition to what I just described is
to set up

a museum exhibit. this one wasn't this
George Pompidou Center in Paris

where he had syriza monitors as you can
see

each showing a different picture the
kind that we just looked at

and down here on the floor are sensors

and the people in the exhibit can go and
stand on the sensors

if they like a particular picture and
then that one

gets chosen and gets evolved further via
the genetic algorithm

perhaps meeting with some the other
chosen pictures

so in that way it wasn't a single person
but it was a whole group of people who

were

in some sense playing the role love the
selection algorithm for the genetic

algorithm

Here what sims said about this: the
viewers at the exhibit can observe a

computer simulated evolution in progress

an evolutionary image but in this
evolution the viewers are not just

observers

they cause the evolution and direct its
course

He goes on to say: a population of images
is displayed by the computer

on archive 16 video screens, the viewers
determine which images will survive by

standing on sensors and for those I
think the most aesthetically interesting

pictures that are not selected are
removed and replaced by offspring from

the surviving images

the new images are copied and
combinations are their parents but with

various alterations

this is an artificial evolution which
the viewers themselves interactively

determine the fitness at the pictures by
choosing where they stand

as the cycle continues the population
have images can progress towards more

and more interesting visual effects

this interactive installation is an
unusual collaboration

between humans and machines.The human
supply decisions a visual aesthetics

and the computer supplies the
mathematical ability for generating

mating and mutating complex textures and
patterns

The viwers are not required to understand
the technical equations involved

the computer can only experiment at
random with no sense of aesthetics

but the combination of human-machine
abilities permits the creation of

results that neither of the two could
produce alone.