Simulated Annealing in C#

Question

I am using simulated annealing to solve a cryptanalysis problem and I've hit a brick wall. I cannot for the life of me get my probability function to operate correctly, it either takes a worse solution too often (so I bounce around a score of 0.03 and 0.2) or it doesn't take it often enough (so I get stuck at 0.35). I've looked around the internet but I only come across examples where the problems involve finding the MINIMUM value....my problem needs to find the MAXIMUM value, worst score is 0, best is 1.

I need advice on Temperature and what probability function I should use.

Answer 1

The Simulated Annealing article on Wikipedia provides some general guidance on how SA temperatures should be initialized and decreased. Efficient selection of these parameters is normally very problem specific and may need to be identified through tedious trial-and-error.

Normally, optimization algorithms search for the minimum of the objective function. If you want to use such an algorithm as-is on your maximization problem, ask the optimizer to minimize the negation of your objective function. For example, let's say that the objective function for which you want to find the maximum is f(x)=score. You should then request the optimizer to minimize -f(x), i.e. -score (or, as you indicate in the comment above, 1-score).

There are lots of simulated annealing and other global optimization algorithms available online, see for example this list on the Decision Tree for Optimization Software. Unfortunately these codes are normally not written in C#, but if the codes are written in Fortran or C it is normally fairly easy to interface with these codes via P/Invoke.

If you do not require that the optimizer necessarily find the global optimum, there are also some derivative-free optimizers listed here. At least one of these codes is available in a C# version, namely BOBYQA (in fact, this algorithm has been adapted to C# by me :-).