Opened 7 years ago

Closed 4 years ago

#1331 closed feature request (done)

Implement Scatter Search

Reported by: swagner Owned by: jkarder
Priority: high Milestone: HeuristicLab 3.3.8
Component: Algorithms Version: 3.3.8
Keywords: Cc:

Description


Change History (82)

comment:1 Changed 7 years ago by swagner

  • Summary changed from Implement scatter search to Implement Scatter Search

comment:2 Changed 5 years ago by ascheibe

  • Component changed from ### Undefined ### to General
  • Owner changed from swagner to ascheibe
  • Status changed from new to accepted
  • Version changed from 3.3.2 to branch

comment:3 Changed 5 years ago by ascheibe

r7720 added Scatter Search branch

comment:4 Changed 5 years ago by ascheibe

  • Owner changed from ascheibe to jkarder
  • Status changed from accepted to assigned

comment:5 Changed 5 years ago by ascheibe

  • Component changed from General to Algorithms

comment:6 Changed 5 years ago by jkarder

r7722: Scatter Search initial commit

Last edited 5 years ago by jkarder (previous) (diff)

comment:7 Changed 5 years ago by jkarder

r7724:

  • added analyzer
  • added parameters and adjusted parameter types
  • corrected ReferenceSetUpdateMethod
  • changed access levels
Last edited 5 years ago by jkarder (previous) (diff)

comment:8 Changed 5 years ago by jkarder

r7727:

  • added custom improvement operator (ScatterSearchImprovementOperator)
  • added parameters and adjusted types
  • replaced improvement operators with placeholders
  • changed access levels

comment:9 Changed 5 years ago by jkarder

r7740:

  • added custom crossover operator (NChildCrossover)
  • added parameters and adjusted types
  • replaced SolutionCombinationMethod with a placeholder
  • adjusted event handling
  • changed access levels
  • minor code improvements

comment:10 Changed 5 years ago by jkarder

r7744:

  • added problem specific improvement operators (KnapsackImprovementOperator, TravelingSalesmanImprovementOperator)
  • added custom interface (IScatterSearchTargetProcessor) for Scatter Search specific operators that use a target parameter
  • added custom operator (OffspringProcessor) to process multiple children that were created by crossovers
  • extracted diversity calculation and added problem/encoding specific operators (BinaryVectorDiversityCalculator, PermutationDiversityCalculator) for it
  • added parameters and adjusted types
  • adjusted event handling
  • minor code improvements

comment:11 Changed 5 years ago by jkarder

  • Status changed from assigned to accepted

comment:12 Changed 5 years ago by jkarder

r7756:

  • added path relinking and problem specific operators (KnapsackPathRelinker, TravelingSalesmanPathRelinker) for it
  • adjusted event handling
  • minor code improvements

comment:13 Changed 5 years ago by jkarder

r7775:

  • added operators for TestFunctions problems
  • added more path relinking operators for the TravelingSalesman and the Knapsack problem
  • added 2-tier version of the SolutionPoolUpdateMethod
  • added parameters and adjusted types
  • added some exception handling
  • adjusted event handling
  • updated plugin dependencies
  • minor code improvements

comment:14 Changed 5 years ago by jkarder

r7776: fixed Plugin.cs.frame

comment:15 Changed 5 years ago by jkarder

r7778: added support for path relinking operators that use a multiple guiding strategy

comment:16 Changed 5 years ago by jkarder

r7786:

  • fixed bug in path relinking selection
  • fixed bug in ScatterSearch.Prepare()
  • added custom interface (IImprovementOperator) for Scatter Search specific improvement operators
  • switched from diversity calculation to similarity calculation
  • separated IPathRelinker from ICrossover
  • changed TestFunctionsImprovementOperator to use reflection for evaluating functions
  • changed SolutionPoolUpdateMethod to use similarity calculation for solution comparison
  • improved TravelingSalesmanImprovementOperator
  • improved operator graph
  • removed specific operators used to evaluate TestFunctions problems
  • removed custom crossover operator (NChildCrossover)
  • added parameters and adjusted types
  • adjusted event handling
  • changed access levels
  • minor code improvements

comment:17 Changed 5 years ago by jkarder

r7787: created branch for ScatterSearch (trunk integration)

comment:18 Changed 5 years ago by jkarder

r7789:

  • added Scatter Search algorithm
  • added problem specific operators for improvement, path relinking and similarity calculation
  • adjusted event handling

comment:19 Changed 5 years ago by jkarder

r7793:

  • added operators for the VehicleRouting problem
  • minor code improvements

comment:20 Changed 5 years ago by jkarder

r7806: VRPPathRelinker now performs tour matching

comment:21 Changed 5 years ago by svonolfe

Added first working version of VRP path relinker in r7815

comment:22 Changed 5 years ago by jkarder

r7954:

  • added EvaluatedSolutions parameter
  • SingleObjectiveTestFunctionImprovementOperator now retrieves the bounds from the scope tree
  • SingleObjectiveTestFunctionProblem now assigns the bounds to the similarity calculator

