Module org.cicirello.chips_n_salsa
Package org.cicirello.search.sa

Class SimulatedAnnealing<T extends Copyable<T>>

java.lang.Object
org.cicirello.search.sa.SimulatedAnnealing<T>
Type Parameters:
T - The type of object under optimization.
All Implemented Interfaces:
Splittable<TrackableSearch<T>>, Metaheuristic<T>, ReoptimizableMetaheuristic<T>, SingleSolutionMetaheuristic<T>, TrackableSearch<T>
public final class SimulatedAnnealing<T extends Copyable<T>> extends Object implements SingleSolutionMetaheuristic<T>
This class is an implementation of the metaheuristic known as simulated annealing. Simulated annealing operates via a mechanism modeled after the process of heating a metal and allowing it to cool slowly. Heating enables the material to be shaped as desired, while cooling at a slow rate minimizes internal stress thus enabling greater stability in the final state. Simulated annealing is a form of local search inspired by this process. It is controlled by a temperature parameter, T, that typically begins high, and is then typically cooled during the search (i.e., T usually decreases during the search). A component of the algorithm known as the annealing schedule controls how the temperature T changes during the search. Simulated annealing usually begins with a random initial candidate solution to the problem. Each iteration of simulated annealing then involves generating a random neighbor of the current candidate solution, and deciding whether or not to accept it (if accepted, the algorithm moves to the neighbor). The decision of whether or not to accept the neighbor is probabilistic. If the neighbor's cost is at least as good as the current cost, then the neighbor is definitely accepted. If the neighbor's cost is worse than (i.e., higher than) the current cost, then the neighbor is accepted with probability, P(accept) = e(currentCost-neighborCost)/T. This is known as the Boltzmann distribution. At high temperatures, there is a higher probability of accepting neighboring solutions than at lower temperatures. The probability of accepting neighbors is also higher for lower cost neighbors than for higher cost neighbors.

The constructors of this class enable specifying an annealing schedule via a class that implements the AnnealingSchedule interface, and the library provides all of the common annealing schedules, such as exponential cooling, and linear cooling, as well as a few less common, such as parameter-free versions of those schedules, as well as multiple adaptive annealing schedules. See the AnnealingSchedule documentation for a list of the classes that implement this interface. You may also implement your own annealing schedule by implementing the AnnealingSchedule interface.

You must also provide the constructors of this class with a mutation operator for generating random neighbors via a class that implements the UndoableMutationOperator interface, as well as an instance of a class that implements the Initializer interface to provide simulated annealing with a means of generating an initial random starting solution. The library provides several mutation operators for commonly optimized structures, as well as Initializer objects for commonly optimized structures. You are not limited to the implementations of UndoableMutationOperator and Initializer provided in the library, and may implement classes that implement these interfaces as necessary for your application.

