org.coinor.opents
Class SingleThreadedTabuSearch

java.lang.Object
  org.coinor.opents.TabuSearchBase
      org.coinor.opents.SingleThreadedTabuSearch

All Implemented Interfaces:

java.io.Serializable, TabuSearch

Direct Known Subclasses:

MultiThreadedTabuSearch

public class SingleThreadedTabuSearch

extends TabuSearchBase

This version of the TabuSearch does not create any new threads, making it ideal for embedding in Enterprise JavaBeans. The startSolving() method blocks until the given number of iterations have been completed.

This code is licensed for public use under the Common Public License version 0.5.
The Common Public License, developed by IBM and modeled after their industry-friendly IBM Public License, differs from other common open source licenses in several important ways:

• You may include this software with other software that uses a different (even non-open source) license.
• You may use this software to make for-profit software.
• Your patent rights, should you generate patents, are protected.

Copyright © 2001 Robert Harder

Since:

1.0

See Also:

Serialized Form

Field Summary

protected AspirationCriteria	aspirationCriteria Aspiration criteria.
protected Solution	bestSolution Best solution.
protected boolean	chooseFirstImprovingMove Choose first improving neighbor instead of best neighbor overall.
protected Solution	currentSolution Current solution.
protected static java.io.PrintStream	err Print errors to this stream.
protected boolean	fireImprovingMoveMade Fire improving solution event at the end of the iteration.
protected boolean	fireNewBestSolution Fire new best solution event at the end of the iteration.
protected boolean	fireNewCurrentSolution Fire new current solution event at the end of the iteration.
protected boolean	fireNoChangeInValueMoveMade Fire no change in value solution event at the end of the iteration.
protected boolean	fireUnimprovingMoveMade Fire unimproving solution event at the end of the iteration.
protected int	iterationsToGo Iterations to go.
protected boolean	keepSolving Whether or not the tabu search should keep solving if it gets a chance to quit.
protected boolean	maximizing Maximizing: true.
protected MoveManager	moveManager Move manager.
protected ObjectiveFunction	objectiveFunction Objective function.
protected boolean	solving Whether or not the the tabu search is solving.
protected TabuList	tabuList Tabu list.

Constructor Summary

SingleThreadedTabuSearch()
Constructs a SingleThreadedTabuSearch with no tabu objects set.

SingleThreadedTabuSearch(Solution initialSolution, MoveManager moveManager, ObjectiveFunction objectiveFunction, TabuList tabuList, AspirationCriteria aspirationCriteria, boolean maximizing)
Constructs a SingleThreadedTabuSearch with all tabu objects set.

Method Summary

