Homework 2 Local Search and Game Playing

40 pts total
1 Genetic Algorithms [10 pts]
Recall that genetic algorithms represent a type of local search. Genetic algorithms have seen application in electronic chip design, a scheme known
as evolvable hardware. (Read a tutorial here: http://folk.uio.no/jimtoer/
fpl04 Torresen.pdf.) Under this scheme, chip layouts can be represented as a
series of bits that correspond to placement of the components (e.g., transistors) on this chip. Suppose we have a population of such chip arrangements,
as shown in Table 1. Further suppose our parent selection chooses chips 4
and 6, chips 1 and 3, and then chips 5 and 6, respectively, for three mating
events. Assume we know that crossover events happen after bits 2, 5, and 8
for the first, second, and third mating events, respectively.
Chip Number Bit String Representation
1 0100010011
2 1011000010
3 1101110010
4 0011110010
5 1000001101
6 0100110011
Table 1: Population of Chips Represented as Bit Strings
a) Follow the genetic algorithm as it’s laid out on the lecture slides. After
the three mating events take place, what will the new population be?
(Don’t worry about the fitness of the children.)
b) In addition to crossover events, mutations are often also used in genetic
algorithms. What are mutation events? Why are they used?
c) Why are genetic algorithms less susceptible to local optima than a standard hillclimbing algorithm?
22 Simulated Annealing [15 pts]
Consider the function f(x) = maxf4 − jxj; 2 − jx − 6j; 2 − jx + 6jg. It
has three peaks with one forming a unique global maximum. Perform 8
rounds of simulated annealing using 4 as your start point, and where the
temperature can be calculated from the function T(i) = 2(0:9)i, where i is
the iteration number. (E.g., for the first iteration, the temperature will be
T(1) = 2(0:9)1 = 1:8.) Show all of your work, including the current point,
the round temperature, and the probability of changing position given the
successor and the temperature.
Note: Recall that a random successor is generated on each iteration of
the simulated annealing. If this successor is better than the current state,
it is always accepted. If it is not better, it will still be accepted with some
probability. Use Table 2 to see which successor was \randomly" chosen at
each step, along with the \randomly" generated number which will help you
to decide if you should take a non-optimal successor at that step.
Iteration Number Random Successor Random Number Generated
1 3 0.102
2 1 0.223
3 1 0.504
4 4 0.493
5 2 0.312
6 3 0.508
7 4 0.982
8 3 0.887
Table 2: Successor States and Random Numbers
33 Game Playing [15 pts]
Figure 1: Question 3 Graph
a) Refer to Figure 1. Use the Minimax algorithm to compute the minimax
value at each node for the tree shown.
b) Refer once more to Figure 1. Use Alpha-Beta Pruning to compute the
minimax value at each node for the game tree shown, assuming children
are visited left to right. Show the alpha and beta values at each node.
Show which branches are pruned, if any.
c) Why do we use Alpha-Beta Pruning?
4