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

Class ParallelMetaheuristic<T extends Copyable<T>>

java.lang.Object
org.cicirello.search.concurrent.ParallelMetaheuristic<T>
Type Parameters:
T - The type of object being optimized.
All Implemented Interfaces:
AutoCloseable, Splittable<TrackableSearch<T>>, Metaheuristic<T>, TrackableSearch<T>
Direct Known Subclasses:
ParallelMultistarter, ParallelReoptimizableMetaheuristic
public class ParallelMetaheuristic<T extends Copyable<T>> extends Object implements Metaheuristic<T>, AutoCloseable
This class enables running multiple copies of a metaheuristic, or multiple metaheuristics, in parallel with multiple threads. It specifically requires that all metaheuristics are solving the same problem, but otherwise, they may be the same or different metaheuristics.

  • Constructor Details

    • ParallelMetaheuristic

      public ParallelMetaheuristic(Metaheuristic<T> search, int numThreads)
      Constructs a parallel metaheuristic that executes multiple identical copies of a metaheuristic in parallel across multiple threads.
      Parameters:
      search - The metaheuristic to run in parallel.
      numThreads - The number of threads to use.
      Throws:
      IllegalArgumentException - if numThreads is less than 1.

    • ParallelMetaheuristic

      public ParallelMetaheuristic(Collection<? extends Metaheuristic<T>> searches)
      Constructs a parallel metaheuristic that executes multiple metaheuristics in parallel across multiple threads.
      Parameters:
      searches - A collection of the metaheuristics to run in parallel. The number of threads will be equal to the size of this collection.
      Throws:
      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).

  • Method Details

    • optimize

      public final SolutionCostPair<T> optimize(int runLength)
      Executes a parallel metaheuristic search. The number of threads, the specific metaheuristic executed by each thread, etc are determined by how the ParallelMetaheuristic was configured at the time of construction. The optimize method runs the optimize method of each of the parallel instances of the search for the specified run length (same run length for all parallel instances), keeping track of the best solution across the multiple parallel runs of the search. The meaning of run length may vary based on the component metaheuristics. Each run of each parallel search begins at a new randomly generate initial state.
      Specified by:
      optimize in interface Metaheuristic<T extends Copyable<T>>
      Parameters:
      runLength - The run length for all parallel metaheuristics.
      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 across all calls to optimize. 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.

    • close

      public final void close()
      Initiates an orderly shutdown of the thread pool used by this ParallelMetaheuristic. The ParallelMetaheuristic 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 ParallelMetaheuristic, 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 ParallelMetaheuristic<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 runs 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 the underlying metaheuristic.

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