Free cookie consent management tool by TermsFeed Policy Generator

Opened 12 years ago

Closed 10 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 12 years ago by swagner

  • Summary changed from Implement scatter search to Implement Scatter Search

comment:2 Changed 11 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 11 years ago by ascheibe

r7720 added Scatter Search branch

comment:4 Changed 11 years ago by ascheibe

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

comment:5 Changed 11 years ago by ascheibe

  • Component changed from General to Algorithms

comment:6 Changed 11 years ago by jkarder

r7722: Scatter Search initial commit

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

comment:7 Changed 11 years ago by jkarder

r7724:

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

comment:8 Changed 11 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 11 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 11 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 11 years ago by jkarder

  • Status changed from assigned to accepted

comment:12 Changed 11 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 11 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 11 years ago by jkarder

r7776: fixed Plugin.cs.frame

comment:15 Changed 11 years ago by jkarder

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

comment:16 Changed 11 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 11 years ago by jkarder

r7787: created branch for ScatterSearch (trunk integration)

comment:18 Changed 11 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 11 years ago by jkarder

r7793:

  • added operators for the VehicleRouting problem
  • minor code improvements

comment:20 Changed 11 years ago by jkarder

r7806: VRPPathRelinker now performs tour matching

comment:21 Changed 11 years ago by svonolfe

Added first working version of VRP path relinker in r7815

comment:22 Changed 11 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 10 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 10 years ago by jkarder

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

comment:25 Changed 10 years ago by jkarder

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

comment:26 Changed 10 years ago by jkarder

r8299: made SimilarityCalculator storable

comment:27 Changed 10 years ago by jkarder

r8303: made similarity calculators storable and cloneable

comment:28 Changed 10 years ago by jkarder

r8304: added support for similarity calculation between multiple individuals

comment:29 Changed 10 years ago by ascheibe

r8305 added missing build configurations

comment:30 Changed 10 years ago by jkarder

r8306: switched from file references to project references

comment:31 Changed 10 years ago by jkarder

r8307: fixed platform configuration

comment:32 Changed 10 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 10 years ago by jkarder (previous) (diff)

comment:33 Changed 10 years ago by ascheibe

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

comment:34 Changed 10 years ago by jkarder

  • Status changed from assigned to accepted

comment:35 Changed 10 years ago by jkarder

Thanks for the detailed review.

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

comment:36 Changed 10 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 10 years ago by jkarder

r8320: fixed bug in KnapsackImprovementOperator

comment:38 Changed 10 years ago by jkarder

r8322:

comment:39 Changed 10 years ago by jkarder

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

comment:40 Changed 10 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 10 years ago by jkarder

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

comment:42 Changed 10 years ago by ascheibe

r8328 fixed comments

comment:43 Changed 10 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 10 years ago by jkarder

Thanks.

comment:45 Changed 10 years ago by jkarder

r8331: merged r8086:8330 from trunk

comment:46 Changed 10 years ago by jkarder

r8332:

  • adjusted parameter types
  • changed access levels

comment:47 Changed 10 years ago by jkarder

r8334: reintegrated branch

comment:48 Changed 10 years ago by jkarder

r8345: made similarity based operators storable and cloneable

comment:49 Changed 10 years ago by jkarder

r8346:

  • added operators for the VehicleRouting problem
  • minor code improvements

comment:50 Changed 10 years ago by jkarder

r8347:

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

comment:51 Changed 10 years ago by jkarder

r8348: removed redundant call of UpdateSimilarityCalculators

comment:52 Changed 10 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 10 years ago by jkarder

r8380: improved support of the parallel engine

comment:54 Changed 10 years ago by jkarder

r8381: fixed race condition

comment:55 Changed 10 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 10 years ago by ascheibe

r8413 fixed memory allocation in CalculateSolutionCrowdSimilarity

comment:57 Changed 10 years ago by jkarder

r8628: adjusted event handling

comment:58 Changed 10 years ago by jkarder

r8630: added missing similarity calculators

comment:59 Changed 10 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 10 years ago by jkarder (previous) (diff)

comment:60 Changed 10 years ago by ascheibe

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

comment:61 Changed 10 years ago by ascheibe

r8721 added a view for SingleObjectiveSolutionSimilarityCalculators

comment:62 Changed 10 years ago by ascheibe

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

comment:63 Changed 10 years ago by ascheibe

r8746 fixed a small bug in the Prepare method of ScatterSearch

comment:64 Changed 10 years ago by ascheibe

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

comment:65 Changed 10 years ago by ascheibe

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

comment:66 Changed 10 years ago by ascheibe

r8775 added Scatter Search sample

comment:67 Changed 10 years ago by ascheibe

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

comment:68 Changed 10 years ago by jkarder

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

comment:69 Changed 10 years ago by jkarder

  • Status changed from assigned to accepted

comment:70 Changed 10 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 10 years ago by jkarder

r8899: fixed cloning ctor

comment:72 Changed 10 years ago by ascheibe

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

comment:73 Changed 10 years ago by jkarder

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

comment:74 Changed 10 years ago by jkarder

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

comment:75 Changed 10 years ago by jkarder

  • Status changed from assigned to accepted

comment:76 Changed 10 years ago by jkarder

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

comment:77 Changed 10 years ago by jkarder

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

comment:78 Changed 10 years ago by ascheibe

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

comment:79 Changed 10 years ago by ascheibe

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

r9030 improved TSPSimilarityCalculator and SingleObjectiveSolutionSimilarityCalculator

comment:80 Changed 10 years ago by ascheibe

r9031 reverted change in SingleObjectiveSolutionSimilarityCalculato

comment:81 Changed 10 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 10 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.