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

Class ParallelVariableAnnealingLength

java.lang.Object
org.cicirello.search.restarts.ParallelVariableAnnealingLength
All Implemented Interfaces:
Splittable<RestartSchedule>, RestartSchedule
public final class ParallelVariableAnnealingLength extends Object implements RestartSchedule
The Parallel Variable Annealing Length (P-VAL) restart schedule originated, as you would expect from the word "annealing" in its name, as a restart schedule for Simulated Annealing. Specifically, it is a parallel version of the Variable Annealing Length (VAL) restart schedule. Its intended use is to schedule the run lengths for restarts across a set of parallel multistart metaheuristics. See the VariableAnnealingLength class for the sequential version of this restart schedule.

The motivation underlying P-VAL 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 sequential version of the restart schedule, known as VAL, 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, ....

P-VAL is a parallel version of VAL. Its essence is the same sequence of restarts, but those restart run lengths are spread across a maximum of 4 parallel instances of the search. If there are more than 4 parallel instances, the schedule repeats with more than one search following the same schedule. The run length, ri,t, of restart i of thread t is as follows: ri,t = 1000 * 2(t mod 4) + i*min(4,N), where i begins at 0, N is the number of parallel search instances (i.e., threads), and the thread id t is an integer in [0, N). Note that we do not implement this with an actual exponentiation. Rather, each run length of the sequence is computed incrementally from the prior run length. Here are a few examples:

Example 1 (N=3): Thread 0 follows the schedule of run lengths: 1000, 8000, 64000, .... Thread 1 follows the schedule of run lengths: 2000, 16000, 128000, .... Thread 2 follows the schedule of run lengths: 4000, 32000, 256000, ....

Example 2 (N=4): Thread 0 follows the schedule of run lengths: 1000, 16000, 256000, .... Thread 1 follows the schedule of run lengths: 2000, 32000, 512000, .... Thread 2 follows the schedule of run lengths: 4000, 64000, 1024000, .... Thread 3 follows the schedule of run lengths: 8000, 128000, 2048000, ....

Example 3 (N>4): Thread 0 follows the schedule of run lengths: 1000, 16000, 256000, .... Thread 1 follows the schedule of run lengths: 2000, 32000, 512000, .... Thread 2 follows the schedule of run lengths: 4000, 64000, 1024000, .... Thread 3 follows the schedule of run lengths: 8000, 128000, 2048000, .... Thread t, where t≥4, follows the same schedule of run lengths as thread (t-4).

See the original publication, referenced below, for the theoretical rationale for beginning the schedule fresh every 4 threads, along with an experimental comparison between P-VAL and a preliminary version referred to in that paper as P-VAL-0, which did not start anew every 4 threads, as validation of that theoretical result.

This class supports both the original schedule as defined above, as well as including a parameter to specify the initial run length r0,0 as something other than 1000.

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.

Since this restart schedule assumes multiple threads, and since each thread requires its own RestartSchedule object that maintains state independent of the others, we do not provide a public constructor for this class. Instead, we provide a couple static factory methods, createRestartSchedules(int) and createRestartSchedules(int,int), each of which create an array of restart schedules for the desired number of parallel instances.

The P-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]

  • 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 ParallelVariableAnnealingLength 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<ParallelVariableAnnealingLength> createRestartSchedules(int numThreads)
      Creates a list of restart schedules that together follow the Parallel Variable Annealing Length (P-VAL) 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.

      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. This factory method ensures that the combination of individual restart schedules together conforms to the parallel restart schedule known as P-VAL.

      Parameters:
      numThreads - The number of parallel instances of the search.
      Returns:
      The P-VAL restart schedule as a list of separate restart schedules, one for each desired parallel instance. The combination of restart schedules together implement P-VAL.
      Throws:
      IllegalArgumentException - if numThreads ≤ 0.

    • createRestartSchedules

      public static List<ParallelVariableAnnealingLength> createRestartSchedules(int numThreads, int r0)
      Creates a list of restart schedules that together follow the Parallel Variable Annealing Length (P-VAL) 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.

      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. This factory method ensures that the combination of individual restart schedules together conforms to the parallel restart schedule known as P-VAL.

      This factory method is a mild modification of the original P-VAL restart schedule. Specifically, the original schedule sets the shortest run length of any of the parallel search instances at 1000, while this factory method enables the programmer to specify this. The original run length of 1000 is appropriate for simulated annealing, however, for other metaheuristics you may have reason to initialize the schedule with either shorter or longer runs.

      Parameters:
      numThreads - The number of parallel instances of the search.
      r0 - The shortest run length of any of the parallel instances.
      Returns:
      The P-VAL restart schedule as a list of separate restart schedules, one for each desired parallel instance. The combination of restart schedules together implement P-VAL.
      Throws:
      IllegalArgumentException - if numThreads ≤ 0 or if r0 ≤ 0.