Graphinder – Simulated Annealing algorithm

About Simulated Annealing

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:

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.

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:

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:

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:

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:

2 thoughts on “Graphinder – Simulated Annealing algorithm”

  1. 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 high-resolution performance counter :)

  2. 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

Leave a Reply

Your email address will not be published. Required fields are marked *