search

heal-research / HeuristicLab

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

Implement local search operator for QAP #1497

Closed HeuristicLab-Trac-Bot closed 13 years ago

HeuristicLab-Trac-Bot commented 13 years ago

Issue migrated from trac ticket # 1497

milestone: HeuristicLab 3.3.5 | component: Problems.QuadraticAssignment | priority: high | resolution: done

2011-04-30 14:53:14: @abeham created the issue

For use in VNS implement a best-improvement local search operator that is problem-specific and fast.

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-30 14:53:21: @abeham changed status from new to accepted

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-30 15:40:50: @abeham commented

r6086

  • Added problem-specific local improvement operator (best improvement local search using swap2 moves)
    • Adapted ExhaustiveSwap2MoveGenerator to yield moves
  • Added a parameter BestKnownSolutions to collect possible optimal invariants
    • Adapted BestQAPSolutionAnalyzer to collect optimal invariants
  • Added a function to the QAP Evaluator that calculates the impact of a certain allele
HeuristicLab-Trac-Bot commented 13 years ago

2011-05-04 10:32:59: @abeham changed priority from medium to high

HeuristicLab-Trac-Bot commented 13 years ago

2011-05-30 18:11:39: @abeham changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 13 years ago

2011-05-30 18:11:39: @abeham changed owner from abeham to svonolfe

HeuristicLab-Trac-Bot commented 13 years ago

2011-05-30 18:11:39: @abeham commented

r6342

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

2011-06-14 13:53:24: svonolfe changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 13 years ago

2011-06-14 13:53:24: svonolfe changed owner from svonolfe to abeham

HeuristicLab-Trac-Bot commented 13 years ago

2011-06-14 13:53:24: svonolfe commented

I think the change is very valuable and improves the runtime efficiency of VNS a lot. The relevant changes to the VNS algorithm have already been incorporated in r6042, so this is ready for release.

For other problems we probably have to implement stochastic variants if the exhaustive move generator produces too many moves.

HeuristicLab-Trac-Bot commented 13 years ago

2011-07-09 20:43:54: @s-wagner changed status from readytorelease to closed

HeuristicLab-Trac-Bot commented 13 years ago

2011-07-09 20:43:54: @s-wagner removed resolution