Module org.cicirello.chips_n_salsa
Package org.cicirello.search.concurrent

Class TimedParallelMultistarter<T extends Copyable<T>>

java.lang.Object
org.cicirello.search.concurrent.TimedParallelMultistarter<T>
Type Parameters:
T - The type of object being optimized.
All Implemented Interfaces:
AutoCloseable, Splittable<TrackableSearch<T>>, Metaheuristic<T>, TrackableSearch<T>
Direct Known Subclasses:
TimedParallelReoptimizableMultistarter
public class TimedParallelMultistarter<T extends Copyable<T>> extends Object implements Metaheuristic<T>, AutoCloseable
This class is used for implementing parallel multistart metaheuristics. It can be used to restart any class that implements the Metaheuristic interface. A multistart metaheuristic returns the best result from among all of the restarts. In the case of a parallel multistart metaheuristic, the search returns the best result from among all restarts across all threads.

This parallel multistarter enables specifying the run length in terms of time, rather than by number of restarts. It then executes as many restarts as that length of time allows. This may be more desirable for multiple use cases. First, if the run lengths can vary from one restart to another, each parallel instance of the search may have rather different run times if we were to specify the number of times to restart. This would lead to some threads sitting idle. Second, if we were executing different metaheuristics in different threads, then again one or more threads may complete early sitting idle if we were to specify number of times to restart. Third, a similar phenomena can result if we were executing the same metaheuristic (e.g., simulated annealing) but where each parallel instance was using a different mutation operator. Finally, if we know how much time we can afford to search, we don't need a priori know the length of time required by a restart.

