Changeset 8304

Timestamp:

07/19/12 13:19:12 (12 years ago)

Author:

jkarder

Message:

#1331: added support for similarity calculation between multiple individuals

Location:

branches/ScatterSearch (trunk integration)

Files:

• HeuristicLab.Algorithms.ScatterSearch/3.3/ReferenceSetUpdateMethod.cs (modified) (1 diff)
• HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs (modified) (1 diff)
• HeuristicLab.Optimization.Operators/3.3/SimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Optimization/3.3/Interfaces/ISimilarityCalculator.cs (modified) (1 diff)
• HeuristicLab.Problems.Knapsack/3.3/SimilarityCalculators/KnapsackSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.TestFunctions/3.3/SimilarityCalculators/SingleObjectiveTestFunctionSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.VehicleRouting/3.3/SimilarityCalculators/VRPSimilarityCalculator.cs (modified) (2 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/ReferenceSetUpdateMethod.cs

@@ -80 +80 @@
         double similarity = 0;
         foreach (var rScope in CurrentScope.SubScopes[1].SubScopes) {
-          similarity += SimilarityCalculator.ExecuteCalculation(pScope, rScope);
+          similarity += SimilarityCalculator.CalculateIndividualSimilarity(pScope, rScope);
         }
         population[pScope] = similarity;

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs

@@ -130 +130 @@
       if (orderedOffspring.Any(hasBetterQuality)) {
         // produce the set union
-        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), new SolutionEqualityComparer<IScope>(SimilarityCalculator.ExecuteCalculation));
+        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), new SolutionEqualityComparer<IScope>(SimilarityCalculator.CalculateIndividualSimilarity));
         if (union.Count() > orderedParents.Count()) {
           var orderedUnion = Maximization.Value ? union.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :

branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization.Operators/3.3/SimilarityCalculator.cs

@@ -21 +21 @@
 
 using System;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -50 +51 @@
     protected SimilarityCalculator() : base() { }
 
-    public double ExecuteCalculation(IScope left, IScope right) {
-      if (left == null || right == null)
-        throw new ArgumentException("Cannot calculate diversity because one or both of the provided scopes is null.");
+    public double[][] CalculateCrowdSimilarity(IScope leftCrowd, IScope rightCrowd) {
+      if (leftCrowd == null || rightCrowd == null)
+        throw new ArgumentException("Cannot calculate similarity because one of the provided crowds or both are null.");
 
-      if (left == right) return 1.0;
-      else return CalculateSimilarity(left, right);
+      var leftIndividuals = leftCrowd.SubScopes;
+      var rightIndividuals = rightCrowd.SubScopes;
+
+      if (!leftIndividuals.Any() || !rightIndividuals.Any())
+        throw new ArgumentException("Cannot calculate similarity because one of the provided crowds or both are empty.");
+
+      var similarityMatrix = new double[leftIndividuals.Count][];
+      for (int i = 0; i < leftIndividuals.Count; i++) {
+        similarityMatrix[i] = new double[rightIndividuals.Count];
+        for (int j = 0; j < rightIndividuals.Count; j++) {
+          similarityMatrix[i][j] = CalculateIndividualSimilarity(leftIndividuals[i], rightIndividuals[j]);
+        }
+      }
+
+      return similarityMatrix;
     }
 
-    protected abstract double CalculateSimilarity(IScope left, IScope right);
+    public abstract double CalculateIndividualSimilarity(IScope leftIndividual, IScope rightIndividual);
   }
 }

branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization/3.3/Interfaces/ISimilarityCalculator.cs

@@ -29 +29 @@
     string Target { get; set; }
 
-    double ExecuteCalculation(IScope left, IScope right);
+    double CalculateIndividualSimilarity(IScope leftIndividual, IScope rightIndividual);
+    double[][] CalculateCrowdSimilarity(IScope leftCrowd, IScope rightCrowd);
   }
 }

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

@@ -42 +42 @@
     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.");
+        throw new ArgumentException("Cannot calculate diversity because one or both of the provided scopes is null.");
+      if (left == right) return 1.0;
 
       double similarity = 0.0;
@@ -50 +51 @@
     }
 
-    protected override double CalculateSimilarity(IScope left, IScope right) {
-      BinaryVector sol1 = left.Variables[Target].Value as BinaryVector;
-      BinaryVector sol2 = right.Variables[Target].Value as BinaryVector;
+    public override double CalculateIndividualSimilarity(IScope left, IScope right) {
+      var sol1 = left.Variables[Target].Value as BinaryVector;
+      var sol2 = right.Variables[Target].Value as BinaryVector;
 
       return CalculateSimilarity(sol1, sol2);

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TestFunctions/3.3/SimilarityCalculators/SingleObjectiveTestFunctionSimilarityCalculator.cs

@@ -57 +57 @@
       if (bounds == null)
         throw new ArgumentException("Cannot calculate similarity because no bounds were provided.");
+      if (left == right) return 1.0;
 
       double maxSum = 0.0;
@@ -71 +72 @@
     }
 
-    protected override double CalculateSimilarity(IScope left, IScope right) {
-      RealVector sol1 = left.Variables[Target].Value as RealVector;
-      RealVector sol2 = right.Variables[Target].Value as RealVector;
+    public override double CalculateIndividualSimilarity(IScope left, IScope right) {
+      var sol1 = left.Variables[Target].Value as RealVector;
+      var sol2 = right.Variables[Target].Value as RealVector;
 
       return CalculateSimilarity(sol1, sol2, Bounds);

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

@@ -43 +43 @@
       if (left == null || right == null)
         throw new ArgumentException("Cannot calculate similarity because one of the provided solutions or both are null.");
+      if (left == right) return 1.0;
 
       int[,] edges = new int[right.Length, 2];
@@ -60 +61 @@
     }
 
-    protected override double CalculateSimilarity(IScope left, IScope right) {
-      Permutation sol1 = left.Variables[Target].Value as Permutation;
-      Permutation sol2 = right.Variables[Target].Value as Permutation;
+    public override double CalculateIndividualSimilarity(IScope left, IScope right) {
+      var sol1 = left.Variables[Target].Value as Permutation;
+      var sol2 = right.Variables[Target].Value as Permutation;
 
       return CalculateSimilarity(sol1, sol2);

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/SimilarityCalculators/VRPSimilarityCalculator.cs

@@ -46 +46 @@
       if (left == null || right == null)
         throw new ArgumentException("Cannot calculate similarity because one of the provided solutions or both are null.");
+      if (left == right) return 1.0;
 
       // extract edges from first solution
@@ -77 +78 @@
     }
 
-    protected override double CalculateSimilarity(IScope left, IScope right) {
-      PotvinEncoding sol1 = left.Variables[Target].Value as PotvinEncoding;
-      PotvinEncoding sol2 = right.Variables[Target].Value as PotvinEncoding;
+    public override double CalculateIndividualSimilarity(IScope left, IScope right) {
+      var sol1 = left.Variables[Target].Value as PotvinEncoding;
+      var sol2 = right.Variables[Target].Value as PotvinEncoding;
 
       return CalculateSimilarity(sol1, sol2);