Package org.cicirello.search.ss

Class HeuristicPermutationGenerator

  • All Implemented Interfaces:
    Splittable<TrackableSearch<Permutation>>, SimpleMetaheuristic<Permutation>, TrackableSearch<Permutation>
    public final class HeuristicPermutationGenerator
extends HeuristicSolutionGenerator<Permutation>

    This class generates solutions to permutation optimization problems using a constructive heuristic. Unless the heuristic given to it is randomized, this class is completely deterministic and has no randomized behavior. Thus, executing the HeuristicSolutionGenerator.optimize() method multiple times should produce the same result each time. When using a constructive heuristic, you begin with an empty solution, in this case an empty permutation, and you then use a constructive heuristic to choose which element to add to the partial solution, in this case to the partial permutation. This is repeated until you derive a complete solution (i.e., a complete permutation).

    Constructive heuristics are not just for permutations. See the HeuristicSolutionGenerator class for a more general implementation.

    Assuming that the length of the permutation is N, and that the runtime of the heuristic is O(f(N)), the runtime to construct one permutation using a constructive heuristic is O(N2 f(N)). If the cost, f(N), to heuristically evaluate one permutation element is simply, O(1), constant time, then the cost to heuristically construct a permutation is simply O(N2).

    • Constructor Detail

      • HeuristicPermutationGenerator

        public HeuristicPermutationGenerator​(ConstructiveHeuristic<Permutation> heuristic)
        Constructs an HeuristicPermutationGenerator for generating solutions to an optimization problem using a constructive heuristic. A ProgressTracker is created for you.
        Parameters:
        heuristic - The constructive heuristic.
        Throws:
        NullPointerException - if heuristic is null

      • HeuristicPermutationGenerator

        public HeuristicPermutationGenerator​(ConstructiveHeuristic<Permutation> heuristic,
                                     ProgressTracker<Permutation> tracker)
        Constructs an HeuristicPermutationGenerator for generating solutions to an optimization problem using a constructive heuristic.
        Parameters:
        heuristic - The constructive heuristic.
        tracker - A ProgressTracker
        Throws:
        NullPointerException - if heuristic or tracker is null

    • Method Detail

      • split

        public HeuristicPermutationGenerator 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 SimpleMetaheuristic<Permutation>
        Specified by:
        split in interface Splittable<TrackableSearch<Permutation>>
        Overrides:
        split in class HeuristicSolutionGenerator<Permutation>
        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.