jopt.csp.search
Interface LocalSearch


public interface LocalSearch

Interface for a class that creates and returns common local search actions and objects that can be used to build searches

Version:
$Revision: 1.13 $
Author:
Nick Coleman

Method Summary
 SearchAction browseNeighborhood(SolverSolution initial, Neighborhood hood, CurrentNeighbor current)
          This action will browse a list of neighbors produced from a Neighborhood and attempt to apply each in turn in order to locate other valid solutions to the problem.
 SearchAction browseNeighborhood(SolverSolution initial, Neighborhood hood, Metaheuristic meta, CurrentNeighbor current)
          This action will browse a list of neighboring solutions with the guidance of a metaheuristic used to determine which solutions are acceptable.
 SearchAction browseNeighbors(SolverSolution initial, SolverSolution[] neighbors)
          This action will browse a list of neighboring solutions based on an initial solution.
 Neighborhood flipNeighborhood(CspIntVariable[] vars)
          Creates a neighborhood that is useful for flipping 0 and 1 values on binary variables.
 SearchAction improve(SolverSolution solution, double step)
          Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action.
 SearchAction improve(SolverSolution solution, float step)
          Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action.
 SearchAction improve(SolverSolution solution, int step)
          Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action.
 SearchAction improve(SolverSolution solution, long step)
          Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action.
 SearchAction moveToNeighbor(SolverSolution initial, SolverSolution neighbor)
          Restores a neighboring solution to the solver
 SearchAction neighborMove(SolverSolution solution, Neighborhood hood)
          Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution
 SearchAction neighborMove(SolverSolution solution, Neighborhood hood, Metaheuristic meta)
          Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution
 SearchAction neighborMove(SolverSolution solution, Neighborhood hood, Metaheuristic meta, SearchGoal goal)
          Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution
 SearchAction neighborMove(SolverSolution solution, Neighborhood hood, SearchGoal goal)
          Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution
 Neighborhood randomize(Neighborhood neighborhood)
          Creates a randomized neighborhood from the specified neighborhood
 Neighborhood randomize(Neighborhood[] neighborhoods)
          Creates a unified, randomized neighborhood from the specified neighborhoods
 SearchAction selectCurrentNeighbor(SolverSolution initial, CurrentNeighbor current)
          Advises neighborhoods that the current neighbor is about to be made the new initial solution.
 Neighborhood swapNeighborhood(CspIntVariable[] vars)
          Creates a neighborhood where each neighbor selects two variables from the initial solution and swaps their values
 Metaheuristic tabu(int forbiddenUndoMoves)
          Tabu Search metaheuristic that tracks moves performed during a local search and maintains lists of moves that are forbidden.
 Metaheuristic tabu(int forbiddenUndoMoves, double objectiveGap)
          Tabu Search metaheuristic that tracks moves performed during a local search and maintains lists of moves that are forbidden.
 Metaheuristic tabu(int forbiddenUndoMoves, int forbiddenAlterMoves, double objectiveGap)
          Tabu Search metaheuristic that tracks moves performed during a local search and maintains lists of moves that are forbidden.
 SearchAction tabuMove(SolverSolution solution, Neighborhood hood, int numToCheck)
           
 SearchAction tabuMove(SolverSolution solution, Neighborhood hood, Metaheuristic meta, int numToCheck)
           
 SearchAction tabuMove(SolverSolution solution, Neighborhood hood, Metaheuristic meta, SearchGoal goal, int numToCheck)
           
 SearchAction tabuMove(SolverSolution solution, Neighborhood hood, SearchGoal goal, int numToCheck)
           
 Neighborhood unifiedNeighborhood(Neighborhood[] neighborhoods)
          Creates a neighborhood from a combination of several neighborhoods
 Neighborhood weightedRandomize(Neighborhood[] neighborhoods, double[] weights)
          Creates a unified, randomized, weighted neighborhood using the specified neighbors and weights.
 

Method Detail

browseNeighbors

public SearchAction browseNeighbors(SolverSolution initial,
                                    SolverSolution[] neighbors)
This action will browse a list of neighboring solutions based on an initial solution. The neighbor can define solutions to variables that should not be updated from the original solution as well as values to assign to variables not in the scope of the original solution. Each neighbor will be applied as an alternative solution to produce a set of choices. If you want to restore a neighboring solution to a problem so the exact solution is restored, you may want to refer to the CspSolver class's CspSolver.reset() and CspSolver.restoreNeighboringSolution(SolverSolution, SolverSolution) This action is not a replacement of the restore neighboring solution method in the CspSolver class. It is just a convenient way of calling the restore during a search.

