Changeset 8319 for branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack

Timestamp:

07/24/12 15:04:37 (12 years ago)

Author:

jkarder

Message:

#1331:

• 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

Location:

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3

Files:

• Improvers/KnapsackImprovementOperator.cs (modified) (5 diffs)
• KnapsackProblem.cs (modified) (1 diff)
• PathRelinkers/KnapsackPathRelinker.cs (modified) (1 diff)
• PathRelinkers/KnapsackSimultaneousPathRelinker.cs (modified) (1 diff)
• SimilarityCalculators/KnapsackSimilarityCalculator.cs (modified) (3 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/Improvers/KnapsackImprovementOperator.cs

@@ -35 +35 @@
   /// An operator that improves knapsack solutions.
   /// </summary>
+  /// <remarks>
+  /// It is implemented as described in Laguna, M. and Martí, R. (2003). Scatter Search: Methodology and Implementations in C. Operations Research/Computer Science Interfaces Series, Vol. 24. Springer.<br />
+  /// The operator first orders the elements of the knapsack according to their value-to-weight ratio, then, if the solution is not feasible, removes the element with the lowest ratio until the solution is feasible and tries to add new elements with the best ratio that are not already included yet until the knapsack is full.
+  /// </remarks>
   [Item("KnapsackImprovementOperator", "An operator that improves knapsack solutions.")]
   [StorableClass]
-  public sealed class KnapsackImprovementOperator : SingleSuccessorOperator, IImprovementOperator {
+  public sealed class KnapsackImprovementOperator : SingleSuccessorOperator, ISingleObjectiveImprovementOperator {
     #region Parameter properties
     public ScopeParameter CurrentScopeParameter {
@@ -48 +52 @@
       get { return (ILookupParameter<DoubleValue>)Parameters["Penalty"]; }
     }
-    public IValueLookupParameter<IItem> TargetParameter {
-      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
+    public IValueLookupParameter<IItem> SolutionParameter {
+      get { return (IValueLookupParameter<IItem>)Parameters["Solution"]; }
     }
     public ILookupParameter<IntArray> ValuesParameter {
@@ -90 +94 @@
       Parameters.Add(new LookupParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack."));
       Parameters.Add(new LookupParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight."));
-      Parameters.Add(new ValueLookupParameter<IItem>("Target", "This parameter is used for name translation only."));
+      Parameters.Add(new ValueLookupParameter<IItem>("Solution", "The solution to be improved. This parameter is used for name translation only."));
       Parameters.Add(new LookupParameter<IntArray>("Values", "The values of the items."));
       Parameters.Add(new LookupParameter<IntArray>("Weights", "The weights of the items."));
@@ -101 +105 @@
 
     public override IOperation Apply() {
-      BinaryVector sol = CurrentScope.Variables[TargetParameter.ActualName].Value as BinaryVector;
+      BinaryVector sol = CurrentScope.Variables[SolutionParameter.ActualName].Value as BinaryVector;
       if (sol == null)
         throw new ArgumentException("Cannot improve solution because it has the wrong type.");
@@ -143 +147 @@
       }
 
-      CurrentScope.Variables[TargetParameter.ActualName].Value = sol;
+      CurrentScope.Variables[SolutionParameter.ActualName].Value = sol;
       CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", new IntValue(evaluatedSolutions)));
 

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

@@ -291 +291 @@
         op.ValuesParameter.Hidden = true;
       }
-      foreach (var op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
+      foreach (IBinaryVectorMultiNeighborhoodShakingOperator op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
         op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
         op.BinaryVectorParameter.Hidden = true;
       }
-      foreach (IImprovementOperator op in Operators.OfType<IImprovementOperator>()) {
-        op.TargetParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        op.TargetParameter.Hidden = true;
-      }
-      foreach (IPathRelinker op in Operators.OfType<IPathRelinker>()) {
+      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
+        op.SolutionParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
+        op.SolutionParameter.Hidden = true;
+      }
+      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
         op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
         op.ParentsParameter.Hidden = true;
       }
-      foreach (ISimilarityCalculator op in Operators.OfType<ISimilarityCalculator>()) {
-        op.Target = SolutionCreator.BinaryVectorParameter.ActualName;
+      foreach (KnapsackSimilarityCalculator op in Operators.OfType<KnapsackSimilarityCalculator>()) {
+        op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
       }
     }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/PathRelinkers/KnapsackPathRelinker.cs

@@ -34 +34 @@
   /// An operator that relinks paths between knapsack solutions.
   /// </summary>
+  /// <remarks>
+  /// The operator incrementally assimilates the initiating solution into the guiding solution by adding and removing elements as needed.
+  /// </remarks>
   [Item("KnapsackPathRelinker", "An operator that relinks paths between knapsack solutions.")]
   [StorableClass]
-  public sealed class KnapsackPathRelinker : PathRelinker {
+  public sealed class KnapsackPathRelinker : SingleObjectivePathRelinker {
     [StorableConstructor]
     private KnapsackPathRelinker(bool deserializing) : base(deserializing) { }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/PathRelinkers/KnapsackSimultaneousPathRelinker.cs

@@ -34 +34 @@
   /// An operator that relinks paths between knapsack solutions starting from both ends.
   /// </summary>
+  /// <remarks>
+  /// The operator incrementally assimilates the initiating solution into the guiding solution and vice versa by adding and removing elements as needed.
+  /// </remarks>
   [Item("KnapsackSimultaneousPathRelinker", "An operator that relinks paths between knapsack solutions starting from both ends.")]
   [StorableClass]
-  public sealed class KnapsackSimultaneousPathRelinker : PathRelinker {
+  public sealed class KnapsackSimultaneousPathRelinker : SingleObjectivePathRelinker {
     [StorableConstructor]
     private KnapsackSimultaneousPathRelinker(bool deserializing) : base(deserializing) { }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/SimilarityCalculators/KnapsackSimilarityCalculator.cs

@@ -30 +30 @@
   /// An operator that performs similarity calculation between two knapsack solutions.
   /// </summary>
+  /// <remarks>
+  /// The operator calculates the similarity based on the number of elements the two solutions have in common.
+  /// </remarks>
   [Item("KnapsackSimilarityCalculator", "An operator that performs similarity calculation between two knapsack solutions.")]
-  public sealed class KnapsackSimilarityCalculator : SimilarityCalculator {
+  public sealed class KnapsackSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
     private KnapsackSimilarityCalculator(bool deserializing) : base(deserializing) { }
     private KnapsackSimilarityCalculator(KnapsackSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
@@ -43 +46 @@
       if (left == null || right == null)
         throw new ArgumentException("Cannot calculate diversity because one or both of the provided scopes is null.");
+      if (left.Length != right.Length)
+        throw new ArgumentException("Cannot calculate similarity because the provided solutions have different lengths.");
       if (left == right) return 1.0;
 
@@ -51 +56 @@
     }
 
-    public override double CalculateIndividualSimilarity(IScope left, IScope right) {
-      var sol1 = left.Variables[Target].Value as BinaryVector;
-      var sol2 = right.Variables[Target].Value as BinaryVector;
+    public override double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution) {
+      var sol1 = leftSolution.Variables[SolutionVariableName].Value as BinaryVector;
+      var sol2 = rightSolution.Variables[SolutionVariableName].Value as BinaryVector;
 
       return CalculateSimilarity(sol1, sol2);