Implement Robust Taboo Search for the QAP

[abeham]

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

[abeham]

r6350:6351

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

[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

[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, but one that is even further away from the description in the paper)
• 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)

[abeham]

r6593

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

[abeham]

r6594

• fixed some bugs

[abeham]

r6627

• updated from trunk

[abeham]

r6628

• merged to trunk

[abeham]

r6632, r6634

• removed branch
• removed obsolete files

[abeham]

r6637

• removed unnecessary dependency

[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

[gkronber]

r6835: added QAP plugins to Builder.testsettings file

[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.

[abeham]

r6953

• Made parameter properties public

[abeham]

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

[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

[abeham]

r7092

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

The issues mentioned by gkronber have all been addressed.

[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.

[abeham]

r7209

• fixed prepare in RTS

[gkronber]

Reviewed r7092, r7209, r7040, r6953. LGTM.