org.jamesframework.core.search

Class NeighbourhoodSearch<SolutionType extends Solution>

java.lang.Object

org.jamesframework.core.search.Search<SolutionType>

org.jamesframework.core.search.LocalSearch<SolutionType>

org.jamesframework.core.search.NeighbourhoodSearch<SolutionType>

Type Parameters:

SolutionType - solution type of the problems that may be solved using this search, required to extend Solution

All Implemented Interfaces:

Runnable

Direct Known Subclasses:

MultiNeighbourhoodSearch, SingleNeighbourhoodSearch

public abstract class NeighbourhoodSearch<SolutionType extends Solution>
extends LocalSearch<SolutionType>

A neighbourhood search is a specific kind of local search in which the current solution is repeatedly modified by applying moves, generated by one or more neighbourhoods, that transform this solution into a similar, neighbouring solution. Generated moves can either be accepted, in which case the current solution is updated, or rejected, in which case the current solution is retained. The number of accepted and rejected moves during the current or last run can be accessed. This additional metadata applies to the current run only.

Author:

Herman De Beukelaer

Constructor Summary

Constructors

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.

Method Summary

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.

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, searchStep, 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

NeighbourhoodSearch

public NeighbourhoodSearch(Problem<SolutionType> problem)

Create a new neighbourhood search to solve the given problem, with default name "NeighbourhoodSearch".

Parameters:

problem - problem to solve

Throws:

NullPointerException - if problem is null

NeighbourhoodSearch

public NeighbourhoodSearch(String name,
                           Problem<SolutionType> problem)

Create a new neighbourhood search to solve the given problem, with a custom name. If name is null, the default name "NeighbourhoodSearch" will be assigned.

Parameters:

problem - problem to solve

name - custom search name

Throws:

NullPointerException - if problem is null

Method Detail

setEvaluatedMoveCache

public 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. By default, a 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.

Parameters:

cache - custom evaluated move cache

Throws:

SearchException - if the search is not idle

init

public void init()

When a neighbourhood search is initialized, the number of accepted and rejected moves is (re)set to zero.

Overrides:

init in class LocalSearch<SolutionType extends Solution>

getNumAcceptedMoves

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:

• If the search is either RUNNING or TERMINATING, this method returns the number of moves accepted since the current run was started.
• If the search is IDLE, the total number of moves accepted during the last run is returned, if any. Before the first run, JamesConstants.INVALID_MOVE_COUNT.
• While INITIALIZING the current run, JamesConstants.INVALID_MOVE_COUNT is returned.

The return value is always positive, except in those cases when JamesConstants.INVALID_MOVE_COUNT is returned.

Returns:

number of moves accepted during the current (or last) run

getNumRejectedMoves

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:

• If the search is either RUNNING or TERMINATING, this method returns the number of moves rejected since the current run was started.
• If the search is IDLE, the total number of moves rejected during the last run is returned, if any. Before the first run, JamesConstants.INVALID_MOVE_COUNT.
• While INITIALIZING the current run, JamesConstants.INVALID_MOVE_COUNT is returned.

The return value is always positive, except in those cases when JamesConstants.INVALID_MOVE_COUNT is returned.

Returns:

number of moves rejected during the current (or last) run

updateCurrentSolution

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.

Overrides:

updateCurrentSolution in class LocalSearch<SolutionType extends Solution>

Parameters:

solution - new current solution

evaluation - evaluation of new current solution

validation - validation of new current solution

evaluate

protected Evaluation evaluate(Move<? super SolutionType> move)

Evaluates a move to be applied to the current solution. If this move has been evaluated before and the obtained evaluation is still available in the cache, the cached evaluation will be returned. Else, the evaluation will be computed and offered to the cache.

Parameters:

move - move to be applied to the current solution

Returns:

evaluation of obtained neighbour, possibly retrieved from the evaluated move cache

validate

protected Validation validate(Move<? super SolutionType> move)

Validates a move to be applied to the current solution. If this move has been validated before and the obtained validation is still available in the cache, the cached validation will be returned. Else, the validation will be computed and offered to the cache.

Parameters:

move - move to be applied to the current solution

Returns:

validation of obtained neighbour, possibly retrieved from the evaluated move cache

isImprovement

protected 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.

Parameters:

move - move to be applied to the current solution

Returns:

true if applying this move yields a valid improvement

getBestMove

@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.

Parameters:

moves - collection of possible moves

requireImprovement - if set to true, only improving moves are considered

filters - additional move filters

Returns:

best valid move, may be null

accept

protected boolean accept(Move<? super SolutionType> move)

Accept the given move by applying it to the current solution. Updates the evaluation and validation of the current solution and checks whether a new best solution has been found. The updates only take place if the applied move yields a valid neighbour, else calling this method does not have any effect and 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.

Parameters:

move - accepted move to be applied to the current solution

Returns:

true if the update has been successfully performed, false if the update was cancelled because the obtained neighbour is invalid

incNumAcceptedMoves

protected void incNumAcceptedMoves(long inc)

Increase the number of accepted moves with the given value.

Parameters:

inc - value with which the number of accepted moves is increased

reject

protected void reject(Move<? super SolutionType> move)

Reject the given move. The default implementation ignores the specified move and simply updates the number of rejected moves. Specific searches can override this behaviour if desired.

Parameters:

move - rejected move (ignored)

incNumRejectedMoves

protected void incNumRejectedMoves(long inc)

Increase the number of rejected moves with the given value.

Parameters:

inc - value with which the number of rejected moves is increased