Cleveland State University
Department of Electrical and Computer Engineering
EEC
693/793, ESC 794
Special
Topics: Population-Based Optimization (4 credit hours)
Fall
2008
Homework
Assignments and Solutions
Homework 1 – Due Tuesday, September 2
1.
The Prisoner’s Dilemma problem
is described in the Wikipedia article http://en.wikipedia.org/wiki/Prisoner’s_dilemma.
Read the article, especially the “real-life examples” section. One good
strategy is for a player to cooperate on his first move, and thereafter to
select whatever strategy his opponent used on his previous move. This is called
the tit-for-tat strategy (“do unto others as they have done unto you”). Use the
payoff matrix in the Wikipedia article to find the total payoff after 10 games
of the tit-for-tat strategy playing against:
a.
A strategy that always defects;
b.
A strategy that always
cooperates (note that this is equivalent to a tit-for-tat strategy in this example);
c.
Anti-tit-for-tat, which is a
strategy that starts out by defecting and thereafter selects the opposite of
its opponent’s previous move;
d.
A strategy that makes random
moves.
Also calculate the opponents’ total payoff in each case.
2.
Generate 1000 random numbers
from a uniform distribution between 0 and 1. How many numbers are generated in
the four quartiles 0–0.25, 0.25–0.50, 0.50–0.75, 0.75–1.0?
Compare the actual counts with the expected counts. Is the difference within
reasonable limits? How can you quantify whether the difference is reasonable?
3.
Write a function that generates
a random integer between specified limits. Test the function by generating 1000
integers between 3 and 12. How many of each integer did you generate, and how
does this compare to the expected counts?
Homework 2 – Due Tuesday, September 9
1. Read Chapters 1-4 of the book Swarm Intelligence.
2. Write a formal, single-spaced, two- or three-page essay about one of the topics in Chapters 1-4 of the text. This is an open-ended assignment. Your essay could be mathematical, or philosophical, or narrative, or any other style, as long as you convince me that you read the text and have thought about it. Grammar, spelling, organization, and layout are all important. If you are not confident in your writing ability (or even if you are) see http://academic.csuohio.edu/simond/courses/ for resources that will improve your writing.
3. Code a binary genetic algorithm. Test it by finding the maximum of the function x10 for x between 0 and 1. Run the GA with the following parameters:
Hand in your code listing. Hand in a plot of maximum fitness and mean fitness (as a function of generation number) for a typical GA run.
Homework 3 – Due Tuesday, September 16
1.
(Goldberg)
Consider the fitness function f(x) = xn.
Suppose that a GA population is uniformly distributed over the domain 0 < x
< 1. Calculate the average fitness of the population. Compare numerical
values for n = 2 and n = 10. Calculate the probability of randomly selecting an
individual x such that f(x) > f0. Compare numerical values for n
= 2 and n = 10.
2.
What is
the coefficient of x25y75 in (2x–5y)100?
Give an exact symbolic answer, and also give a numerical answer to four significant
digits. (Hint: multinomial theorem)
Homework 4 – Due Tuesday, September 23
1. How could you prevent the occurrence of duplicate individuals in a genetic algorithm?
2. Plot the two-dimensional Ackley test function on the domain –30 < x1 < 30 and –30 < x2 < 30. See http://www.geatbx.com/docu/fcnindex-01.html for a description and equation of the Ackley test function.
3. Write
BBO code to minimize the 20-dimensional Ackley test function on the above
domain. Use the following parameters:
30 generations
50 islands
20 SIVs per island (one for each
independent Ackley variable)
9 bits per SIV
no mutation
emigration probability per SIV =
0.98, 0.96, …, 0.02, 0 (from best to worst island)
immigration probability per SIV =
0.02, 0.04, …, 1 (from best to worst island)
Perform migration at the SIV level, not at the bit level. Plot the minimum and
average cost as a function of generation number for a typical simulation.
4. Repeat problem 2 using a GA. With a GA we have individuals instead of islands, and genes instead of SIVs. Set the crossover probability to 1. GAs typically are designed to maximize a function. In order to minimize the Ackley function, you can instead maximize the cost function (25 – Ackley). This ensures that the cost function is positive. The global maximum of this modified function is 25.
5. Comment on the different performance that you see between the GA and BBO.
Homework 4 Solutions:
Homework 5 – Due Tuesday, September 30
1. Consider a BBO problem without mutation with s SIVs per island and n islands. Suppose each SIV is different so that there are a total of ns unique SIVs in the population. How many unique islands are possible after one generation if SIV order must be maintained during migration (i.e., an SIV is restricted to a single position in an island)? How many unique islands are possible if SIV order does not need to be maintained during migration? Compare numerical answers for the case n=50, s=20.
2. Under what special circumstances is an evolutionary program equivalent to an evolution strategy?
3. Read Chapter 5 of the book Swarm Intelligence. Write a formal, single-spaced, two- or three-page essay about one of the topics in Chapter 5 of the text.
Homework 6 – Due Tuesday, October 7
1. Start reviewing the literature to decide the topic of your term project. Find copies of papers that you can study and that you can base your research on. These have to be real papers – refereed conference or journal papers, not Internet sites, not blogs, and especially not Wikipedia pages.
2. Make copies for me of one or more papers that you decide to use for your research.
3. Give a 5–10 minute presentation discussing your research ideas. This will not be graded.
Homework 7 - Due Tuesday, October 28
1. Suppose the path representation of a six-city TSP is 1, 2, 3, 4, 5, 6. What is the adjacency representation of this path? What is the ordinal representation of this path? What is the matrix representation of this path?
2. Propose a mutation operator for the adjacency representation of a path that preserves the validity of the path.
3. Propose a mutation operator for the ordinal representation of a path that preserves the validity of the path.
4. Propose a mutation operator for the matrix representation of a path that preserves the validity of the path.
5. Propose a way that the ideas of PBIL could be combined with the matrix representation of a path to obtain a new way of solving the TSP.
Homework 8 – Due Thursday, November 13
1. Download GAMarkov.zip from http://sites.google.com/a/csuohio.edu/bbo/markov-analysis. Run GATheory.m for 20 mutation rates logarithmically evenly distributed between 0.1 and 0.0001. (Hint: see the Matlab function “logspace”.) Plot the probability of obtaining a uniform optimal population as a function of mutation probability, using a log scale for the x axis. Also plot the probability of obtaining a population with no optimal individuals as a function of mutation probability, using a log scale for the x axis.
2. How large does the mutation rate have to be before the uniform optimal population is not one of the three most probable populations? Answer to the nearest 0.01.
3. How large does the mutation rate have to be before v = [1 1 1 1] is the most probable population? Answer to the nearest 0.01.
4. Run GA simulations for mutation rates 0.0001, 0.001, 0.01, and 0.1. How well do the experimental probabilities compare with the theoretical probabilities?
5. Download BBOMarkov.zip and repeat questions 1–4 for BBO.
6. Comment on the differences that you observe between the GA and BBO.
1. Cleveland is a lovely place to live. Except for the winter weather. We never have two nice days in a row. If we have a nice day, then we are equally likely to have snow or rain the next day. If we have snow or rain, there is a 50% chance of having the same weather the next day and a 25% chance of having nice weather the next day. Use this information to create a three-state Markov transition matrix Q, where Q(i,j) is the probability of transitioning from state j to state i.
2. Over the long term, what is the percentage of rainy days, nice days, and snowy days?
3. Denote by x(j,n) the number of times that the the Markov chain is in state j after the first n transitions. The central limit theorem for Markov chains gives the following approximation for probability : clt.bmp : where q is the vector of the limiting probability distributions of the states. Use the above equation and Matlab’s “erf” function to approximate the probability that there will be no more than seven nice days in December.
4. Run 1000 simulations of Cleveland weather using your Markov matrix to estimate the probability that there will be no more than seven nice days in December. Hand in your software listing. Compare your central limit theorem answer with your simulation answer.
Department of Electrical and Computer Engineering
Last Revised: December 10, 2008