Parameters:
initial - Initial solution related to neighbor
neighbors - Array of neighboring solutions to be browsed

moveToNeighbor

public SearchAction moveToNeighbor(SolverSolution initial,
                                   SolverSolution neighbor)
Restores a neighboring solution to the solver

Parameters:
initial - Initial solution related to neighbor
neighbor - Neighboring solution to be restored

flipNeighborhood

public Neighborhood flipNeighborhood(CspIntVariable[] vars)
Creates a neighborhood that is useful for flipping 0 and 1 values on binary variables. For each variable defined, a neighboring solution will be defined that either assigns the variable's value to 1 or the variable's value to 0.

Parameters:
vars - Array of variables to be flipped to produce neighborhood

swapNeighborhood

public Neighborhood swapNeighborhood(CspIntVariable[] vars)
Creates a neighborhood where each neighbor selects two variables from the initial solution and swaps their values

Parameters:
vars - Array of variables to be swapped

unifiedNeighborhood

public Neighborhood unifiedNeighborhood(Neighborhood[] neighborhoods)
Creates a neighborhood from a combination of several neighborhoods

Parameters:
neighborhoods - the neighborhoods to "combine"

randomize

public Neighborhood randomize(Neighborhood[] neighborhoods)
Creates a unified, randomized neighborhood from the specified neighborhoods

Parameters:
neighborhoods - the neighborhoods to "combine" and randomize

randomize

public Neighborhood randomize(Neighborhood neighborhood)
Creates a randomized neighborhood from the specified neighborhood

Parameters:
neighborhood - to be randomized

weightedRandomize

public Neighborhood weightedRandomize(Neighborhood[] neighborhoods,
                                      double[] weights)
Creates a unified, randomized, weighted neighborhood using the specified neighbors and weights. Note that the number of neighborhoods used must match the number of weights specified.

Parameters:
neighborhoods - the neighborhoods to unify and randomize
weights - the weights determining how frequently neighbors from the associated neighborhood are returned

browseNeighborhood

public SearchAction browseNeighborhood(SolverSolution initial,
                                       Neighborhood hood,
                                       CurrentNeighbor current)
This action will browse a list of neighbors produced from a Neighborhood and attempt to apply each in turn in order to locate other valid solutions to the problem. The application of a neighboring solution is very similar to restoring a solution. It does not reset any of the variables, but simply constrains them further to conform to the values of the currently selected neighbor. If you want to want to apply a neighboring solution to a problem so the exact solution is restored, you may want to refer to the CspSolver class's CspSolver.reset() and CspSolver.restoreNeighboringSolution(SolverSolution, SolverSolution) This action is not a replacement of the restore neighboring solution method in the CspSolver class. It is just a convenient way of calling the restore during a search.

Parameters:
initial - Initial solution related to neighbor
hood - Neighborhood of solutions, each to be applied as an alternative choices
current - Updated as neighbors are restored to solver to store the currently selected neighbor
See Also:
browseNeighbors(SolverSolution, SolverSolution[]), selectCurrentNeighbor(SolverSolution, CurrentNeighbor)

browseNeighborhood

public SearchAction browseNeighborhood(SolverSolution initial,
                                       Neighborhood hood,
                                       Metaheuristic meta,
                                       CurrentNeighbor current)
This action will browse a list of neighboring solutions with the guidance of a metaheuristic used to determine which solutions are acceptable.

Parameters:
initial - Initial solution related to neighbor
hood - Neighborhood of solutions, each to be applied as an alternative choice
meta - Metaheuristic used to guide the search
current - Updated as neighbors are restored to solver to store the currently selected neighbor
See Also:
browseNeighborhood(SolverSolution, Neighborhood, CurrentNeighbor)

selectCurrentNeighbor

public SearchAction selectCurrentNeighbor(SolverSolution initial,
                                          CurrentNeighbor current)
Advises neighborhoods that the current neighbor is about to be made the new initial solution. This is preferable to the StoreSolutionAction since it will call the neighborSelected() method on the neighborhood that produced the solution before the initial solution is updated.

Parameters:
initial - Initial solution neighbor is based upon that will be updated
current - Current neighboring solution that is applied to the problem

improve

