CEE 509/COM S 572 Heuristic Methods for Optimization
Professors: C. Shoemaker, B. Selman
Assignment 2: Simulated Annealing with integer and binary variables
Date assigned: Friday, February 7, 2003 Date due: Friday February 14, 2003
Announcements: It is suggested that students sign up for the 4 credit option, which must be done by today 2/7 to avoid using a petition. If you are not sure how many credits you should take, see Prof. Shoemaker. The next installment of text (Chapter 3 and 4 on Genetic Algorithms and on Tabu Search) is expected to be available at Gnomen Copy on Eddy Street on Monday 2/10.
TA: Abbas Kermani, Office hours: Wednesday 1-2pm, 328C Upson Hall
NOTE: check the newsgroup and website regularly for hints or corrections, if any.
website: http://www.cs.cornell.edu/courses/cs572/
newsgroup: cornell.class.cs572
Reading: Chapter 2 (particularly sections 2.1, 2.2, & 2.4) of Iterative Computer Algorithms with Applications in Engineering, by S.M. Sait and H. Youssef.
Please note: The simulated annealing algorithm and metropolis procedure given on page 54 of the text (figures 2.3 and 2.4) are reprinted here with the corrections that were missing (this same information was posted on the newsgroup). You will implement these algorithms directly in the first problem.
Algorithm Simulated_annealing(S0, T0, a, b, M, Maxtime);
(* S0 is the initial solution *)
(* BestS is the best solution *)
(* T0 is the initial temperature *)
(* a is the cooling rate *)
(* b is a constant *)
(* Maxtime is the total allowed time for the annealing process *)
(* M represents the time until the next parameter update *)
Begin
T = T0;
CurS = S0;
BestS = CurS; /* BestS is the best solution seen so far */
CurCost = Cost(CurS);
BestCost = Cost(BestS);
Time = 0;
Repeat
Call Metropolis(CurS, CurCost, BestS, BestCost, T, M);
Time = Time + M;
T = aT;
M = bM;
Until (Time ³ Maxtime)
Return(BestS);
End (* of Simulated Annealing *)
Algorithm Metropolis(CurS, CurCost, BestS, BestCost, T, M);
Begin
Repeat
NewS = Neighbor(CurS); /* Return a neighbor from aleph(CurS) */
NewCost = Cost(NewS);
DCost = (NewCost - CurCost);
If (DCost < 0) Then
CurS = NewS;
CurCost = Cost(CurS); /* CORRECTION */
If NewCost < BestCost Then
BestS = NewS;
BestCost = Cost(BestS); /* CORRECTION */
EndIf
Else
If (RANDOM < e-DCost / T)Then
CurS = NewS;
CurCost = Cost(CurS); /* CORRECTION */
EndIf
EndIf
M = M - 1;
Until (M = 0)
End. (* of Metropolis *)
1. (4 points) SA Implementation:
Implement the simulated annealing algorithm (which is given above, with the corrections from the version in the text). Combine both the metropolis procedure and simulated annealing procedure in one MATLAB function file called SA.m. For RANDOM, use the MATLAB rand function. Have your program output the same matrix solution as the RW.m and RS.m functions from assignment 1. Thus the header of this function will read:
function solution = SA(sinitial, Tinitial, alpha, beta, Minitial, maxiter)
Submit a printout of the code. Be sure to examine it for bugs – it will affect the rest of your homework!
2. (5 points) SA Parameter Selection:
a) Say you know that the maximum Cost can be is 100, for some particular minimization problem and that Cost is not negative. In other words, if Jmin is the a lower bound on Cost in the search space, and Jmax the upper bound, then Jmax - Jmin = 100. What is the smallest value of Tinitial to use if you want ensure that the probability of accepting an uphill move on the first iteration, Pinitial, will be more than 0.4?
b) Write down a general expression for Tinitial in terms of Jmax, Jmin and Pinitial.
c) Now write down a similar expression for Tfinal, the final temperature, in terms of Jmax, Jmin, and Pfinal - the desired minimum probability of accepting an uphill move on the last iteration.
d) Suppose you have the following parameters for a simulated annealing algorithm:
Tinitial = 100, maxiter = 200, beta = 1, M = 1. What should the value of the cooling parameter alpha be if you want the temperature value Tfinal on the final (200th) iteration to be 0.01?
e) Write down a general expression for alpha in terms of Tinitial, Tfinal, maxiter, and M assuming beta = 1.
f) Now suppose that you have more information. You have picked an initial value of So and 5 points in its neighborhood NewSk, k=1,…,5. The values you have are Cost (So)=50, and Cost (NewSj) = 40, 60, 65, 75,45 for k=1,2,3,4,5, respectively. Using the method discussed in lecture on 2/5, how would you estimate a value of To that would give you an initial acceptance ratio of .9? What is the value of To from this estimate?
3. (11 points) Running SA:
Refer to the cost function and neighborhood function described in problem 3 of assignment 1 for this problem.
a) (1 pts) What is Jmax - Jmin?
b) (2 pts.) If beta = 1, M = 1, maxiter = 10, Pinitial = 0.4, and Pfinal = 0.01, what should Tinitial, Tfinal, and alpha be?
c) (3 pts.) Run SA on this problem 30 times, with the parameters obtained above.
Submit two plots:
(i) a plot of scurrent, sbest versus iterations for one sample run (e.g. the first run), and
(ii) a plot of the average of Jbest & Jcurrent (averaged over all 30 runs) vs. iterations. Compute and report the average and standard deviation of Jbest after 10 iterations. Also report the average CPU time it takes to do one run (use the MATLAB command cputime).
d) (4 pts.) Now experiment with a few values of Pinitial ranging from 0.01 to 0.4, while keeping Pfinal = 0.01, beta = 1, M = 1, maxiter = 10. For each value of Pinitial you will have to compute the corresponding Tinitial and alpha. Run the SA 30 times for each value of Pinitial, and submit a plot of the average and standard deviation of Jbest after 10 iterations with respect to Pinitial. Which value of Pinitial works best? Submit a plot of the average of Jbest and Jcurrent vs. iterations for this "best" value of Pinitial. (Hint: save yourself a lot of time by automating the process of picking different values of Pinitial and testing the algorithm for each value. You can do this by using a for-loop or a while-loop).
e) (1 pt.) Run SA 30 times with the parameters in part b, with one difference: change the exponential in the metropolis algorithm to a power of 2; i.e change the line
”If (RANDOM < e-DCost / T)Then” to the line “If (RANDOM < 2-DCost / T)Then”
Note that you will have to recompute Tinitial, Tfinal and alpha. Submit the same set of plots and numbers asked for in part c. What difference, if any, do you observe between the answer to part c and these results?
Please remember to submit all MATLAB code as well.
CS 572/CEE 509 Grading (summary of lecture transparency)
For students taking the course for 4 credits (doing one project), the distribution of grades is as follows:
homework 25%
mid-term exam 20% (tentative dates : around April 4)
group project 25%
final 30%
class participation and exceptional originality 5%.
If you want to take the course for 3 credits (see me). If you want to change from 3 to 4 credits, you will need to do this soon.
Homework policy: Students can talk to each other about the homework but they should
do the programs and write up the assignment on their own. Students should list the other students with whom they consulted on each assignment.
No prior background in the application area is required for the project. The project description, accompanying code and the lecture on the application will give you the background that you need.