Implement Algorithms: Tabu Search

[abeham]

The attached engine describes a simple tabu search metaheuristic in HL3.2. The central operator is the MoveGenerator (e.g. !ExhaustiveSwap2MoveGenerator or !RandomSwap2MoveGenerator) that injects:

1. An item describing the move (e.g. Swap2Move)
2. An operator evaluating its quality (e.g. Swap2MoveEvaluator)
3. An operator evaluating its tabu status (e.g. Swap2TabuEvaluator)
4. An operator applying its move (e.g. Swap2MoveMaker)

As discussed with Monika, the MoveGenerator can inject the 3 operators either in every subscope together with the move item, or in the scope where it is applied on. The first action allows different types of moves to be made in a single iteration, the second does not allow this, but requires less memory. The MoveGenerator simply appends move subscopes to the current scope's subscopes.

The tabu list is independent of the move in that it is a ringbuffer-like datastructure that stores move items. Tabuness is evaluated by comparing the current move item to all move items in the tabu list. The operator to make a move tabu is therefor independent of the actual move.

The attached engine cannot be executed and constitutes a concept only.

[abeham]

Added initial project for tabu search in r2972

[abeham]

Added an initial TSOperator in r2976 and filled it in r2981:2982

The literature on tabu search is very vague and probably has more possibilities than concrete implementations. For now I decided to include all possibilities as placeholder operators.

So there are quite a number of placeholder operators:

• MoveGenerator: Generates a number of moves either by total enumeration of the neighborhood or by sampling depending on the actual operator used
• MoveQualityEvaluator: Evaluates a certain move on a given problem
• MoveTabuEvaluator: Checks if a move is tabu by comparing the move with the attributes stored in the tabu list
• TabuSelector: There exists one that features the default aspiration criterion, however more complex aspiration criteria exist
• MoveTabuMaker: Adds the move or attributes of it to the tabu list
• MoveMaker: Performs the move

The tabu list data structure has not yet been defined. It will probably be a ring buffer like data structure of IItem.

[abeham]

Added first working tabu search in r2997

[abeham]

First version of Tabu Search for HL 3.3

[swagner]

Updated configurations and project dependencies in r3001.

[abeham]

updated in r3044

[abeham]

updated tabu search in r3074

[abeham]

renamed tabu search (from TS to TabuSearch) in r3100

[abeham]

fixed plugin class after renaming in r3102

[abeham]

As a reminder:

• In all TabuMoveEvaluators I need to make sure that changing the MoveTabuParameter's ActualName doesn't break the TabuSearch algorithm. Need to listen on the parameter's ActualNameChanged event.

[abeham]

fixed reminder in r3104 also added two different tabu criteria for 2-opt moves

[abeham]

fixed TabuSelector in r3132

[abeham]

updated reporing and visualization in r3141

[abeham]

fixed termination of algorithm when neighborhood contains only tabu moves in r3195

[abeham]

greatly improved the performance of TabuSearch by adding a quality parameter to the move attributes and a more specific aspiration criterion that allows making a move as soon as it leads to a better solution than the one given in the tabu list for each move r3340

[abeham]

r3418

• moved TabuMaker from Optimization to Optimization.Operators

[abeham]

thx

[abeham]

r3521

• showed best quality and best known quality in the chart
• simplified the operator graph

[abeham]

r3679

• fixed counting of evaluated moves

[abeham]

Tabu Search has been implemented in 3.3

[swagner]

Milestone Iteration 4 deleted

[swagner]

Milestone Current deleted