org.jamesframework.core.search.algo.tabu

Class TabuSearch<SolutionType extends Solution>

java.lang.Object

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

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

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

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

org.jamesframework.core.search.algo.tabu.TabuSearch<SolutionType>

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 TabuSearch<SolutionType extends Solution>
extends SingleNeighbourhoodSearch<SolutionType>

Tabu search algorithm. In every search step, all neighbours of the current solution are validated and evaluated. The best valid neighbour is then adopted as the new current solution, even if it is no improvement over the current solution. To avoid repeatedly revisiting the same solutions, moves might be declared tabu based on a tabu memory. This memory dynamically tracks (a limited number of) recently visited solutions, features of these solutions and/or recently applied moves (i.e. recently modified features). If a move is tabu, it is not considered, unless it yields a solution which is better than the best solution found so far (aspiration criterion).

If all valid neighbours of the current solution are tabu, the search stops. Note that this may never happen so that a stop criterion should preferably be set to ensure termination.

Author:

Herman De Beukelaer

Constructor Summary

Constructors

Constructor and Description
TabuSearch(Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood, TabuMemory<SolutionType> tabuMemory) Creates a new tabu search, specifying the problem to solve, the neighbourhood used to modify the current solution and the applied tabu memory.
TabuSearch(String name, Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood, TabuMemory<SolutionType> tabuMemory) Creates a new tabu search, specifying the problem to solve, the neighbourhood used to modify the current solution, the applied tabu memory and a custom search name.

Method Summary

Modifier and Type	Method and Description
protected boolean	accept(Move<? super SolutionType> move) Overrides acceptance of a move to update the tabu memory by registering the newly visited solution.
void	clearTabuMemory() Clear the tabu memory.
protected void	generateRandomInitialSolution() Updates the tabu memory if a random initial solution is generated.
TabuMemory<SolutionType>	getTabuMemory() Get the tabu memory.
protected void	searchStep() In every step, all neighbours of the current solution are inspected and the best valid, non tabu neighbour is adopted as the new current solution, if any.
void	setCurrentSolution(SolutionType solution) Updates the tabu memory when a custom current/initial solution is set.
void	setTabuMemory(TabuMemory<SolutionType> tabuMemory) Set the tabu memory.

Methods inherited from class org.jamesframework.core.search.SingleNeighbourhoodSearch

getNeighbourhood, setNeighbourhood

Methods inherited from class org.jamesframework.core.search.NeighbourhoodSearch

evaluate, getBestMove, getNumAcceptedMoves, getNumRejectedMoves, incNumAcceptedMoves, incNumRejectedMoves, init, isImprovement, reject, setEvaluatedMoveCache, updateCurrentSolution, validate

Methods inherited from class org.jamesframework.core.search.LocalSearch

getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, 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

TabuSearch

public TabuSearch(Problem<SolutionType> problem,
                  Neighbourhood<? super SolutionType> neighbourhood,
                  TabuMemory<SolutionType> tabuMemory)

Creates a new tabu search, specifying the problem to solve, the neighbourhood used to modify the current solution and the applied tabu memory. None of the arguments can be null. The search name defaults to "TabuSearch".

Note that the applied neighbourhood and tabu memory should be compatible in terms of generated and accepted move types, respectively, else an IncompatibleTabuMemoryException might be thrown during search.

Parameters:

problem - problem to solve

neighbourhood - neighbourhood used to create neighbouring solutions

tabuMemory - applied tabu memory

Throws:

NullPointerException - if problem, neighbourhood or tabuMemory are null

TabuSearch

public TabuSearch(String name,
                  Problem<SolutionType> problem,
                  Neighbourhood<? super SolutionType> neighbourhood,
                  TabuMemory<SolutionType> tabuMemory)

Creates a new tabu search, specifying the problem to solve, the neighbourhood used to modify the current solution, the applied tabu memory and a custom search name. The problem, neighbourhood and tabu memory can not be null. The search name can be null in which case the default name "TabuSearch" is assigned.

Note that the applied neighbourhood and tabu memory should be compatible in terms of generated and accepted move types, respectively, else an IncompatibleTabuMemoryException might be thrown during search.

Parameters:

name - custom search name

problem - problem to solve

neighbourhood - neighbourhood used to create neighbouring solutions

tabuMemory - applied tabu memory

Throws:

NullPointerException - if problem, neighbourhood or tabyMemory are null

Method Detail

clearTabuMemory

public void clearTabuMemory()

Clear the tabu memory.

getTabuMemory

public TabuMemory<SolutionType> getTabuMemory()

Get the tabu memory.

Returns:

tabu memory used by this search

setTabuMemory

public void setTabuMemory(TabuMemory<SolutionType> tabuMemory)

Set the tabu memory. Can not be null.

Parameters:

tabuMemory - new tabu memory

Throws:

NullPointerException - if tabuMemory is null

accept

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

Overrides acceptance of a move to update the tabu memory by registering the newly visited solution.

Overrides:

accept in class NeighbourhoodSearch<SolutionType extends Solution>

Parameters:

move - move to be accepted

Returns:

true if the update was successful, false if the move is invalid

setCurrentSolution

public void setCurrentSolution(SolutionType solution)

Updates the tabu memory when a custom current/initial solution is set. Note that this method may only be called when the search is idle.

Overrides:

setCurrentSolution in class LocalSearch<SolutionType extends Solution>

Parameters:

solution - manually specified current solution

Throws:

SearchException - if the search is not idle

NullPointerException - if solution is null

generateRandomInitialSolution

protected void generateRandomInitialSolution()

Updates the tabu memory if a random initial solution is generated.

Overrides:

generateRandomInitialSolution in class LocalSearch<SolutionType extends Solution>

Throws:

SearchException - if a current solution is already set when calling this method

searchStep

protected void searchStep()

In every step, all neighbours of the current solution are inspected and the best valid, non tabu neighbour is adopted as the new current solution, if any. If all valid neighbours are tabu, the search stops.

Specified by:

searchStep in class Search<SolutionType extends Solution>

Throws:

IncompatibleTabuMemoryException - if the applied tabu memory is not compatible with the type of moves generated by the applied neighbourhood

JamesRuntimeException - if depending on malfunctioning components (problem, neighbourhood, ...)