|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.sf.cpsolver.exam.heuristics.ExamTabuSearch
public class ExamTabuSearch
Tabu search algorithm.
If used as NeighbourSelection
, the most improving (re)assignment of a
value to a variable is returned (all variables and all their values are
enumerated). If there are more than one of such assignments, one is selected
randomly. A returned assignment can cause unassignment of other existing
assignments. The search is stopped (
selectNeighbour(Solution)
returns null) after
TabuSearch.MaxIdle idle (not improving) iterations.
If used as ValueSelection
, the most improving (re)assignment of a
value to a given variable is returned (all values of the given variable are
enumerated). If there are more than one of such assignments, one is selected
randomly. A returned assignment can cause unassignment of other existing
assignments.
To avoid cycling, a tabu is maintainded during the search. It is the list of
the last n selected values. A selection of a value that is present in the
tabu list is only allowed when it improves the best ever found solution.
The minimum size of the tabu list is TabuSearch.MinSize, maximum size is
TabuSearch.MaxSize (tabu list is not used when both sizes are zero). The
current size of the tabu list starts at MinSize (and is reset to MinSize
every time a new best solution is found), it is increased by one up to the
MaxSize after TabuSearch.MaxIdle / (MaxSize - MinSize) non-improving
iterations.
Conflict-based Statistics ConflictStatistics
(CBS) can be used
instead of (or together with) tabu list, when CBS is used as a solver
extension.
Constructor Summary | |
---|---|
ExamTabuSearch(DataProperties properties)
TabuSearch.MaxIdle ... maximum number of idle iterations (default is 10000) TabuSearch.MinSize ... minimum size of the tabu list TabuSearch.MaxSize ... maximum size of the tabu list Value.ValueWeight ... weight of a value (i.e., Value.toDouble() )
Value.ConflictWeight ... weight of a conflicting value (see
Model.conflictValues(Value) ), it is also weighted by the past
occurrences when conflict-based statistics is used
|
Method Summary | |
---|---|
void |
init(Solver<Exam,ExamPlacement> solver)
Initialization |
Neighbour<Exam,ExamPlacement> |
selectNeighbour(Solution<Exam,ExamPlacement> solution)
Neighbor selection |
ExamPlacement |
selectValue(Solution<Exam,ExamPlacement> solution,
Exam exam)
Value selection |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public ExamTabuSearch(DataProperties properties) throws Exception
Value.toDouble()
)
Model.conflictValues(Value)
), it is also weighted by the past
occurrences when conflict-based statistics is used
Exception
Method Detail |
---|
public void init(Solver<Exam,ExamPlacement> solver)
init
in interface NeighbourSelection<Exam,ExamPlacement>
init
in interface ValueSelection<Exam,ExamPlacement>
public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution)
selectNeighbour
in interface NeighbourSelection<Exam,ExamPlacement>
solution
- given solution
public ExamPlacement selectValue(Solution<Exam,ExamPlacement> solution, Exam exam)
selectValue
in interface ValueSelection<Exam,ExamPlacement>
solution
- current solutionexam
- selected variable
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |