Implement Simulated Annealing

[abeham]

Simulated Annealing is one of the oldest metaheuristic and was described by Kirkpatrick et al in 1983 in an article in Science.

It is a trajectory-based metaheuristic that accepts uphill move in the beginning of the search. In later stages it is gradually restricting the search more and more to downhill moves (minimization problem). The next possible solution in each iteration is drawn from a neighborhood around the current solution, thus a neighborhood function is necessary. Typically this is similar to ES mutation. It has been proven that with the right annealing method and an infinite amount of time SA is able to find the global optimum. Practically this is irrelevant though and recently the importance of SA has decreased in the light of a multitude of other metaheuristics being developed and improved.

SA is a fast metaheuristic that is able to converge quickly into a local minimum. To achieve good solutions in short time it's possible to apply multistart techniques from different starting points. The annealing scheme and thus temperature curve, as well as the neighborhood function are crucial to its performance.

A general SA definition also includes an inner loop where, at the same temperature, multiple solutions are created. This can be as simple as a for loop or a maximum number of iterations for finding a better solution at each temperature.

[abeham]

done in r1289

The stop criterion regarding the temperature could still be parametrized to allow to set any minimium temperature as stop criterion. Currently it will abort when the temperature becomes 0 or less.

[abeham]

added minimum temperature as additional stop criterion in r1353

[swagner]

Milestone Iteration 2 deleted

[swagner]

Milestone Current deleted