public SearchAction improve(SolverSolution solution,
                            int step)
Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action. The constraint is based upon the objective expression and value stored in the solution.

Parameters:
solution - Solution that should be improved upon
step - Positive value indicating amount objective value should be improved

improve

public SearchAction improve(SolverSolution solution,
                            float step)
Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action. The constraint is based upon the objective expression and value stored in the solution.

Parameters:
solution - Solution that should be improved upon
step - Positive value indicating amount objective value should be improved

improve

public SearchAction improve(SolverSolution solution,
                            long step)
Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action. The constraint is based upon the objective expression and value stored in the solution.

Parameters:
solution - Solution that should be improved upon
step - Positive value indicating amount objective value should be improved

improve

public SearchAction improve(SolverSolution solution,
                            double step)
Action that will post a constraint during searching that will require additional solutions located to be better than the solution given to this action. The constraint is based upon the objective expression and value stored in the solution.

Parameters:
solution - Solution that should be improved upon
step - Positive value indicating amount objective value should be improved

neighborMove

public SearchAction neighborMove(SolverSolution solution,
                                 Neighborhood hood,
                                 Metaheuristic meta,
                                 SearchGoal goal)
Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution

Parameters:
solution - Solution that move is based upon and result will be stored in
hood - Neighborhood of solutions relative to initial
meta - Metaheuristic used to guide the search
goal - Search goal used to select neighboring solution

neighborMove

public SearchAction neighborMove(SolverSolution solution,
                                 Neighborhood hood,
                                 Metaheuristic meta)
Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution

Parameters:
solution - Solution that move is based upon and result will be stored in
hood - Neighborhood of solutions relative to initial
meta - Metaheuristic used to guide the search

neighborMove

public SearchAction neighborMove(SolverSolution solution,
                                 Neighborhood hood,
                                 SearchGoal goal)
Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution

Parameters:
solution - Solution that move is based upon and result will be stored in
hood - Neighborhood of solutions relative to initial
goal - Search goal used to select neighboring solution

neighborMove

public SearchAction neighborMove(SolverSolution solution,
                                 Neighborhood hood)
Advanced action that performs all actions necessary to move to a neighboring solution during local search operations and will only return the first valid neighboring solution

Parameters:
solution - Solution that move is based upon and result will be stored in
hood - Neighborhood of solutions relative to initial

tabuMove

public SearchAction tabuMove(SolverSolution solution,
                             Neighborhood hood,
                             Metaheuristic meta,
                             SearchGoal goal,
                             int numToCheck)

tabuMove

public SearchAction tabuMove(SolverSolution solution,
                             Neighborhood hood,
                             Metaheuristic meta,
                             int numToCheck)

tabuMove

public SearchAction tabuMove(SolverSolution solution,
                             Neighborhood hood,
                             SearchGoal goal,
                             int numToCheck)

tabuMove

public SearchAction tabuMove(SolverSolution solution,
                             Neighborhood hood,
                             int numToCheck)

tabu

public Metaheuristic tabu(int forbiddenUndoMoves,
                          int forbiddenAlterMoves,
                          double objectiveGap)
Tabu Search metaheuristic that tracks moves performed during a local search and maintains lists of moves that are forbidden.

Parameters:
forbiddenUndoMoves - Number of moves that will return a variable to a previous value that are not allowed
forbiddenAlterMoves - Number of moves that will alter a previously changed variable in any way that are not allowed
objectiveGap - Amount objective value of move must be within initial objective value
See Also:
browseNeighborhood(SolverSolution, Neighborhood, Metaheuristic, CurrentNeighbor)

tabu

public Metaheuristic tabu(int forbiddenUndoMoves,
                          double objectiveGap)
Tabu Search metaheuristic that tracks moves performed during a local search and maintains lists of moves that are forbidden.

Parameters:
forbiddenUndoMoves - Number of moves that will return a variable to a previous value that are not allowed
objectiveGap - Amount objective value of move must be within initial objective value
See Also:
browseNeighborhood(SolverSolution, Neighborhood, Metaheuristic, CurrentNeighbor)

tabu

public Metaheuristic tabu(int forbiddenUndoMoves)
Tabu Search metaheuristic that tracks moves performed during a local search and maintains lists of moves that are forbidden.

Parameters:
forbiddenUndoMoves - Number of moves that will return a variable to a previous value that are not allowed
See Also:
browseNeighborhood(SolverSolution, Neighborhood, Metaheuristic, CurrentNeighbor)