Skip to content

Include Simulated Annealing functionality

Summary

The new feature should introduce a Simulated Annealing algorithm as new optimisation functionality.

Component

Part of the optimisation component.

Expected Behavior

Simulated Annealing works as follows:

  • Choose a first candidate s (w.r.t. some initialisation strategy)
  • Choose a neighbour s' (w.r.t. some neighbour-choosing strategy)
  • For this neighbour, compute P(f(s), f(s'), T). (w.r.t. some chosen probability acceptance function)
  • if P >= random(0,1), replace s with s' and update temperature (w.r.t. some chosen temperature scheme)
  • else try next neighbour.
  • Repeat until termination criterion is fulfilled or no neighbours exceed original candidate.

Initialisation strategy See HillClimbing. Either we want a random one, read one from a file or define one in the config file.

Neighbour-Choosing Strategy See HillClimbing. For now, assume a cardinal scale, so a clear order is given, and we only need a step size value. There will be the need for defining neighbour-functions for discrete (non-ordered) values later on.

Probability Acceptance Function For now, please use: If (f(s) >= f(s')), P=1; else e(-(f(s)-f(s'))/T), when assuming a maximising problem. We'd like to extend that later on.

Temperature Scheme Needs two aspects: Initial Temperature (to be configured in the file) and temperature decrease function. For the later, it should be possible to either define one's own or choose of the following (might be extended in the future):

  • linear decrease: T(k) = T_init -(k* T_init/#iterationSteps)
  • geometric decrease: T(k) = T(k-1)* percentage
  • arithmetic decrease: T(k) = T(k-1)-t(k), with T(0)=T_init and t(k) = t(k-1) - rate --- please note, the difference between t and T!

Termination Criterion Configurable. Can be number of iterations, number of function evaluations. For now, number of iterations is enough.

Use Case

Simulated Annealing is still a simple approach as it contains only one individual. However, it already includes a probability decision mechanism which allows escaping local optima.

Possible approach

See Repo of MY and description above.

Contact Person

(Link a person/ people, that can answer questions about this issue, e.g. yourself)

/cc @berber