org.jamesframework.core.search.algo.vns

## Class VariableNeighbourhoodSearch<SolutionType extends Solution>

• Type Parameters:
SolutionType - solution type of the problems that may be solved using this search, required to extend Solution
All Implemented Interfaces:
Runnable

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:

1. Shaking: sample a random neighbour $$x'$$ of the current solution $$x$$, using shaking neighbourhood $$N_s$$ (initially, $$s = 0$$).
2. Local search: apply algorithm $$L$$ with $$x'$$ as its initial solution, until it terminates. The best solution found by $$L$$ is referred to as $$x''$$.
3. Acceptance: if $$x''$$ is a valid improvement over $$x$$ it is accepted as the new current solution and $$s$$ is reset to 0. Else, $$x$$ remains the current solution and $$s$$ is increased by one, so that the next shaking neighbourhood will be applied in the next step. If $$s$$ becomes equal to the number of shaking neighbourhoods $$n_s$$, it is cyclically reset to 0. Therefore, VNS never terminates internally but continues until a stop criterion is met.

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''$$.

Author:
Herman De Beukelaer
• ### Constructor Summary

Constructors
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.
• ### Method Summary

All Methods
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.
• ### Methods inherited from class org.jamesframework.core.search.MultiNeighbourhoodSearch

getNeighbourhoods, setNeighbourhoods
• ### Methods inherited from class org.jamesframework.core.search.NeighbourhoodSearch

accept, evaluate, getBestMove, getNumAcceptedMoves, getNumRejectedMoves, incNumAcceptedMoves, incNumRejectedMoves, init, isImprovement, reject, setEvaluatedMoveCache, updateCurrentSolution, validate
• ### Methods inherited from class org.jamesframework.core.search.LocalSearch

generateRandomInitialSolution, getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, setCurrentSolution, setCurrentSolution, updateCurrentAndBestSolution, updateCurrentAndBestSolution, updateCurrentSolution
• ### Methods inherited from class org.jamesframework.core.search.Search

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
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
• ### Constructor Detail

• #### VariableNeighbourhoodSearch

public 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. None of the arguments can be 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".
Parameters:
problem - problem to solve
shakingNeighs - list of shaking neighbourhoods used by the variable neighbourhood search
vndNeighs - list of neighbourhoods used by the default variable neighbourhood descent algorithm (applied after each shaking operation)
Throws:
NullPointerException - if problem or shakingNeighs are null, or if shakingNeighs contain any null elements
IllegalArgumentException - if shakingNeighs is empty
• #### VariableNeighbourhoodSearch

public 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. None of the arguments can be null, and the list of shaking neighbourhoods can not be empty and can not contain any null elements. The search name defaults to "VariableNeighbourhoodSearch".
Parameters:
problem - problem to solve
shakingNeighs - list of shaking neighbourhoods used by the variable neighbourhood search
localSearchFactory - factory to create instances of the local search algorithm $$L$$ applied after each shaking operation
Throws:
NullPointerException - if problem, shakingNeighs or localSearchFactory are null, or if shakingNeighs contains any null elements
IllegalArgumentException - if shakingNeighs is empty
• #### VariableNeighbourhoodSearch

public 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. Only the search name can be 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.
Parameters:
name - custom search name
problem - problem to solve
shakingNeighs - list of shaking neighbourhoods used by VNS
localSearchFactory - factory to create instances of the local search algorithm $$L$$
Throws:
NullPointerException - if problem, shakingNeighs or localSearchFactory are null, or if shakingNeighs contains any null elements
IllegalArgumentException - if shakingNeighs is empty
• ### Method Detail

• #### setLocalSearchFactory

public 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. The given factory can not be null.
Parameters:
localSearchFactory - custom local search factory
Throws:
NullPointerException - if localSearchFactory is null
• #### getLocalSearchFactory

public LocalSearchFactory<SolutionType> getLocalSearchFactory()
Get the factory used to create instances of the local search algorithm which is applied to modify solutions obtained after shaking. By default, this factory creates variable neighbourhood descent (VND) searches, but a custom factory may have been set.
Returns:
local search factory
• #### searchStep

protected void searchStep()
Performs a step of VNS. One step consists of:
1. Shaking using the current shaking neighbourhood
2. Modification using a new instance of the local search algorithm
3. Acceptance of modified solution if it is a global improvement. In such case, the search continues with the first shaking neighbourhood; else, the next shaking neighbourhood will be used (cyclically).
Specified by:
searchStep in class Search<SolutionType extends Solution>
Throws:
JamesRuntimeException - if depending on malfunctioning components (problem, neighbourhood, ...)