EECS 391/491: PROBLEM SET #4
Reading:
- R&N: 4.3, box on page 120; 5.1, 5.2 (only through "Forward Checking"), 5.3
The answers to the following four problems should be typed:
Problem 4.1 [5 points]
Problem 4.11 of R&N, parts (a), (c), and (d) only.
Problem 4.2 [5 points]
[Nilsson] Determine what the words "genotype" and "phenotype" mean in (biological) evolutionary theory.
How might these words be used to describe genetic algorithms?
Problem 4.3 [10 points]
[Nilsson] Specify fitness functions for use in evolving agents that
(1) control an elevator, (2) control stop lights on a city main street.
Problem 4.4 [10 points]
Problem 5.5 of R&N, part (b) only. In formulating your answer, consider the definition of CSPs at the
bottom of page 137 (and the map-coloring problem formulated in paragraph 1 of page 138).
This problem requires hand calculation and need not be typeset:
Problem 4.5 [20 points]
Problem 5.6 of R&N. Record the steps and the reasoning/method behind them.
Does min-conflicts make sense for this type of problem?
The following two problems require programming:
Problem 4.6 [25 points]
Repeat the one-dimensional optimization experiment from the eHandout
of Lecture #7. Specifically, maximize
F(x) = 4 + 2x + 2 sin(20x) - 4 x^2
on the interval [0, 1] using fitness-proportional selection
(aka roulette selection) of
individuals (points of the form 0.01*k, k= 0, ..., 100)
and simple mutation
(x-epsilon with probability 0.3, copy with probability
0.4, x + epsilon with probability 0.3). You may use epsilon=0.01.
Use at least N=10 individuals in your population.
Report N and comment on your experiments/results.
Turn in documented code.
Repeat the above, but add a crossover operator that
is a convex combination of two individuals,
x and y:
a x + (1-a)y, for 0 <= a <= 1
Problem 4.7 [25 points]
Consider the 8-queens Problem from R&N.
Here, you will solve 8-queens using two different
search algorithms:
- Random-restart hill-climbing (RRHC; pp. 113-4 of R&N)
- Simulated annealing (SA; p. 115 and Figure 4.14 of R&N)
In each case, you will be maximizing "fitness," defined
as the number of non-attacking pairs of queens
(p. 117 of R&N), which is 28 minus "the number of pairs of queens that are attacking
each other, either directly or indirecty" (p. 112 of R&N). Thus, when you find a
configuration/state with fitness = 28, you have found a solution.
- Implement each algorithm above. In each case, write your algorithm so that it
exits as soon as a solution is found, prints the solution (as a string of digits
like those depicted in Figure 4.15 of R&N), and prints the total number of fitness
evaluations required from the start of the algorithm.
Your simulated annealing program should accept an arbitrary cooling schedule.
- Test your routines enough to convince yourself that they work and that
solutions are being found appropriately. (Do not report on this.)
- You will gather statistics regarding the operation of the two algorithms,
using different parameters for the simulated annealing search
(as discussed below; read through before implementing). Record
each algorithm's performance by running each algorithm 100 times (from different
random starting positions/populations) and report only the average
of the number of evaluations until a solution is found.
For SA,
use a starting temperature T0 and a cooling schedule that sets
Tt = a Tt-1 on the t iteration of the algorithm (see Figure
4.14 of R&N). You must try T0=30 and a=0.998.
Try at least one other schedule (by changing
parameters or choosing some other cooling function; your choice).
Turn in your code and a table summarizing all your results.
Always note both the algorithm and the different parameters/options used.
Recapping the above, your table should have at least 3 rows (1 for RRHC
and at least 2 for SA).
Note::
I don't expect you to program this from scratch.
This problem is much, much easier if you look at or use the
code that is already available:
Also, note that PS#5 will also use the 8-queens problem in an effort to amortize
your time and effort.
Problem G4.1 [20 points]
Read Karl Sims' article "Evolving Virtual Creatures", SIGGRAPH 1994
(a link appears on the course webpage).
Now, consider the vacuum cleaner robot of Section 3.6 of R&N.
Explain how you would use evolutionary and/or stochastic search to create
a program that maximizes its performance (assume the world
to be an arbitrary grid, so "turn 90 degrees" and "move forward"
might be useful primitives). Specifically,
- What is the representation?
- Explain how you would define the mutation and crossover operators
for evolutionary search.
- How would you define the neighborhood operator (specifying
which points should be looked at in choosing a "ascent" direction) in
the general global optimization framework?
Created: 2008-02-04.
Modified: 2008-02-04.