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

Timestamp:

06/22/12 11:11:38 (12 years ago)

Author:

jkarder

Message:

#1331:

• 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

Location:

branches/ScatterSearch (trunk integration)

Files:

• . (modified) (2 props)
• HeuristicLab.Problems.Knapsack/3.3/HeuristicLab.Problems.Knapsack-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.Knapsack/3.3/Improvers/KnapsackImprovementOperator.cs (modified) (7 diffs)
• HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs (modified) (3 diffs)
• HeuristicLab.Problems.Knapsack/3.3/PathRelinkers/KnapsackMultipleGuidesPathRelinker.cs (deleted)
• HeuristicLab.Problems.Knapsack/3.3/Plugin.cs.frame (modified) (1 diff)
• HeuristicLab.Problems.Knapsack/3.3/SimilarityCalculators/KnapsackSimilarityCalculator.cs (modified) (2 diffs)

branches/ScatterSearch (trunk integration)

@@ -20 +20 @@
 bin
 protoc.exe
+_ReSharper.HeuristicLab 3.3 Tests

@@ -20 +20 @@
 bin
 protoc.exe
+_ReSharper.HeuristicLab 3.3 Tests

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

@@ -116 +116 @@
     <Compile Include="MoveEvaluators\KnapsackMoveEvaluator.cs" />
     <Compile Include="MoveEvaluators\KnapsackOneBitflipMoveEvaluator.cs" />
-    <Compile Include="PathRelinkers\KnapsackMultipleGuidesPathRelinker.cs" />
     <Compile Include="PathRelinkers\KnapsackPathRelinker.cs" />
     <Compile Include="PathRelinkers\KnapsackSimultaneousPathRelinker.cs" />

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Linq;
 using HeuristicLab.Common;
@@ -26 +27 @@
 using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Operators;
-using HeuristicLab.Optimization.Operators;
+using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -70 +71 @@
       set { PenaltyParameter.ActualValue = value; }
     }
-    private IItem Target {
-      get { return TargetParameter.ActualValue; }
-    }
     private IntArray Values {
       get { return ValuesParameter.ActualValue; }
@@ -89 +87 @@
       : base() {
       #region Create parameters
-      Parameters.Add(new ScopeParameter("CurrentScope"));
-      Parameters.Add(new LookupParameter<IntValue>("KnapsackCapacity"));
-      Parameters.Add(new LookupParameter<DoubleValue>("Penalty"));
-      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
-      Parameters.Add(new LookupParameter<IntArray>("Values"));
-      Parameters.Add(new LookupParameter<IntArray>("Weights"));
+      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solution to be improved."));
+      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 LookupParameter<IntArray>("Values", "The values of the items."));
+      Parameters.Add(new LookupParameter<IntArray>("Weights", "The weights of the items."));
       #endregion
     }
@@ -104 +102 @@
     public override IOperation Apply() {
       BinaryVector sol = CurrentScope.Variables[TargetParameter.ActualName].Value as BinaryVector;
+      if (sol == null)
+        throw new ArgumentException("Cannot improve solution because it has the wrong type.");
 
       // calculate value-to-weight ratio
@@ -113 +113 @@
       // calculate order for ratio
       int[] order = new int[ratio.Length];
-      ratio.Select((x, index) => new { Value = x, ValueIndex = index })
-           .OrderBy(x => x.Value)
-           .Select((x, index) => new { ValueIndex = x.ValueIndex, ItemIndex = index }).ToList()
-           .ForEach(x => order[x.ItemIndex] = x.ValueIndex);
+      foreach (var x in ratio.Select((x, index) => new { Value = x, ValueIndex = index })
+                             .OrderBy(x => x.Value)
+                             .Select((x, index) => new { ValueIndex = x.ValueIndex, ItemIndex = index })) {
+        order[x.ItemIndex] = x.ValueIndex;
+      }
 
+      int evaluatedSolutions = 0;
       int j = sol.Length - 1;
       while (KnapsackEvaluator.Apply(sol, KnapsackCapacity, Penalty, Weights, Values)
-                              .SumWeights.Value > KnapsackCapacity.Value && j >= 0)
+                              .SumWeights.Value > KnapsackCapacity.Value && j >= 0) {
         sol[order[j--]] = false;
+        evaluatedSolutions++;
+      }
 
       // calculate weight
@@ -136 +140 @@
           weight += Weights[order[j]];
         } else feasible = false;
+        evaluatedSolutions++;
       }
 
       CurrentScope.Variables[TargetParameter.ActualName].Value = sol;
+      CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", new IntValue(evaluatedSolutions)));
 
       return base.Apply();

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

@@ -28 +28 @@
 using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Optimization;
-using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -246 +245 @@
     private void InitializeOperators() {
       Operators.Add(new KnapsackImprovementOperator());
-      Operators.Add(new KnapsackMultipleGuidesPathRelinker());
       Operators.Add(new KnapsackPathRelinker());
       Operators.Add(new KnapsackSimultaneousPathRelinker());
@@ -306 +304 @@
       }
       foreach (ISimilarityCalculator op in Operators.OfType<ISimilarityCalculator>()) {
-        op.TargetParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        op.TargetParameter.Hidden = true;
+        op.Target = SolutionCreator.BinaryVectorParameter.ActualName;
       }
     }

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

@@ -36 +36 @@
   [PluginDependency("HeuristicLab.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Optimization", "3.3")]
+  [PluginDependency("HeuristicLab.Optimization.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Parameters", "3.3")]
   [PluginDependency("HeuristicLab.Persistence", "3.3")]

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Optimization.Operators;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.Knapsack {
@@ -31 +31 @@
   /// </summary>
   [Item("KnapsackSimilarityCalculator", "An operator that performs similarity calculation between two knapsack solutions.")]
-  [StorableClass]
   public sealed class KnapsackSimilarityCalculator : SimilarityCalculator {
-    [StorableConstructor]
     private KnapsackSimilarityCalculator(bool deserializing) : base(deserializing) { }
     private KnapsackSimilarityCalculator(KnapsackSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
     public KnapsackSimilarityCalculator() : base() { }
 
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new KnapsackSimilarityCalculator(this, cloner);
+    public static double CalculateSimilarity(BinaryVector left, BinaryVector right) {
+      if (left == null || right == null)
+        throw new ArgumentException("Cannot calculate similarity because one of the provided solutions or both are null.");
+
+      double similarity = 0.0;
+      for (int i = 0; i < left.Length; i++)
+        if (left[i] == right[i]) similarity++;
+      return similarity / left.Length;
     }
 
     protected override double CalculateSimilarity(IScope left, IScope right) {
-      BinaryVector sol1 = left.Variables[TargetParameter.ActualName].Value as BinaryVector;
-      BinaryVector sol2 = right.Variables[TargetParameter.ActualName].Value as BinaryVector;
+      BinaryVector sol1 = left.Variables[Target].Value as BinaryVector;
+      BinaryVector sol2 = right.Variables[Target].Value as BinaryVector;
 
-      double similarity = 0.0;
-      for (int i = 0; i < sol1.Length; i++)
-        if (sol1[i] == sol2[i]) similarity++;
-      return similarity / sol1.Length;
+      return CalculateSimilarity(sol1, sol2);
     }
   }

@@ -20 +20 @@
 bin
 protoc.exe
+_ReSharper.HeuristicLab 3.3 Tests