fr.jussieu.gla.wasa.core
Class Algorithm

java.lang.Object
  |
  +--fr.jussieu.gla.wasa.core.Algorithm

public class Algorithm

extends java.lang.Object

The heart of the WASA framework, containing the Adaptative Search Algorithm implementation.

Start from a random assignment of variables in V

Repeat

1. Compute errors of all constraints in C and combine errors on each variable by considering for a given variable only the constraints on which it appears
2. select the variable X (not marked as Tabu) with highest error and evaluate costs of possible moves from X
3. if no improving move exists
   then mark X tabu for a given number of iterations
   else select the best move (min - conflict) and change the value of X accordingly

until a solution is found or a maximal number of iterations is reached

Version:

$Revision: 1.14 $ $Date: 2002/04/12 11:41:34 $

Author:

Laurent Caillette

Constructor Summary

Algorithm(Engine engine)

Method Summary

protected void	customize()
protected void	evaluateConstraints() Evaluates Constraints on current Buisness Object state.
protected AlgorithmState	explore() Evaluates Constraints on current Buisness Object state.
protected Evaluation	getAbsoluteBest()
protected Evaluation	getBestInLastNeighbourhood()
protected Constraint	getCurrentConstraint()
protected Engine	getEngine()
protected boolean	getErrorAssigned()
protected ErrorTable	getErrorTable()
protected Evaluation	getLastEvaluation()
protected Problem	getProblem()
protected Var	getSelectedVar()
AlgorithmState	getState()
protected Evaluation	getStepStartPoint()
protected TabuList	getTabuList()
protected void	setState(AlgorithmState newState)
AlgorithmState	step()

Methods inherited from class java.lang.Object

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

Constructor Detail

Algorithm

public Algorithm(Engine engine)

Method Detail

getEngine

protected Engine getEngine()

getProblem

protected Problem getProblem()

getTabuList

protected TabuList getTabuList()

getErrorTable

protected ErrorTable getErrorTable()

getState

public AlgorithmState getState()

setState

protected void setState(AlgorithmState newState)

getAbsoluteBest

protected Evaluation getAbsoluteBest()

getStepStartPoint

protected Evaluation getStepStartPoint()

getBestInLastNeighbourhood

protected Evaluation getBestInLastNeighbourhood()

getLastEvaluation

protected Evaluation getLastEvaluation()

getCurrentConstraint

protected Constraint getCurrentConstraint()

getErrorAssigned

protected boolean getErrorAssigned()

evaluateConstraints

protected void evaluateConstraints()
                            throws EngineException,
                                   java.lang.CloneNotSupportedException

Evaluates Constraints on current Buisness Object state.

Instance variables access :

• #problem : errors are unset
• #errorTable : cleared, then updated with errors set by each constraint's evaluation
• #lastEvaluation : assigned
• #absoluteBest : re-assigned if better than best was found

Method calls

• Problem#unsetErrors()
• Constraint.evaluate()
• #notifyErrorFor( Var ) from Constraint.evaluate()

getSelectedVar

protected Var getSelectedVar()

explore

protected AlgorithmState explore()
                          throws EngineException,
                                 java.lang.CloneNotSupportedException

Evaluates Constraints on current Buisness Object state.

Instance variables access :

• #stepStartPoint
• #lastEvaluation : assigned
• #absoluteBest : re-assigned if better than best was found

Method calls

• Problem.restore( Configuration )
• Explorer#reset()
• Explorer#apply()

Returns:

false if no Var to run an Explorer on was found, true otherwise.

customize

protected void customize()
                  throws EngineException,
                         java.lang.CloneNotSupportedException

step

public AlgorithmState step()
                    throws EngineException,
                           java.lang.CloneNotSupportedException