Opened 13 years ago
Closed 12 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 13 years ago by abeham
- Status changed from new to accepted
comment:2 Changed 13 years ago by abeham
comment:3 Changed 13 years ago by abeham
- Version changed from 3.3.4 to branch
comment:4 Changed 13 years ago by abeham
- 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
comment:5 Changed 13 years ago by abeham
- 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)
comment:6 Changed 13 years ago by abeham
- Changed aspiration criterion after contacting Taillard
- added option to choose between old or new adaption scheme
comment:7 Changed 13 years ago by abeham
- fixed some bugs
comment:8 Changed 13 years ago by abeham
- Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.6
comment:9 Changed 13 years ago by abeham
- updated from trunk
comment:10 Changed 13 years ago by abeham
- Owner changed from abeham to gkronber
- Status changed from accepted to reviewing
- Version changed from branch to 3.3.5
- merged to trunk
comment:11 Changed 13 years ago by abeham
comment:12 Changed 13 years ago by abeham
- removed unnecessary dependency
comment:13 Changed 13 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 13 years ago by gkronber
r6835: added QAP plugins to Builder.testsettings file
comment:15 Changed 13 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 13 years ago by abeham
- Made parameter properties public
comment:17 Changed 13 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 13 years ago by abeham
- 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 13 years ago by abeham
- Owner changed from abeham to gkronber
- Status changed from assigned to reviewing
- Clearing the graphics with white color solves the text rendering problem
The issues mentioned by gkronber have all been addressed.
comment:20 Changed 13 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 13 years ago by abeham
- fixed prepare in RTS
comment:22 Changed 13 years ago by gkronber
comment:23 Changed 13 years ago by gkronber
- Status changed from reviewing to readytorelease
comment:24 Changed 12 years ago by swagner
- Resolution set to done
- Status changed from readytorelease to closed
- Version changed from 3.3.5 to 3.3.6
r6350:6351