Opened 12 years ago

Closed 11 years ago

Last modified 11 years ago

#840 closed feature request (done)

Implement Algorithms: Tabu Search

Reported by: abeham Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.0
Component: Algorithms.TabuSearch Version: 3.3
Keywords: Cc: mkofler

Description

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.

Attachments (2)

Tabu Search 3.2.hl (27.2 KB) - added by abeham 12 years ago.
Tabu Search.hl (12.6 KB) - added by abeham 11 years ago.
First version of Tabu Search for HL 3.3

Download all attachments as: .zip

Change History (24)

Changed 12 years ago by abeham

comment:1 Changed 11 years ago by abeham

  • Component changed from ### Undefined ### to Algorithms.TS
  • Owner changed from swagner to abeham
  • Status changed from new to assigned

Added initial project for tabu search in r2972

comment:2 Changed 11 years ago by 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.

comment:3 Changed 11 years ago by abeham

Added first working tabu search in r2997

Changed 11 years ago by abeham

First version of Tabu Search for HL 3.3

comment:4 Changed 11 years ago by swagner

Updated configurations and project dependencies in r3001.

comment:5 Changed 11 years ago by abeham

updated in r3044

comment:6 Changed 11 years ago by abeham

updated tabu search in r3074

comment:7 Changed 11 years ago by abeham

renamed tabu search (from TS to TabuSearch) in r3100

comment:8 Changed 11 years ago by abeham

fixed plugin class after renaming in r3102

comment:9 Changed 11 years ago by 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.

comment:10 Changed 11 years ago by abeham

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

comment:11 Changed 11 years ago by abeham

fixed TabuSelector in r3132

comment:12 Changed 11 years ago by abeham

updated reporing and visualization in r3141

comment:13 Changed 11 years ago by abeham

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

comment:14 Changed 11 years ago by 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

comment:15 Changed 11 years ago by abeham

  • Summary Implement Algorithms: Tabu Search deleted

r3418

  • moved TabuMaker from Optimization to Optimization.Operators

comment:16 Changed 11 years ago by swagner

  • Summary set to Implement Algorithms: Tabu Search

comment:17 Changed 11 years ago by abeham

thx

comment:18 Changed 11 years ago by abeham

r3521

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

comment:19 Changed 11 years ago by abeham

r3679

  • fixed counting of evaluated moves

comment:20 Changed 11 years ago by abeham

  • Resolution set to fixed
  • Status changed from assigned to closed

Tabu Search has been implemented in 3.3

comment:21 Changed 11 years ago by swagner

  • Milestone changed from Iteration 4 to Current

Milestone Iteration 4 deleted

comment:11 Changed 11 years ago by swagner

  • Milestone changed from Current to HeuristicLab 3.3.0

Milestone Current deleted

Note: See TracTickets for help on using tickets.