Opened 6 years ago

Closed 6 years ago

#1541 closed enhancement (done)

Implement Robust Taboo Search for the QAP

Reported by: abeham Owned by: gkronber
Priority: medium Milestone: HeuristicLab 3.3.6
Component: Problems.QuadraticAssignment Version: 3.3.6
Keywords: Cc:

Description

Taillard presents in an article from 1991 an algorithm that is often cited and that is based on Glover's tabu search.

Change History (24)

comment:1 Changed 6 years ago by abeham

  • Status changed from new to accepted

comment:2 Changed 6 years ago by abeham

r6350:6351

  • Created branch for implementing QAP specific algorithms
  • Added Robust Taboo Search (Taillard 1991)

comment:3 Changed 6 years ago by abeham

  • Version changed from 3.3.4 to branch

comment:4 Changed 6 years ago by abeham

r6416

  • Added PermutationView that allows to change the permutation type
  • Updated AFA and PopDiv Analyzer
  • Simplified QAP name to just the instance when loading from embedded resource
Last edited 6 years ago by abeham (previous) (diff)

comment:5 Changed 6 years ago by abeham

r6586

  • Updated code to reflect what Eric Taillard's code does at http://mistic.heig-vd.ch/taillard/codes.dir/tabou_qap.cpp which is however not quite what is described in the paper. (there's a newer implementation also)
  • Updated the swap2 move evaluator to perform move evaluations in O(1) for several cases by memorizing the move quality of the previous iteration
  • Added a unit test to test the new faster evaluation
  • Changed the robust taboo search to use this faster evaluation
  • Renamed some operators (dropping the QAP pre- and postfix)
Last edited 6 years ago by abeham (previous) (diff)

comment:6 Changed 6 years ago by abeham

r6593

  • Changed aspiration criterion after contacting Taillard
  • added option to choose between old or new adaption scheme

comment:7 Changed 6 years ago by abeham

r6594

  • fixed some bugs

comment:8 Changed 6 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.6

comment:9 Changed 6 years ago by abeham

r6627

  • updated from trunk

comment:10 Changed 6 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from accepted to reviewing
  • Version changed from branch to 3.3.5

r6628

  • merged to trunk

comment:11 Changed 6 years ago by abeham

r6632, r6634

  • removed branch
  • removed obsolete files

comment:12 Changed 6 years ago by abeham

r6637

  • removed unnecessary dependency

comment:13 Changed 6 years ago by gkronber

A few observations from short testing:

  • in the permutations view: changing the type (label: 'Value') seemingly has no effect?
  • the parameter TerminateOnOptimalSolution is unique to robust tabu search in HeuristicLab. I think the parameter should be set to false by default and should be hidden to have consistent behavior of all algorithms in HeuristicLab.
  • The visualization in the solution view is not updated when a new best solution is found. The chart is redrawn only after the algorithm has been paused or stopped.
  • Text in the visualization view looks 'strange' (maybe an aliasing effect?)
  • Btw. the visualization is pretty cool, thanks for implementing this!
  • more thorough code review will follow soon

comment:14 Changed 6 years ago by gkronber

r6835: added QAP plugins to Builder.testsettings file

comment:15 Changed 6 years ago by abeham

Thanks for your comment. Regarding the extra termination criterion: I found this quite useful while testing and experimenting with the RTS and actually want to have something like this in other algorithms as well (currently I have to convert every algorithm into a user defined algorithm). Maybe the parameter should not necessarily terminate on finding the optimal solution, but something like "terminate on solution quality" with the option to map this to BestKnownQuality. Pre-release we had talked about customizable termination criteria, but this topic has not been pursued since then.

comment:16 Changed 6 years ago by abeham

r6953

  • Made parameter properties public

comment:17 Changed 6 years ago by abeham

  • Owner changed from gkronber to abeham
  • Status changed from reviewing to assigned

A bug has been identified, most probably in the case when all moves are tabu

comment:18 Changed 6 years ago by abeham

r7040

  • Fixed permutation view and changed label
  • Fixed problem in the RTS operator when all moves are tabu (the original code continues when all moves are tabu, so this is also the case here)
  • Changed the Analyzer parameter type in RTS, a FixedValueParameter is not appropriate for operator parameters

comment:19 Changed 6 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from assigned to reviewing

r7092

  • Clearing the graphics with white color solves the text rendering problem

The issues mentioned by gkronber have all been addressed.

comment:20 Changed 6 years ago by abeham

ascheibe and me found out that the RTS and the NSGA-II are missing the Prepare override that prevents these algorithms from running with an empty problem. This still has to be fixed.

comment:21 Changed 6 years ago by abeham

r7209

  • fixed prepare in RTS

comment:22 Changed 6 years ago by gkronber

Reviewed r7092, r7209, r7040, r6953. LGTM.

comment:23 Changed 6 years ago by gkronber

  • Status changed from reviewing to readytorelease

comment:24 Changed 6 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.5 to 3.3.6
Note: See TracTickets for help on using tickets.