This assignment was NOT given on 24 February 2009. (I changed my mind and gave a modified assignment!)
Question 1: Finish your work on a program that uses simulated annealing to minimize a function f(x) over an interval [A,B].
Use the function myf.m as the function to be minimized over the interval [0,7].
Your program should start with a random initial value x1 that is inside the interval, and store the function value f1=f(x1). Each step of your procedure considers a new value x2 as a possible replacement for x1. Generate x2 as another random value in [0,7].
Evaluate f2=f(x2). If f2 < f1, then immediately replace x1 by x2.
However, even if f2 > f1, we might choose x2! Whether or not we do this depends on the "temperature" and on how much greater f2 is than f1. The details of how to do this are outlined in the project writeup. Suggested values for the inital temperature T and the temperature reduction factor alpha
Run your simulated annealing program until it has made 1,000 updates to x1. Every time you update, store the values of x1 and f1. When you have reached 1,000 updates, make a plot of the x values versus the f values. This will show us how rapidly the function is decreasing.
1A) Plot the 1000 x values versus the f values that represent the successive candidates for the minimizer (even though, with simulated annealing, the function values can increase sometimes). This will show us how rapidly the function is decreasing.
Question 2: Write a program that seeks a minimizer for a traveling salesperson problem. We'll call this program the "basic" version, because it will NOT use simulated annealing.
Let path be a list of the cities, which represents an itinerary for the traveling salesperson.
Write function m = mileage ( path ) that returns the mileage corresponding to the given path. Since this is a round trip, you need to remember to include the cost of returning from the last city to the first one! The entire exercise is based on seeking a round trip for which this mileage function is close to the minimum.
To get started, take city position data from the file lau15_xy.txt. Your first guess for path can be simply [ 1, 2, 3, ..., 15 ]. What is the total mileage for this path?
Given a current round trip, we will try to find a better round trip by considering, one at a time, simple modifications. For our work, we will consider two kinds of changes:
To implement reversals, you will need a function that chooses a pair of cities at random from a total of city_num.
function [ i, j ] = random_pair ( city_num )How do you guarantee that the i and j are distinct? How do you ensure that every pair of cities has an equal chance of being picked?
Now write a function called reversal which computes a new itinerary p2
based on the current itinerary p and the reversal cities i through j.
Inside your function, you might write this:
p2 = p;
p2(i:j) = p2(j:i); <-- NOT correct!
which is almost correct, except that p(i:j) only
makes sense to MATLAB if i is less than j. So the
way I have written this expression, either p(i:j) of p(j:i)
won't make sense. You can fix this!
To implement transfers, you will need a function that chooses three cities at random from a total of city_num.
function [ i, j, k ] = random_trio ( city_num )It's actually reasonable to allow i and j to be equal, but we certainly need k to be distinct!
Now write a function called transfer which computes a new itinerary p2
based on the current itinerary p, the transfer cities i through j
and the transfer site k.
Inside your function, you might write this:
q1 = p(1:i-1);
q2 = p(i:j); <-- (assuming I is less than J!)
q3 = p(j:city_num);
which is almost correct, except that p(i:j) only
makes sense to MATLAB if i is less than j. So the
way I have written this expression, either p(i:j) of p(j:i)
won't make sense. You can fix this!
Try to improve your path simply by considering random pairwise switches of cities. But only change the path if the switch reduces the mileage. Your program needs a way to know how to stop. You can start by restricting your program to trying 1,000 random switches. It's hard to know if that value is too small. If your program is still able to stumble across significant improvements, you will want to increase the number of random switches you consider.
What is the estimate for the shortest round trip that your program finds for each of the following sets of cities?
Question 3: Try to improve the program you wrote for question 2 by including simulated annealing.
It makes sense for the temperature T to start out as the largest distance between any pair of cities. We can let the reduction factor ALPHA be 0.5, at least to begin with. It's not clear how many steps you should take at a given temperature. Perhaps a reasonable first guess would be 100; it's not clear how many times you can reduce the temperature, but a reasonable first guess might be 5. We can adjust these values if, watching the program, we see whether we could get more improvement by taking more steps.
What is the estimate for the shortest round trip that your program finds for each of the following sets of cities?
Question 4: Permutations.
A permutation can be thought of as a rearrangement of the integers, or as a mapping that "sends" the value I to the value P(I). A permutation is often described simply by listing the "scrambled" values. Thus, we might write a sample permutation as (3,4,1,5,2). This really means that the value that was at 1 went to position 3, the value that was at 2 went to position 4, and so on.
When a permutation rearranges the integers from 1 to N, we say that the order of the permutation is N.
4A) write a function that computes a random permutation of the integers from 1 to N. Test your program by generating random permutations of order 4. Does every possible permutation show up about as often as it should?
If it happens that I=P(I), we say that I is a fixed point of the permutation. If a permutation has no fixed points, we say the permutation is a derangement.
Example: (5,1,4,2,3) is a derangement of order 5. (2,3,6,4,1,5) has 4 as a fixed point, so it is not a derangement.
Write a function that estimates the probability that a random permutation or order N will be a derangement. The function should examine TRIALS random permutations in order to estimate this probability:
function PROB = derangement_prob ( N, TRIALS )
PROB is simply the ratio formed by the number of derangements you found
divided by the number of trials.
4B) Compute a table of the derangement probabilities. Try to compute the chart for N from 1 to 15; see if your program can use a value of TRIALS that is at least 1000.
As a check, the exact value for N=7 is 0.36785713...
A permutation can be applied twice. Starting with I we get P(I). If we permute again, we get P(P(I)). For some permutations, P(P(I))=I for all I. These special permutations are called involutions. In an involution, each number either stays the same, or swaps places with another number, so doing it twice returns everything to the original state.
Example: (4,2,5,1,3) is an involution, because we have 2 as a fixed point, and pairwise swaps (1,4) and (3,5).
In MATLAB, if P is a permutation, then P(P) is the result of applying the permutation twice. To see if P is an involution, therefore, we simply need to compare P(P) to the vector 1:N as follows:
if ( p(p) == 1:n )
P is an involution!
end
4C) Compute a chart of the involution probabilities. Try to compute the chart for N from 1 to 10; for each value of N, you are reporting your estimate of the probability that a permutation of order N is an involution.
As a check, the exact value for N=7 is 0.0460317...
Question 5: One Chance in a Hundred?
You've made the king very angry, and he plans to execute you and your pals Biff and Clem. However, the king likes to think he's fair, so he's going to give you a chance to live. The king has a deck of 100 cards. Each card has a different (real) number written on it. Only the king knows what numbers are on the cards.
He comes to Biff's cell and tells him to pick one card from the deck and turn it over. If the number on that card is the highest value, then he will live. Biff picks a card, it's a loser, and he is executed. But he did have one chance in 100 of living, so that's pretty fair, at least the way the king thinks.
However, it wasn't very much fun. So the next day, when the king comes to Clem's, he's changed the game. He tells Clem that he is allowed to pick a card and look at it. He can either keep the card, or discard it and try again. In fact, he can have as many tries as he wants. (However, if he rejects the first 99 cards, then he is stuck with the last one.) Once he has chosen a card to keep, he shows it to the king, and if the number written on that card is the biggest one in the deck, Clem will live.
Clem decides on the following strategy: he will pitck the first card, look at it, and ALWAYS reject it. Then he will continue to pick until he reaches the first card that is bigger than the first card (or he reaches the end of the deck) and that will be the card he chooses to show to the king.
Write a program that simulates this process. Instead of labeling each card with a real number, we'll simply assume they are labeled 1 to 100. That makes it easy for us to tell the lowest card (1) from the highest (100). To represent the shuffled deck, choose a random permutation of 100 objects. Clem obviously wants to pick the biggest card, which we are representing as "100". Your program should look at the first entry in the permutation, P(1), and store that value as TEST. Then your program should consider successive entries P(2), P(3), and so on, until finding the first value P(I) that is bigger than TEST, and choose that card. If P(I) is actually equal to 100, then Clem lives.
5A) Do enough simulations of Clem's strategy to estimate his chances of survival.
Now it's your turn. You've come up with the following strategy. You are going to look at, and reject, the first 25 cards. Then you will choose the very next card which is larger than the maximum of the first 25 (and if no such card shows up, you end up with the last card in the deck) and this is the card you will show the king.
5B) What are your chances of survival under this strategy?
Your strategy is pretty good, but 25 is not the very best stopping point.
Question 6: Allen and Bob decide to fight a duel, but they only have one gun and one bullet. They load the gun and spin the chamber and after flipping a coin, decide that Allen will go first. Allen fires at Bob once. Unless Bob is shot, he gets the gun, spins the chamber and fires at Allen. They keep doing this until someone is shot.
You can actually work out the probabilities mathematically. However, write a program that simulates this duel. Have it run 10,000 simulations of the duel. Have it answer the following questions:
Carl and Delbert also fight a duel. They decide to try to make their duel more fair. Carl will get one shot at Delbert, but then Delbert gets two shots at Carl, then Carl gets three shots at Delbert, and so on. Of course, before each shot, the chamber is spun to randomize the position of the bullet. Modify your program to simulate this duel. Have it run 10,000 simulations of the duel.
I am giving you more than a week's worth of problems! However, you do have two weeks to work on them (and I am NOT counting spring break), since we will not be meeting on 3 March.