comment:23 Changed 5 years ago by jkarder

r8086:

  • synced branch with trunk
  • added custom interface (ISimilarityBasedOperator) to mark operators that conduct similarity calculation
  • similarity calculators are now parameterized by the algorithm
  • deleted SolutionPool2TierUpdateMethod
  • deleted KnapsackMultipleGuidesPathRelinker
  • moved IImprovementOperator, IPathRelinker and ISimilarityCalculator to HeuristicLab.Optimization
  • added parameter descriptions
  • fixed plugin references
  • fixed count of EvaluatedSolutions
  • fixed check for duplicate solutions
  • minor code improvements

comment:24 Changed 5 years ago by jkarder

  • Owner changed from jkarder to ascheibe
  • Status changed from accepted to reviewing

comment:25 Changed 5 years ago by jkarder

r8171: forgot to add custom interface (ISimilarityBasedOperator) to mark operators that conduct similarity calculation

comment:26 Changed 5 years ago by jkarder

r8299: made SimilarityCalculator storable

comment:27 Changed 5 years ago by jkarder

r8303: made similarity calculators storable and cloneable

comment:28 Changed 5 years ago by jkarder

r8304: added support for similarity calculation between multiple individuals

comment:29 Changed 5 years ago by ascheibe

r8305 added missing build configurations

comment:30 Changed 5 years ago by jkarder

r8306: switched from file references to project references

comment:31 Changed 5 years ago by jkarder

r8307: fixed platform configuration

comment:32 Changed 5 years ago by ascheibe

Thanks for implementing Scatter Search! I have reviewed the code and here are my review comments:

  • The ReferenceSetUpdateMethod could now use the CalculateCrowdSimilarity method added with r8304. I don't know if that makes the code in ReferenceSetUpdateMethod more complicated, but if not we should use this method because we have introduced it for exactly that case.
  • ISimilarityCalculator should contain a documentation that explains what the range and the meaning of the returned value of CalculateIndividualSimilarity(..) is.
  • TSPSimilarityCalculator should check for the different Permutation types. I think you should implement this in the same way as the PermutationEqualityComparer does.
  • SimilarityCalculators should check that the length of the individuals is equal.
  • Rename Target in SimilarityCalculator to VariableName. The Target parameter property should not be located in ISimilarityCalculator but in the problem-specific implementations.
  • The same holds for the IImprovementOperator. The reason is that there could exist multiple targets when using an encoding that contains more than one component representing a solution.
  • The comment in line 414 in ScatterSearch.cs has a typo. Maybe you should also add a comment that states that we have to think about the way we handle the target parameter again if we have an encoding where individuals consist of more than one target.
  • UpdateSimilarityCalculators() in ScatterSearch.cs should use similarity instead of diversity for the naming of local variables.
  • There should be an empty view for ISimiliarityCalculator so that HL doesn't display the "No view available" in the GUI.
  • If you have based your improvers on code from a book or internet source, please add a comment with the link or reference.
  • This should also be done for the Path Relinkers. If you have a look at the crossover operators, there are always the paper or book references included in the description of the operator (ItemDescription) on which the implementation is based on.
Last edited 5 years ago by jkarder (previous) (diff)

comment:33 Changed 5 years ago by ascheibe

  • Owner changed from ascheibe to jkarder
  • Status changed from reviewing to assigned

comment:34 Changed 5 years ago by jkarder

  • Status changed from assigned to accepted

comment:35 Changed 5 years ago by jkarder

Thanks for the detailed review.

Last edited 5 years ago by jkarder (previous) (diff)

comment:36 Changed 5 years ago by jkarder

r8319:

  • applied some of the changes suggested by ascheibe in comment:32:ticket:1331
  • restructured path relinking and improvement operators and similarity calculators
  • fixed bug in TSPMultipleGuidesPathRelinker

comment:37 Changed 5 years ago by jkarder

r8320: fixed bug in KnapsackImprovementOperator

comment:38 Changed 5 years ago by jkarder

r8322:

comment:39 Changed 5 years ago by jkarder

r8327: applied the rest of the changes suggested by ascheibe in comment:32:ticket:1331

comment:40 Changed 5 years ago by jkarder

I have applied the changes you suggested in comment:32. Thanks again. I have also checked the problem specific improvement and path relinking operators as well as the similarity calculators and fixed some bugs. Maybe you could have a look at the changes and check if everything is implemented correctly.

comment:41 Changed 5 years ago by jkarder

  • Owner changed from jkarder to ascheibe
  • Status changed from accepted to reviewing

comment:42 Changed 5 years ago by ascheibe

r8328 fixed comments

comment:43 Changed 5 years ago by ascheibe

  • Owner changed from ascheibe to swagner

Thanks implementing the comments. I have reviewed the changes, looks good! Please move the code to trunk. I'm handing this ticket over to swagner for a final review of the similarity calculators.

comment:44 Changed 5 years ago by jkarder

Thanks.

