rapid_solve::heuristics

Module threshold_accepting

Source
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, an Objective, an initial_threshold (ObjectiveValue) and a threshold_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§