Class SimulatedAnnealing<S extends Solution<S>>

java.lang.Object
io.github.nhtc2005.alns.acceptance.SimulatedAnnealing<S>
Type Parameters:
S - the solution type
All Implemented Interfaces:
AcceptanceCriterion<S>

public final class SimulatedAnnealing<S extends Solution<S>> extends Object implements AcceptanceCriterion<S>
Accepts candidates probabilistically using simulated annealing for minimization.

For objective difference \(\Delta = f(s_{\mathrm{candidate}}) - f(s_{\mathrm{current}})\) and temperature \(T\), the acceptance probability is:

\[ P(\mathrm{accept}) = \exp\!\left(-\frac{\max(0, \Delta)}{T}\right). \]

Each evaluation uses the current temperature, then cools it, regardless of acceptance. Temperature is bounded below by the configured end temperature; reaching it does not stop the search. Instances maintain mutable temperature state and must not be shared by concurrent runs.

  • Constructor Details

    • SimulatedAnnealing

      public SimulatedAnnealing(double startTemperature, double endTemperature, double step)
      Creates a criterion with exponential cooling.
      Parameters:
      startTemperature - the finite positive initial temperature; at least endTemperature
      endTemperature - the finite positive minimum temperature
      step - the cooling factor in (0, 1)
      Throws:
      IllegalArgumentException - if a temperature or step is invalid
    • SimulatedAnnealing

      public SimulatedAnnealing(double startTemperature, double endTemperature, double step, SimulatedAnnealing.CoolingMethod method)
      Creates a criterion with the specified cooling schedule.
      Parameters:
      startTemperature - the finite positive initial temperature; at least endTemperature
      endTemperature - the finite positive minimum temperature
      step - the finite positive decrement for linear cooling, or factor in (0, 1) for exponential cooling
      method - the cooling method
      Throws:
      IllegalArgumentException - if a temperature or step is invalid
      NullPointerException - if method is null
  • Method Details

    • shouldAccept

      public boolean shouldAccept(AcceptanceContext<S> context)
      Evaluates acceptance, once per iteration, including for infeasible candidates and new bests.

      Implementations may update their own state but must not modify the solutions in the context.

      Uses the temperature before cooling and advances the cooling schedule once per call.

      Specified by:
      shouldAccept in interface AcceptanceCriterion<S extends Solution<S>>
      Parameters:
      context - the non-null acceptance context
      Returns:
      true to accept the candidate, subject to the solver's feasibility checks
    • reset

      public void reset()
      Restores the temperature to its configured initial value.
      Specified by:
      reset in interface AcceptanceCriterion<S extends Solution<S>>
    • getStartTemperature

      public double getStartTemperature()
      Returns the configured initial temperature.
      Returns:
      the configured initial temperature
    • getEndTemperature

      public double getEndTemperature()
      Returns the configured minimum temperature.
      Returns:
      the configured minimum temperature
    • getStep

      public double getStep()
      Returns the linear decrement or exponential cooling factor.
      Returns:
      the linear decrement or exponential cooling factor
    • getMethod

      Returns the configured cooling method.
      Returns:
      the configured cooling method
    • getTemperature

      public double getTemperature()
      Returns the temperature for the next acceptance evaluation.
      Returns:
      the temperature for the next acceptance evaluation
    • autofit

      public static <S extends Solution<S>> SimulatedAnnealing<S> autofit(double initialObjectiveValue, double worse, double acceptProbability, long numIterations)
      Fits exponential cooling with an end temperature of 1.0.

      See autofit(double, double, double, long, double, CoolingMethod) for the fitting formulas and validation rules.

      Type Parameters:
      S - the solution type
      Parameters:
      initialObjectiveValue - the finite non-zero initial objective; may be negative
      worse - the worsening fraction in (0, 1]; 0.1 means 10% of the objective magnitude
      acceptProbability - the initial probability of accepting that worsening, in (0, 1)
      numIterations - the positive number of cooling updates
      Returns:
      a criterion initialized with the fitted temperature and step
      Throws:
      IllegalArgumentException - if inputs are invalid or the fitted temperature or step is invalid
    • autofit

      public static <S extends Solution<S>> SimulatedAnnealing<S> autofit(double initialObjectiveValue, double worse, double acceptProbability, long numIterations, SimulatedAnnealing.CoolingMethod method)
      Fits the specified cooling method with an end temperature of 1.0.

      See autofit(double, double, double, long, double, CoolingMethod) for the fitting formulas and validation rules.

      Type Parameters:
      S - the solution type
      Parameters:
      initialObjectiveValue - the finite non-zero initial objective; may be negative
      worse - the worsening fraction in (0, 1]; 0.1 means 10% of the objective magnitude
      acceptProbability - the initial probability of accepting that worsening, in (0, 1)
      numIterations - the positive number of cooling updates
      method - the cooling method
      Returns:
      a criterion initialized with the fitted temperature and step
      Throws:
      IllegalArgumentException - if inputs are invalid or the fitted temperature or step is invalid
      NullPointerException - if method is null
    • autofit

      public static <S extends Solution<S>> SimulatedAnnealing<S> autofit(double initialObjectiveValue, double worse, double acceptProbability, long numIterations, double endTemperature)
      Fits exponential cooling with the specified end temperature.

      See autofit(double, double, double, long, double, CoolingMethod) for the fitting formulas and validation rules.

      Type Parameters:
      S - the solution type
      Parameters:
      initialObjectiveValue - the finite non-zero initial objective; may be negative
      worse - the worsening fraction in (0, 1]; 0.1 means 10% of the objective magnitude
      acceptProbability - the initial probability of accepting that worsening, in (0, 1)
      numIterations - the positive number of cooling updates
      endTemperature - the finite positive minimum temperature
      Returns:
      a criterion initialized with the fitted temperature and step
      Throws:
      IllegalArgumentException - if inputs are invalid or the fitted temperature or step is invalid
    • autofit

      public static <S extends Solution<S>> SimulatedAnnealing<S> autofit(double initialObjectiveValue, double worse, double acceptProbability, long numIterations, double endTemperature, SimulatedAnnealing.CoolingMethod method)
      Fits a cooling schedule to an initial acceptance probability.

      For initial objective \(f_0\), worsening fraction \(w\), and target probability \(p\):

      \[ \Delta = w|f_0|, \qquad T_0 = -\frac{\Delta}{\ln p}. \]

      The candidate objective used for fitting is \(f_0 + \Delta\), including when \(f_0\) is negative. A zero initial objective cannot define a relative worsening and is rejected.

      For \(N\) evaluations and minimum temperature \(T_e\), the fitted step is:

      \[ d = \frac{T_0 - T_e}{N} \quad\text{(linear)}, \qquad r = \left(\frac{T_e}{T_0}\right)^{1/N} \quad\text{(exponential)}. \]

      The temperature reaches \(T_e\) after \(N\) updates, subject to floating-point rounding. The fitted \(T_0\) must be strictly greater than \(T_e\).

      Type Parameters:
      S - the solution type
      Parameters:
      initialObjectiveValue - the finite non-zero initial objective; may be negative
      worse - the worsening fraction in (0, 1]; 0.1 means 10% of the objective magnitude
      acceptProbability - the initial probability of accepting that worsening, in (0, 1)
      numIterations - the positive number of cooling updates
      endTemperature - the finite positive minimum temperature
      method - the cooling method
      Returns:
      a criterion initialized with the fitted temperature and step
      Throws:
      IllegalArgumentException - if inputs are invalid or the fitted temperature or step is invalid
      NullPointerException - if method is null