search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
34 stars 16 forks source link

Implement Robust Taboo Search for the QAP #1541

Closed HeuristicLab-Trac-Bot closed 12 years ago

HeuristicLab-Trac-Bot commented 13 years ago

Issue migrated from trac ticket # 1541

milestone: HeuristicLab 3.3.6 | component: Problems.QuadraticAssignment | priority: medium | resolution: done

2011-05-31 11:41:50: @abeham created the issue

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

HeuristicLab-Trac-Bot commented 13 years ago

2011-05-31 11:42:23: @abeham changed status from new to accepted

HeuristicLab-Trac-Bot commented 13 years ago

2011-06-01 13:06:33: @abeham commented

r6350 to r6351

  • Created branch for implementing QAP specific algorithms
  • Added Robust Taboo Search (Taillard 1991)
HeuristicLab-Trac-Bot commented 13 years ago

2011-06-15 23:11:58: @abeham commented

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
HeuristicLab-Trac-Bot commented 13 years ago

2011-06-15 23:11:58: @abeham

HeuristicLab-Trac-Bot commented 13 years ago

2011-07-22 12:03:49: @abeham commented

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)
HeuristicLab-Trac-Bot commented 13 years ago

2011-07-22 12:03:49: @abeham

HeuristicLab-Trac-Bot commented 13 years ago

2011-07-22 12:03:49: @abeham

HeuristicLab-Trac-Bot commented 13 years ago

2011-07-25 18:28:32: @abeham commented

r6593

  • Changed aspiration criterion after contacting Taillard
  • added option to choose between old or new adaption scheme
HeuristicLab-Trac-Bot commented 13 years ago

2011-07-25 23:28:20: @abeham commented

r6594

  • fixed some bugs
HeuristicLab-Trac-Bot commented 13 years ago

2011-07-29 13:13:28: @abeham changed milestone from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.6

HeuristicLab-Trac-Bot commented 13 years ago

2011-08-04 08:27:47: @abeham commented

r6627

  • updated from trunk
HeuristicLab-Trac-Bot commented 13 years ago

2011-08-04 10:06:44: @abeham changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 13 years ago

2011-08-04 10:06:44: @abeham changed owner from abeham to gkronber

HeuristicLab-Trac-Bot commented 13 years ago

2011-08-04 10:06:44: @abeham commented

r6628

  • merged to trunk
HeuristicLab-Trac-Bot commented 13 years ago

2011-08-04 11:26:17: @abeham commented

r6632 (not migrated), r6634

  • removed branch
  • removed obsolete files
HeuristicLab-Trac-Bot commented 13 years ago

2011-08-05 07:49:24: @abeham commented

r6637

  • removed unnecessary dependency
HeuristicLab-Trac-Bot commented 12 years ago

2011-09-27 10:23:16: @gkronber commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2011-09-27 10:30:45: @gkronber commented

r6835: added QAP plugins to Builder.testsettings file

HeuristicLab-Trac-Bot commented 12 years ago

2011-10-19 09:54:26: @abeham commented

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.

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-06 21:09:01: @abeham commented

r6953

  • Made parameter properties public
HeuristicLab-Trac-Bot commented 12 years ago

2011-11-08 12:16:05: @abeham changed status from reviewing to assigned

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-08 12:16:05: @abeham changed owner from gkronber to abeham

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-08 12:16:05: @abeham commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 14:54:40: @abeham commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2011-11-29 10:15:08: @abeham changed status from assigned to reviewing

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-29 10:15:08: @abeham changed owner from abeham to gkronber

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-29 10:15:08: @abeham commented

r7092

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

The issues mentioned by gkronber have all been addressed.

HeuristicLab-Trac-Bot commented 12 years ago

2011-12-18 09:59:56: @abeham commented

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.

HeuristicLab-Trac-Bot commented 12 years ago

2011-12-20 09:16:04: @abeham commented

r7209

  • fixed prepare in RTS
HeuristicLab-Trac-Bot commented 12 years ago

2011-12-25 20:22:55: @gkronber commented

Reviewed r7092, r7209, r7040, r6953. LGTM.

HeuristicLab-Trac-Bot commented 12 years ago

2011-12-25 20:25:22: @gkronber changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-03 05:27:42: @s-wagner changed status from readytorelease to closed

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-03 05:27:42: @s-wagner removed resolution