SolutionType
- solution type of the problems that may be solved using this search,
required to extend Solution
public class VariableNeighbourhoodSearch<SolutionType extends Solution> extends MultiNeighbourhoodSearch<SolutionType>
Variable neighbourhood search (VNS) algorithm. This search applies a series of neighbourhoods for random shaking of the current solution in combination with an arbitrary other local search algorithm L to modify the solution obtained after shaking, in an attempt to find a global improvement. More precisely, given a series of \(n_s\) shaking neighbourhoods \(N_i, i=0, ..., n_s-1\) and an arbitrary other local search algorithm \(L\), each step of VNS consists of:
By default, VNS applies variable neighbourhood descent (VND) as the local search algorithm L used to modify \(x'\). The list of neighbourhoods of VND is not required to be related to the shaking neighbourhoods of VNS. As VND is computationally intensive (it generates all neighbours in the current neighbourhood in every step), smaller neighbourhoods are often applied for VND compared to the shaking neighbourhoods of VNS. The latter may grow larger without computational concerns as they are only used for random sampling.
It is possible to use any other local search algorithm \(L\), by specifying a custom neighbourhood search factory. In every step, a fresh instance of \(L\) is created to be applied to solution \(x'\); afterwards, this instance is disposed. Usually, an algorithm is applied that terminates internally at some point in time (VND, steepest descent, ...). Alternatively, a never ending algorithm may be applied in combination with some stop criterion (e.g. random descent with a maximum runtime).
The combination of shaking and local search is considered to be one move in the VNS algorithm, which is only accepted
if it yields a global improvement. Therefore, NeighbourhoodSearch.getNumAcceptedMoves()
and NeighbourhoodSearch.getNumRejectedMoves()
reflect the number of times that such complex move has been accepted and rejected, respectively.
Note that MultiNeighbourhoodSearch.getNeighbourhoods()
returns the list of shaking neighbourhoods applied by VNS, which are, in
general, unrelated to the neighbourhoods applied by the default VND local search algorithm. All internals of the
applied local search algorithm \(L\) are shielded inside this algorithm, i.e. the algorithm is simply applied as
a black box to transform a given solution \(x'\) into another solution \(x''\).
Constructor and Description |
---|
VariableNeighbourhoodSearch(Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> shakingNeighs,
List<? extends Neighbourhood<? super SolutionType>> vndNeighs)
Creates a new variable neighbourhood search, specifying the problem to solve, the neighbourhoods used for shaking
and the neighbourhoods used by the default variable neighbourhood descent algorithm applied after shaking.
|
VariableNeighbourhoodSearch(Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> shakingNeighs,
LocalSearchFactory<SolutionType> localSearchFactory)
Creates a new variable neighbourhood search, specifying the problem to solve, the neighbourhoods used for
shaking, and a factory to create instances of a custom local search algorithm \(L\) to be applied after
shaking.
|
VariableNeighbourhoodSearch(String name,
Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> shakingNeighs,
LocalSearchFactory<SolutionType> localSearchFactory)
Creates a new variable neighbourhood search, specifying the problem to solve, the neighbourhoods used for
shaking in VNS, a factory to create instances of a custom local search algorithm \(L\) to be applied to
modify solutions obtained after shaking, and a custom search name.
|
Modifier and Type | Method and Description |
---|---|
LocalSearchFactory<SolutionType> |
getLocalSearchFactory()
Get the factory used to create instances of the local search algorithm which is applied to modify
solutions obtained after shaking.
|
protected void |
searchStep()
Performs a step of VNS.
|
void |
setLocalSearchFactory(LocalSearchFactory<SolutionType> localSearchFactory)
Set a custom factory to create instances of the local search algorithm to be applied to modify solutions
obtained after shaking.
|
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 VariableNeighbourhoodSearch(Problem<SolutionType> problem, List<? extends Neighbourhood<? super SolutionType>> shakingNeighs, List<? extends Neighbourhood<? super SolutionType>> vndNeighs)
null
and the lists of neighbourhoods can not be empty and can not
contain any null
elements. Violating these requirements will either throw an exception here,
or during search. The search name defaults to "VariableNeighbourhoodSearch".problem
- problem to solveshakingNeighs
- list of shaking neighbourhoods used by the variable neighbourhood searchvndNeighs
- list of neighbourhoods used by the default variable neighbourhood
descent algorithm (applied after each shaking operation)NullPointerException
- if problem
or shakingNeighs
are null
,
or if shakingNeighs
contain any null
elementsIllegalArgumentException
- if shakingNeighs
is emptypublic VariableNeighbourhoodSearch(Problem<SolutionType> problem, List<? extends Neighbourhood<? super SolutionType>> shakingNeighs, LocalSearchFactory<SolutionType> localSearchFactory)
null
, and the list of shaking neighbourhoods can not
be empty and can not contain any null
elements.
The search name defaults to "VariableNeighbourhoodSearch".problem
- problem to solveshakingNeighs
- list of shaking neighbourhoods used by the variable neighbourhood searchlocalSearchFactory
- factory to create instances of the local search algorithm \(L\)
applied after each shaking operationNullPointerException
- if problem
, shakingNeighs
or
localSearchFactory
are null
, or if
shakingNeighs
contains any null
elementsIllegalArgumentException
- if shakingNeighs
is emptypublic VariableNeighbourhoodSearch(String name, Problem<SolutionType> problem, List<? extends Neighbourhood<? super SolutionType>> shakingNeighs, LocalSearchFactory<SolutionType> localSearchFactory)
null
in which case the default name "VariableNeighbourhoodSearch" is assigned. The list of shaking neighbourhoods
can not be empty and can not contain any null
elements.name
- custom search nameproblem
- problem to solveshakingNeighs
- list of shaking neighbourhoods used by VNSlocalSearchFactory
- factory to create instances of the local search algorithm \(L\)NullPointerException
- if problem
, shakingNeighs
or
localSearchFactory
are null
, or if
shakingNeighs
contains any null
elementsIllegalArgumentException
- if shakingNeighs
is emptypublic void setLocalSearchFactory(LocalSearchFactory<SolutionType> localSearchFactory)
null
.localSearchFactory
- custom local search factoryNullPointerException
- if localSearchFactory
is null
public LocalSearchFactory<SolutionType> getLocalSearchFactory()
protected void searchStep()
searchStep
in class Search<SolutionType extends Solution>
JamesRuntimeException
- if depending on malfunctioning components (problem, neighbourhood, ...)Copyright © 2016. All rights reserved.