protected void	fireQueuedEvents() Fires events that are queued for firing at the end of an iteration.
static boolean	firstIsBetterThanSecond(double[] first, double[] second, boolean maximizing) Deprecated.
AspirationCriteria	getAspirationCriteria() Returns the aspiration criteria.
protected java.lang.Object[]	getBestMove(Solution soln, Move[] moves, ObjectiveFunction objectiveFunction, TabuList tabuList, AspirationCriteria aspirationCriteria, boolean maximizing, boolean chooseFirstImprovingMove) Gets the best move--one that should be used for this iteration.
protected static java.lang.Object[]	getBestMove(Solution soln, Move[] moves, ObjectiveFunction objectiveFunction, TabuList tabuList, AspirationCriteria aspirationCriteria, boolean maximizing, boolean chooseFirstImprovingMove, TabuSearch This) The static method that actually does the work.
Solution	getBestSolution() Returns the best solution found by the tabu search.
Solution	getCurrentSolution() Returns the current solution being used by the tabu search.
int	getIterationsToGo() Returns the number of iterations left for the tabu search to execute.
MoveManager	getMoveManager() Returns the move manager being used by the tabu search.
ObjectiveFunction	getObjectiveFunction() Returns the objective function being used by the tabu search.
TabuList	getTabuList() Returns the tabu list being used by the tabu search.
protected void	internalSetBestSolution(Solution solution) Set the best solution and prepare to fire an event.
protected void	internalSetCurrentSolution(Solution solution) Set the current solution and prepare to fire an event.
boolean	isChooseFirstImprovingMove() Returns whether or not the tabu search engine will choose the first improving move it encounters at each iteration (true) or the best move (false).
protected boolean	isFireImprovingMoveMade() Returns whether or not the tabu search plans to fire an improving move made TabuSearchEvent at the end of the iteration.
protected boolean	isFireNewBestSolution() Returns whether or not the tabu search plans to fire a new best solution TabuSearchEvent at the end of the iteration.
protected boolean	isFireNewCurrentSolution() Returns whether or not the tabu search plans to fire a new current solution TabuSearchEvent at the end of the iteration.
protected boolean	isFireNoChangeInValueMoveMade() Returns whether or not the tabu search plans to fire a no change in value move made TabuSearchEvent at the end of the iteration.
protected boolean	isFireUnimprovingMoveMade() Returns whether or not the tabu search plans to fire an unimproving move made TabuSearchEvent at the end of the iteration.
static boolean	isFirstBetterThanSecond(double[] first, double[] second, boolean maximizing) This single method is called many times to compare solutions.
protected boolean	isKeepSolving() Returns whether or not the tabu search should keep solving the next chance it gets to quit, like at the start of a new iteration.
boolean	isMaximizing() Returns whether or not the tabu search should be maximizing the objective function.
boolean	isSolving() Returns whether or not the tabu search is currently solving.
protected static boolean	isTabu(Solution soln, Move move, double[] val, TabuList tabuList, AspirationCriteria aspirationCriteria, TabuSearch This) Determine if the move is tabu and consider whether or not it satisfies the aspiration criteria.
protected void	performOneIteration() This large method goes through one iteration.
void	setAspirationCriteria(AspirationCriteria aspirationCriteria) Sets the aspiration criteria, effective at the start of the next iteration.
void	setBestSolution(Solution solution) Sets the best solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.
void	setChooseFirstImprovingMove(boolean choose) Setting this to true will cause the search to go faster by not necessarily evaluating all of the moves in a neighborhood for each iteration.
void	setCurrentSolution(Solution solution) Sets the current solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.
protected void	setFireImprovingMoveMade(boolean b) Internally set whether or not an improving move made TabuSearchEvent should be fired at the end of the iteration.
protected void	setFireNewBestSolution(boolean b) Internally set whether or not a new best solution TabuSearchEvent should be fired at the end of the iteration.
protected void	setFireNewCurrentSolution(boolean b) Internally set whether or not a new current solution TabuSearchEvent should be fired at the end of the iteration.
protected void	setFireNoChangeInValueMoveMade(boolean b) Internally set whether or not a no change in value move made TabuSearchEvent should be fired at the end of the iteration.
protected void	setFireUnimprovingMoveMade(boolean b) Internally set whether or not an unimproving move made TabuSearchEvent should be fired at the end of the iteration.
void	setIterationsToGo(int iterations) Sets the number of iterations that the tabu search has left to go.
protected void	setKeepSolving(boolean keepSolving) Tells the tabu search internally whether or not to keep solving the next chance it gets to quit, like at the start of a new iteration.
void	setMaximizing(boolean maximizing) Sets whether the tabu search should be maximizing or minimizing the objective function.
void	setMoveManager(MoveManager moveManager) Sets the move manager, effective at the start of the next iteration.
void	setObjectiveFunction(ObjectiveFunction function) Sets the objective function, effective at the start of the next iteration, and re-evaluates the current and best solution values.
protected void	setSolving(boolean solving) Sets the status of either solving or not solving.
void	setTabuList(TabuList tabuList) Sets the tabu list, effective at the start of the next iteration.
void	startSolving() Starts the tabu search solving in the current thread, blocking until the iterationsToGo property is zero.
void	stopSolving() Stops the tabu search and preserves the number of iterations remaining.