There are several constructors enabling different ways to configure the search. You can initialize the search with a combination of a Metaheuristic and number of threads along with either a RestartSchedule for the purpose of specifying run lengths for the restarts, or a run length if all runs are to be of the same length. You can also initialize the search with a Collection of RestartSchedule objects, one for each thread (with number of threads implied by size of Collection. Or you can initialize the search with a Collection of Metaheuristic objects and a Collection of RestartSchedule objects (both Collections of the same size). You can also initialize the search with a Multistarter configured with your restart schedule, along with the number of threads, or a Collection of Multistarter objects.

  • Field Details

  • Constructor Details

    • TimedParallelMultistarter

      public TimedParallelMultistarter(Metaheuristic<T> search, int runLength, int numThreads)
      Constructs a parallel multistart metaheuristic that executes multiple runs of a specified metaheuristic in parallel across multiple threads. All restarts are the same in length.
      Parameters:
      search - The metaheuristic to restart multiple times in parallel.
      runLength - The length of every restarted run of the metaheuristic.
      numThreads - The number of threads to use.
      Throws:
      IllegalArgumentException - if numThreads is less than 1.
      IllegalArgumentException - if nunLength is less than 1.

    • TimedParallelMultistarter

      public TimedParallelMultistarter(Metaheuristic<T> search, RestartSchedule r, int numThreads)
      Constructs a parallel multistart metaheuristic that executes multiple runs of a specified metaheuristic in parallel across multiple threads. All parallel instances follow the same restart schedule of run lengths.
      Parameters:
      search - The metaheuristic to restart multiple times in parallel.
      r - The schedule of run lengths. Note that the threads do not share a single RestartSchedule. Rather, each thread will be initialized with its own copy of r.
      numThreads - The number of threads to use.
      Throws:
      IllegalArgumentException - if numThreads is less than 1.

    • TimedParallelMultistarter

      public TimedParallelMultistarter(Metaheuristic<T> search, Collection<? extends RestartSchedule> schedules)
      Constructs a parallel multistart metaheuristic that executes multiple runs of a specified metaheuristic in parallel across multiple threads. Each parallel instance follows its own restart schedule of run lengths.
      Parameters:
      search - The metaheuristic to restart multiple times in parallel.
      schedules - The schedules of run lengths, one for each thread. The number of threads will be equal to the number of restart schedules.
      Throws:
      IllegalArgumentException - if schedules.size() is less than 1.

    • TimedParallelMultistarter

      public TimedParallelMultistarter(Collection<? extends Metaheuristic<T>> searches, Collection<? extends RestartSchedule> schedules)
      Constructs a parallel multistart metaheuristic that executes multiple runs of a set of specified metaheuristics in parallel across multiple threads. Each parallel search follows its own restart schedule of run lengths.
      Parameters:
      searches - A collection of the metaheuristics to restart multiple times in parallel. The number of threads will be equal to the size of this collection.
      schedules - The schedules of run lengths, one for each thread.
      Throws:
      IllegalArgumentException - if searches.size() is not equal to schedules.size().
      IllegalArgumentException - if the Collection of Metaheuristics don't all share the same problem (i.e., requires that s1.getProblem() == s2.getProblem() for all s1, s2 in searches).
      IllegalArgumentException - if the Collection of Metaheuristics don't all share a single ProgressTracker (i.e., requires that s1.getProgressTracker() == s2.getProgressTracker() for all s1, s2 in searches).

    • TimedParallelMultistarter

      public TimedParallelMultistarter(Collection<? extends Metaheuristic<T>> searches, int runLength)
      Constructs a parallel multistart metaheuristic that executes multiple runs of a set of specified metaheuristics in parallel across multiple threads. All runs of all parallel instances follows a constant run length.
      Parameters:
      searches - A collection of the metaheuristics to restart multiple times in parallel. The number of threads will be equal to the size of this collection.
      runLength - The length of all restarted runs of all parallel metaheuristics.
      Throws:
      IllegalArgumentException - if runLength < 1.
      IllegalArgumentException - if the Collection of Metaheuristics don't all share the same problem (i.e., requires that s1.getProblem() == s2.getProblem() for all s1, s2 in searches).
      IllegalArgumentException - if the Collection of Metaheuristics don't all share a single ProgressTracker (i.e., requires that s1.getProgressTracker() == s2.getProgressTracker() for all s1, s2 in searches).

    • TimedParallelMultistarter

      public TimedParallelMultistarter(Multistarter<T> multistartSearch, int numThreads)
      Constructs a parallel multistart metaheuristic that executes multiple runs of a specified metaheuristic in parallel across multiple threads. All parallel instances follow the same restart schedule of run lengths.
      Parameters:
      multistartSearch - A Multistarter configured with the metaheuristic and restart schedule. Each of the threads will be an identical copy of this Multistarter.
      numThreads - The number of threads to use.
      Throws:
      IllegalArgumentException - if numThreads is less than 1.

    • TimedParallelMultistarter

      public TimedParallelMultistarter(Collection<? extends Multistarter<T>> multistarters)
      Constructs a parallel multistart metaheuristic that executes multiple runs of a set of specified metaheuristics in parallel across multiple threads. Each of the Multistarters will run in its own thread. The number of threads will be equal to the number of Multistarters passed to the constructor.
      Parameters:
      multistarters - A collection of Multistarters configured with the metaheuristics and restart schedules for the threads.
      Throws:
      IllegalArgumentException - if the Collection of Multistarters don't all share the same problem (i.e., requires that s1.getProblem() == s2.getProblem() for all s1, s2 in multistarters).
      IllegalArgumentException - if the Collection of Multistarters don't all share a single ProgressTracker (i.e., requires that s1.getProgressTracker() == s2.getProgressTracker() for all s1, s2 in multistarters).

  • Method Details

    • setTimeUnit

      public final void setTimeUnit(int timeUnit)
      Changes the unit of time used by the optimize(int) method.
      Parameters:
      timeUnit - The unit of time to use with the optimize(int) method, specified in milliseconds. For example, if timeUnit equals 2000, then the call optimize(3) will run for approximately 6 seconds, since 3 * 2000 is 6000 milliseconds, which is 6 seconds.
      Throws:
      IllegalArgumentException - if timeUnit is less than 1.
      See Also:

    • getTimeUnit

      public final int getTimeUnit()
      Gets the unit of time used by the optimize(int) method.
      Returns:
      The unit of time used by the optimize(int) method, specified in milliseconds. For example, if timeUnit equals 2000, then the call optimize(3) will run for approximately 6 seconds, since 3 * 2000 is 6000 milliseconds, which is 6 seconds.
      See Also:

    • getSearchHistory

      public final ArrayList<SolutionCostPair<T>> getSearchHistory()
      Gets a list of the best solution stored in this search's ProgressTracker at each time interval of the most recent call to the optimize(int) method, or null if optimize(int) has not been called. Note that the ProgressTracker stores the best solution found across all calls to the optimize(int) method, so the solutions in the list returned by this method may or may not have been found during the most recent call to optimize(int). The length of the list returned will be no greater than the value passed to optimize(int) for the time parameter. The length will be less than the time parameter in the event that the search terminates early due to finding the optimal solution.
      Returns:
      A list of the best found solution, as stored in the ProgressTracker, at each time interval during the most recent call to the optimize(int) method, or null if optimize(int) has not been called.

    • optimize

      public final SolutionCostPair<T> optimize(int time)
      Executes a parallel multistart search. The number of threads, the specific metaheuristic executed by each thread, the restart schedules, etc are determined by how the TimedParallelMultistarter was configured at the time of construction. All parallel instances of the search are executed for approximately the length of time indicated by the time parameter, restarting as many times as time allows, keeping track of the best solution across the multiple parallel runs of the search. It may terminate earlier if one of the parallel searches indicates the best possible solution was found. Each restart of each parallel search begins at a new randomly generate initial state.

      If this method is called multiple times, the restart schedules of the parallel metaheuristics are not reinitialized, and the run lengths for the additional restarts will continue where the schedules left off.

      Specified by:
      optimize in interface Metaheuristic<T extends Copyable<T>>
      Parameters:
      time - The approximate length of time for the search. The unit of time is as indicated by the constant TIME_UNIT_MS unless changed by a call to the setTimeUnit(int) method. For example, assuming setTimeUnit(int) has not been called, then the search will run for approximately: time * TIME_UNIT_MS milliseconds.
      Returns:
      The best end of run solution (and its cost) of this set of parallel runs, which may or may not be the same as the solution contained in this metaheuristic'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.
      Throws:
      IllegalStateException - if the close() method was previously called.
      See Also:

    • close

      public final void close()
      Initiates an orderly shutdown of the thread pool used by this TimedParallelMultistarter. The TimedParallelMultistarter utilizes a fixed thread pool so that multiple calls to the optimize(int) method can reuse threads to minimize the expensive task of thread creation. When you no longer need the TimedParallelMultistarter, you should call the close method to ensure that unneeded threads do not persist. Once close is called, all subsequent calls to optimize(int) will throw an exception.

      This method is invoked automatically on objects managed by the try-with-resources statement.

      Specified by:
      close in interface AutoCloseable

    • isClosed

      public final boolean isClosed()
      Checks whether the thread pool has been shutdown.
      Returns:
      true if and only if the close() method has been called previously.

    • split

      public TimedParallelMultistarter<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 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.

    • 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.

    • 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.

    • getTotalRunLength

      public final long getTotalRunLength()
      Gets the total run length of all restarts of all parallel instances of the underlying metaheuristics combined. This may differ from what may be expected based on run lengths passed to the optimize and reoptimize methods of the underlying metaheuristics. For example, the optimize method terminates if it finds the theoretical best solution, and also immediately returns if a prior call found the theoretical best. In such cases, the total run length may be less than the requested run length.

      The meaning of run length may vary based on what metaheuristic is being restarted.

      Specified by:
      getTotalRunLength in interface TrackableSearch<T extends Copyable<T>>
      Returns:
      the total run length of all restarts of the underlying metaheuristic, which includes across multiple calls to the restart mechanism and across all parallel instances.