Module org.cicirello.chips_n_salsa
Package org.cicirello.search.restarts

Class VariableAnnealingLength

java.lang.Object
org.cicirello.search.restarts.VariableAnnealingLength
All Implemented Interfaces:
Splittable<RestartSchedule>, RestartSchedule
public final class VariableAnnealingLength extends Object implements RestartSchedule
The Variable Annealing Length (VAL) restart schedule originated, as you would expect from the word "annealing" in its name, as a restart schedule for Simulated Annealing. Its motivation is two-fold. First, a commonly encountered observation is that a single long run of simulated annealing usually outperforms multiple short runs whose combined length is that of the long run (assuming the annealing schedule is tuned well). Second, it is often the case that we don't know beforehand how long of a run we have time to execute, thus our annealing schedule may not be tuned properly for our available time (e.g., we may cool too quickly or too slowly).

The VAL restart schedule starts with a short run, and increases run length exponentially across restarts. Specifically, define ri as the run length for run i, with the following: ri = 1000 * 2i. For simulated annealing, run length is number of evaluations (i.e., iterations of the simulated annealing main loop). You can compute the sequence of run lengths incrementally with r0 = 1000 and ri = 2ri-1. The first few run lengths in the sequence are: 1000, 2000, 4000, ....

The VAL restart schedule was introduced in:
Vincent A. Cicirello. "Variable Annealing Length and Parallelism in Simulated Annealing." In Proceedings of the Tenth International Symposium on Combinatorial Search (SoCS 2017), pages 2-10. AAAI Press, June 2017. doi:10.1609/socs.v8i1.18424. [PDF] [BIB]

This class supports both the original schedule as defined above, as well as including a parameter to specify the initial run length r0 as something other than 1000. In this case, the subsequent run lengths are still twice the previous. For example, if you start r0 = 50, then the run lengths will follow the sequence: 50, 100, 200, 400, ....

Although not originally stated in the paper that proposed this restart schedule, this implementation converges to a constant restart length of Integer.MAX_VALUE if the next run length of the schedule would otherwise exceed the maximum positive 32-bit integer value.

  • Constructor Details

    • VariableAnnealingLength

      public VariableAnnealingLength()
      The default constructor constructs the original Variable Annealing Length (VAL) restart schedule of: Vincent A. Cicirello. "Variable Annealing Length and Parallelism in Simulated Annealing." In Proceedings of the Tenth International Symposium on Combinatorial Search (SoCS 2017), pages 2-10. AAAI Press, June 2017. Specifically, the initial run length is 1000, and each subsequent run length is twice the previous.

    • VariableAnnealingLength

      public VariableAnnealingLength(int r0)
      This constructor enables specifying the initial run length for the first run. Subsequent runs otherwise follow the original schedule and are twice the length of the previous run. This restart schedule originated with simulated annealing, but when used with other metaheuristics it may be desirable to either increase or decrease the initial run length from what was originally used.
      Parameters:
      r0 - The initial run length for the first run.

  • Method Details

    • nextRunLength

      public int nextRunLength()
      Description copied from interface: RestartSchedule
      Gets the next run length in the restart schedule's sequence of run lengths.
      Specified by:
      nextRunLength in interface RestartSchedule
      Returns:
      the length for the next run of a multistart metaheuristic

    • reset

      public void reset()
      Description copied from interface: RestartSchedule
      Resets the restart schedule to its initial conditions, such that the next call to RestartSchedule.nextRunLength() will return the initial run length of the schedule.
      Specified by:
      reset in interface RestartSchedule

    • split

      public VariableAnnealingLength 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 Splittable<RestartSchedule>
      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.

    • createRestartSchedules

      public static List<VariableAnnealingLength> createRestartSchedules(int numThreads)
      This is a convenience method for use in generating several identical VAL annealing schedules, such as if needed for a parallel search. All of the annealing schedules in the returned list are identical, but are independent (no shared state). This does NOT give you the P-VAL schedule (see ParallelVariableAnnealingLength for the P-VAL schedule).

      The list that is returned is of the size of the requested number of threads. This should correspond to the number of parallel instances of the search you intend to execute.

      Parameters:
      numThreads - The number of parallel instances of the search.
      Returns:
      A list of numThreads identical VAL restart schedules.
      Throws:
      IllegalArgumentException - if numThreads ≤ 0.

    • createRestartSchedules

      public static List<VariableAnnealingLength> createRestartSchedules(int numThreads, int r0)
      This is a convenience method for use in generating several identical VAL annealing schedules, such as if needed for a parallel search. All of the annealing schedules in the returned list are identical, but are independent (no shared state). This does NOT give you the P-VAL schedule (see ParallelVariableAnnealingLength for the P-VAL schedule).

      The list that is returned is of the size of the requested number of threads. This should correspond to the number of parallel instances of the search you intend to execute.

      Parameters:
      numThreads - The number of parallel instances of the search.
      r0 - The initial run length for the first run.
      Returns:
      A list of numThreads identical VAL restart schedules.
      Throws:
      IllegalArgumentException - if numThreads ≤ 0.