Package es.urjc.etsii.grafo.solution.neighborhood

Class Neighborhood<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance>

java.lang.Object
es.urjc.etsii.grafo.solution.neighborhood.Neighborhood<M,S,I>
Direct Known Subclasses:
InsertNeighborhood, RandomizableNeighborhood, SwapNeighborhood
public abstract class Neighborhood<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> extends Object
Defines a neighbourhood. A neighborhoods represents all potential solutions that can be reached for a given solution applying a given move. Usually used inside, but not limited to, a local search procedure,

  • Field Details

  • Constructor Details

    • Neighborhood

      public Neighborhood()

  • Method Details

    • explore

      public abstract ExploreResult<M,S,I> explore(S solution)
      Build an exhaustive stream that allows iterating the whole neighborhood Using a stream is more efficient that a list as moves are only generated if they are needed
      Parameters:
      solution - Solution used to generate the neighborhood
      Returns:
      Stream with all the available moves in the neighborhood

    • neighborhoodSize

      public int neighborhoodSize(S solution)

      Optionally calculate how big the neighborhood is for a given solution. It does not need to be an exact value, but it should be an upper bound. It is perfectly valid to estimate the size to 100 and then returning only 90 elements from the neighborhood, but it is not ok to estimate size to 10 and then returning 100 elements. Internally will be used to correctly size data structures and try to improve performance. Moreover, can be used when using a random neighborhood to optionally balance probabilities, so the bigger neighborhood has a bigger chance of having a move picked, instead of equal probability between all neighborhoods. Implementation should have O(1) or O(log n) complexity, if the size can be calculated but takes O(n) or longer, it is recommended to return UNKNOWN_SIZE instead.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • concat

      @SafeVarargs public static <M extends Move<S, I>, S extends Solution<S, I>, I extends Instance> Neighborhood<M,S,I> concat(Neighborhood<M,S,I>... neighborhoods)
      Concatenate several neighborhoods, such as N1(A,B,C) and N2(D,E,F) return a new neighborhood with moves N(A,B,C,D,E,F)
      Type Parameters:
      M - Move type
      S - Solution type
      I - Instance type
      Parameters:
      neighborhoods - neighborhoods to concatenate
      Returns:
      a new neighborhood which returns the moves from each neighborhood as a sequence

    • interleave

      @SafeVarargs public static <M extends Move<S, I>, S extends Solution<S, I>, I extends Instance> Neighborhood<M,S,I> interleave(Neighborhood<M,S,I>... neighborhoods)
      Alternate between several neighborhoods, such as N1(A,B,C) and N2(D,E,F) return a new neighborhood with moves N(A,D,B,E,C,F)
      Type Parameters:
      M - Move type
      S - Solution type
      I - Instance type
      Parameters:
      neighborhoods - neighborhoods to alternate
      Returns:
      a new neighborhood which returns the moves from each neighborhood alternating between them

    • empty

      public static <M extends Move<S, I>, S extends Solution<S, I>, I extends Instance> Neighborhood<M,S,I> empty()
      Create an empty neighborhood with no moves
      Type Parameters:
      M - Move type
      S - Solution type
      I - Instance type
      Returns:
      empty neighborhood

    • random

      @SafeVarargs public static <M extends Move<S, I>, S extends Solution<S, I>, I extends Instance> RandomizableNeighborhood<M,S,I> random(boolean balanced, RandomizableNeighborhood<M,S,I>... neighborhoods)
      Create a neighborhood that picks random moves from a set of given neighborhoods
      Type Parameters:
      M - Move type
      S - Solution type
      I - Instance type
      Parameters:
      balanced - if false, all neighborhoods will be chosen with the same probability. If true, the neighborhood size for the current solution will be taken into account
      Returns:
      a RandomizableNeighborhood that randomly picks movements from a given set of neighborhoods.