Methods inherited from class org.coinor.opents.TabuSearchBase

addTabuSearchListener, fireImprovingMoveMade, fireNewBestSolution, fireNewCurrentSolution, fireNoChangeInValueMoveMade, fireTabuSearchStarted, fireTabuSearchStopped, fireUnimprovingMoveMade, getIterationsCompleted, incrementIterationsCompleted, removeTabuSearchListener

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

objectiveFunction

protected ObjectiveFunction objectiveFunction

Objective function.

moveManager

protected MoveManager moveManager

Move manager.

tabuList

protected TabuList tabuList

Tabu list.

aspirationCriteria

protected AspirationCriteria aspirationCriteria

Aspiration criteria.

currentSolution

protected Solution currentSolution

Current solution.

bestSolution

protected Solution bestSolution

Best solution.

iterationsToGo

protected int iterationsToGo

Iterations to go.

maximizing

protected boolean maximizing

Maximizing: true. Minimizing: false.

solving

protected boolean solving

Whether or not the the tabu search is solving.

keepSolving

protected boolean keepSolving

Whether or not the tabu search should keep solving if it gets a chance to quit.

fireNewCurrentSolution

protected boolean fireNewCurrentSolution

Fire new current solution event at the end of the iteration.

fireNewBestSolution

protected boolean fireNewBestSolution

Fire new best solution event at the end of the iteration.

fireUnimprovingMoveMade

protected boolean fireUnimprovingMoveMade

Fire unimproving solution event at the end of the iteration.

fireImprovingMoveMade

protected boolean fireImprovingMoveMade

Fire improving solution event at the end of the iteration.

fireNoChangeInValueMoveMade

protected boolean fireNoChangeInValueMoveMade

Fire no change in value solution event at the end of the iteration.

chooseFirstImprovingMove

protected boolean chooseFirstImprovingMove

Choose first improving neighbor instead of best neighbor overall.

err

protected static java.io.PrintStream err

Print errors to this stream.

Constructor Detail

SingleThreadedTabuSearch

public SingleThreadedTabuSearch()

Constructs a SingleThreadedTabuSearch with no tabu objects set.

Since:

1.0

SingleThreadedTabuSearch

public SingleThreadedTabuSearch(Solution initialSolution,
                                MoveManager moveManager,
                                ObjectiveFunction objectiveFunction,
                                TabuList tabuList,
                                AspirationCriteria aspirationCriteria,
                                boolean maximizing)

Constructs a SingleThreadedTabuSearch with all tabu objects set. The initial solution is evaluated with the objective function, becomes the currentSolution and a copy becomes the bestSolution.

Parameters:

initialSolution - The initial currentSolution

moveManager - The move manager

objectiveFunction - The objective function

tabuList - The tabu list

aspirationCriteria - The aspiration criteria or null if none is to be used

maximizing - Whether or not the tabu search should be maximizing the objective function

Since:

1.0

See Also:

Solution, ObjectiveFunction, MoveManager, TabuList, AspirationCriteria

Method Detail

performOneIteration

protected void performOneIteration()
                            throws NoMovesGeneratedException,
                                   NoCurrentSolutionException

This large method goes through one iteration. It performs these steps:

• Get copies of tabu objects
• If there is no current solution, throw an exception
• If the best solution is null, set it to a copy of the current solution
• Clear event-queuing flags
• Get list of moves to try
• Find the best of those moves
• Register the best move
• Calculate new solution value using previously evaluated move's contribution
• Determine if move is unimproving
• Determine if new solution will be new best
• Operate on the current solution, making the new solution
• Set the new solution's value
• If new best, clone the solution
• Fire queued events

Throws:

NoMovesGeneratedException

NoCurrentSolutionException

Since:

1.0

See Also:

