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

Class Multistarter<T extends Copyable<T>>

java.lang.Object
org.cicirello.search.restarts.Multistarter<T>
Type Parameters:
T - The type of object being optimized.
All Implemented Interfaces:
Splittable<TrackableSearch<T>>, Metaheuristic<T>, TrackableSearch<T>
Direct Known Subclasses:
ReoptimizableMultistarter
public class Multistarter<T extends Copyable<T>> extends Object implements Metaheuristic<T>
This class is used for implementing multistart metaheuristics. It can be used to restart any class that implements the Metaheuristic interface, and requires specification of 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. A multistart metaheuristic returns the best result from among all of the restarts.

  • Constructor Details

    • Multistarter

      public Multistarter(Metaheuristic<T> search, RestartSchedule r)
      Constructs a multistart metaheuristic that executes multiple runs of a specified metaheuristic, whose run lengths follow a specified schedule.
      Parameters:
      search - The metaheuristic to restart multiple times.
      r - The schedule of run lengths for the multistart search

    • Multistarter

      public Multistarter(Metaheuristic<T> search, int runLength)
      Constructs a multistart metaheuristic that executes multiple runs of a specified metaheuristic, whose runs are all the same in length.
      Parameters:
      search - The metaheuristic to restart multiple times.
      runLength - The length of every restarted run of the metaheuristic.
      Throws:
      IllegalArgumentException - if runLength < 1

  • Method Details

    • 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 the underlying metaheuristic combined. This may differ from what may be expected based on run lengths passed to the optimize and reoptimize methods of the underlying metaheuristic. 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

    • optimize

      public final SolutionCostPair<T> optimize(int numRestarts)
      Executes a multistart search, calling the underlying metaheuristic the specified number of times, keeping track of the best solution across the multiple runs of the search. Each restart begins at a new randomly generate initial state.

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

      Specified by:
      optimize in interface Metaheuristic<T extends Copyable<T>>
      Parameters:
      numRestarts - The number of times to restart the metaheuristic.
      Returns:
      The best end of run solution (and its cost) of this set of restarts, 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.

    • split

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