
Graphinder series articles
 Graphinder – Project Introduction
 Graphinder – I don’t need this covered…
 Graphinder – Minimum Vertex Cover problem
 Graphinder – Simulated Annealing algorithm
 Graphinder – Code review yourself
 Graphinder – Genetic Algorithm – Introduction
 Graphinder – Genetic Algorithm – Selection
 Graphinder – Genetic Algorithm – Crossover
 Graphinder – Genetic Algorithm – Mutation
 Graphinder – Genetic Algorithm – Wrap up
 Graphinder – Monthly Progress Report – March
 Graphinder – Async IEnumerable with Rx.Net and IObservable
 Graphinder – Reporting progress with Rx.Net
 Graphinder – TDD and starting from red
 Graphinder – Domain models vs Persistence models
 Graphinder – Queries and Commands vs Repository pattern
 Graphinder – Encapsulating persistence layer
 Graphinder – Solution changes and nuget hell
 Graphinder – Monthly Progress Report – April
 Graphinder – Application architecture
 Graphinder – Resources planning on Azure
 Graphinder – Quick summary and what next
 Quick thoughts after Daj Sie Poznac 2016 finals
About Simulated Annealing
Simulated Annealing is an algorithm based (as many, many other algorithms) on everyday life and observation of nature. In this particular case, the idea was to somehow mimic the process of annealing in metallurgy: to heat up system to some initial temperature and then step by step, work on it, cooling it slowly in a process.
Simulated Annealing is great solution, if we’re aiming for global optimum (best solution) instead of accepting local optima.
Algorithm depending on a temperature of system will be either likely to reject even high scored solutions (if temperature is high) or will stick to its current solution, provided that no better one was provided (if temperature is low).
There’s awesome animation on Wikipedia of how the process actually looks over the cooling process and as I don’t think I could come up with anything better, I’ll support myself with it:
Source: Simulated annealing – Wikipedia
As you can see, the lower the temperature of the system, the less likely algorithm will accept other, worse solution. On the other hand, when temperature is high, algorithm keeps on accepting almost anything that comes up with.
Note: accepting solution worse than current is important, if we don’t want to get stuck in local minimum. It might look as best at first, but we might later find out it was not globally best! :)
Implementation side
Algorithm definition
For any algorithm, including Simulated Annealing, there’s an interface IAlgorithm
defining it’s behavior:
1 2 3 4 5 6 7 8 9 10 
public interface IAlgorithm { IProblem Problem { get; } long ProcessorTimeCost { get; } int CurrentSolution { get; } Graph Graph { get; } void LaunchAlgorithm(); bool CanAcceptAnswer(ICollection<Node> proposedSolution); bool CanContinueSearching(); } 
Any Algorithm
will attempt to find solution for a Problem
by continuously searching for a solution better than CurrentSolution
on a Graph
. Of course, depending on its acceptance algorithm, it CanAcceptAnswer
as a new one or just reject it. Once we LaunchAlgorithm
, algorithm won’t stop while it CanContinueSearching()
. Second most important thing besides finding a solution to our problem is to know what actual ProcessorTimeCost
was, so that we can compare different strategies for our algorithm and perhaps, compare it even with other algorithms we have already implemented or imported to our application.
Algorithm logic
Besides everything we defined in our IAlgorithm
, there’s actually couple of properties that are characteristic for Simulated Annealing algorithm.
1 2 3 4 5 6 7 8 9 
public class SimulatedAnnealing : Algorithm { (...) public double InitialTemperature { get; private set; } public double CurrentTemperature { get; private set; } public double CoolingRate { get; private set; } public ICoolingStrategy CoolingStrategy { get; private set; } (...) } 
First of all, we’ve been talking all the time about the temperature! So we have InitialTemperature
on which we’ll start everything and CurrentTemperature
that will keep on decreasing over and over until algorithm stops. How much system will cool on single step is defined by CoolingRate
and how actually process of picking solution will look like is up to CoolingStrategy
we’ve chosen for algorithm.
Currently then only implemented cooling strategy for Simulated Annealing is AllRandomCooling
. In a simple manner: it will keep on rolling for random node from Graph until solution it’s building up is a correct solution to IProblem
:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 
public class AllRandomCooling : ICoolingStrategy { public long Cool(IAlgorithm algorithm, Action coolingAction) { if (algorithm == null) throw new ArgumentException(nameof(algorithm)); if (coolingAction == null) throw new ArgumentException(nameof(coolingAction)); var startTime = DateTime.Now.Ticks; while (algorithm.CanContinueSearching()) { //Pick random node from graph and keep on adding them to solution until correctness criteria is met HashSet<Node> proposedSolution = new HashSet<Node>(); while (!algorithm.Problem.IsSolutionCorrect(proposedSolution)) { proposedSolution.Add(algorithm.Graph.GetRandomNode()); } //Accept the answer if algorithm allows if (algorithm.CanAcceptAnswer(proposedSolution)) algorithm.Problem.SetNewSolution(proposedSolution); //Cool system coolingAction.Invoke(); } return DateTime.Now.Ticks  startTime; } } 
CoolingStrategy will keep on searching for the solution, until it can continue. Simulated Annealing by definition allows the process to go on until the iron is hot ie. until the temperature does not reach an extreme minimum:
1 2 3 4 5 6 
public double MinimalTemperature { get { return 0.001f; } } public override bool CanContinueSearching() { return CurrentTemperature > MinimalTemperature; } 
One last thing that we needed implemented is how algorithm decides if it can accept proposed solution.
Let me note that mentioned implementation is meant to be partly replaced by IProblem.SolutionFitness
. Common code smell (switch that might likely grow up in a future) will be removed on upcoming TO DO’s session. :)
One thing worth noting here is the calculation part, where you can easily notice how Math.Exp
result will significantely change during cooling process:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
private double AcceptanceProbability(int energy, int newEnergy) { if (_problem.Criteria == ProblemCriteria.BiggerIsBetter) { //Accept if it's better than current one if (newEnergy > energy) return 1.0; //Calculate probability otherwise return Math.Exp((newEnergy  energy) / CurrentTemperature); } else { //Accept if it's better than current one if (newEnergy < energy) return 1.0; //Calculate probability otherwise return Math.Exp((energy  newEnergy) / CurrentTemperature); } } 
As previously, all of the code is available on my GitHub. Link leads to subfolder containing anything concerning Simulated Annealing algorithm and also everything that was mentioned in this article:
Localwire.Graphinder.Core/Algorithms/SimulatedAnnealing/ @ GitHub.com
Are you going to prepare Async versions of methods in IAlgorithm?
And I suggest you to use “Stopwatch” instead of “DateTime.Now.Ticks” – it has higher resolution when hardware / OS supports highresolution performance counter :)
Every algorithm will go async in one way or another. I’m thinking over possible ways that fit my solution and you’ll probably see some reactive programming with Rx.Net up here. :)
As for ‘Stopwatch’, I’m just waiting for your implementation. :P