comment:45 Changed 5 years ago by jkarder

r8331: merged r8086:8330 from trunk

comment:46 Changed 5 years ago by jkarder

r8332:

  • adjusted parameter types
  • changed access levels

comment:47 Changed 5 years ago by jkarder

r8334: reintegrated branch

comment:48 Changed 5 years ago by jkarder

r8345: made similarity based operators storable and cloneable

comment:49 Changed 5 years ago by jkarder

r8346:

  • added operators for the VehicleRouting problem
  • minor code improvements

comment:50 Changed 5 years ago by jkarder

r8347:

  • removed branch ScatterSearch
  • removed branch ScatterSearch (trunk integration)

comment:51 Changed 5 years ago by jkarder

r8348: removed redundant call of UpdateSimilarityCalculators

comment:52 Changed 5 years ago by ascheibe

r8351 fixed algorithms that couldn't handle Items that they get now from the problem (I overlooked these two cases, all other algorithms/cases have been adapted in the course of ticket #1864)

comment:53 Changed 5 years ago by jkarder

r8380: improved support of the parallel engine

comment:54 Changed 5 years ago by jkarder

r8381: fixed race condition

comment:55 Changed 5 years ago by ascheibe

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.8
  • Version changed from branch to 3.3.7

comment:56 Changed 5 years ago by ascheibe

r8413 fixed memory allocation in CalculateSolutionCrowdSimilarity

comment:57 Changed 5 years ago by jkarder

r8628: adjusted event handling

comment:58 Changed 5 years ago by jkarder

r8630: added missing similarity calculators

comment:59 Changed 5 years ago by ascheibe

r8662 fixed setting of the QualityVariableName for the NoSimilarityCalculator as this is needed by the SolutionPoolUpdateMethod because it uses the GetHashCode method of SingleObjectiveSolutionSimilarityCalculator

Last edited 5 years ago by jkarder (previous) (diff)

comment:60 Changed 5 years ago by ascheibe

  • Owner changed from swagner to ascheibe
  • Status changed from reviewing to assigned

comment:61 Changed 5 years ago by ascheibe

r8721 added a view for SingleObjectiveSolutionSimilarityCalculators

comment:62 Changed 5 years ago by ascheibe

  • Owner changed from ascheibe to swagner
  • Status changed from assigned to reviewing

comment:63 Changed 5 years ago by ascheibe

r8746 fixed a small bug in the Prepare method of ScatterSearch

comment:64 Changed 5 years ago by ascheibe

  • Owner changed from swagner to ascheibe
  • Status changed from reviewing to assigned

comment:65 Changed 5 years ago by ascheibe

r8774 fixed parameters of the random number generator so that the seed can be set

comment:66 Changed 5 years ago by ascheibe

r8775 added Scatter Search sample

comment:67 Changed 5 years ago by ascheibe

  • Owner changed from ascheibe to swagner
  • Status changed from assigned to reviewing

comment:68 Changed 5 years ago by jkarder

  • Owner changed from swagner to jkarder
  • Status changed from reviewing to assigned

comment:69 Changed 5 years ago by jkarder

  • Status changed from assigned to accepted

comment:70 Changed 5 years ago by jkarder

r8894:

  • improved path relinking and improvement operators for the VehicleRouting problem
  • recreated SS VRP sample
  • corrected SS VRP sample test

comment:71 Changed 5 years ago by jkarder

r8899: fixed cloning ctor

comment:72 Changed 5 years ago by ascheibe

  • Owner changed from jkarder to swagner
  • Status changed from accepted to reviewing

comment:73 Changed 5 years ago by jkarder

  • Owner changed from swagner to jkarder
  • Status changed from reviewing to assigned

comment:74 Changed 5 years ago by jkarder

r8987: fixed lookup of the method used to evaluate TestFunctions in the SingleObjectiveTestFunctionImprovementOperator

comment:75 Changed 5 years ago by jkarder

  • Status changed from assigned to accepted

comment:76 Changed 5 years ago by jkarder

r8988: Equals method in SingleObjectiveSolutionSimilarityCalculator now only performs structural comparison if solutions have almost the same quality

comment:77 Changed 5 years ago by jkarder

  • Owner changed from jkarder to swagner
  • Status changed from accepted to reviewing

comment:78 Changed 5 years ago by ascheibe

  • Owner changed from swagner to ascheibe
  • Status changed from reviewing to assigned

comment:79 Changed 5 years ago by ascheibe

  • Owner changed from ascheibe to swagner
  • Status changed from assigned to reviewing

r9030 improved TSPSimilarityCalculator and SingleObjectiveSolutionSimilarityCalculator

comment:80 Changed 5 years ago by ascheibe

r9031 reverted change in SingleObjectiveSolutionSimilarityCalculato

comment:81 Changed 4 years ago by swagner

  • Owner changed from swagner to jkarder
  • Status changed from reviewing to readytorelease

Briefly reviewed changes and found no issues. Many thanks for implementing this feature.

comment:82 Changed 4 years ago by swagner

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