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.