SolutionType
- solution type of the problems that may be solved using this search,
required to extend Solution
public class ReducedVariableNeighbourhoodSearch<SolutionType extends Solution> extends MultiNeighbourhoodSearch<SolutionType>
Reduced variable neighbourhood search (RVNS) algorithm. In every search step, a random neighbour of the current solution is sampled using the k-th neighbourhood (initially, k = 0). If this neighbour is a improvement, it is accepted as the new current solution. Else, k is increased by 1 so that the next neighbourhood will be used in the next step. Whenever an improvement is found, or whenever all neighbourhoods have been used, k is reset to 0. Note that, by default, RVNS never terminates internally, as neighbourhoods are applied cyclically. This behaviour can be changed so that the search stops when all neighbourhoods have been successively applied without yielding any improvement. However, in most cases, this is not desired as random moves are produced so that a few cycles through all neighbourhoods might be required to find an improvement.
The reduced variable neighbourhood search can be useful for larger problems, for which variable neighbourhood descent is too costly because it generates and evaluates all neighbours in every step.
Constructor and Description |
---|
ReducedVariableNeighbourhoodSearch(Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> neighs)
Creates a new reduced variable neighbourhood search, specifying the problem to solve and the neighbourhoods
used to modify the current solution.
|
ReducedVariableNeighbourhoodSearch(String name,
Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> neighs)
Creates a new reduced variable neighbourhood search, specifying the problem to solve, the neighbourhoods used
to modify the current solution, and a custom search name.
|
ReducedVariableNeighbourhoodSearch(String name,
Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> neighs,
boolean cycleNeighbourhoods)
Creates a new reduced variable neighbourhood search, specifying the problem to solve, the neighbourhoods used
to modify the current solution, and a custom search name; also, it is indicated whether neighbourhoods should
be applied cyclically or not (by default, they are).
|
Modifier and Type | Method and Description |
---|---|
protected void |
searchStep()
Samples a random neighbour of the current solution, using the k-th neighbourhood, and accepts it as the new
current solution if it is an improvement.
|
void |
setCycleNeighbourhoods(boolean cycleNeighbourhoods)
Indicates whether neighbourhoods should be applied cyclically or not, when all neighbourhoods have been
successively applied without finding any improvements.
|
getNeighbourhoods, setNeighbourhoods
accept, evaluate, getBestMove, getNumAcceptedMoves, getNumRejectedMoves, incNumAcceptedMoves, incNumRejectedMoves, init, isImprovement, reject, setEvaluatedMoveCache, updateCurrentSolution, validate
generateRandomInitialSolution, getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, setCurrentSolution, setCurrentSolution, updateCurrentAndBestSolution, updateCurrentAndBestSolution, updateCurrentSolution
addSearchListener, addStopCriterion, assertIdle, clearSearchListeners, clearStopCriteria, computeDelta, dispose, getBestSolution, getBestSolutionEvaluation, getBestSolutionValidation, getID, getMinDelta, getName, getProblem, getRandom, getRuntime, getSearchListeners, getStatus, getStatusLock, getSteps, getStepsWithoutImprovement, getTimeWithoutImprovement, removeSearchListener, removeStopCriterion, run, searchDisposed, searchStarted, searchStopped, setRandom, setStopCriterionCheckPeriod, start, stop, toString, updateBestSolution, updateBestSolution
public ReducedVariableNeighbourhoodSearch(Problem<SolutionType> problem, List<? extends Neighbourhood<? super SolutionType>> neighs)
null
and the list of neighbourhoods
can not be empty and can not contain any null
elements. The search name defaults to
"ReducedVariableNeighbourhoodSearch".problem
- problem to solveneighs
- list of neighbourhoods used to create neighbouring solutionsNullPointerException
- if problem
or neighs
are null
, or if
neighs
contains a null
elementIllegalArgumentException
- if neighs
is emptypublic ReducedVariableNeighbourhoodSearch(String name, Problem<SolutionType> problem, List<? extends Neighbourhood<? super SolutionType>> neighs)
null
, and the list of neighbourhoods can not be empty and can not contain any null
elements. The search name can be null
in which case the default name
"ReducedVariableNeighbourhoodSearch" is assigned.problem
- problem to solveneighs
- list of neighbourhoods used to create neighbouring solutionsname
- custom search nameNullPointerException
- if problem
or neighs
are null
, or if
neighs
contains a null
elementIllegalArgumentException
- if neighs
is emptypublic ReducedVariableNeighbourhoodSearch(String name, Problem<SolutionType> problem, List<? extends Neighbourhood<? super SolutionType>> neighs, boolean cycleNeighbourhoods)
null
, and the list of neighbourhoods can not be empty and can not contain any null
elements. The search name can be null
in which case the default name
"ReducedVariableNeighbourhoodSearch" is assigned.problem
- problem to solveneighs
- list of neighbourhoods used to create neighbouring solutionscycleNeighbourhoods
- indicates whether neighbourhoods are applied cyclically; if not, the search
will terminate internally when all neighbourhoods have been successively applied
without yielding any improvementname
- custom search nameNullPointerException
- if problem
or neighs
are null
, or if
neighs
contains a null
elementIllegalArgumentException
- if neighs
is emptypublic void setCycleNeighbourhoods(boolean cycleNeighbourhoods)
cycleNeighbourhoods
- indicates whether neighbourhoods are cyclically appliedprotected void searchStep()
If the k-th neighbourhood is unable to generate any move, k is also increased to try the next neighbourhood (if any) in the next step.
searchStep
in class Search<SolutionType extends Solution>
JamesRuntimeException
- if depending on malfunctioning components (problem, neighbourhood, ...)Copyright © 2016. All rights reserved.