Expand description
This module contains the ThresholdAcceptingSolver
implementing the
threshold accpeting metaheuristic.
- Starts with an initial solution and iteratively considers neighbors.
- An improvement is always accepted, but a worse neighbor is also accepted if the difference in objective value is below a given threshold.
- After every step, in which a worse neighbor is accepted, the threshold is reduced by a factor.
- The search stops after a certain number of iterations, after a certain time limit, or if the whole neighborhood is explored without any acceptance.
- The best solution seen during this process is returned.
- The threshold accepting heuristic is similar to the simulated annealing heuristic, but deterministic and without computing the acceptance probability (which often contains costly computations of exponential functions).
For an example, see the threshold accepting solver for the TSP.
Structs§
- The threshold accepting solver uses a
Neighborhood
, anObjective
, aninitial_threshold
(ObjectiveValue
) and athreshold_factor
(f32
between 0 and 1, e.g., 0.9) to find a good solution, while occasionally accepting worse solutions with the hope to not get trapped within a bad local minimum.
Type Aliases§
- Type for the
threshold_factor
.