SolutionType
- solution type of the problems that may be solved using this search, required to extend Solution
public class VariableNeighbourhoodDescent<SolutionType extends Solution> extends MultiNeighbourhoodSearch<SolutionType>
Variable neighbourhood descent algorithm. In every search step, all neighbours of the current solution are generated using the k-th neighbourhood (initially, k = 0). The best neighbour is identified and accepted as the new current solution if it is an improvement. Else, k is increased by 1 so that the next neighbourhood will be used in the next step. Whenever an improvement is found, k is reset to 0. When k becomes equal to the number of available neighbourhoods, the search stops, as none of the neighbourhoods contains an improvement.
Good results are often obtained by providing (preferably disjoint) neighbourhoods ordered by increasing size. Then, only the smallest neighbourhood is extensively used, which will reduce computational costs, while larger neighbourhoods offer ways to escape from local optima where necessary.
Constructor and Description |
---|
VariableNeighbourhoodDescent(Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> neighs)
Creates a new variable neighbourhood descent search, specifying the problem to solve and the neighbourhoods
used to modify the current solution.
|
VariableNeighbourhoodDescent(String name,
Problem<SolutionType> problem,
List<? extends Neighbourhood<? super SolutionType>> neighs)
Creates a new variable neighbourhood descent search, specifying the problem to solve, the neighbourhoods used
to modify the current solution, and a custom search name.
|
Modifier and Type | Method and Description |
---|---|
protected void |
searchStep()
Investigates all neighbours of the current solution, using the k-th neighbourhood, and adopts the best one
as the new current solution, if it is an improvement.
|
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 VariableNeighbourhoodDescent(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
"VariableNeighbourhoodDescent".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 VariableNeighbourhoodDescent(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 "VariableNeighbourhoodDescent"
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 emptyprotected void searchStep()
searchStep
in class Search<SolutionType extends Solution>
JamesRuntimeException
- if depending on malfunctioning components (problem, neighbourhood, ...)Copyright © 2016. All rights reserved.