COGS2010
Week 7 Questions
Evolutionary
Computation I: Introduction to genetic algorithms
Due week 7 at the end of the lab session, or before the lab by email to the
tutor
The
genetic algorithm tutorial is an online one, developed by by Marek Obitko at the
You only need to hand in the answers to questions 1-10.
The background material in sections I-III was mostly covered in the lecture and need only be reviewed briefly in the tutorial.
I. Introduction
II. Biological Background (the DNA pictures are interesting)
III. Search Space (omit the “NP-hard problems” section)
Work through sections IV
onwards, in particular, stepping through the applets that demonstrate the
genetic algorithm (section VI), parameter variations (section VII) and defining
your own functions (VIII).
IV. Genetic Algorithm
V. GA Operators
VI.
GA Example (1D func.)
VII.
Parameters of GA
VIII.
GA Example (2D func.) NB. The graph
can be rotated by clicking and dragging it to get a good perspective. See the neural net fitness landscapes
defined in Question 9 below.
IX.
Selection
X.
Encoding - but only
“Binary and Value Encoding” sections
XI.
Crossover and Mutation
but only “Binary Encoding” section
XII.
Omit.
Questions
(Hand in the answers to the following)
Part A
(questions 1-9 refer to the GA tutorial)
1.
a. In most of the
problems in this tutorial, a binary representation is used. How many different
alleles are there for each gene in a binary representation?
b. What is an allele for real-world DNA?
c. Discuss the similarities and differences between the use of the term
“alleles” in binary representations (in EC) and in DNA (real biology).
2.
In the genetic
algorithm simulation on the “Genetic Algorithm” page, the best current solution
in the population is represented by a red line, and other solutions in the
population are represented by green lines.
What plausible reason can be given as to why the red line moves so infrequently
relative to the other lines in the population. Justify
your answer.
3.
Consider a crossover
operation between the following two chromosomes:
1011 0100 11
0101 0001 10
a. Choose a random cut point and show the two children possible from crossing
the parent chromosomes at that point.
b. Counting all possible cut points, how many different offspring could be
created by (i) single point crossover; (ii)
multi-point crossover with 50% probability of crossing at every point
c. The size of the space is the number of different possible chromosomes. With
10 bits, how many different chromosomes are possible?
d. Starting from the two chromosomes given above, what percentage of the space
can be reached in one generation using (i) single
point crossover; (ii) multi-point crossover.
4.
Run the “GA example
(1D func.)" for a minute. Try to get a feel for
all of the operations that are occurring. Then, reset the example and step
through the process. The green arrows from the chromosomes to the graph below
indicate the position of the chromosome on the search space. Notice how
the crossover and mutation processes change this position.
a. Describe the process.
b. Does the population size change during the course of the evolution?
c. Does crossover always occur?
d. Does mutation always occur?
Note that in the “Parameters of GA” example, the default values are:
Speed: 0 Crossover: 29 Mutation: 3 Elitism: Off
5.
Try playing with the
elitism in the “Parameters of GA” example.
Explain the difference that elitism makes to the simulation and explain why.
6.
Try varying the
mutation rate in the “Parameters of GA” example.
a. What happens if mutation is set to zero?
b. Does the GA always reach the optimal solution?
c. How about if it is set too high (~75%)?
d. Explain the relationship between mutation rate and the balance between
exploration and exploitation.
7.
In the “Parameters of
GA” example, set the mutation rate to 1 and the crossover rate to 0.
Compare the GA under this set of parameters with the GA under the default set
of parameters. In what way does the movement of the population over the search
space differ in the two cases? What causes the difference in population
movement? What does this suggest about the role of mutation?
8.
In section VIII where
you can define your own function, test the optimizer’s performance on the
q
The fitness function
for the 1-1-1 neural network is as follows, and can be pasted directly into the
optimizer (full details of the derivation are provided for interest for the
mathematically-minded here)
(1/(1+e^(-0.5*y)))^2 +(1-1/(1+e^(-(1/(1+e^(-x)))*y)))^2
a.
Run 10 trials. How
many times does the optimizer get stuck in the local minima?
b.
Under what conditions
would you expect a trial to get stuck in the local minima?
c. Test the optimizer’s performance on
the And and Or neural
networks. Do they have local minima? Why
or why not?
q
AND-network (full
details of the derivation are here)
(1/(1+e^(-x)))^2 + 2 *
(1/(1+e^(-(y+x))))^2 + (1-(1/(1+e^(-(2*y+x)))))^2
q
OR-network (full
details of the derivation are here)
(1/(1+e^(-x)))^2 + 2 *
(1-(1/(1+e^(-(y+x)))))^2 + (1-(1/(1+e^(-(2*y+x)))))^2
9.
a. What makes a function easy or difficult for the GA to solve?
b. (Challenge Question – optional)
In the “GA Example (2D func.)”,
formulate a function that is difficult for the GA (in its default settings) to
optimize. Describe your function and why it is a difficult optimisation
problem. How many generations does it take to reach a global optimum (assuming
that you can tell when it does)?
10.
Part B. Biomorphs. Load the biomorph demo from http://www.hedweb.com/biomorph/biomorph.htm
In the demo, the top biomorph is
the prototype, and the 5 examples below it are variations. Each time you click
on a variation, it is moved to the top position, and five new variations are
created.
a.
Choose the most
interesting one of the five, and repeat several times. Describe the shape you
have evolved.
b.
Try to evolve (i) a classic tree (ii) a bushy shrub (iii) an insect-like
shape
c.
What happens if you
choose a random one repeatedly?
[optional] There are many other
demos of biomorphs on the web. If you are interested,
more details of the algorithm can be found at http://users.iol.it/acnard/biomorph.html