Opened 9 years ago

Closed 8 years ago

#1425 closed feature request (done)

Implement VNS

Reported by: svonolfe Owned by: svonolfe
Priority: medium Milestone: HeuristicLab 3.3.4
Component: Algorithms.VariableNeighborhoodSearch Version: 3.3.4
Keywords: Cc:

Description

Variable Neighborhood Search (VNS) should be implemented in HL 3.3.

Change History (24)

comment:1 Changed 9 years ago by svonolfe

Created branch in r5594

comment:2 Changed 9 years ago by svonolfe

  • Status changed from new to accepted
  • Type changed from defect to feature request

comment:3 Changed 9 years ago by svonolfe

Added VNS plugin in r5595

comment:4 Changed 9 years ago by svonolfe

Added first version of VNS main loop in r5603

comment:5 Changed 9 years ago by svonolfe

Worked on VNS main loop in r5609, r5610

Last edited 9 years ago by svonolfe (previous) (diff)

comment:6 Changed 9 years ago by svonolfe

Worked on VNS in r5622

comment:7 Changed 9 years ago by svonolfe

Implemented wiring in r5642

comment:8 Changed 9 years ago by svonolfe

Implemented review comments of swagner in r5735, Updated naming of operators in r5738

Last edited 9 years ago by svonolfe (previous) (diff)

comment:9 Changed 9 years ago by svonolfe

Modified LocalSearch main loop in r5751

comment:10 Changed 9 years ago by svonolfe

Added simulated annealing improvement operator in r5752

comment:11 Changed 9 years ago by svonolfe

Integrated VNS into trunk in r5753, deleted branch in r5754

comment:12 Changed 9 years ago by svonolfe

Added VNS sample in r5755

comment:13 Changed 9 years ago by svonolfe

  • Milestone changed from HeuristicLab Backlog to HeuristicLab 3.3.4
  • Owner changed from svonolfe to swagner
  • Status changed from accepted to reviewing
  • Version changed from branch to 3.3.4

comment:14 Changed 8 years ago by abeham

  • Owner changed from swagner to abeham

comment:15 Changed 8 years ago by abeham

r6042

  • Changed LocalImprovementOperators
    • Changed interface (made Problem a property, added a property that denotes the type of the problem that it can be applied on, added some general parameters)
    • Added some parameters and wiring
    • Changed move discovery and parameterization and added a helper class to ease finding compatible move operators
    • Discovering only IMultiMoveOperators and IExhaustiveMoveOperators and putting the multi move ones first
    • Fixed bug in Apply method that could create an endless string of nested execution contexts
    • Removed all problem specific analyzers in the two local improvement operators and only left the BestAverageWorstQualityAnalyzer since it doesn't make any sense to perform diversity or allele analysis during local improvement in the most common case and those analyzers take a lot of time (one can always add them manually should he/she be interested). The analyzers in the VNS's Analyzer parameter are left untouched.
  • Removed shaking operator and interface from VNS plugin and added that to Optimization and Optimization.Operators
  • Changed some ValueParameters to ConstrainedValueParameters and added type discovery to fill them (using the ProblemType property to get compatible local improvement operators)
  • Added missing GPL license headers
  • Changed some ValueParameters to the new FixedValueParameters
  • Added an additional encoding specific ShakingOperator to each encoding and added that to each problem
    • reason is that only the problem/encoding can really decide if a shaking operator is meaningful or not
  • Fixed an unrelated bug in the BestAverageWorstQualityAnalyzer that I encountered (and made the fix backwards compatible)
    • Also added a snippet for creating the backwards compatible comment marker and region
  • Fixed the operator graph of the VNS main loop
    • The condition to continue only when the local search was not successful is not necessary and is not part of the VNS definition as far as I know it (only condition to break the inner loop is when k reaches k_max)
  • Changed the ShakingOperator to input current index and output the maximum number of neighborhoods instead of a boolean that indicates that the last index has been reached since the maximum number is a little more generally useful and equally powerful in modeling
    • Remodeled the VNS main loop to check for k < k_max in order to continue the inner loop
  • other changes that I forgot...

Still necessary

  • test, test, test
  • check for backwards compatible breakers
  • add a maximum evaluated solutions stop criterion
  • optionally: implement fast problem specific local search improvement operators that do not build on the whole generic overhead (e.g. a 2-opt TSP specific local search operator). The idea of VNS is really to converge to a local optimum which is difficult to achieve using the current rather limited termination options

comment:16 Changed 8 years ago by abeham

r6043

  • added backwards compatibility for LocalSearchMainLoop
  • fixed build breaker

comment:17 Changed 8 years ago by abeham

r6044

  • readded the removal of one of the result collector's collected values (and added a comment to the local search mainloop hinting, that a change can break another operator)
  • updated and readded the sample

comment:18 Changed 8 years ago by abeham

I did some testing and all backwards compatibility issues should be fixed. From my point of view this looks release ready now.

Still on my wishlist would be a maximum evaluated solutions stop criterion although of course that's hard to do without enforcing this also inside the local improvement operator... And the other more important thing would be to write custom local search improvement operators for each problem... but well, probably for the next release.

comment:19 Changed 8 years ago by abeham

  • Owner changed from abeham to svonolfe

Thanks svonolfe for the implemenation! Please have a look at the changes I made, apart from fixing some bugs I also think that the implementation is improved somewhat.

comment:20 Changed 8 years ago by svonolfe

  • Status changed from reviewing to readytorelease

I think the changes by abeham improve the quality of the implementation a lot.

In r6052, I re-added the problem-specific analyzers to the local improvement operators. This is convenient for the user. However, we have to keep in mind that the VNS-algorithm and the local improvement operation share the same analyzers. Thus, in the local improvement operation a clone is created which cannot be correctly wired by the problem. Probably this issue can be fixed along with Ticket #1489.

I think the VNS implementation is ready to release now.

comment:21 Changed 8 years ago by abeham

I just remember one last thing. Could you please add a reference to the paper that describes VNS in the description of the algorithm? Last time I saw that there wasn't one.

comment:22 Changed 8 years ago by svonolfe

Thanks for the hint, added reference to paper for the VNS implementation in r6057.

I just saw we are lacking several references in other algorithms...

comment:23 Changed 8 years ago by abeham

Thank you!

You're right, I'm adding a general ticket to improve references in algorithms, problems, and operators for 3.3.5.

comment:24 Changed 8 years ago by swagner

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