G53DSM Coursework 1 Lab 3
Simulated Annealing and
Cooling Schedules
1 INTRODUCTION
Simulated annealing is another meta‐heuristic which we can use to escape from local optima to
broaden the search of the search space. Simulated annealing is a stochastic move acceptance criteria
which means that rather than accepting or rejecting moves outright based on the quality of solutions,
a probability is assigned to the acceptance of the candidate solution in each move.
This probability is determined from the equation below, where is the probability that a move is
accepted, is Euler’s constant, Δ is the difference between the solution qualities of the current
solution and candidate solution, and is the temperature of the annealing schedule from with
simulated annealing was inspired:
You have already been given excerpts of two papers which use simulated annealing to solve various
problems. Each paper uses a slightly different way of calculating this temperature parameter . In this
lab exercise, you are asked to first implement simulated annealing, and then experiment with different
temperatures and cooling schedules to devise a simulated annealing meta‐heuristic search method
for solving satisfiability problems. You will be given the same SAT instance #1 to solve as good as you
can in 20 seconds as with the previous labs to allow for comparison.
2 NOTES/HELP
Since our heuristic is a single random mutation, copying solutions on every iteration greatly increases
the execution time of the meta‐heuristic, despite the actual iteration count being the same as previous
labs, for me each run took about 8 times longer.
The power of Euler’s constant can be calculated in Java as shown below:
. exp ;
It is easy to fall into this trap, but remember we cannot divide by zero and thus the temperature value
should never be equal to 0 (or if it does, then program defensively by returning 0).
3 DELIVERABLES
Deadline at the end of the lab:
1) Simulated Annealing source code(s) (30 marks)
2) Target qualities (20 marks)
Deadline Tuesday 3rd March at 5pm:
3) Report (50 marks)
3.1 SIMULATED ANNEALING SOURCE CODE
This includes the AbstractSimulatedAnnealing.java file along with any extra Classes that were made
for each of the different cooling schedules.
3.2 TARGET QUALITIES
In the previous lab, this caused a few problems since only a few people got the actual implementation
correct and therefore many people could not reach the targets. The same scheme will be used as
before, selecting the best solution quality and ranking it against some targets, and the overall
percentage of the marks will be significantly reduced and reassigned to the report.
22 20
25 10
25 0
Note: the best score (22) was obtained though very limited experimentation and should hopefully
not be too hard to achieve during the lab given that you have analysed the pre‐lab material and
think carefully about the parameter settings before trying them.
At the end of the lab, a file called [Forename]_BestResult.txt should be submitted to the coursework
area cw1lab3a and should contain the binary string of the best solution found. The cooling schedule
and parameter settings should be included in the report.
3.3 REPORT
The report should not exceed more than 500 words.
In this report, we are looking for the following:
Literature
Short discussion, citing relevant papers, of different cooling schedules
Equally short discussion of how the search process of SA differs from that of ILS
o Think about the types of move acceptance (see tutorial/lecture slides)
o How does the move acceptance classification of ILS differ from that of SA and what
advantages (or disadvantages) might these incur?
Experimental Setup (SA implementation)
The cooling schedule and settings used in your best (from the lab) simulated annealing
algorithm
There is no need to talk about the actual setup of the experimentation which is already
handled by the framework, only what you have done.
Results
Analysis of the fitness trace and how it compares to those from previous labs, discussing the
effects of the cooling schedule and temperature at strategic points.
Statistical comparison of your best (from the lab) simulated annealing cooling schedule with
the one from the lecture notes given 20 seconds (can be ran after the lab). Note, no extra
marks are awarded here for comparing the “best” cooling schedule possible to the one from
the lecture.
o 1.0
o 0.99
o 0.99 where is iteration and 0
Statistical comparison of your best SA cooling schedule (from the lab) with your best iterated
local search method from the previous lab
4 REMINDER
Plagiarism is an academic offense. Plagiarism is passing off someone else's work, whether intentionally
or unintentionally, as your own for your own benefit. We are aware that plagiarism was likely present
in the previous coursework and subsequent attempts will be dealt with in accordance with the
universities rules.