getBestMove(org.coinor.opents.Solution, org.coinor.opents.Move[], org.coinor.opents.ObjectiveFunction, org.coinor.opents.TabuList, org.coinor.opents.AspirationCriteria, boolean, boolean), isFirstBetterThanSecond(double[], double[], boolean), fireQueuedEvents()

getBestMove

protected java.lang.Object[] getBestMove(Solution soln,
                                         Move[] moves,
                                         ObjectiveFunction objectiveFunction,
                                         TabuList tabuList,
                                         AspirationCriteria aspirationCriteria,
                                         boolean maximizing,
                                         boolean chooseFirstImprovingMove)

Gets the best move--one that should be used for this iteration. By setting chooseFirstImprovingMove to true you tell the tabu search to return the first move it encounters that is improving and non-tabu rather than search through all of the moves. It's not static so that when the MultiThreadedTabuSearch invokes the performOneIteration method the proper method is invoked. Java's weird about overriding static methods...

Since:

1.0

getBestMove

protected static java.lang.Object[] getBestMove(Solution soln,
                                                Move[] moves,
                                                ObjectiveFunction objectiveFunction,
                                                TabuList tabuList,
                                                AspirationCriteria aspirationCriteria,
                                                boolean maximizing,
                                                boolean chooseFirstImprovingMove,
                                                TabuSearch This)

The static method that actually does the work. It's static so that the NeighborhoodHelper in the MultiThreadedTabuSearch can use the same code.

Since:

1.0

isTabu

protected static boolean isTabu(Solution soln,
                                Move move,
                                double[] val,
                                TabuList tabuList,
                                AspirationCriteria aspirationCriteria,
                                TabuSearch This)

Determine if the move is tabu and consider whether or not it satisfies the aspiration criteria.

Since:

1.0

firstIsBetterThanSecond

public static boolean firstIsBetterThanSecond(double[] first,
                                              double[] second,
                                              boolean maximizing)

Deprecated.

Deprecated and renamed to isFirstBetterThanSecond(double[], double[], boolean) to be named more consistently. This method still works. It simply calls the newly-named version.

Parameters:

first - The first array of doubles

second - The second array of doubles

maximizing - Whether or not the tabu search should be maximizing

Returns:

true if the first array of numbers is better than the second

Since:

1.0

isFirstBetterThanSecond

public static boolean isFirstBetterThanSecond(double[] first,
                                              double[] second,
                                              boolean maximizing)

This single method is called many times to compare solutions. Although all data is stored as doubles, they are cast to floats before they are compared. This ensures that the inevitable errors associated with all floating point numbers do not affect the likely intent of the numbers.

Parameters:

first - The first array of doubles

second - The second array of doubles

maximizing - Whether or not the tabu search should be maximizing

Returns:

true if the first array of numbers is better than the second

Since:

1.0

fireQueuedEvents

protected void fireQueuedEvents()

Fires events that are queued for firing at the end of an iteration.

Since:

1.0

internalSetCurrentSolution

protected void internalSetCurrentSolution(Solution solution)

Set the current solution and prepare to fire an event.

Parameters:

solution - The new current solution

Since:

1.0

internalSetBestSolution

protected void internalSetBestSolution(Solution solution)

Set the best solution and prepare to fire an event.

Parameters:

solution - The new best solution

Since:

1.0

setSolving

protected void setSolving(boolean solving)

Sets the status of either solving or not solving. This does not start and stop the solver--it only sets the reporting flag.

Parameters:

solving - Whether or not the tabu search should be marked as solving or not.

Since:

1.0

setKeepSolving

protected void setKeepSolving(boolean keepSolving)

Tells the tabu search internally whether or not to keep solving the next chance it gets to quit, like at the start of a new iteration.

Parameters:

keepSolving - Whether or not to keep solving

Since:

1.0

isKeepSolving

protected boolean isKeepSolving()

Returns whether or not the tabu search should keep solving the next chance it gets to quit, like at the start of a new iteration.