This simulated annealing implementation supports an optional post-processing via a hill climber. To use this feature, you must use one of the constructors that accepts a hill climber as a parameter. This hill climber is then used to locally optimize the end of run solution generated by simulated annealing. This hill climber must implement the SimpleLocalMetaheuristic interface, such as the most commonly used hill climbers (steepest descent and first descent) implemented by the SteepestDescentHillClimber and FirstDescentHillClimber classes.

  • Constructor Details

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal, ProgressTracker<T> tracker)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal, ProgressTracker<T> tracker)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal, ProgressTracker<T> tracker, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems that runs a hill climber as a post-processing step.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal, ProgressTracker<T> tracker, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems that runs a hill climber as a post-processing step.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, ProgressTracker<T> tracker)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021).
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, ProgressTracker<T> tracker)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021).
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, ProgressTracker<T> tracker, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021), and which runs a hill climber as a post-processing step.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, ProgressTracker<T> tracker, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021), and which runs a hill climber as a post-processing step.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems that runs a hill climber as a post-processing step. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, AnnealingSchedule anneal, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems that runs a hill climber as a post-processing step. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      anneal - An annealing schedule.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021). A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021). A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      Throws:
      NullPointerException - if any of the parameters are null.

    • SimulatedAnnealing

      public SimulatedAnnealing(OptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for real-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021), and which runs a hill climber as a post-processing step. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

    • SimulatedAnnealing

      public SimulatedAnnealing(IntegerCostOptimizationProblem<T> problem, UndoableMutationOperator<T> mutation, Initializer<T> initializer, SimpleLocalMetaheuristic<T> hc)
      Creates a SimulatedAnnealing search instance for integer-valued optimization problems, with a default annealing schedule of SelfTuningLam, which is the Self-Tuning Lam annealing schedule of Cicirello (2021), and which runs a hill climber as a post-processing step. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      mutation - A mutation operator supporting the undo operation.
      initializer - The source of random initial states for simulated annealing.
      hc - The Hill Climber that is used to locally optimize simulated annealing's end of run solution. If hc is null, then no post-processing step is performed, and the search is strictly simulated annealing. If hc.getProgressTracker() is not equal to tracker, then hc's ProgressTracker is reset to tracker. That is, the ProgressTracker must be shared between the simulated annealer and the Hill Climber.
      Throws:
      NullPointerException - if any of the parameters are null (except for hc, which may be null).
      IllegalArgumentException - if hc is not null and problem is not equal to hc.getProblem()

  • Method Details

    • reoptimize

      public final SolutionCostPair<T> reoptimize(int maxEvals)
      Reaneals starting from the previous best found solution contained in the tracker object. In reannealing, simulated annealing starts from a prior found solution rather than from a random one. The annealing schedule is reinitialized (e.g., high starting temperature, etc) as if it was a fresh run. If no prior run had been performed, then this method starts the run from a randomly generated solution.
      Specified by:
      reoptimize in interface ReoptimizableMetaheuristic<T extends Copyable<T>>
      Parameters:
      maxEvals - The maximum number of simulated annealing evaluations (i.e., iterations) to execute.
      Returns:
      the current solution at the end of this run and its cost, which may or may not be the best of run solution, and which may or may not be the same as the solution contained in this simulated annealer's ProgressTracker, which contains the best of all runs. Returns null if the run did not execute, such as if the ProgressTracker already contains the theoretical best solution.

    • optimize

      public final SolutionCostPair<T> optimize(int maxEvals)
      Executes a run of simulated annealing beginning at a randomly generated solution. If this method is called multiple times, each call begins at a new randomly generated starting solution, and reinitializes the annealing schedule (e.g., starting temperature, etc) as if it was a fresh run.
      Specified by:
      optimize in interface Metaheuristic<T extends Copyable<T>>
      Parameters:
      maxEvals - The maximum number of simulated annealing evaluations (i.e., iterations) to execute during this run.
      Returns:
      The current solution at the end of this run and its cost, which may or may not be the best of run solution, and which may or may not be the same as the solution contained in this simulated annealer's ProgressTracker, which contains the best of all runs. Returns null if the run did not execute, such as if the ProgressTracker already contains the theoretical best solution.

    • optimize

      public final SolutionCostPair<T> optimize(int maxEvals, T start)
      Executes a run of simulated annealing beginning at a specified starting solution. If this method is called multiple times, each call begins by reinitializing the annealing schedule (e.g., starting temperature, etc) as if it was a fresh run.
      Specified by:
      optimize in interface SingleSolutionMetaheuristic<T extends Copyable<T>>
      Parameters:
      maxEvals - The maximum number of simulated annealing evaluations (i.e., iterations) to execute during this run.
      start - The desired starting solution.
      Returns:
      The current solution at the end of this run and its cost, which may or may not be the best of run solution, and which may or may not be the same as the solution contained in this simulated annealer's ProgressTracker, which contains the best of all runs. Returns null if the run did not execute, such as if the ProgressTracker already contains the theoretical best solution.

    • getProblem

      public final Problem<T> getProblem()
      Description copied from interface: TrackableSearch
      Gets a reference to the problem that this search is solving.
      Specified by:
      getProblem in interface TrackableSearch<T extends Copyable<T>>
      Returns:
      a reference to the problem.

    • getProgressTracker

      public final ProgressTracker<T> getProgressTracker()
      Description copied from interface: TrackableSearch
      Gets the ProgressTracker object that is in use for tracking search progress. The object returned by this method contains the best solution found during the search (including across multiple concurrent runs if the search is multithreaded, or across multiple restarts if the run methods were called multiple times), as well as cost of that solution, among other information. See the ProgressTracker documentation for more information about the search data tracked by this object.
      Specified by:
      getProgressTracker in interface TrackableSearch<T extends Copyable<T>>
      Returns:
      the ProgressTracker in use by this metaheuristic.

    • setProgressTracker

      public final void setProgressTracker(ProgressTracker<T> tracker)
      Description copied from interface: TrackableSearch
      Sets the ProgressTracker object that is in use for tracking search progress. Any previously set ProgressTracker is replaced by this one.
      Specified by:
      setProgressTracker in interface TrackableSearch<T extends Copyable<T>>
      Parameters:
      tracker - The new ProgressTracker to set. The tracker must not be null. This method does nothing if tracker is null.

    • split

      public SimulatedAnnealing<T> split()
      Description copied from interface: Splittable
      Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms. The state of the object that is returned may or may not be identical to that of the original. Thus, this is a distinct concept from the functionality of the Copyable interface. Classes that implement this interface must ensure that the object returned performs the same functionality, and that it does not share any state data that would be either unsafe or inefficient for concurrent access by multiple threads. The split method is allowed to simply return the this reference, provided that it is both safe and efficient for multiple threads to share a single copy of the Splittable object. The intention is to provide a multithreaded search with the capability to provide spawned threads with their own distinct search operators. Such multithreaded algorithms can call the split method for each thread it spawns to generate a functionally identical copy of the operator, but with independent state.
      Specified by:
      split in interface Metaheuristic<T extends Copyable<T>>
      Specified by:
      split in interface ReoptimizableMetaheuristic<T extends Copyable<T>>
      Specified by:
      split in interface Splittable<T extends Copyable<T>>
      Returns:
      A functionally identical copy of the object, or a reference to this if it is both safe and efficient for multiple threads to share a single instance of this Splittable object.

    • getTotalRunLength

      public long getTotalRunLength()
      Gets the total number of simulated annealing evaluations (iterations) performed by this SimulatedAnnealing object. This is the total number of such evaluations across all calls to the optimize and reoptimize methods. This may differ from the combined number of maxEvals passed as a parameter to those methods. For example, those methods terminate if they find the theoretical best solution, and also immediately return if a prior call found the theoretical best. In such cases, the total run length may be less than the requested maxEvals.

      If the simulated annealer has been configured with hill climbing as a post-processing step, then the total run length includes both the simulated annealing iterations as well as the number of hill climbing neighbor evaluations.

      Specified by:
      getTotalRunLength in interface TrackableSearch<T extends Copyable<T>>
      Returns:
      the total number of simulated annealing evaluations