Implement Scatter Search

[ascheibe]

r7720 added Scatter Search branch

[jkarder]

r7722: Scatter Search initial commit

[jkarder]

r7724:

• added analyzer
• added parameters and adjusted parameter types
• corrected ReferenceSetUpdateMethod
• changed access levels

[jkarder]

r7727:

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

[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

[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

[jkarder]

r7756:

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

[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

[jkarder]

r7776: fixed Plugin.cs.frame

[jkarder]

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

[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

[jkarder]

r7787: created branch for ScatterSearch (trunk integration)

[jkarder]

r7789:

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

[jkarder]

r7793:

• added operators for the VehicleRouting problem
• minor code improvements

[jkarder]

r7806: VRPPathRelinker now performs tour matching

[svonolfe]

Added first working version of VRP path relinker in r7815

[jkarder]

r7954:

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

[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

[jkarder]

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

[jkarder]

r8299: made SimilarityCalculator storable

[jkarder]

r8303: made similarity calculators storable and cloneable

[jkarder]

r8304: added support for similarity calculation between multiple individuals

[ascheibe]

r8305 added missing build configurations

[jkarder]

r8306: switched from file references to project references

[jkarder]

r8307: fixed platform configuration

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

[jkarder]

Thanks for the detailed review report.

[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

[jkarder]

r8320: fixed bug in KnapsackImprovementOperator

[jkarder]

r8322:

• applied some of the changes suggested by ascheibe in comment:32:ticket:1331
• minor code improvements

[jkarder]

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

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

[ascheibe]

r8328 fixed comments

[ascheibe]

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.

[jkarder]

Thanks.

[jkarder]

r8331: merged r8086:8330 from trunk

[jkarder]

r8332:

• adjusted parameter types
• changed access levels

[jkarder]

r8334: reintegrated branch

[jkarder]

r8345: made similarity based operators storable and cloneable

[jkarder]

r8346:

• added operators for the VehicleRouting problem
• minor code improvements

[jkarder]

r8347:

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

[jkarder]

r8348: removed redundant call of UpdateSimilarityCalculators

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

[jkarder]

r8380: improved support of the parallel engine

[jkarder]

r8381: fixed race condition

[ascheibe]

r8413 fixed memory allocation in CalculateSolutionCrowdSimilarity

[jkarder]

r8628: adjusted event handling

[jkarder]

r8630: added missing similarity calculators

[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

[ascheibe]

r8721 added a view for SingleObjectiveSolutionSimilarityCalculators

[ascheibe]

r8746 fixed a small bug in the Prepare method of ScatterSearch

[ascheibe]

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

[ascheibe]

r8775 added Scatter Search sample

[jkarder]

r8894:

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

[jkarder]

r8899: fixed cloning ctor

[jkarder]

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

[jkarder]

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

[ascheibe]

r9030 improved TSPSimilarityCalculator and SingleObjectiveSolutionSimilarityCalculator

[ascheibe]

r9031 reverted change in SingleObjectiveSolutionSimilarityCalculato

[swagner]

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