Package es.urjc.etsii.grafo.improve.ls

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

java.lang.Object
es.urjc.etsii.grafo.improve.Improver<S,I>
es.urjc.etsii.grafo.improve.ls.LocalSearch<M,S,I>
Type Parameters:
M - type of move
S - type of the problem solution
I - type of the problem instance
Direct Known Subclasses:
LocalSearchBestImprovement, LocalSearchFirstImprovement
public abstract class LocalSearch<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> extends Improver<S,I>
Local search procedures start from a given feasible solution and explore a determined neighborhood in each iteration, replacing the current solution if a neighbor solution improves the objective function of the current one. The search ends when all neighbor solutions are worse meaning that a local optimum is found.

There exist two typical strategies to explore the corresponding neighborhood: best improvement and first improvement. To use or extend those procedures see LocalSearchBestImprovement and LocalSearchFirstImprovement respectively.

  • Field Details

  • Constructor Details

    • LocalSearch

      protected LocalSearch(Objective<M,S,I> objective, Neighborhood<M,S,I> neighborhood)
      Create a new local search method using the given neighborhood
      Parameters:
      objective - MAXIMIZE to maximize scores returned by the given move, MINIMIZE for minimizing
      neighborhood - neighborhood to use

    • LocalSearch

      protected LocalSearch(Neighborhood<M,S,I> neighborhood)
      Create a new local search method using the given neighborhood. Uses the method Move::getValue as the guiding function, with fMaximize = maximize.
      Parameters:
      neighborhood - neighborhood to use

  • Method Details

    • improve

      public S improve(S solution)
      Improves a model.Solution Iterates until we run out of time, or we cannot improve the current es.urjc.etsii.grafo.solution any further

      Improves a model.Solution Iterates until we run out of time, or we cannot improve the current solution any further

      Specified by:
      improve in class Improver<S extends Solution<S,I>,I extends Instance>
      Parameters:
      solution - model.Solution to improve
      Returns:
      Improved s

    • iteration

      public boolean iteration(int round, S solution)
      This procedure check if there are valid moves to neighbors solutions. In that case, the move is executed. Otherwise, the procedure ends.
      Returns:
      true if the solution has improved, false otherwise

    • getMove

      public abstract M getMove(S solution)
      Get next move to execute, different strategies are possible
      Parameters:
      solution - Solution
      Returns:
      Proposed move, null if there are no candidate moves in the neighborhood

    • improves

      protected boolean improves(M move)

    • toString

      public String toString()
      Overrides:
      toString in class Object