Returns:

Whether or not to keep solving

Since:

1.0

setFireNewCurrentSolution

protected void setFireNewCurrentSolution(boolean b)

Internally set whether or not a new current solution TabuSearchEvent should be fired at the end of the iteration.

Parameters:

b - Whether or not to fire a new current solution event.

Since:

1.0

setFireNewBestSolution

protected void setFireNewBestSolution(boolean b)

Internally set whether or not a new best solution TabuSearchEvent should be fired at the end of the iteration.

Parameters:

b - Whether or not to fire a new best solution event.

Since:

1.0

setFireUnimprovingMoveMade

protected void setFireUnimprovingMoveMade(boolean b)

Internally set whether or not an unimproving move made TabuSearchEvent should be fired at the end of the iteration.

Parameters:

b - Whether or not to fire an unimproving move made event.

Since:

1.0

setFireImprovingMoveMade

protected void setFireImprovingMoveMade(boolean b)

Internally set whether or not an improving move made TabuSearchEvent should be fired at the end of the iteration.

Parameters:

b - Whether or not to fire an improving move made event.

Since:

1.0-exp7

setFireNoChangeInValueMoveMade

protected void setFireNoChangeInValueMoveMade(boolean b)

Internally set whether or not a no change in value move made TabuSearchEvent should be fired at the end of the iteration.

Parameters:

b - Whether or not to fire a no change in value move made event.

Since:

1.0-exp7

isFireNewCurrentSolution

protected boolean isFireNewCurrentSolution()

Returns whether or not the tabu search plans to fire a new current solution TabuSearchEvent at the end of the iteration.

Returns:

whether or not the tabu search plans to fire a new current solution event

Since:

1.0

isFireNewBestSolution

protected boolean isFireNewBestSolution()

Returns whether or not the tabu search plans to fire a new best solution TabuSearchEvent at the end of the iteration.

Returns:

whether or not the tabu search plans to fire a new best solution event

Since:

1.0

isFireUnimprovingMoveMade

protected boolean isFireUnimprovingMoveMade()

Returns whether or not the tabu search plans to fire an unimproving move made TabuSearchEvent at the end of the iteration.

Returns:

whether or not the tabu search plans to fire an unimproving move made event

Since:

1.0

isFireImprovingMoveMade

protected boolean isFireImprovingMoveMade()

Returns whether or not the tabu search plans to fire an improving move made TabuSearchEvent at the end of the iteration.

Returns:

whether or not the tabu search plans to fire an improving move made event

Since:

1.0-exp7

isFireNoChangeInValueMoveMade

protected boolean isFireNoChangeInValueMoveMade()

Returns whether or not the tabu search plans to fire a no change in value move made TabuSearchEvent at the end of the iteration.

Returns:

whether or not the tabu search plans to fire a no change in value move made event

Since:

1.0-exp7

startSolving

public void startSolving()

Starts the tabu search solving in the current thread, blocking until the iterationsToGo property is zero.

Since:

1.0c

See Also:

TabuSearch.setIterationsToGo(int), TabuSearch.getIterationsToGo()

stopSolving

public void stopSolving()

Stops the tabu search and preserves the number of iterations remaining.

Since:

1.0

See Also:

TabuSearch.setIterationsToGo(int), TabuSearch.getIterationsToGo()

isSolving

public boolean isSolving()

Returns whether or not the tabu search is currently solving.

Returns:

Whether or not the tabu search is currently solving.

Since:

1.0

setObjectiveFunction

public void setObjectiveFunction(ObjectiveFunction function)

Sets the objective function, effective at the start of the next iteration, and re-evaluates the current and best solution values.

Parameters:

function - The new objective function.

Since:

1.0

See Also:

ObjectiveFunction

setMoveManager

public void setMoveManager(MoveManager moveManager)

Sets the move manager, effective at the start of the next iteration.

Parameters:

moveManager - The new move manager.

Since:

