SolutionType
- solution type of the problems that may be solved using this search, required to extend Solution
public abstract class NeighbourhoodSearch<SolutionType extends Solution> extends LocalSearch<SolutionType>
Constructor and Description |
---|
NeighbourhoodSearch(Problem<SolutionType> problem)
Create a new neighbourhood search to solve the given problem, with default name "NeighbourhoodSearch".
|
NeighbourhoodSearch(String name,
Problem<SolutionType> problem)
Create a new neighbourhood search to solve the given problem, with a custom name.
|
Modifier and Type | Method and Description |
---|---|
protected boolean |
accept(Move<? super SolutionType> move)
Accept the given move by applying it to the current solution.
|
protected Evaluation |
evaluate(Move<? super SolutionType> move)
Evaluates a move to be applied to the current solution.
|
protected Move<? super SolutionType> |
getBestMove(Collection<? extends Move<? super SolutionType>> moves,
boolean requireImprovement,
Predicate<? super Move<? super SolutionType>>... filters)
Get the best valid move among a collection of possible moves.
|
long |
getNumAcceptedMoves()
Get the number of moves accepted during the current (or last) run.
|
long |
getNumRejectedMoves()
Get the number of moves rejected during the current (or last) run.
|
protected void |
incNumAcceptedMoves(long inc)
Increase the number of accepted moves with the given value.
|
protected void |
incNumRejectedMoves(long inc)
Increase the number of rejected moves with the given value.
|
void |
init()
When a neighbourhood search is initialized, the number of accepted and rejected moves is (re)set to zero.
|
protected boolean |
isImprovement(Move<? super SolutionType> move)
Checks whether applying the given move to the current solution yields a valid improvement.
|
protected void |
reject(Move<? super SolutionType> move)
Reject the given move.
|
void |
setEvaluatedMoveCache(EvaluatedMoveCache cache)
Sets a custom evaluated move cache, which is used to avoid repeated evaluation or validation of the same move
from the same current solution.
|
protected void |
updateCurrentSolution(SolutionType solution,
Evaluation evaluation,
Validation validation)
When updating the current solution in a neighbourhood search, the evaluated move cache is
cleared because it is no longer valid for the new current solution.
|
protected Validation |
validate(Move<? super SolutionType> move)
Validates a move to be applied to the current solution.
|
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, searchStep, searchStopped, setRandom, setStopCriterionCheckPeriod, start, stop, toString, updateBestSolution, updateBestSolution
public NeighbourhoodSearch(Problem<SolutionType> problem)
problem
- problem to solveNullPointerException
- if problem
is null
public NeighbourhoodSearch(String name, Problem<SolutionType> problem)
name
is
null
, the default name "NeighbourhoodSearch" will be assigned.problem
- problem to solvename
- custom search nameNullPointerException
- if problem
is null
public void setEvaluatedMoveCache(EvaluatedMoveCache cache)
SingleEvaluatedMoveCache
is used. Note that this method
may only be called when the search is idle. If the cache is set to null
, no caching will be applied.cache
- custom evaluated move cacheSearchException
- if the search is not idlepublic void init()
init
in class LocalSearch<SolutionType extends Solution>
public long getNumAcceptedMoves()
Get the number of moves accepted during the current (or last) run. The precise return value depends on the status of the search:
JamesConstants.INVALID_MOVE_COUNT
.
JamesConstants.INVALID_MOVE_COUNT
is returned.
The return value is always positive, except in those cases when JamesConstants.INVALID_MOVE_COUNT
is returned.
public long getNumRejectedMoves()
Get the number of moves rejected during the current (or last) run. The precise return value depends on the status of the search:
JamesConstants.INVALID_MOVE_COUNT
.
JamesConstants.INVALID_MOVE_COUNT
is returned.
The return value is always positive, except in those cases when JamesConstants.INVALID_MOVE_COUNT
is returned.
protected void updateCurrentSolution(SolutionType solution, Evaluation evaluation, Validation validation)
updateCurrentSolution
in class LocalSearch<SolutionType extends Solution>
solution
- new current solutionevaluation
- evaluation of new current solutionvalidation
- validation of new current solutionprotected Evaluation evaluate(Move<? super SolutionType> move)
move
- move to be applied to the current solutionprotected Validation validate(Move<? super SolutionType> move)
move
- move to be applied to the current solutionprotected boolean isImprovement(Move<? super SolutionType> move)
Checks whether applying the given move to the current solution yields a valid improvement.
An improvement is made if and only if (1) the given move is not null
,
(2) the move is valid, and (3) the obtained neighbour has a better evaluation than the
current solution or the current solution is invalid.
Note that computed values are cached to prevent multiple evaluations or validations of the same move.
move
- move to be applied to the current solutiontrue
if applying this move yields a valid improvement@SafeVarargs protected final Move<? super SolutionType> getBestMove(Collection<? extends Move<? super SolutionType>> moves, boolean requireImprovement, Predicate<? super Move<? super SolutionType>>... filters)
Get the best valid move among a collection of possible moves. The best valid move is the one yielding the
largest delta (see Search.computeDelta(Evaluation, Evaluation)
) when being applied to the current solution.
If requireImprovement
is set to true
, only moves that improve the current solution
are considered, i.e. moves that yield a positive delta (unless the current solution is invalid, then all
valid moves are improvements). Any number of additional filters can be specified so that moves are only
considered if they pass through all filters. Each filter is a predicate that should return true
if a given move is to be considered. If any filter returns false
for a specific move, this
move is discarded.
Returns null
if no move is found that satisfies all conditions.
Note that all computed evaluations and validations are cached. Before returning the selected best move, if any, its evaluation and validity are cached again to maximize the probability that these values will remain available in the cache.
moves
- collection of possible movesrequireImprovement
- if set to true
, only improving moves are consideredfilters
- additional move filtersnull
protected boolean accept(Move<? super SolutionType> move)
false
is returned.
After updating the current solution, the evaluated move cache is cleared as this cache is no longer valid for the new current solution. Furthermore, any local search listeners are informed and the number of accepted moves is updated.
move
- accepted move to be applied to the current solutiontrue
if the update has been successfully performed,
false
if the update was cancelled because the obtained
neighbour is invalidprotected void incNumAcceptedMoves(long inc)
inc
- value with which the number of accepted moves is increasedprotected void reject(Move<? super SolutionType> move)
move
- rejected move (ignored)protected void incNumRejectedMoves(long inc)
inc
- value with which the number of rejected moves is increasedCopyright © 2016. All rights reserved.