Add optimisation algorithm Threshold Accepting

Summary

We need another optimisation algorithm. Threshold Accepting works as Simulated Annealing, but accepts non-superior solutions only if they're not worse than a given threshold (no probability). This threshold is reduced with increasing iteration number.

Component

search

Expected Behavior

The algorithm chooses a starting individual (according to some initialisation strategy ), and evaluates this according to the given optimisation function.

Then, it chooses a neighbour (according to some neighbour-finding strategy ) and evaluates the neighbour. If the neighbour has an improved optimisation value, it is accepted as new individual. If its optimisation has not improved but is inside a predefined threshold , it is still accepted. Then, the threshold is decreased via a decreasing-strategy (cf. Simulated Annealing ) . Otherwise, the algorithm chooses the next neighbour. If there are no more neighbours left, it terminates.

Otherwise, it terminates after reaching the termination criterion (e.g., max number of iterations).

Use Case

It is a different black-box optimisation algorithm, that can escape local optima and does not need to compute probabilities.

Possible approach

See description above.

Contact Person

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

/cc