1.0

See Also:

MoveManager

setTabuList

public void setTabuList(TabuList tabuList)

Sets the tabu list, effective at the start of the next iteration.

Parameters:

tabuList - The new tabu list.

Since:

1.0

See Also:

TabuList

setAspirationCriteria

public void setAspirationCriteria(AspirationCriteria aspirationCriteria)

Sets the aspiration criteria, effective at the start of the next iteration. A null value means there is no aspiration criteria.

Parameters:

aspirationCriteria - The new aspiration criteria

Since:

1.0

See Also:

AspirationCriteria

setBestSolution

public void setBestSolution(Solution solution)

Sets the best solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.

Parameters:

solution - The new best solution.

Since:

1.0

See Also:

Solution

setCurrentSolution

public void setCurrentSolution(Solution solution)

Sets the current solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.

Parameters:

solution - The new current solution.

Since:

1.0

See Also:

Solution

setIterationsToGo

public void setIterationsToGo(int iterations)

Sets the number of iterations that the tabu search has left to go. If the tabu search was previously idle, that is iterationsToGo was less than or equal to zero, the tabu search will not automatically begin again. In this case the tabu search will not begin again until startSolving() is called.

Parameters:

iterations - The number of iterations left for the tabu earch to execute.

Since:

1.0

See Also:

startSolving()

setMaximizing

public void setMaximizing(boolean maximizing)

Sets whether the tabu search should be maximizing or minimizing the objective function. A value of true means maximize. A value of false means minimize.

Parameters:

maximizing - Whether or not the tabu search should be maximizing the objective function.

Since:

1.0

setChooseFirstImprovingMove

public void setChooseFirstImprovingMove(boolean choose)

Setting this to true will cause the search to go faster by not necessarily evaluating all of the moves in a neighborhood for each iteration. Instead of evaluating all of the moves and selecting the best one for execution, setting this will cause the tabu search engine to select the first move that it encounters that causes an improvement to the current solution. The default value is false.

Parameters:

choose - Whether or not the first improving move will be chosen

Since:

1.0.1

getObjectiveFunction

public ObjectiveFunction getObjectiveFunction()

Returns the objective function being used by the tabu search.

Returns:

The objective function being used by the tabu search.

Since:

1.0

See Also:

ObjectiveFunction

getMoveManager

public MoveManager getMoveManager()

Returns the move manager being used by the tabu search.

Returns:

The move manager being used by the tabu search.

Since:

1.0

See Also:

MoveManager

getTabuList

public TabuList getTabuList()

Returns the tabu list being used by the tabu search.

Returns:

The tabu list being used by the tabu search.

Since:

1.0

See Also:

TabuList

getAspirationCriteria

public AspirationCriteria getAspirationCriteria()

Returns the aspiration criteria. A null value means there is no aspiration criteria.

Returns:

The aspiration criteria

Since:

1.0

See Also:

AspirationCriteria

getBestSolution

public Solution getBestSolution()

Returns the best solution found by the tabu search.

Returns:

The best solution found by the tabu search.

Since:

1.0

See Also:

Solution

getCurrentSolution

public Solution getCurrentSolution()

Returns the current solution being used by the tabu search.

Returns:

The current solution being used by the tabu search.

Since:

1.0

See Also:

Solution

getIterationsToGo

public int getIterationsToGo()

Returns the number of iterations left for the tabu search to execute.

Returns:

The number of iterations left for the tabu search to execute.

Since:

1.0

isMaximizing

public boolean isMaximizing()

Returns whether or not the tabu search should be maximizing the objective function.

Returns:

Whether or not the tabu search should be maximizing the objective function.

Since:

1.0

isChooseFirstImprovingMove

public boolean isChooseFirstImprovingMove()

Returns whether or not the tabu search engine will choose the first improving move it encounters at each iteration (true) or the best move (false).

Returns:

Whether or not the first improving move will be chosen

Since:

1.0.1